[antlr-interest] Issues with mutually left-recursive rules

Fri Jul 2 10:01:56 PDT 2010

I'm not sure if you're willing to take this leap, but you could always throw out the EBNF your using (which seems to have many instances of left recursion and could be more work than it's worth in trying to eliminate those left recursive calls) and start from scratch by redesigning the EBNF from the ground up.

In order to help you redesign a new EBNF, you could ask yourself, "What grammar does this language most closely resemble?"  If it's C, then use the C grammar that is available online as a template to implementing the EBNF of your language.

I can say from my own experience that using the C grammar as a template has helped me in implementing two general languages.

Just my .02

- Darin

-----Original Message-----
From: Christian (VuuRWerK) Seifert [mailto:vuurwerk.christian at googlemail.com] 
Sent: Friday, July 02, 2010 9:52 AM
To: Mikesell, Darin B.
Subject: Re: [antlr-interest] Issues with mutually left-recursive rules

Yeah, I already read it (I've quote it also in my first message) and
I've tried it as the author described but without success.
It's very very disappointing for me, because I know how and why the
left-recursion happen but I have no clue to solve it :(

The array_declaration should be possible to declare with different
kind of expression. Thus I tried to remove the array_declaration from
the pre_unary_expression-rule and add it to the expression-rule
instead. Now I just get a left-recursion with expression and
array_declaration. I know it is because the array_declaration are
different kind of expression, which can in turn be yet another
array_declaration, which can be in turn ... you got the point :) But
how the hell I can solve the misery? ... :(

- Christian

2010/7/2 Mikesell, Darin B. <Darin.Mikesell at gd-ais.com>:
> Have you read the article at the following link:
> http://www.antlr.org/wiki/display/ANTLR3/Left-Recursion+Removal
>
>
>> And I can't get the
>> meaning that an array_declaration is an pre_unary_expression at the
>> moment. I've just work it out depending on that EBNF-grammar ...
>
> An array_declaration is a pre_unary_expression in your grammar because an array_declaration references an expression which references a pre_unary_expression which references an array_declaration which references an expression which references a pre_unary_expression and on and on and on.
>
> The EBNF grammar that you are using is probably valid, but because ANTLR is a recursive descent parser it cannot handle left-recursive grammars, it would cause an infinite loop.
>
>
> - Darin
>
>
> -----Original Message-----
> From: Christian (VuuRWerK) Seifert [mailto:vuurwerk.christian at googlemail.com]
> Sent: Friday, July 02, 2010 12:33 AM
> To: Mikesell, Darin B.
> Subject: Re: [antlr-interest] Issues with mutually left-recursive rules
>
> Erm ... it should not :)
>
> Actually the "instanceof"-check should work with a "primary_variable"
> only. For the sake of completeness the "primary_variable"-rule:
> ========== >8 ==========
> primary_variable    : '$' identifier ( '[' expression ']' | '->' expression )*;
> ========== 8< ==========
>
> I've changed the "pre_unary_expression" according to this conclusion:
> ========== >8 ==========
> pre_unary_expression: '++' primary_variable
>                    | '--' primary_variable
>                    | unary_expression
>                    | primary_variable KW_INSTANCEOF identifier
>                    | array_declaration
>                    ;
> ========== 8< ==========
>
> But the error still exists :(
>
> If I remove the "array_declaration"-rule from the
> "pre_unary_expression"-rule the error disappear. And I can't get the
> meaning that an array_declaration is an pre_unary_expression at the
> moment. I've just work it out depending on that EBNF-grammar ...
>
> But I hope I found a solution for my plight.
>
>
> 2010/7/2 Mikesell, Darin B. <Darin.Mikesell at gd-ais.com>
>>
>> So in your grammar it's possible to have an expression of the form:
>>
>> ++primary_variable KW_INSTANCEOF identifier KW_INSTANCEOF identifier KW_INTANCEOF identifier KW_INSTANCEOF identifier and on and on?
>>
>>
>> - Darin
>>
>> -----Original Message-----
>> From: Mikesell, Darin B.
>> Sent: Thursday, July 01, 2010 3:51 PM
>> To: 'vuurwerk.christian at gmail.com'
>> Subject: RE: [antlr-interest] Issues with mutually left-recursive rules
>>
>> So in your grammar it's possible to have an expression of the form:
>>
>> ++primary_variable KW_INSTANCEOF identifier KW_INSTANCEOF identifier KW_INTANCEOF identifier KW_INSTANCEOF identifier and on and on?
>>
>>
>> - Darin
>>
>>
>> -----Original Message-----
>> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Christian (VuuRWerK) Seifert
>> Sent: Thursday, July 01, 2010 3:03 PM
>> To: antlr-interest at antlr.org
>> Subject: [antlr-interest] Issues with mutually left-recursive rules
>>
>> Hi list,
>>
>> I've got some troubles with mutually left-recursive rules in my
>> grammar (which is just an easy conversion of an original EBNF
>> grammar).
>>
>> First the error message:
>> ========== >8 ==========
>> error(210):  The following sets of rules are mutually left-recursive
>> [pre_unary_expression, expression, array_declaration]
>> ========== 8< ==========
>>
>> The rules which cause the error:
>> ========== >8 ==========
>> expression          : pre_unary_expression ( binary_operator expression )?;
>>
>> pre_unary_expression: '++' primary_variable
>>                    | '--' primary_variable
>>                    | unary_expression
>>                    | expression KW_INSTANCEOF identifier
>>                    | array_declaration
>>                    ;
>>
>> array_declaration   : KW_ARRAY '(' ( ( expression '=>' )? expression (
>> ',' expression )* ( ',' )? )? ')'
>>                    | expression '..' expression
>>                    ;
>> ========== 8< ==========
>>
>> If I remove the pre_unary_expression from the expression rule the
>> error disappear, But for my intention the rule "expression" comprise a
>> pre_unary_expression.
>>
>> I've already read
>> http://www.antlr.org/wiki/display/ANTLR3/Left-Recursion+Removal and
>> tried it as the author suggest it but I get no idea which rules I
>> should "inline". And ANTLRWorks means the selected rule has no
>> left-recursion ...
>> I've also read a lot of left-recursion and how to remove it but all
>> what I've tried so far doesn't work :(
>>
>> I'm very sad about that I can't get it to work and it's my last idea
>> to try one's luck here at the list.
>> Hope someone can help me or just can give me a hint where I can find
>> more infos about to solve my problem.
>>
>> Best regards
>> Christian
>>
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>>
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>