changes_summary.txt

来自「EFI BIOS是Intel提出的下一代的BIOS标准。这里上传的Edk源代码是」· 文本 代码 · 共 1,594 行 · 第 1/5 页

  |                                                                     |
  |    Choice:2  Depth:1  Group:6  ("#tokclass")                        |
  |  2 to tclass                      grammar/94       line 656   a.g   |
  |  3 tclass                         tclass/1         line 937   a.g   |
  |  4 #token "#tokclass"             tclass/2         line 938   a.g   |
  |                                                                     |
  |    Choice:2  Depth:1  Group:7  ("class")                            |
  |  2 to class_def                   grammar/95       line 657   a.g   |
  |  3 class_def                      class_def/1      line 669   a.g   |
  |  4 #token "class"                 class_def/3      line 671   a.g   |
  |                                                                     |
  |    Choice:2  Depth:1  Group:8  ("\}")                               |
  |  2 #token "\}"                    grammar/96       line 658   a.g   |
  +---------------------------------------------------------------------+

      For a linear lookahead set ambiguity (where k=1 or for k>1 but
      when all lookahead sets [i] with i<k all have degree one) the
      reports appear in the following order:

        for (depth=1 ; depth <= "-aad depth" ; depth++) {
          for (alternative=1; alternative <=2 ; alternative++) {
            while (matches-are-found) {
              group++;
              print-report
            };
          };
       };

      For reporting a k-tuple ambiguity, the reports appear in the
      following order:

        for (depth=1 ; depth <= "-aad depth" ; depth++) {
          while (matches-are-found) {
            for (alternative=1; alternative <=2 ; alternative++) {
              group++;
              print-report
            };
          };
       };

      This is because matches are generated in different ways for
      linear lookahead and k-tuples.

#117. (Changed in 1.33MR10) new EXPERIMENTAL predicate hoisting code

      The hoisting of predicates into rules to create prediction
      expressions is a problem in antlr.  Consider the following
      example (k=1 with -prc on):

        start   : (a)* "@" ;
        a       : b | c ;
        b       : <<isUpper(LATEXT(1))>>? A ;
        c       : A ;

      Prior to 1.33MR10 the code generated for "start" would resemble:

        while {
            if (LA(1)==A &&
                    (!LA(1)==A || isUpper())) {
              a();
            }
        };

      This code is wrong because it makes rule "c" unreachable from
      "start".  The essence of the problem is that antlr fails to
      recognize that there can be a valid alternative within "a" even
      when the predicate <<isUpper(LATEXT(1))>>? is false.

      In 1.33MR10 with -mrhoist the hoisting of the predicate into
      "start" is suppressed because it recognizes that "c" can
      cover all the cases where the predicate is false:

        while {
            if (LA(1)==A) {
              a();
            }
        };

      With the antlr "-info p" switch the user will receive information
      about the predicate suppression in the generated file:

      --------------------------------------------------------------
        #if 0

        Hoisting of predicate suppressed by alternative without predicate.
        The alt without the predicate includes all cases where
            the predicate is false.

           WITH predicate: line 7  v1.g
           WITHOUT predicate: line 7  v1.g

        The context set for the predicate:

             A

        The lookahead set for the alt WITHOUT the semantic predicate:

             A

        The predicate:

          pred <<  isUpper(LATEXT(1))>>?
                          depth=k=1  rule b  line 9  v1.g
            set context:
               A
            tree context: null

        Chain of referenced rules:

            #0  in rule start (line 5 v1.g) to rule a
            #1  in rule a (line 7 v1.g)

        #endif
      --------------------------------------------------------------

      A predicate can be suppressed by a combination of alternatives
      which, taken together, cover a predicate:

        start   : (a)* "@" ;

        a       : b | ca | cb | cc ;

        b       : <<isUpper(LATEXT(1))>>? ( A | B | C ) ;

        ca      : A ;
        cb      : B ;
        cc      : C ;

      Consider a more complex example in which "c" covers only part of
      a predicate:

        start   : (a)* "@" ;

        a       : b
                | c
                ;

        b       : <<isUpper(LATEXT(1))>>?
                    ( A
                    | X
                    );

        c       : A
                ;

      Prior to 1.33MR10 the code generated for "start" would resemble:

        while {
            if ( (LA(1)==A || LA(1)==X) &&
                    (! (LA(1)==A || LA(1)==X) || isUpper()) {
              a();
            }
        };

      With 1.33MR10 and -mrhoist the predicate context is restricted to
      the non-covered lookahead.  The code resembles:

        while {
            if ( (LA(1)==A || LA(1)==X) &&
                  (! (LA(1)==X) || isUpper()) {
              a();
            }
        };

      With the antlr "-info p" switch the user will receive information
      about the predicate restriction in the generated file:

      --------------------------------------------------------------
        #if 0

        Restricting the context of a predicate because of overlap
          in the lookahead set between the alternative with the
          semantic predicate and one without
        Without this restriction the alternative without the predicate
          could not be reached when input matched the context of the
          predicate and the predicate was false.

           WITH predicate: line 11  v4.g
           WITHOUT predicate: line 12  v4.g

        The original context set for the predicate:

             A                X

        The lookahead set for the alt WITHOUT the semantic predicate:

             A

        The intersection of the two sets

             A

        The original predicate:

          pred <<  isUpper(LATEXT(1))>>?
                          depth=k=1  rule b  line 15  v4.g
            set context:
               A                X
            tree context: null

        The new (modified) form of the predicate:

          pred <<  isUpper(LATEXT(1))>>?
                          depth=k=1  rule b  line 15  v4.g
            set context:
               X
            tree context: null

        #endif
      --------------------------------------------------------------

      The bad news about -mrhoist:

        (a) -mrhoist does not analyze predicates with lookahead
            depth > 1.

        (b) -mrhoist does not look past a guarded predicate to
            find context which might cover other predicates.

      For these cases you might want to use syntactic predicates.
      When a semantic predicate fails during guess mode the guess
      fails and the next alternative is tried.

      Limitation (a) is illustrated by the following example:

        start    : (stmt)* EOF ;

        stmt     : cast
                 | expr
                 ;
        cast     : <<isTypename(LATEXT(2))>>? LP ID RP ;

        expr     : LP ID RP ;

      This is not much different from the first example, except that
      it requires two tokens of lookahead context to determine what
      to do.  This predicate is NOT suppressed because the current version
      is unable to handle predicates with depth > 1.

      A predicate can be combined with other predicates during hoisting.
      In those cases the depth=1 predicates are still handled.  Thus,
      in the following example the isUpper() predicate will be suppressed
      by line #4 when hoisted from "bizarre" into "start", but will still
      be present in "bizarre" in order to predict "stmt".

        start    : (bizarre)* EOF ;     // #1
                                        // #2
        bizarre  : stmt                 // #3
                 | A                    // #4
                 ;

        stmt     : cast
                 | expr
                 ;

        cast     : <<isTypename(LATEXT(2))>>? LP ID RP ;

        expr     : LP ID RP ;
                 | <<isUpper(LATEXT(1))>>? A

      Limitation (b) is illustrated by the following example of a
      context guarded predicate:

        rule : (A)? <<p>>?          // #1
                     (A             // #2
                     |B             // #3
                     )              // #4
             | <<q>> B              // #5
             ;

      Recall that this means that when the lookahead is NOT A then
      the predicate "p" is ignored and it attempts to match "A|B".
      Ideally, the "B" at line #3 should suppress predicate "q".
      However, the current version does not attempt to look past
      the guard predicate to find context which might suppress other
      predicates.

      In some cases -mrhoist will lead to the reporting of ambiguities
      which were not visible before:

        start   : (a)* "@";
        a       : bc | d;
        bc      : b  | c ;

        b       : <<isUpper(LATEXT(1))>>? A;
        c       : A ;

        d       : A ;

      In this case there is a true ambiguity in "a" between "bc" and "d"
      which can both match "A".  Without -mrhoist the predicate in "b"
      is hoisted into "a" and there is no ambiguity reported.  However,
      with -mrhoist, the predicate in "b" is suppressed by "c" (as it
      should be) making the ambiguity in "a" apparent.

      The motivations for these changes were hoisting problems reported
      by Reinier van den Born ([e-mail]) and several others.

#113. (Changed in 1.33MR10) new context guarded pred: (g)? && <<p>>? expr

      The existing context guarded predicate:

            rule : (guard)? => <<p>>? expr
                 | next_alternative
                 ;

      generates code which resembles:

            if (lookahead(expr) && (!guard || pred)) {
              expr()
            } else ....

      This is not suitable for some applications because it allows
      expr() to be invoked when the predicate is false.  This is
      intentional because it is meant to mimic automatically computed
      predicate context.

      The new context guarded predicate uses the guard information
      differently because it has a different goal.  Consider: