The Definitive ANTLR 4 Reference, 2nd Edition

Chapter 14Removing Direct Left Recursion

In ​Dealing with Precedence, Left Recursion, and Associativity​, we saw that the natural way to specify arithmetic expressions grammatically is ambiguous. For example, the following expr can interpret 1+2*3 as (1+2)*3 or 1+(2*3). By giving precedence to the alternatives specified first, however, ANTLR neatly sidesteps the ambiguity.

left-recursion-removal/Expr.g4

stat: expr ';' ;

expr:   expr '*' expr       // precedence 4
    |   expr '+' expr       // precedence 3
    |   INT                 // primary (precedence 2)
    |   ID                  // primary (precedence 1)
    ;

Rule expr is still left-recursive, though, which traditional top-down grammars (for example, ANTLR v3) cannot handle. In this chapter, we’re going to explore ...