[antlr-interest] Nondeterminism in a simple expression grammar

[Dave Bailey]

Hi,

I have a simple expression grammar that I'm trying to fix.  I get a
nondeterminism warning and I can't seem to make it go away.

The grammar has two operators, U and B.  U is a unary operator, and
has lower precedence than B.  I want to be able to parse expressions
like the following:

U a B b;           // equivalent to (U (B a b))
a B U b;           // equivalent to (B a (U b))
a B U b B U c B d; // equivalent to (B a (U (B b (U (B c d)))))

I wrote the following grammar (test.g):

--------------------------------------------------------------------
options { language = "Cpp"; genHashLines = true; }
class test_parser extends Parser;
options { k = 3; buildAST = true; }

test : (expr SEMI!)+ EOF! ;
expr : uexp | bexp ;
uexp : U^ expr ;
bexp : ID (B^ (uexp | ID))* ;

class test_lexer extends Lexer;
options { testLiterals = true; }
tokens  { U = "U"; B = "B"; }
SEMI : ';' ;
WS   : (' '|'\n'{newline();}) {$setType(antlr::Token::SKIP);} ;
ID   : ('a'..'z'|'A'..'Z')+ ;
--------------------------------------------------------------------

With this grammar, I can parse the way I want to, but antlr gives me
the following warning:

test.g:8: warning:nondeterminism upon
test.g:8:     k==1:"B"
test.g:8:     k==2:"U",ID
test.g:8:     k==3:SEMI,"U",ID,"B"
test.g:8:     between alt 1 and exit branch of block

The warning can be suppressed if I change the 'bexp' rule to:

bexp : ID (options {warnWhenFollowAmbig=false;} : B^ (uexp | ID))* ;

Is this the only way to eliminate the warning?  Or can I rewrite the
grammar somehow?

Thanks in advance-

-dave



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
     antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
     http://docs.yahoo.com/info/terms/