[antlr-interest] ANTLR Optional statements

[Tom Moog]

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/