[antlr-interest] nondeterminism

[Geir Ove Skjaervik]

Hello again,

Yes, ANTLR often get problems resolving Ambiguities, and the reason for
this can bee read in the ANTLR docs  that I have quoted below.

WARNING: Because of this limitation, I often find that Introducing an
Ambiugity in one rule, may lead to ANTLR reporting the problem in
another rule at a great depth from the rule where the problem was
introduced.

This is why I find that it is important to do an ANTLR compile each time
I write a new rule / change a rule. If I write a lot of new rules and
then compile, I will often get error messages that leaves me CLUELESS at
what the problem is !


***************** Start From ANTLR Documentation **********************

k: Setting the lookahead depth

You may set the lookahead depth for any grammar (parser, lexer, or
tree-walker), by using the k=
option:
class MyLexer extends Lexer;
options { k=3; }
...
Setting the lookahead depth changes the maximum number of tokens that
will be examined to select
alternative productions, and test for exit conditions of the EBNF
constructs (...)?, (...)+, and (...)*. The
lookahead analysis is linear approximate (as opposed to full LL(k) ).
This is a bit involved to explain in
detail, but consider this example with k=2:
r : ( A B | B A )
| A A
;


Full LL(k) analysis would resolve the ambiguity and produce a lookahead
test for the first alternate like:
if ( (LA(1)==A && LA(2)==B) || (LA(1)==B && LA(2)==A) )
However, linear approximate analysis would logically OR the lookahead
sets at each depth, resulting in
a test like:
if ( (LA(1)==A || LA(1)==B) && (LA(2)==A || LA(2)==B) )
Which is ambiguous with the second alternate for {A,A}. Because of this,
setting the lookahead depth
very high tends to yield diminishing returns in most cases, because the
lookahead sets at large depths
will include almost everything.

***************** End From ANTLR Documentation **********************

Geir Ove




-----Original Message-----
From: Matt Benson [mailto:gudnabrsam at yahoo.com] 
Sent: 14. desember 2005 19:25
To: Geir Ove Skjaervik; 'Antlr List'
Subject: RE: [antlr-interest] nondeterminism


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