[antlr-interest] Left-Recursion Removal Help

John B. Brodie jbb at acm.org
Tue Feb 23 18:22:55 PST 2010


Greetings!

It is really hard to know for sure how to truly answer your question
without seeing a complete example of your problem (e.g. please always
try to post a *smallest* yet *complete* example of your issue when
asking a question).

With that mealy worded excuse for my incompetence, I will venture an
answer below...

On Tue, 2010-02-23 at 19:30 -0600, Kyle Robson wrote:
> Hi, I have been reading on the wiki, and I already fixed two of my
> larger issues in my grammar (hopefully correctly). Now I've run into a
> new set of rules that need fixing, and I would like to verify I'm
> going about this correctly. I will take a guess, and can someone tell
> me if it's correct?
> 
> The problem snippet:
> 
> timesExp: (timesExp | divExp | modExp | andExp | factor) '*' factor;
> divExp : (timesExp | divExp | modExp | andExp | factor) 'div' factor;
> modExp : (timesExp | divExp | modExp | andExp | factor) 'mod' factor;
> andExp : (timesExp | divExp | modExp | andExp | factor) 'and' factor;
> factor : '#'; // this rule is itself broken, but I will get to this
> later, so I'm pretending it's something harmless
> 
> My guess is to change them like this, using timesExp as an example
> 
> timesExp: ((divExp | modExp | andExp | factor) '*' factor) ('*' factor)*
> 
> Is this correct?

I doubt it.

maybe try something like the following (untested):

timesExp : multiplicativeExp ;
divExp : multiplicativeExp ;
modExp : multiplicativeExp ;
andExp : multiplicativeExp ;
factor : multiplicativeExp ;

multiplicativeExp : factor_x ( multiplicativeOperator factor_x )* ;

multiplicativeOperator : '*' | 'div' | 'mod' | 'and' ;

factor_x : .....whatever you have for `factor` now.... ;



and, of course, if the above helps, you will really want to do *alot* of
renaming of rules --- rather than having the factor_x, timesExp,
divExp, ... stuff above

hope this helps
   -jbb




More information about the antlr-interest mailing list