野牛:奇怪的转变，减少冲突 [英] Bison: strange shift-reduce conflict

问题描述

我尝试在自定义语法中实现函数调用(加上类似的数组访问运算符):

I try to implement a function call in a custom grammar (plus a similar array-access operator):

expression
    :   ....OTHER EXPRESSION RULES....

    | expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE   {  }     %prec DOT
    | expression SQUARE_OPEN expressions SQUARE_CLOSE      {  }          %prec DOT
    ;

这是我所有的运算符优先级:

Here is my all my operator precedences:

%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个移位/减少警告，所有警告都遵循此模式:

Please note that DOT is has the highest precedence. So, I try to give this to my function-call rules. Still, I get 74 shift/reduce warnings, that all follow this pattern:

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, that the conflicted shift indicates, says the following:

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

我真的不明白为什么野牛选择减少.由于我给了函数调用规则最高的优先级，所以野牛应该尝试转移直到它匹配那个规则.前缀DECREASE运算符仍然看起来像是野牛的选择，即使它的优先级较低.

I really do not get why bison chooses to reduce. Since I gave the function-call rule the highest possible precedence, bison should try to shift until it matches that one. Still, the prefix DECREASE operator looks like been the choice of bison, even if it has lower precedence.

为什么野牛会这么做?我如何对野牛清楚地说，函数调用规则应具有更高的优先级，从而避免冲突?

Why bison does that? How can I say clearly to bison that the function-call rule should have the higher precedence, and thus, avoid the conflicts?

推荐答案

以下内容引自

回想一下，在产品和终端之间定义了优先级关系.它既不涉及两个终端，也不涉及两个产品(因此不能用于解决减少-减少冲突).可以减少的生产优先级与超前的终端之间的比较确定是减少还是转移.

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.

%prec声明(重新)定义了它所属的 reduce 的优先级.就您而言，

A %prec declaration (re-)defines the precedence of the reduction it is part of. In your case,

| expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE   {  }     %prec DOT
| expression SQUARE_OPEN expressions SQUARE_CLOSE      {  }          %prec DOT

声明这两个减法均具有DOT的优先级，而不是PARENTHESIS_CLOSE和SQUARE_CLOSE的优先级[注1].由于后两个标记未出现在%left / %right声明中，因此这实际上是优先级的定义，但是由于两个原因，它是不必要的:

declares that both of those reductions have the precedence of DOT, instead of PARENTHESIS_CLOSE and SQUARE_CLOSE [Note 1]. Since the latter two tokens don't appear in the %left / %right declarations, this is actually a definition of precedence, but it was unnecessary for two reasons:

1. 您可以将PARENTHESIS_CLOSE和SQUARE_CLOSE添加到适当的优先级，但更重要的是

1. You could have just added PARENTHESIS_CLOSE and SQUARE_CLOSE to the appropriate precedence level, but more importantly

这两个减少项不参与任何移位/减少冲突.

These two reductions do not participate in any shift/reduce conflict.

您应该尝试理解(并希望同意)我在第(2)项中的主张.首先，考虑问题中已包含的25号州.在状态25中，唯一可能的减少是规则53(expression: DECREASE expression).您可以看到，因为这是该状态中唯一在右边缘具有.的项目.只能减少在右边缘带有点的项目(因为该点在右边缘表示该项目对应的生产在此状态下可能是完整的.)并且，实际上，您可以看到此状态报告的转移/减少冲突:

You should make some attempt to understand (and hopefully agree with) my claim in item (2). As a place to start, consider State 25 which you've included in your question. In State 25, the only possible reduction is by rule 53 (expression: DECREASE expression). You can see that because that is the only item in the state which has the . at the right-hand edge. Only items which have the dot at the right-hand edge can be reduced (since the dot being at the right-hand edge indicates that the production corresponding to the item might be complete in this state.) And, indeed, you can see the shift/reduce conflicts reported for this state:

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进行可能的减少.

Both of those conflicts involve a possible reduction using rule 53.

因此在状态25中，如果(是超前字符，则语法将允许其中任何一个

So in State 25 if a ( is the lookahead character, the grammar would allow either

• ()的移位，导致进入带有项expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE的状态(请注意点如何在PARENTHESIS_OPEN令牌上移动).

• a shift of the (, leading to a state with the item expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE (note how the dot has moved over the PARENTHESIS_OPEN token).

或规则expression: DECREASE expression的简化.

野牛通过比较归约(DECREASE)的优先级与先行标记(PARENTHESIS_OPEN)的优先级来解决此冲突. PARENTHESIS_OPEN没有出现在任何优先级上，因此Bison退回了默认值，它倾向于移动.

Bison resolves this conflict by comparing the precedence of the reduction (DECREASE) with the precedence of the look-ahead token (PARENTHESIS_OPEN). PARENTHESIS_OPEN does not appear in any precedence level, so Bison falls back on its default, which is to prefer shifting.

很明显，更改减少量的优先级expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE对该冲突的解决没有影响，因为该减少量与该冲突无关.

Evidently, changing the precedence of the reduction expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE has no impact on the resolution of this conflict, because that reduction is not relevant to this conflict.

现在，我的主张是，这种减少与语法中的任何冲突无关.这似乎有点奇怪，因为我看不到太多语法，而且确实是错的.从理论上讲，表中可能还有其他状态，其中包括以下项目:

Now, my claim is that that reduction is not relevant to any conflict in the grammar. That might seem a slightly outlandish claim, since I cannot see much of the grammar, and indeed I could be wrong. In theory, there could be some other state in the table which included the item:

expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE .

，其中还包括一些可能会发生变化的项目，例如

and also included some item in which a shift was possible, such as

some_non_terminal: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE . something

在我看来，这似乎不太可能.

That just doesn't seem likely to me.

通常，后缀运算符的减少(概念上，函数调用和数组索引是后缀运算符)绝不会参与shift-reduce冲突，因为实际上在后缀运算符之后几乎没有可能的移位.如果发生这种变化，运算符将为infix，而不是postfix.您可以想象一个语法，其中的运算符可以是中缀运算符，也可以是后缀运算符，类似于-之类的运算符，可以是中缀或前缀.但是事实证明，这种情况是不对称的，其原因超出了此答案的范围. [注2]

Normally, postfix operator reductions (and function call and array indexing are conceptually postfix operators) never participate in shift-reduce conflicts precisely because there is practically never a possible shift after a postfix operator. If there were such a shift, the operator would be infix, not postfix. You could imagine a grammar in which an operator symbol could be either an infix and a postfix operator, by analogy with operators like - which could be either infix or prefix. But it turns out that the situation is not symmetric for reasons beyond the scope of this answer. [Note 2]

回到最初的问题:我们已经看到移位/减少冲突是在减少 expression: DECREASE expression(在这种情况下)和终端之间PARENTHESIS_OPEN和SQUARE_OPEN，并且无法解决，因为PARENTHESIS_OPEN和SQUARE_OPEN不在您的优先级中列出.所以解决方案是列出它们:

To get back to the original question: We've seen that the shift/reduce conflict is between the reduction expression: DECREASE expression (in this case) and the terminals PARENTHESIS_OPEN and SQUARE_OPEN, and it cannot be resolved because PARENTHESIS_OPEN and SQUARE_OPEN are not listed in your precedence levels. So the solution is to list them:

/* ... */
%left PERCENT STAR SLASH
%precedence TILDE NOT DECREASE INCREASE
%precedence PARENTHESIS_OPEN SQUARE_OPEN

请注意，我将最后一个%left和%right更改为%precedence，这是一个野牛扩展，可让您为关联性无意义的运算符定义优先级.我这样做是因为我认为这更清楚. [注3]

Note that I changed the last %left and %right to %precedence, which is a bison extension which allows you to define a precedence level for operators for which associativity is meaningless. I did that because I think it is clearer. [Note 3]

1. 使用PARENTHESIS_OPEN确实没有什么好说的，而不是更简单，更易读的'('. Yacc和bison允许单字符标记像这样单引号，以使

1. There is really very little good to be said for using PARENTHESIS_OPEN rather than the much simpler and more readable '('. Yacc and bison allow single character tokens to be single-quoted like that precisely to allow for the readability of

expression:  expression '(' expressions ')'
expression:  expression '[' expressions ']'

这也简化了(f)lex扫描器，因为单个后备规则可以处理所有这四个标记，以及所有其他单个字符标记，包括尚未添加到语法中的标记:

That also simplifies your (f)lex scanner, because a single fallback rule can handle all four of those tokens, and all the other single character tokens, including the ones you have yet to add to your grammar:

      /* Put this rule at the end of your ruleset */ 
.    { return *yytext;}

例如，假设！可以是后缀或后缀，并考虑表达式a!-b*4.二进制bang，减号和乘号运算符也具有有效的优先级规则，这使此处的模糊性((a!)-b或a!(-b))变得更加复杂.

For example, suppose that ! could be postfix or infix, and consider the expression a!-b*4. The ambiguity here ((a!)-b or a!(-b)) is compounded by the fact that the binary bang, minus and multiply operators also have active precedence rules.

一元运算符(无论是前缀还是后缀)都没有关联性，因为关联性仅适用于二进制运算符.关联性是为什么a + b + c是(a + b) + c而a = b = c是a = (b = c)的原因.相反，只有一种解析--a或!!a(或其组合)的方法. (如果您考虑优先级关系如何影响移位减少冲突的解决方案，这也很清楚.什么是冲突，需要将一元 reduction ('!' expression .)与! lookahead进行比较对于像'-'这样的双重用途运算符，我们需要将归约的优先级更改为伪终端(%prec UMINUS)，此后很明显，由于UMINUS前瞻符号.

Unary operators, whether prefix or postfix, don't have associativity because associativity only applies to binary operators. Associativity is why a + b + c is (a + b) + c while a = b = c is a = (b = c). In contrast, there is only one way to parse --a or !!a (or combinations thereof). (This is also clear if you think about how precedence relations affect shift-reduce conflict resolutions. What is the conflict which would require a unary reduction ('!' expression .) to be compared with a ! lookahead symbol? In the case of dual-purposed operators like '-', we need to change the precedence of the reduction to a pseudo-terminal (%prec UMINUS), after which it's clear that associativity cannot apply because UMINUS cannot possibly be a lookahead symbol.

这篇关于野牛:奇怪的转变，减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！