4

LALR（1）パーサージェネレーターであるLemonでコンパイルされます。

program ::= statement.

statement ::= ifstatement Newline.
statement ::= returnstatement Newline.

ifstatement ::= If Number A statement B.
ifstatement ::= If Number A statement B Newline Else A statement B.

returnstatement ::= Return Number.

エラーメッセージは次のとおりです。

user@/tmp > lemon test.lm
test.lm:6: This rule can not be reduced.

1 parsing conflicts.

デバッグ出力は次のとおりです。

State 0:
          program ::= * statement
          statement ::= * ifstatement Newline
          statement ::= * returnstatement Newline
          ifstatement ::= * If Number A statement B
          ifstatement ::= * If Number A statement B Newline Else A statement B
          returnstatement ::= * Return Number

                            If shift  10
                        Return shift  3
                       program accept
                     statement shift  13
                   ifstatement shift  12
               returnstatement shift  11

State 1:
          statement ::= * ifstatement Newline
          statement ::= * returnstatement Newline
          ifstatement ::= * If Number A statement B
          ifstatement ::= * If Number A statement B Newline Else A statement B
          ifstatement ::= If Number A statement B Newline Else A * statement B
          returnstatement ::= * Return Number

                            If shift  10
                        Return shift  3
                     statement shift  4
                   ifstatement shift  12
               returnstatement shift  11

State 2:
          statement ::= * ifstatement Newline
          statement ::= * returnstatement Newline
          ifstatement ::= * If Number A statement B
          ifstatement ::= If Number A * statement B
          ifstatement ::= * If Number A statement B Newline Else A statement B
          ifstatement ::= If Number A * statement B Newline Else A statement B
          returnstatement ::= * Return Number

                            If shift  10
                        Return shift  3
                     statement shift  8
                   ifstatement shift  12
               returnstatement shift  11

State 3:
          returnstatement ::= Return * Number

                        Number shift  14

State 4:
          ifstatement ::= If Number A statement B Newline Else A statement * B

                             B shift  15

State 5:
          ifstatement ::= If Number A statement B Newline Else * A statement B

                             A shift  1

State 6:
          ifstatement ::= If Number A statement B Newline * Else A statement B

                          Else shift  5

State 7:
      (3) ifstatement ::= If Number A statement B *
          ifstatement ::= If Number A statement B * Newline Else A statement B

                       Newline shift  6
                       Newline reduce 3   ** Parsing conflict **

State 8:
          ifstatement ::= If Number A statement * B
          ifstatement ::= If Number A statement * B Newline Else A statement B

                             B shift  7

State 9:
          ifstatement ::= If Number * A statement B
          ifstatement ::= If Number * A statement B Newline Else A statement B

                             A shift  2

State 10:
          ifstatement ::= If * Number A statement B
          ifstatement ::= If * Number A statement B Newline Else A statement B

                        Number shift  9

State 11:
          statement ::= returnstatement * Newline

                       Newline shift  16

State 12:
          statement ::= ifstatement * Newline

                       Newline shift  17

State 13:
      (0) program ::= statement *

                             $ reduce 0

State 14:
      (5) returnstatement ::= Return Number *

                     {default} reduce 5

State 15:
      (4) ifstatement ::= If Number A statement B Newline Else A statement B *

                     {default} reduce 4

State 16:
      (2) statement ::= returnstatement Newline *

                     {default} reduce 2

State 17:
      (1) statement ::= ifstatement Newline *

                     {default} reduce 1

----------------------------------------------------
Symbols:
    0: $:
    1: Newline
    2: If
    3: Number
    4: A
    5: B
    6: Else
    7: Return
    8: error:
    9: program: If Return
   10: statement: If Return
   11: ifstatement: If
   12: returnstatement: Return
4

1 に答える 1

1

デバッグ出力から状態7を見てください。これは、パーサーが次のトークンのセットをすでに受け入れている場合を説明しています。

    ifstatement ::= If Number A statement B *

この場合、Newlineトークンが来るときにパーサーが選択できる2つのオプションは次のとおりです。

  1. それを覚えて、状態6に切り替えてください。このシフトは、文法の次のルールによって規定されています。

    ifstatement ::= If Number A statement B Newline Else A statement B.

  2. 現在のルールが完了したと見なし、上位レベルのルールに戻ります。この削減は、文法から次の規則によって規定されています。

    ifstatement ::= If Number A statement B.

LALR（1）パーサーには、ストリーム内の次のトークンを先読みできないため、この場合に失敗する他のオプションはありません。Newlineの後にElseが来ることを予測することはできません。

この矛盾する状況を回避するために文法を修正してください。改行文字は通常、言語文法に含まれていないことを追加することしかできません。Tokenizerは通常、他の空白文字と同様に、それらをトークン境界と見なします。

于 2012-08-07T12:35:27.237 に答える