[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