具有两次以上递归的运算符优先级

Question

我正在尝试对野牛进行算子优先级和关联性的一些组合。尽管在某些情况下看起来很奇怪，但出现了一个基本问题，即以下规则是否有效，但确实没有错。

expr: expr OP1 expr OP5 '+' expr

根据野牛信息页面，规则优先于最后一个终端符号或为其明确分配的优先级。下面是优先级，并从代码中粘贴了完整的expr规则：

%left OP4
%left OP3
%left OP2
%left OP1
%left '*'
%left '/'
%left '+'
%left '-'

expr:  NUM                               { $$ = $1; }
| expr OP2 expr OP5 '+' expr             { printf("+"); }
| expr OP1 expr OP5 '-' expr             { printf("-"); }
| expr OP4 expr OP5 '*' expr             { printf("*"); }
| expr OP3 expr OP5 '/' expr             { printf("/"); }
          ;
Below is data tokens given:
1op11op5-2op22op5+3op33op5/4op44op5*5

执行解析器的输出低于预期。

-+/*

现在，一旦优先级在算术运算符和OP之间翻转，结果将反转，表明不是最后一个终端也影响规则优先级。

%left '*'
%left '/'
%left '+'
%left '-'
%left OP4
%left OP3
%left OP2
%left OP1

解析器的现在输出是反向的，指示最后一个终端的优先级没有帮助：

*/-+

此外，如果第一个组合仅具有比OP运算符更高优先级的算术运算符，如果删除了OP运算符的优先级，则结果仍然是第二个组合，没有先例的规则。这个结果使得很难得出结论，第二个expr用于优先而不是第三个。从以上结果可以得出什么结论。如果规则中使用了两次以上的递归，那么优先级和关联性逻辑是什么？

Answer 1

bison中的“优先”规则实际上与传统意义上的运算符优先级没有多大关系，它们实际上只是解决可减少移位冲突的一种方法，该方法可以在操作系统中实现简单的运算符优先级。模棱两可的语法。因此，要了解它们是如何工作的，您需要了解移位/减少解析以及优先级规则如何用于解决冲突。

实际机制实际上非常简单。只要野牛在解析器中为语法生成的解析器中有移位/减少冲突，就会查看冲突中涉及的规则（减少）和令牌（转移），并且如果两者都分配了优先级，它将解决冲突。优先选择较高的优先级。就这样。

因此，这对于解决简单的二进制运算符的优先级非常有效，但是，如果您尝试将其用于更复杂的事物，则可能会惹上麻烦。在您的示例中，所有冲突都发生在规则和OP1 / 2/3/4的移位之间，因此，重要的是这两个组的相对优先级-每个组中的优先级均无关紧要，因为从不存在任何冲突它们之间。因此，当规则的优先级较高时，它们将从左到右减少，而当OP令牌的优先级较高时，它将转移（最终导致从右到左的减少）。