代码之家 › 专栏 › 技术社区 › Alkis Mavridis

野牛:奇怪的转变减少冲突

operator-precedence bison

Alkis Mavridis · 技术社区 · 6 年前

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

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

请注意,点具有最高优先级。所以,我试着把这个给我的函数调用规则。不过,我得到74个换档/减速警告,所有警告都遵循以下模式:

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应该尝试移动,直到它与那个规则匹配。尽管如此,前缀减少操作符看起来像是野牛的选择,即使它的优先级较低。

为什么是野牛?我怎样才能清楚地告诉比森函数调用规则应该具有更高的优先级,从而避免冲突?

1 回复 | 直到 6 年前

rici 6 年前

以下引自 this answer 以下内容:

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

A %prec 声明(re-)定义减少它是的一部分。就你而言,

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

声明这两个缩减都具有 DOT ,而不是 PARENTHESIS_CLOSE 和 SQUARE_CLOSE [注1]。因为后两个令牌没有出现在 %left / %right 声明,这实际上是优先级的定义,但由于两个原因,这是不必要的:

你可以添加 括号关闭 和 方块字“关闭” 到适当的优先级别,但更重要的是
这两项削减不参与任何转移/减少冲突。

你应该试着理解(并希望同意)我在第(2)项中的主张。作为一个开始的地方,考虑一下25号州,你已经把它包括在你的问题中了。在国家25中,唯一可能的减少是根据规则53( expression: DECREASE expression )。您可以看到,因为这是状态中唯一具有 . 在右手边。只有在右边缘有点的项目可以减少(因为点在右边缘表示与该项目对应的生产可能在此状态下完成),并且,实际上,您可以看到针对此状态报告的移位/减少冲突:

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如果 ( 是lookahead字符,语法允许

改变 ( ,导致项目的状态 expression: expression PARENTHESIS_OPEN . expressions PARENTHESIS_CLOSE (注意圆点是如何移动到 PARENTHESIS_OPEN 令牌)。
或者规则的简化 表达式:减少表达式 .

野牛通过比较减少 ( DECREASE )具有先行标记的优先级( 括号开 )。 括号开 不会出现在任何优先级别中,所以bison会回到默认状态,这是更倾向于移位。

显然,改变了约简的优先顺序 expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE 对解决这一冲突没有影响,因为减少与这一冲突无关。

现在,我的主张是减少与任何语法冲突。这似乎有点奇怪,因为我看不到太多的语法,实际上我可能是错的。理论上,表中可能还有其他状态,其中包括项目:

expression: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE .

还包括一些可能发生转变的项目,例如

some_non_terminal: expression PARENTHESIS_OPEN expressions PARENTHESIS_CLOSE . something

对我来说这似乎不太可能。

通常,后缀操作符减少(函数调用和数组索引在概念上是后缀操作符)从不参与移位减少冲突,因为后缀操作符之后几乎没有可能的移位。如果有这样的移位,操作符将是中缀,而不是后缀。你可以想象一种语法,在这种语法中,运算符符号可以是中缀运算符和后缀运算符,类似于 - 可以是中缀或前缀。但事实证明,由于超出这个答案范围的原因,情况是不对称的。[注2]

回到最初的问题:我们已经看到,转移/减少冲突是在减少 表达式:减少表达式 (在本例中)和终端 括号开 和 SQUARE_OPEN 无法解决,因为 括号开 和 方块字\开 在优先级别中没有列出。因此,解决方案是列出它们:

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

注意我改变了最后一个 %left 和 %right 到 %precedence ,这是一个bison扩展,允许您为关联性毫无意义的运算符定义优先级。我这么做是因为我觉得这更清楚。[注3]

笔记

真的没有什么好用的。 括号开 而不是更简单更易读的 '(' .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 (或其组合)。(如果您考虑优先关系如何影响班次,这一点也很清楚,可以减少冲突解决。需要一元的冲突是什么? 减少 ( '!' expression . )与…相比 ! 先行标志?在双重目的的情况下,如 '-' ,我们需要将约简的优先级更改为伪终端。( %prec UMINUS )之后很明显,关联性不能应用,因为 UMINUS 不能是先行符号。