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

[Christopher Schultz]

Alexey,

Thanks for the response. I must admit that I'm not really in tune with
the Zen of these kinds of things. I built a very simply language
compiler in university and that was about all other than this project ;)

> 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 ")" ;

Okay, I used to have the following parser rules:

expr: exp=relexpr ( ( AND^ relexpr) | (OR^ relexpr) )* (EOF!)?;

relexpr: exp=addexpr ( (EQUALS^ addexpr)
                     | (NOT_EQUALS^ addexpr)
                     | (GREATERTHAN^ addexpr)
                     | (LESSTHAN^ addexpr)
                     | (GREATERTHANEQUALTO^ addexpr)
                     | (LESSTHANEQUALTO^ addexpr)
                     )* ;

addexpr: exp=multexpr (( PLUS^ multexpr  | MINUS^ multexpr ))* ;

multexpr: exp=unaryExpr ( ( STAR^ unaryExpr ) | ( SLASH unaryExpr )
            | ( PERCENT unaryExpr ) )* ;

unaryExpr : ( (BANG^ atom ) | (MINUS^ atom ) | (PLUS!)? atom ) ;

atom:   functioncall | arrayref | identifier | number | string |
        LPAREN! expr !RPAREN ;

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

I have modified my 'atom' rule to be the following:

atom:   identifier ( functionsuffix | arraysuffix ) *
	| number | string |
        LPAREN! expr !RPAREN ;

The functionsuffix and arraysuffix branches then wrap the identifier and
appropriate extra information into the appropriate Expression subclass
that I have (I build my own tree, instead of letting ANTLR do it for me).

Everything seems to work properly (and all my old unit tests, which
included function call testing), but I get a bunch of lexical
nondeterminism warnings. Increasing 'k' seems to make things worse.

Given that things are working properly, do you think that it's safe to
ignore these warnings?

Thanks again,
-chris


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 250 bytes
Desc: OpenPGP digital signature
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20060303/93f3cc6e/signature.bin