| 1 |
# Left-recursive rules |
| 2 |
|
| 3 |
The most natural expression of some common language constructs is left recursive. For example C declarators and arithmetic expressions. Unfortunately, left recursive specifications of arithmetic expressions are typically ambiguous but much easier to write out than the multiple levels required in a typical top-down grammar. Here is a sample ANTLR 4 grammar with a left recursive expression rule: |
| 4 |
|
| 5 |
``` |
| 6 |
stat: expr '=' expr ';' // e.g., x=y; or x=f(x); |
| 7 |
| expr ';' // e.g., f(x); or f(g(x)); |
| 8 |
; |
| 9 |
expr: expr '*' expr |
| 10 |
| expr '+' expr |
| 11 |
| expr '(' expr ')' // f(x) |
| 12 |
| id |
| 13 |
; |
| 14 |
``` |
| 15 |
|
| 16 |
In straight context free grammars, such a rule is ambiguous because `1+2*3` it can interpret either operator as occurring first, but ANTLR rewrites that to be non-left recursive and unambiguous using semantic predicates: |
| 17 |
|
| 18 |
``` |
| 19 |
expr[int pr] : id |
| 20 |
( {4 >= $pr}? '*' expr[5] |
| 21 |
| {3 >= $pr}? '+' expr[4] |
| 22 |
| {2 >= $pr}? '(' expr[0] ')' |
| 23 |
)* |
| 24 |
; |
| 25 |
``` |
| 26 |
|
| 27 |
The predicates resolve ambiguities by comparing the precedence of the current operator against the precedence of the previous operator. An expansion of expr[pr] can match only those subexpressions whose precedence meets or exceeds pr. |
| 28 |
|
| 29 |
## Formal rules |
| 30 |
|
| 31 |
The formal 4.0, 4.1 ANTLR left-recursion elimination rules were changed (simplified) for 4.2 and are laid out in the [ALL(*) tech report](http://www.antlr.org/papers/allstar-techreport.pdf): |
| 32 |
|
| 33 |
* Binary expressions are expressions which contain a recursive invocation of the rule as the first and last element of the alternative. |
| 34 |
* Suffix expressions contain a recursive invocation of the rule as the first element of the alternative, but not as the last element. |
| 35 |
* Prefix expressions contain a recursive invocation of the rule as the last element of the alternative, but not as the first element. |
| 36 |
|
| 37 |
There is no such thing as a "ternary" expression--they are just binary expressions in disguise. |
| 38 |
|
| 39 |
The right associativity specifiers used to be on the individual tokens but it's done on alternative basis anyway so the option is now on the individual alternative; e.g., |
| 40 |
|
| 41 |
``` |
| 42 |
e : e '*' e |
| 43 |
| e '+' e |
| 44 |
|<assoc=right> e '?' e ':' e |
| 45 |
|<assoc=right> e '=' e |
| 46 |
| INT |
| 47 |
; |
| 48 |
``` |
| 49 |
|
| 50 |
If your 4.0 or 4.1 grammar uses a right-associative ternary operator, you will need to update your grammar to include `<assoc=right>` on the alternative operator. To smooth the transition, `<assoc=right>` is still allowed on token references but it is ignored. |