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 (

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!

CodePudding user response：

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

ANTLR4 left-recursive error

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.

CodePudding user response：

As mentioned by rici above, one of the items that Antlr4 does not support is indirect left-recursion. Here would be an example:

grammar DBParser;
expr: binop | Atom;
binop: expr ' ' expr;
Atom: [a-z]  | [0-9]  ;

error(119): DBParser.g4::: The following sets of rules are mutually left-recursive [expr, binop]

Notice that Antlr4 can support the following direct left-recursion though:

grammar DBParser;
expr: expr ' ' expr | Atom;
Atom: [a-z]  | [0-9]  ;

However, even if you add in parentheticals (for whatever reason?) it doesn't work:

grammar DBParser;
expr: (expr ' ' expr) | Atom;
Atom: [a-z]  | [0-9]  ;

Or:

grammar DBParser;
expr: (expr ' ' expr | Atom);
Atom: [a-z]  | [0-9]  ;

Both will raise:

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