Many simple languages, including most data languages, avoid the subtleties of grammar design by not introducing operators. Operators such as " + " and " - " bring up the question of whether
11 + 5 * 2
should equal 32 or 21 . Different languages, notably Smalltalk and Java, have different answers to this question, depending on the precedence of operators. Another question that arithmetic encounters is whether
25 16 - 9
equals or 18 . Here the answer depends on the associativity of the " - " operator, which determines whether the rightmost or leftmost operator applies first. The grammar for your language determines the associativity and precedence of operators in your language.
In addition to establishing operator precedence and associativity, a grammar can contain loops . There is nothing wrong with a grammar that has loops, but translating such a grammar to code can result in code that contains infinite loops. In particular, a grammar rule that refers to itself with its leftmost element will cause a loop when you translate the grammar to code. In addition, if a grammar contains cyclic definitions, implementing the grammar as a parser class can cause looping in the code.
This chapter shows how to transform a grammar to attain the following objectives:
Ensure correct associativity.
Eliminate left recursion.
Ensure correct precedence.
Eliminate parser class loops.