野牛：奇怪的转变——减少冲突
Bison: strange shift-reduce conflict
我尝试在自定义语法中实现函数调用（加上类似的数组访问运算符）：
expression
: ....OTHER EXPRESSION RULES....
| expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE { } %prec DOT
| expression SQUARE_OPEN expressions SQUARE_CLOSE { } %prec DOT
;
这是我所有的运算符优先级：
%right ASSIGN ASSIGN_MOD ASSIGN_XOR ASSIGN_AND ASSIGN_STAR ASSIGN_MINUS ASSIGN_PLUS ASSIGN_OR ASSIGN_DIV ASSIGN_LSHIFT ASSIGN_RSHIFT
%right QUESTION COLON
%left OR
%left AND
%left BIN_OR
%left XOR
%left BIN_AND
%left NOT_EQUALS NOT_SAME EQUALS SAME
%left LESS LESS_EQUALS MORE MORE_EQUALS
%left LSHIFT RSHIFT
%left PLUS MINUS
%left PERCENT STAR SLASH
%right TILDE NOT DECREASE INCREASE
%left DOT
请注意，DOT 具有最高的优先级。因此，我尝试将其纳入我的函数调用规则。尽管如此，我还是收到了 74 shift/reduce 条警告，它们都遵循以下模式：
State 25
15 expression: expression . PLUS expression
16 | expression . MINUS expression
17 | expression . NOT_EQUALS expression
18 | expression . NOT_SAME expression
19 | expression . PERCENT expression
20 | expression . ASSIGN_MOD expression
21 | expression . XOR expression
22 | expression . ASSIGN_XOR expression
23 | expression . BIN_AND expression
24 | expression . AND expression
25 | expression . ASSIGN_AND expression
26 | expression . STAR expression
27 | expression . ASSIGN_STAR expression
28 | expression . ASSIGN_MINUS expression
29 | expression . ASSIGN expression
30 | expression . EQUALS expression
31 | expression . SAME expression
32 | expression . ASSIGN_PLUS expression
33 | expression . BIN_OR expression
34 | expression . OR expression
35 | expression . ASSIGN_OR expression
36 | expression . SLASH expression
37 | expression . ASSIGN_DIV expression
38 | expression . DOT expression
39 | expression . LESS expression
40 | expression . LESS_EQUALS expression
41 | expression . LSHIFT expression
42 | expression . ASSIGN_LSHIFT expression
43 | expression . MORE expression
44 | expression . MORE_EQUALS expression
45 | expression . RSHIFT expression
46 | expression . ASSIGN_RSHIFT expression
48 | expression . PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE
49 | expression . SQUARE_OPEN expressions SQUARE_CLOSE
53 | DECREASE expression .
55 | expression . DECREASE
56 | expression . INCREASE
PARENTHESIS_OPEN shift, and go to state 46
DECREASE shift, and go to state 47
INCREASE shift, and go to state 52
SQUARE_OPEN shift, and go to state 54
DOT shift, and go to state 61
PARENTHESIS_OPEN [reduce using rule 53 (expression)]
SQUARE_OPEN [reduce using rule 53 (expression)]
$default reduce using rule 53 (expression)
状态 46，表示冲突的班次，说明如下：
State 46
48 expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE
MINUS shift, and go to state 5
TILDE shift, and go to state 6
NOT shift, and go to state 7
PARENTHESIS_OPEN shift, and go to state 8
DECREASE shift, and go to state 9
INCREASE shift, and go to state 10
INT shift, and go to state 11
FLOAT shift, and go to state 12
STRING shift, and go to state 13
CHAR shift, and go to state 14
ID shift, and go to state 15
$default reduce using rule 59 (expressions)
expression go to state 87
expressions go to state 88
我真的不明白野牛为什么选择减少。因为我给了函数调用规则尽可能高的优先级，bison 应该尝试移动直到匹配那个规则。不过，前缀 DECREASE 运算符看起来像是野牛的选择，即使它的优先级较低。
为什么野牛会那样做？我如何向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.
A %prec 声明（重新）定义了它所属的 reduction 的优先级。在你的情况下，
| expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE { } %prec DOT
| expression SQUARE_OPEN expressions SQUARE_CLOSE { } %prec DOT
声明这两个缩减都具有 DOT 的优先级，而不是 PARENTHESIS_CLOSE 和 SQUARE_CLOSE [注 1]。由于后两个标记未出现在 %left / %right 声明中，这实际上是优先级的定义，但由于以下两个原因是不必要的：
您可以将 PARENTHESIS_CLOSE 和 SQUARE_CLOSE 添加到适当的优先级，但更重要的是
这两个归约不参与任何shift/reduce冲突。
您应该尝试理解（并希望同意）我在第 (2) 项中的主张。作为起点，请考虑您在问题中包含的状态 25。在状态 25 中，唯一可能的减少是根据规则 53 (expression: DECREASE expression)。您可以看到这一点，因为这是该州中唯一在右侧边缘具有 . 的项目。只有右边缘有圆点的项目才能减少（因为右边缘的圆点表示对应于该项目的生产可能在此状态下完成。）而且，确实，你可以看到shift/reduce 为该州报告的冲突：
PARENTHESIS_OPEN shift, and go to state 46
PARENTHESIS_OPEN [reduce using rule 53 (expression)]
SQUARE_OPEN shift, and go to state 54
SQUARE_OPEN [reduce using rule 53 (expression)]
这两个冲突都涉及使用规则 53 的可能减少。
所以在状态 25 中，如果 ( 是先行字符，语法将允许
( 的转变，导致项目 expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE 的状态（注意点如何移动到 PARENTHESIS_OPEN令牌）。
或规则的缩减 expression: DECREASE expression.
Bison 通过比较 reduction (DECREASE) 的优先级与前瞻标记 (PARENTHESIS_OPEN) 的优先级来解决这个冲突。 PARENTHESIS_OPEN 没有出现在任何优先级中，因此 Bison 回到其默认值，即更喜欢移位。
显然，改变归约的优先级expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE对这个冲突的解决没有影响，因为那个归约与这个冲突无关。
现在，我的主张是缩减与语法中的任何冲突无关。这似乎是一个有点古怪的说法，因为我看不到很多语法，事实上我可能是错的。理论上，table 中可能还有一些其他状态，其中包括项目：
expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE .
并且还包括了一些可以转换的项目，例如
some_non_terminal: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE . something
我觉得这不太可能。
通常，后缀运算符归约（函数调用和数组索引在概念上是后缀运算符）从不参与移位归约冲突，因为在后缀运算符之后几乎不可能发生移位。如果有这样的转变，运算符将是中缀，而不是后缀。您可以想象一个语法，其中运算符符号可以是中缀运算符和后缀运算符，类比像 - 这样的运算符，它可以是中缀或前缀。但事实证明，由于超出此答案范围的原因，情况并不对称。 [注2]
回到最初的问题：我们已经看到 shift/reduce 冲突发生在 reduction expression: DECREASE expression（在本例中）和terminals PARENTHESIS_OPEN 和 SQUARE_OPEN，它无法解决，因为 PARENTHESIS_OPEN 和 SQUARE_OPEN 未在您的优先级别中列出。所以解决方案是列出它们：
/* ... */
%left PERCENT STAR SLASH
%precedence TILDE NOT DECREASE INCREASE
%precedence PARENTHESIS_OPEN SQUARE_OPEN
请注意，我将最后一个 %left 和 %right 更改为 %precedence，这是一个 bison 扩展，允许您为关联性无意义的运算符定义优先级。我这样做是因为我认为它更清楚。 [注3]
备注
使用 PARENTHESIS_OPEN 而不是更简单、更易读的 '(' 确实没什么好说的。 Yacc 和 bison 允许单字符标记像那样被单引号精确地允许
的可读性
expression: expression '(' expressions ')'
expression: expression '[' expressions ']'
这也简化了您的 (f)lex 扫描器，因为单个后备规则可以处理所有这四个标记，以及所有其他单字符标记，包括您尚未添加到语法中的标记：
/* Put this rule at the end of your ruleset */
. { return *yytext;}
例如，假设 ! 可以是后缀或中缀，并考虑表达式 a!-b*4。这里的歧义（(a!)-b 或 a!(-b)）由于二进制 bang、减号和乘法运算符也具有有效的优先级规则这一事实而变得更加复杂。
一元运算符，无论是前缀还是后缀，都没有结合律，因为结合律只适用于二元运算符。结合性是 a + b + c 是 (a + b) + c 而 a = b = c 是 a = (b = c) 的原因。相反，只有一种方法可以解析 --a 或 !!a（或其组合）。 （如果您考虑优先关系如何影响 shift-reduce 冲突解决方案，这也很清楚。需要一元 reduction ('!' expression .) 进行比较的冲突是什么a ! lookahead symbol? 在像'-'这样的双用途运算符的情况下，我们需要将归约的优先级更改为伪终端（%prec UMINUS），之后就很清楚了该关联性无法应用，因为 UMINUS 不可能是前瞻符号。
我尝试在自定义语法中实现函数调用（加上类似的数组访问运算符）：
expression
: ....OTHER EXPRESSION RULES....
| expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE { } %prec DOT
| expression SQUARE_OPEN expressions SQUARE_CLOSE { } %prec DOT
;
这是我所有的运算符优先级：
%right ASSIGN ASSIGN_MOD ASSIGN_XOR ASSIGN_AND ASSIGN_STAR ASSIGN_MINUS ASSIGN_PLUS ASSIGN_OR ASSIGN_DIV ASSIGN_LSHIFT ASSIGN_RSHIFT
%right QUESTION COLON
%left OR
%left AND
%left BIN_OR
%left XOR
%left BIN_AND
%left NOT_EQUALS NOT_SAME EQUALS SAME
%left LESS LESS_EQUALS MORE MORE_EQUALS
%left LSHIFT RSHIFT
%left PLUS MINUS
%left PERCENT STAR SLASH
%right TILDE NOT DECREASE INCREASE
%left DOT
请注意，DOT 具有最高的优先级。因此，我尝试将其纳入我的函数调用规则。尽管如此，我还是收到了 74 shift/reduce 条警告，它们都遵循以下模式：
State 25
15 expression: expression . PLUS expression
16 | expression . MINUS expression
17 | expression . NOT_EQUALS expression
18 | expression . NOT_SAME expression
19 | expression . PERCENT expression
20 | expression . ASSIGN_MOD expression
21 | expression . XOR expression
22 | expression . ASSIGN_XOR expression
23 | expression . BIN_AND expression
24 | expression . AND expression
25 | expression . ASSIGN_AND expression
26 | expression . STAR expression
27 | expression . ASSIGN_STAR expression
28 | expression . ASSIGN_MINUS expression
29 | expression . ASSIGN expression
30 | expression . EQUALS expression
31 | expression . SAME expression
32 | expression . ASSIGN_PLUS expression
33 | expression . BIN_OR expression
34 | expression . OR expression
35 | expression . ASSIGN_OR expression
36 | expression . SLASH expression
37 | expression . ASSIGN_DIV expression
38 | expression . DOT expression
39 | expression . LESS expression
40 | expression . LESS_EQUALS expression
41 | expression . LSHIFT expression
42 | expression . ASSIGN_LSHIFT expression
43 | expression . MORE expression
44 | expression . MORE_EQUALS expression
45 | expression . RSHIFT expression
46 | expression . ASSIGN_RSHIFT expression
48 | expression . PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE
49 | expression . SQUARE_OPEN expressions SQUARE_CLOSE
53 | DECREASE expression .
55 | expression . DECREASE
56 | expression . INCREASE
PARENTHESIS_OPEN shift, and go to state 46
DECREASE shift, and go to state 47
INCREASE shift, and go to state 52
SQUARE_OPEN shift, and go to state 54
DOT shift, and go to state 61
PARENTHESIS_OPEN [reduce using rule 53 (expression)]
SQUARE_OPEN [reduce using rule 53 (expression)]
$default reduce using rule 53 (expression)
状态 46，表示冲突的班次，说明如下：
State 46
48 expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE
MINUS shift, and go to state 5
TILDE shift, and go to state 6
NOT shift, and go to state 7
PARENTHESIS_OPEN shift, and go to state 8
DECREASE shift, and go to state 9
INCREASE shift, and go to state 10
INT shift, and go to state 11
FLOAT shift, and go to state 12
STRING shift, and go to state 13
CHAR shift, and go to state 14
ID shift, and go to state 15
$default reduce using rule 59 (expressions)
expression go to state 87
expressions go to state 88
我真的不明白野牛为什么选择减少。因为我给了函数调用规则尽可能高的优先级，bison 应该尝试移动直到匹配那个规则。不过，前缀 DECREASE 运算符看起来像是野牛的选择，即使它的优先级较低。
为什么野牛会那样做？我如何向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.
A %prec 声明（重新）定义了它所属的 reduction 的优先级。在你的情况下，
| expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE { } %prec DOT
| expression SQUARE_OPEN expressions SQUARE_CLOSE { } %prec DOT
声明这两个缩减都具有 DOT 的优先级，而不是 PARENTHESIS_CLOSE 和 SQUARE_CLOSE [注 1]。由于后两个标记未出现在 %left / %right 声明中，这实际上是优先级的定义，但由于以下两个原因是不必要的：
您可以将
PARENTHESIS_CLOSE和SQUARE_CLOSE添加到适当的优先级，但更重要的是这两个归约不参与任何shift/reduce冲突。
您应该尝试理解（并希望同意）我在第 (2) 项中的主张。作为起点，请考虑您在问题中包含的状态 25。在状态 25 中，唯一可能的减少是根据规则 53 (expression: DECREASE expression)。您可以看到这一点，因为这是该州中唯一在右侧边缘具有 . 的项目。只有右边缘有圆点的项目才能减少（因为右边缘的圆点表示对应于该项目的生产可能在此状态下完成。）而且，确实，你可以看到shift/reduce 为该州报告的冲突：
PARENTHESIS_OPEN shift, and go to state 46
PARENTHESIS_OPEN [reduce using rule 53 (expression)]
SQUARE_OPEN shift, and go to state 54
SQUARE_OPEN [reduce using rule 53 (expression)]
这两个冲突都涉及使用规则 53 的可能减少。
所以在状态 25 中，如果 ( 是先行字符，语法将允许
( 的转变，导致项目
expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE的状态（注意点如何移动到PARENTHESIS_OPEN令牌）。或规则的缩减
expression: DECREASE expression.
Bison 通过比较 reduction (DECREASE) 的优先级与前瞻标记 (PARENTHESIS_OPEN) 的优先级来解决这个冲突。 PARENTHESIS_OPEN 没有出现在任何优先级中，因此 Bison 回到其默认值，即更喜欢移位。
显然，改变归约的优先级expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE对这个冲突的解决没有影响，因为那个归约与这个冲突无关。
现在，我的主张是缩减与语法中的任何冲突无关。这似乎是一个有点古怪的说法，因为我看不到很多语法，事实上我可能是错的。理论上，table 中可能还有一些其他状态，其中包括项目：
expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE .
并且还包括了一些可以转换的项目，例如
some_non_terminal: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE . something
我觉得这不太可能。
通常，后缀运算符归约（函数调用和数组索引在概念上是后缀运算符）从不参与移位归约冲突，因为在后缀运算符之后几乎不可能发生移位。如果有这样的转变，运算符将是中缀，而不是后缀。您可以想象一个语法，其中运算符符号可以是中缀运算符和后缀运算符，类比像 - 这样的运算符，它可以是中缀或前缀。但事实证明，由于超出此答案范围的原因，情况并不对称。 [注2]
回到最初的问题：我们已经看到 shift/reduce 冲突发生在 reduction expression: DECREASE expression（在本例中）和terminals PARENTHESIS_OPEN 和 SQUARE_OPEN，它无法解决，因为 PARENTHESIS_OPEN 和 SQUARE_OPEN 未在您的优先级别中列出。所以解决方案是列出它们：
/* ... */
%left PERCENT STAR SLASH
%precedence TILDE NOT DECREASE INCREASE
%precedence PARENTHESIS_OPEN SQUARE_OPEN
请注意，我将最后一个 %left 和 %right 更改为 %precedence，这是一个 bison 扩展，允许您为关联性无意义的运算符定义优先级。我这样做是因为我认为它更清楚。 [注3]
备注
使用
的可读性PARENTHESIS_OPEN而不是更简单、更易读的'('确实没什么好说的。 Yacc 和 bison 允许单字符标记像那样被单引号精确地允许expression: expression '(' expressions ')' expression: expression '[' expressions ']'这也简化了您的 (f)lex 扫描器，因为单个后备规则可以处理所有这四个标记，以及所有其他单字符标记，包括您尚未添加到语法中的标记：
/* Put this rule at the end of your ruleset */ . { return *yytext;}例如，假设 ! 可以是后缀或中缀，并考虑表达式
a!-b*4。这里的歧义（(a!)-b或a!(-b)）由于二进制 bang、减号和乘法运算符也具有有效的优先级规则这一事实而变得更加复杂。一元运算符，无论是前缀还是后缀，都没有结合律，因为结合律只适用于二元运算符。结合性是
a + b + c是(a + b) + c而a = b = c是a = (b = c)的原因。相反，只有一种方法可以解析--a或!!a（或其组合）。 （如果您考虑优先关系如何影响 shift-reduce 冲突解决方案，这也很清楚。需要一元 reduction ('!' expression .) 进行比较的冲突是什么a!lookahead symbol? 在像'-'这样的双用途运算符的情况下，我们需要将归约的优先级更改为伪终端（%prec UMINUS），之后就很清楚了该关联性无法应用，因为UMINUS不可能是前瞻符号。