[antlr-interest] Left-Recursion Removal Help

[Kyle Robson]

Apologies, I believe I had made an error in the grammar sample I
mailed out. I was doing what I thought was inlining--except I believe
I did it backwards, making it very incorrect. Here is the relevant
section of the original grammar as presented in the grammar of this
language (BETA), modified to ANTLR's syntax.

term	:	mulExp
	|	factor
	;
mulExp	:	timesExp
	|	divExp
	|	modExp
	|	andExp
	;
// irrelevant code removed
timesExp:	term '*' factor;
divExp	:	term 'div' factor;
modExp	:	term 'mod' factor;
andExp	:	term 'and' factor;
factor	:	textConst
	|	integerConst
	|	notExp
	|	noneExp
	|	repetitionSlice
	|	transaction
	;

I turned it into this:

term	:	factor (timesExp | divExp | modExp | andExp)*
	;
// irrelevant code removed
timesExp:	'*' factor;
divExp	:	'div' factor;
modExp	:	'mod' factor;
andExp	:	'and' factor;
factor	:	textConst
	|	integerConst
	|	notExp
	|	noneExp
	|	repetitionSlice
	|	transaction
	;

I have attached two copies of the entire grammar for anyone who is
curious. Beta.g is almost identical to the grammar as presented in the
book /Object-Oriented Programming in the BETA Programming Language/:
http://www.daimi.au.dk/~beta/Books/index.html#betabook_download

BetaNew.g is the grammar as I've adapted it to work with ANTLR.

Also, thanks for the help, John.

Sincerely,

Kyle

On Tue, Feb 23, 2010 at 8:22 PM, John B. Brodie <jbb at acm.org> wrote:
> 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 beenA 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
>
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Beta.g
Type: application/octet-stream
Size: 5968 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20100228/d59d1bf3/attachment.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BetaNew.g
Type: application/octet-stream
Size: 5869 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20100228/d59d1bf3/attachment-0001.obj