I've been trial-and-erroring to figure out from an intuitive level when a rule in antlr is left-recursive of not. For example, this (Removing left recursion) is left-recursive in theory, but works in Antlr:
// Example input: x+y+1
grammar DBParser;
expression
: expression '+' term
| term;
term
: term '*' atom
| atom;
atom
: NUMBER
| IDENTIFIER
;
NUMBER : [0-9]+ ;
IDENTIFIER : [a-zA-Z]+ ;
So what makes a rule left-recursive and a problem in antlr4, and what would be the simplest example of showing that (in an actual program)? I'm trying to practice remove left-recursive productions, but I can't even figure out how to intentionally add a left-recursive rule that antlr4 can't resolve!
Antlr4 can handle direct left-recursion as long as it is not hidden:
Hidden means that the recursion is not at the beginning of the right-hand side but it might still be at the beginning of the expansion because all previous symbols are nullable.
Indirect means that the first symbol on the right-hand side of a production for N
eventually derives a sequence starting with N
. Antlr describes that as "mutual recursion".
Here are some SO questions I found by searching for [antlr] left recursive
:
ANTLR4 - Mutually left-recursive grammar
ANTLR4 mutually left-recursive error when parsing
ANTLR Grammar Mutually Left Recursive
Mutually left-recursive lexer rules on ANTL4?
Mutually left recursive with simple calculator
There are lots more, including one you asked. I'm sure you can mine some examples.