parsingcompiler-constructionantlrantlr4left-recursion

Understanding what makes a rule left-recursive in antlr


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]+     ;

enter image description here

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!


Solution

  • Antlr4 can handle direct left-recursion as long as it is not hidden:

    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.