[antlr-interest] nondeterminism

[Geir Ove Skjaervik]

Hello,

I think we need to see your grammar to understand why you get this
problem. In general, what happens is that with a given lookahead, ANTLR
gives this error message when it cannot distingusih between two rules. 

In general, I add one rule at a time, because the ANTLR error messages
can be really hard to track when rules recurse !


For eksampel, I have the following two rules that works OK

expressionEquality throws GeosParserException,
GeosCalculatorTerminateException
	:  expressionRelations ((EQUALS^ | NOTEQUALS^)
expressionRelations)*
	;

expressionRelations throws GeosParserException,
GeosCalculatorTerminateException
	: simpleExpression ((GT^ | LT^ | GTE^ | LTE^) simpleExpression)*
	;	

Now, If I add another rule to expressionEquality  like below, I get a
non-determinism 
(Silly to introduce ID there, but it demonstrates the concept !)


expressionEquality throws GeosParserException,
GeosCalculatorTerminateException
	:  (expressionRelations | ID) ((EQUALS^ | NOTEQUALS^)
(expressionRelations))*
	;

warning:nondeterminism between alts 1 and 2 of block upon
k==1:ID
k==2:SEMI,COMMA,RPAREN,AND,OR,XOR,EQUALS,NOTEQUALS,RSQUARE


However, I can write out the expressionEquality rule as follows: 

expressionEquality throws GeosParserException,
GeosCalculatorTerminateException
	:  expressionRelations ((EQUALS^ | NOTEQUALS^) {allowNull =
true;} expressionRelations {allowNull = false;})*
	| ID ((EQUALS^ | NOTEQUALS^) {allowNull = true;}
expressionRelations {allowNull = false;})*
	;	

Now, I can use a Syntactic Predicate to resolve this problem: 

expressionEquality throws GeosParserException,
GeosCalculatorTerminateException
	: (ID (EQUALS | NOTEQULLS)) => ID ((EQUALS^ | NOTEQUALS^)
{allowNull = true;}  expressionRelations {allowNull = false;})*
	|  expressionRelations ((EQUALS^ | NOTEQUALS^) {allowNull =
true;} expressionRelations {allowNull = false;})*
	;	

Now I get NO error messages !

NOTE: I then had to move the conflicting rule to alternative 1, because
the Syntactic Predicate must come **before** the rule it resolves a
conflict with.


Hope this helps

Geir Ove

-----Original Message-----
From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Matt Benson
Sent: 12. desember 2005 17:43
To: Antlr List
Subject: [antlr-interest] nondeterminism


I am having trouble recognizing nondeterminisms.  I
get warnings like
FooParser.g:106:17: warning:nondeterminism between
alts 1 and 2 of block upon
FooParser.g:106:17:     k==1:LPAREN
FooParser.g:106:17:    
k==2:"null",IDENT,BEANREF,BEANCOPY,STRING_LITERAL,LBRACK,LPAREN,RPAREN,"
true","false",NUM_INT,NUM_DOUBLE,NUM_LONG,NUM_FLOAT

The generated code looks as though it will behave in
the way I want.  Are there any rules of thumb that may
help me better understand what ANTLR is flagging, so
that I can know better how to (a) remove the condition
that generates the warning, (b) work around the
condition with predicates, or (c) shut off the warning confident that I
am not missing anything

?

TIA,
Matt

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com