[antlr-interest] ANTLR Optional statements
Tom Moog
tmoog at polhode.com
Thu Apr 11 15:39:50 PDT 2002
Maybe this will explain what is going on more
clearly:
------------------------------------------------------------
#196. (Changed in MR14) Problems with "(alpha)? beta" guess
Consider the following syntactic predicate in a grammar
with 2 tokens of lookahead (k=2 or ck=2):
rule : ( alpha )? beta ;
alpha : S t ;
t : T U
| T
;
beta : S t Z ;
When antlr computes the prediction expression with one token
of lookahead for alts 1 and 2 of rule t it finds an ambiguity.
Because the grammar has a lookahead of 2 it tries to compute
two tokens of lookahead for alts 1 and 2 of t. Alt 1 clearly
has a lookahead of (T U). Alt 2 is one token long so antlr
tries to compute the follow set of alt 2, which means finding
the things which can follow rule t in the context of (alpha)?.
This cannot be computed, because alpha is only part of a rule,
and antlr can't tell what part of beta is matched by alpha and
what part remains to be matched. Thus it impossible for antlr
to properly determine the follow set of rule t.
Prior to 1.33MR14, the follow of (alpha)? was computed as
FIRST(beta) as a result of the internal representation of
guess blocks.
With MR14 the follow set will be the empty set for that context.
Normally, one expects a rule appearing in a guess block to also
appear elsewhere. When the follow context for this other use
is "ored" with the empty set, the context from the other use
results, and a reasonable follow context results. However if
there is *no* other use of the rule, or it is used in a different
manner then the follow context will be inaccurate - it was
inaccurate even before MR14, but it will be inaccurate in a
different way.
For the example given earlier, a reasonable way to rewrite the
grammar:
rule : ( alpha )? beta
alpha : S t ;
t : T U
| T
;
beta : alpha Z ;
If there are no other uses of the rule appearing in the guess
block it will generate a test for EOF - a workaround for
representing a null set in the lookahead tests.
If you encounter such a problem you can use the -alpha option
to get additional information:
line 2: error: not possible to compute follow set for alpha
in an "(alpha)? beta" block.
With the antlr -alpha command line option the following information
is inserted into the generated file:
#if 0
Trace of references leading to attempt to compute the follow set of
alpha in an "(alpha)? beta" block. It is not possible for antlr to
compute this follow set because it is not known what part of beta has
already been matched by alpha and what part remains to be matched.
Rules which make use of the incorrect follow set will also be incorrect
1 #token T alpha/2 line 7 brief.g
2 end alpha alpha/3 line 8 brief.g
2 end (...)? block at start/1 line 2 brief.g
#endif
At the moment, with the -alpha option selected the program marks
any rules which appear in the trace back chain (above) as rules with
possible problems computing follow set.
Reported by Greg Knapen.
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list