4

它是用 Lemon 编译的，它是一个 LALR(1) 解析器生成器：

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 *

在这种情况下，当出现换行符时，解析器可以选择以下两个选项：

  1. 记住它并切换到状态 6。这种转变由语法中的下一条规则规定：

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

  2. 认为当前规则已完成并返回上一级规则。此归约是由您的语法中的此规则规定的：

    ifstatement ::= If Number A statement B.

在这种情况下，LALR(1) 解析器没有其他选择会失败，因为它无法提前查看流中的下一个标记。它无法预测 Else 会在 Newline 之后出现。

修改你的语法以避免这种冲突的情况。我只能补充一点，换行符通常不包含在语言语法中。Tokenizer 通常将它们视为类似于其他空白字符的标记边界。

于 2012-08-07T12:35:27.237 回答