ANTLR direct recursive grammar rules

0
votes

I'm trying to play around with left recursive grammar rules in ANTLR4. My understanding is that as long as the rule isn't indirectly recursive, it should work. The first viable alternative should be the path chosen.

So why is it that the following grammar doesn't compile? As far as I can tell it seems fairly straight forward.

grammar Hello;

stat: stat* '}'
      | ID
      ;

ID: [A-Za-z0-9]+;
WS: [ \t\r\n]+ -> skip;

ANTLR keeps erroring out with...

error(119): Hello.g4::: The following sets of rules are mutually left-recursive [stat]

1
antlrantlr4
Look at a String "a b } } } } }". To build the parse tree the parser must know that there are 5 recursions. Yet the parser will know of that only if it consumes all IDs. Yet to consume these IDs it must know the parse tree. It is not sufficient to expect * to be greedy because this leads to the recursive evaluation of stat which will never return if greedyness is assumed. - CoronA

1 Answers

1
votes

Antlr4 doesn't solve recursion for the general case. Rather, it detects and handles four specific recursive patterns. The detected patterns correspond to rules for:

  • binary operators
  • unary prefix operators
  • unary postfix operators and
  • ternary operators

When it detects such patterns antlr4 internally rewrites a grammar to work around them and then creates a parser for the rewritten grammar. This allows it to handle expressions with complex operator precedence hierarchies with no need for e.g. a corresponding hierarchy of expression types in the user-provided grammar.

Whilst not being completely general, Antlr4's handling of these patterns (plus the ability to annotate operator associativity within a grammar) does fully cover an extremely common use case.