[antlr-interest] Newbie Ques: How to remove mutual left-recursion among rules

John B. Brodie jbb at acm.org
Thu Sep 7 06:03:56 PDT 2006


Hi!

Sandeep Gupta wrote:
>I apologize for the rules mentioned in the previous mail were wrongly
>specified. The rules should have been
>
>fragment choiceLists
>    :    '(' contentParticle ( '|' contentParticle )+ ')'
>    ;
>
>fragment sequenceLists
>    :    '(' contentParticle ( ',' contentParticle )* ')'
>    ;
>
>fragment contentParticle
>    :    (name | choiceLists | sequenceLists) Qualifier?
>    ;
>
>I have tried using the algorithm quoted at
>http://web.cs.wpi.edu/~kal/courses/compilers/images/PLTelralgorithm.gif but
>to no avail. Can any one guide me how to remove such mutual left-recursions
>and also how to handle the + and * qualifiers for it.

When running the org.antlr.Tool on the above rules, the tool suggests
left-factoring. so lets do that. e.g. we should merge the two list rules:

list :'(' contentParticle (choiceTail | sequenceTail) ')' ;

choiceTail : ( '|' contentParticle )+ ;

sequenceTail : ( ',' contentParticle )* ;

contentParticle : (name | list) Qualifier? ;




or maybe this would build a better tree:

list
    :'('! contentParticle
        ( ( '|'^^ contentParticle )+
        | ( ','^^ contentParticle )*
        ) ')'!
    ;


Hope this helps...
   -jbb


More information about the antlr-interest mailing list