Bison LALR改变/减少冲突

Question

我最近再次选择了野牛，但我仍在与优先工作的方式以及如何解决基本的转移/减少冲突进行斗争。我很乐意编写语法规则以及递归如何工作等等，但我仍然无法绕过优先规则。

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

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)

这个例子产生一个移位减少冲突，因为状态机无法弄清楚它是否应该减少ID类型* - >类型* - >类型或ID类型* - > ID类型 - >类型。后者是理想的结果。我尝试通过提供规则类型来解决此冲突：键入ASTERIX的优先级高于f_type：ID类型，但似乎不起作用。我也不想给终端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)

此示例产生移位/减少冲突，因为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

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

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

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

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

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

如果将标记插入到优先规则中会在语法的另一部分中创建与优先顺序的冲突，那么就不能使用优先级声明作为快捷方式;你只需要编写你的语法，使优先级明确。这通常并不困难。另一方面，两种不同语法语境中的冲突优先级对于人类来说可能非常混乱，因此您可能需要重新考虑。

关于.output文件中的状态机输出，打印整个状态，而不仅仅是产生冲突的部分。行动中表明了冲突; […]所包含的行为与其他行动相冲突，并被野牛的默认冲突解决机制所取消（更喜欢转移到减少;更喜欢减少其规则在文件中较早的规则）。粗略地说，转换规则在令牌之前有.;减少规则在规则的末尾有.。