[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