CODEWITHSUNDEEP
parsingantlrgrammarleft-recursion
Sanuuu
Sanuuu

Reputation: 243

What exactly makes grammar rules left-recursive in antlr?

So, I was wondering what makes a parser like:

line        :   expression EOF;
expression  :   m_expression (PLUS m_expression)?;
m_expression:   basic (TIMES basic)?;
basic       :   NUMBER | VARIABLE | (OPENING expression CLOSING) | expression;

left recursive and invalid, while a parser like

line        :   expression EOF;
expression  :   m_expression (PLUS m_expression)?;
m_expression:   basic (TIMES basic)?;
basic       :   NUMBER | VARIABLE | (OPENING expression CLOSING);

is valid and works even though the definition of 'basic' still refers to 'expression'. In particular, I'd like to be able to parse expressions in the form of

a+b+c

without introducing operations acting on more than two operands.

Upvotes: 1

Views: 425

Answers (1)

Terence Parr
Terence Parr

Reputation: 5962

line calls expression calls m_expression calls basic which calls expression... that is indirectly left recursive and bad for both v3 antlr and v4. The definition of left recursion means you can get back to the same rule without consuming a token. You have the OPENING token in front of expression in the second instance.

Upvotes: 1

Related Questions