[antlr-interest] nondeterminism

Matt Benson gudnabrsam at yahoo.com
Wed Dec 14 10:25:29 PST 2005


Thanks for the reply, Geir.  I had resolved the
particular problem I was having by, yep, the use of a
couple of syntactic preds.  But it was very nearly
blind luck that helped me figure out where to put
them, which is why I left my request for
"nondeterminism resolution guidelines" open.  Reading
your example probably gelled a little bit of what I
had done Monday, but leads me to the conclusion that
the line number ANTLR reports is the most useful piece
of info I'll get from antlr.Tool, since it at least
shows me where to look for one of the ambiguous
constructs.  What really perplexes me is that every
time I get caught up in a nondeterminism, increasing k
does absolutely no good.  Not that I want to have a
grammar where k=10 or some such, but I find it
interesting that most of the types of nondeterminisms
I introduce cannot be resolved by lookahead tweaking. 
That may be related to the fact that many of my
problems were, IIRC, caused by optional rules and
subrules rather than the types of ambiguities you
outlined here.  Without thinking hard enough to hurt
my head right now, it seems sensible that increasing k
adds no benefit when the ambiguity refers to something
_missing_.

Anyway, thanks again for your input.  Feel free
(anyone) to comment on any of my musings as well.

-Matt

--- Geir Ove Skjaervik <geiroves at online.no> wrote:

> 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 
> 
> 
> 
> 


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


More information about the antlr-interest mailing list