消除shift/reduce个前缀相同的生产规则引起的冲突

Question

这是简化的 yaac 文件：

%token CONTEXT_    // the corresponding string is "context"
%token CONTEXTREF_ //"contextref"
%token IS_         //"is"
%token ID_L        //"id_l"
%token ID_L1       //"id_l1"
%token LIB_

%start design_file

%%
design_file   :design_unit
              |design_file design_unit 
              ;

design_unit   :context_cl LIB_
              |context_decl
              ;

context_cl    : /* empty */  {  }
              |context_cl context_ref
              ;

context_decl  :CONTEXT_ ID_L IS_ ';'
              ;

context_ref   :CONTEXT_ ID_L1 '.' ID_L ';'
              ;

有 2 个 shift/reduce 冲突。

CONTEXT_  shift, and go to state 1

CONTEXT_  [reduce using rule 5 (context_cl)]

规则 5 是 context_cl : /* empty */ { }。

一般来说，这无关紧要，解析器在大多数时候都运行良好。但是在一个奇怪的情况下，对于如下的源文件：

context id_l is ...
...

解析器不会移动而是减少，因此使用context_ref :CONTEXT_ ID_L1 '.' ID_L ';'来解析context id_l is ...，这会导致语法错误。

所以我必须消除冲突。我猜它们是由规则 context_decl 和 context_ref 开头的 CONTEXT_ 引起的。

为了验证我的猜测，我刚刚将 context_ref :CONTEXT_ ID_L1 '.' ID_L ';' 更改为 context_ref :CONTEXTREF_ ID_L1 '.' ID_L ';'。然后，没有冲突，没有语法错误。

但是，我不能这样替换context_ref。这是标准。

那么，如何通过其他方式避免这两种冲突呢？或者，是否有解决此类冲突的通用方法？

并且，对于 shift/reduce 冲突，解析器会选择减少而不是移动吗？因为我认为解析器总是会转移到 reduce 上。

Answer 1

我不确定你的 "intermittent" 语法错误是从哪里来的——正如你写的那样，你的语法永远无法匹配 context id_l1 . id_l 这样的输入...因为转换会导致它尝试解析 context_decl 而不是 context_ref.

不过，您的冲突与通用前缀几乎没有关系 -- 它实际上来自 /* empty */，最简单的解决方法是重构它以删除该规则：

design_unit   : context_cl LIB_
              | LIB_
              | context_decl
              ;

context_cl    : context_ref
              | context_cl context_ref
              ;

所以现在 context_cl 是“1 个或多个”context_ref 而不是“0 个或多个”，并且我们复制了 design_unit 规则以分别具有 0 个案例.

Answer 2

引起这种冲突的基本模式是：

union : x x_rest
      | y_list y_rest
y_list: /* empty */
      | y_list y

其中 x 和 y 都有以相同符号开头的产生式。

值得注意的是，如果 y_list 是一个或多个 y，而不是零个或多个，问题将消失：

y_list: y
      | y_list y

只要x和y真的能区分就可以了。（还有一些其他要求，取决于生产的其余部分，但如果它们具有相同的前缀基本上就可以了。它们甚至可以相同，前提是第一个标记的延续不同。）

如果你真的需要 y_list 可能为空（或者 x 和 y 都可能为空），你应该进行通常的空生产消除，这涉及从语法中分解出可能为空的产生式：

union : x x_rest
      | y_rest           /* Corresponds to an empty y_list */
      | y_list y_rest
y_list: y                /* As above, this list cannot be empty */
      | y_list y

消除shift/reduce个前缀相同的生产规则引起的冲突

Eliminate shift/reduce conflicts caused by production rules with same prefix

parsing

compiler-construction

bison

yacc

shift-reduce-conflict