[antlr-interest] Fwd: ANTLRWorks bug: Remove Left Recursion with comments in grammar

[Kevin J. Cummings]

I'm confused.  If you have:

string : string Plus string
       | string Minus string
       | Digit
       ;

and you remove left recursion, why don't you end up with:

string : Digit ( Plus Digit | Minus Digit )*
       ;

And, yes, the error message with the ";" in it is amusing.

On 09/26/2011 02:05 PM, The Researcher wrote:
> I forgot to give credit where credit is due.
> 
> This grammar is from
> 
> Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007) Compilers:
> principles, techniques, & tools (2nd ed.). Boston: Pearson/Addison Wesley.
> pg. 47, Example 2.5
> 
> 
> 
> 
> 
> ---------- Forwarded message ----------
> From: The Researcher <researcher0x00 at gmail.com>
> Date: Mon, Sep 26, 2011 at 1:51 PM
> Subject: ANTLRWorks bug: Remove Left Recursion with comments in grammar
> To: antlr-interest at antlr.org
> 
> 
> grammar Ambiguious001;
> 
> 
> 
> string      : string Plus string
> 
>             | string Minus string
> 
>             | Digit
> 
>             ;
> 
> 
> 
> Digit       : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
> 
> Minus       : '-' ;
> 
> Plus        : '+' ;
> 
> 
> 
> Remove All Left Recursion or Remove Left Recursion produces
> 
> grammar Ambiguious001;
> 
> 
> 
> string      : (Digit) (Plus string | Minus string)*
> 
>             ;
> 
> 
> 
> Digit       : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
> 
> Minus       : '-' ;
> 
> Plus        : '+' ;
> 
> 
> 
> However
> 
> grammar Ambiguious001;
> 
> 
> 
> // Parser
> 
> 
> 
> string      : string Plus string
> 
>             | string Minus string
> 
>             | Digit
> 
>             ;
> 
> 
> 
> // Lexer
> 
> 
> 
> Digit       : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
> 
> Minus       : '-' ;
> 
> Plus        : '+' ;
> 
> 
> 
> Remove All Left Recursion or Remove Left Recursion produces
> 
> 
> 
> grammar Ambiguious001;
> 
> 
> 
> // Parser
> 
> 
> 
> string      : (Digit
> 
>             ;) (Plus string | Minus string)*
> 
> 
> 
> // Lexer
> 
> 
> 
> Digit       : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
> 
> Minus       : '-' ;
> 
> Plus        : '+' ;
> 
>   It's the first time I have ever had an error wink at me.
> 
> Eric
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address


-- 
Kevin J. Cummings
kjchome at verizon.net
cummings at kjchome.homeip.net
cummings at kjc386.framingham.ma.us
Registered Linux User #1232 (http://www.xlinuxcounter.net/)