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

[Christopher Schultz]

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.

The actual error is super long, but I'm including it, anyway, in the
interest in full disclosure. Feel free to skip past it.

antlr:
    [antlr] ANTLR Parser Generator   Version 2.7.3   1989-2004 jGuru.com
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:63:13: infinite
recursion to rule atom from rule multexpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:53:13: infinite
recursion to rule atom from rule addexpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:37:13: infinite
recursion to rule atom from rule relexpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:23:13: infinite
recursion to rule atom from rule expr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:104:17: infinite
recursion to rule atom from rule arrayref
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:140:13: infinite
recursion to rule atom from rule atom
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:77:21: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:77:21: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:79:22: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:63:13: infinite
recursion to rule atom from rule multexpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:53:13: infinite
recursion to rule atom from rule addexpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:37:13: infinite
recursion to rule atom from rule relexpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:23:13: infinite
recursion to rule atom from rule expr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:104:17: infinite
recursion to rule atom from rule arrayref
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:140:13: infinite
recursion to rule atom from rule atom
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:180:21: infinite
recursion to rule atom from rule atom
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:76:9:
warning:nondeterminism between alts 1 and 3 of block upon
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:76:9:     k==1:BANG
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:76:9:
k==2:PLUS,MINUS,BANG,IDENTIFIER,LPAREN,HEX_LITERAL,OCTAL_LITERAL,INT_LITERAL,DECIMAL_LITERAL,STRING
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:79:22: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:76:9:
warning:nondeterminism between alts 2 and 3 of block upon
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:76:9:     k==1:MINUS
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:76:9:
k==2:PLUS,MINUS,BANG,IDENTIFIER,LPAREN,HEX_LITERAL,OCTAL_LITERAL,INT_LITERAL,DECIMAL_LITERAL,STRING
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:23: infinite
recursion to rule atom from rule unaryExpr
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:10:
warning:nondeterminism between alts 1 and 2 of block upon
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:10:     k==1:PLUS
    [antlr]
/home/chris/projects/evaluator/src/grammar/expression.g:81:10:
k==2:PLUS,MINUS,BANG,IDENTIFIER,LPAREN,HEX_LITERAL,OCTAL_LITERAL,INT_LITERAL,DECIMAL_LITERAL,STRING
    [antlr] Exiting due to errors.

===========================

END OF ERROR MESSAGE

===========================

Perhaps I'm way off base, too. I'm attaching my full grammar file which
has the non-working definition of "arrayref" in there.

Any help would be most appreciated.

Thanks,
-chris