Bison LALR shift/reduce 冲突

Question

我最近又拿起了野牛，但我仍在为优先级的工作方式以及如何解决基本 shift/reduce 冲突而苦恼。我对编写语法规则和递归的工作原理等很满意，但我仍然无法理解优先级规则。

我将非常感谢对以下示例的一些评论以及我对它们的问题和理解。

test1.y

%token              ID
%token              TYPE_NAME
%token              ASTERIX

%nonassoc           F_T
%nonassoc           P_T

%%
f_type:
                    ID type         %prec F_T
;

type:
                    TYPE_NAME
|                   type ASTERIX    %prec P_T
|                   f_type
;
%%

test1.output

State 5

     1 f_type: ID type .
     3 type: type . ASTERIX

     ASTERIX  shift, and go to state 7

     ASTERIX   [reduce using rule 1 (f_type)]
     $default  reduce using rule 1 (f_type)

这个例子产生了 shift reduce 冲突，因为状态机无法确定它是否应该减少 ID type* -> type* -> type 或 身份证类型* -> 身份证类型 -> 类型。后者是期望的结果。我尝试通过给规则 type: type ASTERIX 一个比 f_type: ID type 更高的优先级来解决这个冲突，但事实并非如此似乎工作。我也不想为终端 ASTERIX 分配任何优先级，因为我想在其他情况下使用它。

test2.y

%token      ID
%token      DOUBLE_PLUS

%left       POSTFIX_OP
%right      PREFIX_OP

%%
exp:
            ID
|           exp DOUBLE_PLUS     %prec POSTFIX_OP
|           DOUBLE_PLUS exp     %prec PREFIX_OP
;
%%

test2.output

State 4

    2 exp: exp . DOUBLE_PLUS
    3    | DOUBLE_PLUS exp .

    DOUBLE_PLUS  shift, and go to state 6

    DOUBLE_PLUS  [reduce using rule 3 (exp)]
    $default     reduce using rule 3 (exp)

这个例子产生了shift/reduce冲突，因为DOUBLE_PLUS exp DOUBLE_PLUS的约简有歧义。所以我试图为 DOUBLE_PLUS exp 分配比 exp DOUBLE_PLUS 更高的优先级，但这也不起作用.可以通过为终端 DOUBLE_PLUS 分配左优先级或右优先级来解决此冲突，我猜分配左优先级意味着 exp DOUBLE_PLUS 首先减少，正确的意思是 DOUBLE_PLUS exp 首先减少，但我也希望有一些方法可以做到这一点通过使用 %prec 注释。

我也不确定我是否正确理解了 .output 文件。规则中的 . 表示堆栈中的内容以及超前令牌是什么，但是为什么在后一个示例中甚至提到了规则 2？我的意思是 exp: exp 。 DOUBLE_PLUS应该不会有什么冲突吧？

Answer 1

这里引用我写的关于 yacc/bison 优先算法的一段话。我不知道它是否比龙书上的文档或描述更清楚，但这是我迄今为止能做的最好的。如果您觉得它令人困惑，请告诉我：

Recall that a precedence relation is defined between a production and a terminal. It does not relate two terminals nor two productions (and so cannot be used to resolve reduce-reduce conflicts). The comparison between precedence of the production which could be reduced and the lookahead terminal determines whether a reduce or a shift will occur. For notational convenience, productions are represented by the name of a terminal, usually the only terminal in the production; this corresponds to a common use case but it is sometimes confusing. In particular, the %prec declaration only serves to give a rule a name for use in precedence declarations, and it is probably better to think about it in that way rather than as an "explicit" declaration.

由于优先级比较永远不会在两个规则之间进行——它们总是在规则和先行标记之间——优先顺序声明必须包括规则（无论是隐式还是显式）和标记名称。因此，在您的第一个示例中， F_T 和 P_T 之间的优先顺序没有任何影响。同样，在第二个示例中，PREFIX_OP 和 POSTFIX_OP 是仅与规则相关联的优先级，因此优先级排序无效。

如果shift和reduce都是可能的，并且规则和lookahead token之间的比较会显示规则具有更高的优先级，那么将生成reduce动作。如果先行标记具有更高的优先级，则将生成移位操作。但是只有在转移和减少都可能的情况下才会参考声明。如果文法只能执行一个动作，那么不管怎样，它都会执行这个动作。（例外：%nonassoc 声明实际上会禁止某些减少。）

如果比较结果相等——规则和标记都在同一个优先组中——那么 shift 将有利于 %left 组，而 reduce 则适用于 %right 组。这种情况通常不会应用于一元运算符的情况，无论是前缀还是后缀，因为在这种情况下，只有一个动作是可能的。

如果在优先规则中插入标记会与语法另一部分的优先顺序发生冲突，那么您不能使用优先声明作为捷径；您只需要编写语法以使优先级明确。这通常并不困难。另一方面，两种不同语法上下文中的优先顺序冲突可能会让人类非常困惑，因此您可能需要重新考虑。

关于.output文件中的状态机输出，打印了整个状态，而不仅仅是引起冲突的部分。冲突在动作中指出； […] 包含的动作与其他动作冲突，并被 bison 的默认冲突解决机制消除（更喜欢 shift 而不是 reduce；更喜欢其规则在文件中较早的 reduce）。粗略地说，移位规则在标记前有 .；减少规则在规则末尾有 .。

Bison LALR shift/reduce 冲突

Bison LALR shift/reduce conflicts

yacc

lalr

bison