[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