bison - 野牛 LALR 移位/减少冲突

问题描述

我最近再次拿起野牛，但我仍在与优先级的工作方式以及如何解决基本的移位/减少冲突作斗争。我对编写语法规则以及递归的工作原理等非常满意，但我仍然无法理解优先规则。

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

测试1.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
;
%%

测试1.输出

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)

这个例子产生了一个移位减少冲突，因为状态机无法确定它是否应该减少ID type* -> type* -> type或ID type* -> ID 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
;
%%

测试2.输出

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)

此示例产生移位/减少冲突，因为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不应该有任何冲突吗？

标签： bisonyacclalr

解决方案

这是我写的关于 yacc/bison 优先算法的另一个答案的引用。我不知道它是否比龙书中的文档或描述更清晰，但这是我迄今为止能够做到的最好的。如果您发现它令人困惑，请告诉我：

回想一下，在产生式和终端之间定义了优先关系。它不涉及两个终端或两个产生式（因此不能用于解决归约-归约冲突）。可以减少的生产的优先级与前瞻终端之间的比较确定是否会发生减少或转移。为方便起见，产生式由终端的名称表示，通常是产生式中唯一的终端；这对应于一个常见的用例，但有时会令人困惑。特别是，%prec声明仅用于为规则命名以在优先声明中使用，并且以这种方式考虑它可能比作为“显式”声明更好。

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

如果 shift 和 reduce 都是可能的，并且规则和前瞻标记之间的比较可以显示规则具有更高的优先级，则将生成 reduce 操作。如果前瞻令牌具有更高的优先级，则将生成移位动作。但只有在 shift 和 reduce 都可能的情况下，才会查阅声明。如果语法只能执行一个动作，那就是它将执行的动作，无论如何。（例外：%nonassoc声明实际上会禁止某些减少。）

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

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

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

bison - 野牛 LALR 移位/减少冲突

问题描述

解决方案

推荐阅读