parsinggrammarleft-recursion

Eliminating Left Recursion from this weird Expression Grammar

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!

Solution

  • 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: 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:new parse tree