[antlr-interest] Lookahead set merging

Brad Schick schick at robotbattle.com
Sun May 2 23:35:03 PDT 2004


For a given block, why does antlr create "lookahead sets" that are 
mergers of all possible tokens for each value of k? I ask because it 
appears that merged lookahead sets can report nondeterminisms that 
do not really exist (either that or I am missing something obvious :)

If you compile the grammar below with k=2 you will get 
nondeterminisms that I believe do not exist. The cause of the 
nondeterminism is the non-matching alt-2 case for (variable_qual)?. 
When alt-2 is reached, I don't believe it is possible for lookahead
(k=1) to be '[' and lookahead(k=2) to be IDENT. Antlr only thinks 
this is possible because all tokens where merged for each lookahead 
depth, and the merged sets do contain '[' at k=1 and IDENT at k=2.

Wouldn't it be possible to test the lookahead tokens from each 
contributing rule separately rather than merging them? Or would that 
be inefficient?


// Tweaked from a larger grammar
expression
    : variable "+" variable;

array_init_lvalue
    : variable "[" "]";

variable
    : IDENT (variable_qual)?;

variable_qual
    : "[" expression "]" (variable_qual)?; 




 
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/
 



More information about the antlr-interest mailing list