[antlr-interest] Re: unexpected nondeterminism...

[Jan Oetting]

Hi Mark,
in a LL(k)-Parser is it not allowed to have two productions resulting
in a text, where the first k Tokens are identical. In your grammar it
is possible to break this rule, independent of the size of k.

Let me simplify your grammar to show you the point
ID OP ID (OP ID)*  ( AOP ID )?

example for the nondeterminus (with k=2)
beginning with 'statement' you can produce following
First way:

statement -> expression assignment -> term OP term assignment
-> ID OP ID assignment -> ID OP IP AOP expression -> ID OP ID AOP ID



second way:
statement -> expression -> term OP term -> ID OP term --> ID OP ID

Setting k higher doesn't help.
But because the meaning doesn't change whichever way the parser
choose, you could ignore the warning.

Cheers
Jan




Call me dense, but I'm not getting why this results in a nondeterminism:

class TestParser extends Parser;
        options { k = 2; }

term:           ID ;
expression:     term ( OP term )* ;
statement:      expression ( assignment )? ;
assignment:     ( OP )? AOP expression ;

The warning given is:

ANTLR Parser Generator   Version 2.7.3 (20040322-1)   1989-2004 jGuru.com
foo.g:7: warning:nondeterminism upon
foo.g:7:     k==1:OP
foo.g:7:     k==2:ID
foo.g:7:     between alt 1 and exit branch of block

Surely, with k=2 look ahead, the sequence [ OP, ID ] can only be alternative one of the 
block.  There doesn't seem to be a way in which OP can be followed by anything other than 
ID (in which case it is a continuation of the ()* block in expression), or AOP, in which case 
it is an assignment.  Doesn't the k=2 ensure that in the code for expression, it can look 
ahead and say if k==1:OP, k==2:ID then continue the loop, otherwise exit?

Any help to clear my thick-headed understanding would be appreciated!

- Mark



 
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/