0

我正在用 Bison 定义语法，我偶然发现了一个我想消除的 shift/reduce 冲突。冲突是由旨在匹配if/else语句的规则引起的：

state 17

   13 Stmt: IfBlock . OptionalElseBlock

    ELSE  shift, and go to state 42

    ELSE      [reduce using rule 16 (OptionalElseBlock)]
    $default  reduce using rule 16 (OptionalElseBlock)

    OptionalElseBlock  go to state 43

OptionalElseBlock定义如下：

   16 OptionalElseBlock: /* empty */
   17                  | ELSE Stmt

状态 42 和 43 看起来像这样，省略了 shift 和 reduce 信息：

state 42
   17 OptionalElseBlock: ELSE . Stmt

state 43
   13 Stmt: IfBlock OptionalElseBlock .

我以前使用过可选标记，但我猜测由于解析器的前瞻缓冲区仅包含 1 个终端OptionalElseBlock会导致冲突。有没有简单的方法来解决这个冲突？

4

2 回答 2

0

这是经典的 shift/reduce 冲突。问题如下：

if (c1) if (c2) stmt1; else stmt2;

问题是if属于else哪个。如果它不是可选的，那么就没有问题，或者如果if必须终止语句（比如用fior end，选择两个流行的替代方案），但C语法似乎赢了，因此我们有 shift/reduce 冲突。

编写一个不存在此问题的语法是可能的，但并非易事。您可以通过玩具有优先规则的游戏或简单地“预期”转移/减少冲突来隐藏冲突。（我更喜欢后者，但有很多人会说优先破解更好，尽管它等同于恕我直言。）

重写的语法是龙书中的练习，可能还有其他解析文本，因此出于学习目的可能值得这样做，但是在语法维护方面确实很痛苦，并且如果在都是一个问题。

关于如何使用优先级和移位偏好来简化解析的经典论文是 Aho、Johnson 和 Ullman 于 1975 年左右发表的“Deterministic parsing of ambiguous grammars”。如果您无法访问一个好的图书馆，Google 可能会为您找到可以在线阅读的副本。

于 2012-11-25T17:16:52.410 回答
0

您可能想看看我对同一问题的回答。这是一个常见问题解答。

改革语法以消除移位减少 if-then-else 中的冲突

我建议不要使用%expect n除 0 以外的任何东西。

于 2012-11-26T08:27:23.557 回答