[antlr-interest] Help with circular reference in parser?

Alexey Demakov demakov at ispras.ru
Fri Mar 3 00:05:31 PST 2006


It is well-known left recursion. Such kind of circular references not allowed
in LL-parsers. So, you need to transform recursions to loops like

expr: primaryExpr ( arraySuffix | functionSuffix )* ;

primaryExpr: literal | identifier ;

arraySuffix: "[" expr "]" ;

functionSuffix: "(" expr ")" ;

Regards,
Alexey

-----
Alexey Demakov
TreeDL: Tree Description Language: http://treedl.sourceforge.net
RedVerst Group: http://www.unitesk.com

----- Original Message ----- 
From: "Christopher Schultz" <christopher.d.schultz at comcast.net>
To: <antlr-interest at antlr.org>
Sent: Thursday, March 02, 2006 6:58 PM
Subject: [antlr-interest] Help with circular reference in parser?


> All,
> 
> Sorry for the potentially newbie question, but I have a circular
> reference in my grammar that I'm not sure how to resolve. I'd love it if
> someone would take a quick look and let me know if it's something simple
> that I should change.
> 
> To begin with, I had a completely working mathematical expression
> evaluator. I decided to add "array references" so that I could have
> expressions like
> 
>     array[index]
> 
> This worked just fine, and I even got dynamic indexes working, like:
> 
>     array[1+1]
> 
> The problem arises when I want to allow the array reference itself to be
> dynamic, like this:
> 
>     array()[1]
> 
> ...where "array" is a function that hopefully returns an array. In order
> to allow the reference to be dynamic, I had to change my parser rule
> from this:
> 
> // Array reference (i.e. a[3])
> arrayref returns [ Expression exp = null ] throws EvaluationException
>    {
>        Expression index; // dynamic index ;)
>    }
>    :
>        array:IDENTIFIER^ LBRACKET! (index=expr) RBRACKET!
>        {
>            exp = new ArrayReferenceExpression(array.getText(), index);
>        }
>    ;
> 
> To this:
> 
> // Array reference (i.e. a[3])
> arrayref returns [ Expression exp = null ] throws EvaluationException
>    {
>        Expression arrayRef; // dynamic reference ;)
>        Expression index; // dynamic index ;)
>    }
>    :
>        ( array=expr ) LBRACKET! (index=expr) RBRACKET!
>        {
>            exp = new ArrayReferenceExpression(array, index);
>        }
>    ;
> 
> As one might imagine, the rule "array=expr" refers to my top-level
> expression parser rule, which of course feeds back on itself. My guess
> is that even though the rules are (technically) circular, the parser
> ought to eventually reach a point where the input does not cause it to
> feedback.




More information about the antlr-interest mailing list