Eliminating Left Recursion from this weird Expression Grammar

Question

I am trying to write an Expression Grammar where there are 3 operators '+','-' and '/'. The multiplication operator is implied by juxtaposition as in:

(1+2)(3+4 5)

Here is the Grammar:

S -> A ('+' A)*

A -> B ('-' B)*

B -> C ('/' C)*

C -> D ( D )*

D ->ID
    |Num
    |'(' S ')'

I am using Xtext which uses the ANTLR parser and it says this is left recursive on Rule C. If I were to change Rule 4 as

C -> D ('\*' D)*

Then error is eliminated. I am confused. Would like some help!

I don't think it's the problem, but your rules are redundant. E.g. S->A('+' A)* already allows for derivation of a single A, so S->A is unnecessary. Same for all the others. — Gene
Okay. I removed those. I am pretty new with parsing. Please bear with me. — Kartik Sayani

Gene Gene · Accepted Answer · 2017-07-01T02:27:14

I don't know anything about Xtext, but Antlr 4 has no problem with this grammar:

grammar Expr; 
s: a ('+' a)* ;
a: b ('-' b)* ;
b: c ('/' c)* ;
c: d ( d )* ;
d: ID | NUM |'(' s ')' ;
ID: [a-z][a-z0-9]* ;
NUM: [0-9]+ ;
WS: [ \t\r\n]+ -> skip ;

When I compile and run your example (1+2)(3+4 5), I get this parse tree:

It may be Xtext is using an old version of Antlr. It's a great bit of software, but in older versions especially it's not perfect. This grammar is not left-recursive by the standard definition. It's possible Antlr is transforming it into a simpler grammar that is left recursive, but that would be a bug that's apparently been fixed.

So if my guess is correct, you'll be successful with the following explicitly "simplified" grammar:

grammar Expr; 
s: a ap ;
ap: '+' a ap | /* eps */ ;
a: b bp ;
bp: '-' b bp | /* eps */ ;
b: c cp ;
cp: '/' c cp | /* eps */ ;
c: d dp ;
dp: d dp | ;
d: ID | NUM |'(' s ')' ;
ID: [a-z][a-z0-9]* ;
NUM: [0-9]+ ;
WS: [ \t\r\n]+ -> skip ;

New parse tree:

Eliminating Left Recursion from this weird Expression Grammar

1 Answers