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

[Mikesell, Darin B.]

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