Bison 解析器转移/减少冲突

Question

我是

Bison

的新手，我正在尝试编写一个解析器。我已经用 Flex 编写了一个扫描仪。我为解析器想出了以下语法：

%token NUMBER
%token IDENTIFIER

%start Program

%%

Program: Stats;

Stats: Stats Stat ";"
    | /* Epsilon */
    ;

Stat: "var" IDENTIFIER ":=" Expr
    | Lexpr ":=" Expr
    | Expr;

Lexpr: IDENTIFIER
    | "head" Expr
    | "tail" Expr;

Expr: Term
    | UnaryOperatorChain Term;

UnaryOperatorChain: UnaryOperatorChain UnaryOperator
    | UnaryOperator;

UnaryOperator: "head" | "tail" | "not" | "islist";

Term:
    "(" Expr ")"
    | NUMBER
    | IDENTIFIER;

%%

我收到此错误：

14 shift/reduce conflicts

shift/reduce conflict on token "head"

我认为问题在于解析器无法区分 Lexpr 和 Expr，因此不知道使用哪个规则。我尝试了几个小时来重新安排我的语法，但似乎没有任何效果。预先感谢:)

Answer 1

使用

bison -v

运行会生成一个扩展名为

.output

的文件。这可以帮助您找到冲突的原因。就您而言，它开头为：

State 7 conflicts: 7 shift/reduce
State 8 conflicts: 7 shift/reduce

稍后，对于状态 7（状态 8 类似）：

State 7

    8 Lexpr: "head" • Expr
   14 UnaryOperator: "head" •

    NUMBER      shift, and go to state 4
    IDENTIFIER  shift, and go to state 19
    "head"      shift, and go to state 20
    "tail"      shift, and go to state 21
    "not"       shift, and go to state 9
    "islist"    shift, and go to state 10
    "("         shift, and go to state 11

    NUMBER      [reduce using rule 14 (UnaryOperator)]
    IDENTIFIER  [reduce using rule 14 (UnaryOperator)]
    "head"      [reduce using rule 14 (UnaryOperator)]
    "tail"      [reduce using rule 14 (UnaryOperator)]
    "not"       [reduce using rule 14 (UnaryOperator)]
    "islist"    [reduce using rule 14 (UnaryOperator)]
    "("         [reduce using rule 14 (UnaryOperator)]

    Expr                go to state 22
    UnaryOperatorChain  go to state 15
    UnaryOperator       go to state 16
    Term                go to state 17

状态7对应于由前两行中的两个项目组成的项目集。在这两项中，您刚刚读取了标记

"head"

。以下几行显示 Bison 不知道当出现标记

NUMBER

或标记

IDENTIFIER

时该怎么办。

• 它可以转移并进入状态 4，其中包含项目

  19 Term: NUMBER •

  ，从而继续执行规则 8 中

  head

  后面的表达式；或
• 它可以根据规则 14 进行约简，规则 14 表示

  head

  是一元运算符。

这说明你的表达语言有歧义。凭借经验，您应该能够找到歧义的原因，但是使用

bison -Wcounterexamples

运行也可以帮助您：

  First example: Stats "head" • "head" Term ":=" Expr ";" $end
  Shift derivation
    $accept
    ↳ 0: Stats                                                                     $end
         ↳ 2: Stats Stat                                                       ";"
                    ↳ 5: Lexpr                                       ":=" Expr
                         ↳ 8: "head" Expr
                                     ↳ 11: UnaryOperatorChain   Term
                                           ↳ 13: UnaryOperator
                                                 ↳ 14: • "head"
  Second example: Stats "head" • "head" Term ";" $end
  Reduce derivation
    $accept
    ↳ 0: Program                                                                      $end
         ↳ 1: Stats
              ↳ 2: Stats Stat                                                     ";"
                         ↳ 6: Expr
                              ↳ 11: UnaryOperatorChain                       Term
                                    ↳ 12: UnaryOperatorChain   UnaryOperator
                                          ↳ 13: UnaryOperator  ↳ 14: "head"
                                                ↳ 14: "head" •

这告诉你 Bison 无法决定如何解析诸如

head head id

之类的字符串前缀。 （事实上，作为反例，即使是

head id

也可以在这里工作。）请记住，Bison 只能解析 LALR(1) 语法，即使用一个前瞻符号。当第一个

head

被读取并且第二个

head

是前瞻符号时，Bison 需要决定这是否是

Lexpr

的一部分（稍后会跟上

:=

）或它的一部分一个

Expr

（后面会跟一个

;

）。当稍后找到（或未找到）标记

:=

时，两者之间的差异将变得明显。但是，为了看到这个标记，我们需要任意数量的前瞻符号，因为

Expr

中

head

后面的

Lexpr

的大小可以是任意大。

所以，这里的问题是

Lexpr

和

Expr

生成的语言的公共子集，在

Stat

的两个替代规则中。

恐怕没有简单的解决方案。你必须重构你的语法并消除歧义。