尽管有优先权规则，但仍可转移/减少冲突 [英] Shift/reduce conflict despite precedence rules

问题描述

我正在为其编写解析器的语言具有三种与此处相关的构造:由TOK_ORD表示的ord运算符，它将字符表达式转换为整数表达式，以及[ ]和，分别用于索引和字段访问，就像在C中一样.

The language I'm writing a parser for has three constructs that are relevant here: the ord operator, represented by TOK_ORD, which casts character expressions into integer expressions, and [ ] and ., which are used for index and field access, respectively, just like in C.

这是我的优先规则摘录:

Here's an excerpt from my precedence rules:

%right TOK_ORD
%left  PREC_INDEX PREC_MEMBER

我的语法有一个非终结符expr，它表示表达式.这是语法中的一些相关片段(TOK_IDENT是我的.l文件中定义的标识符的正则表达式):

My grammar has a nonterminal expr, which represents expressions. Here's some relevant snippets from the grammar (TOK_IDENT is a regular expression for identifiers defined in my .l file):

expr     : TOK_ORD expr                         { /* semantic actions */ }
         | variable                             { /* semantic actions */ }
         ;
variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }
         ;

以下是野牛输出文件中有关移位/减少冲突的信息:

Here's information about the shift/reduce conflict from the bison output file:

state 61

42 expr: expr . '=' expr
43     | expr . TOK_EQ expr
44     | expr . TOK_NE expr
45     | expr . TOK_LT expr
46     | expr . TOK_LE expr
47     | expr . TOK_GT expr
48     | expr . TOK_GE expr
49     | expr . '+' expr
50     | expr . '-' expr
51     | expr . '*' expr
52     | expr . '/' expr
53     | expr . '%' expr
57     | TOK_ORD expr .
72 variable: expr . '[' expr ']'
73         | expr . '.' TOK_IDENT

'['  shift, and go to state 92
'.'  shift, and go to state 93

'['       [reduce using rule 57 (expr)]
'.'       [reduce using rule 57 (expr)]
$default  reduce using rule 57 (expr)

状态92和93，以供参考:

States 92 and 93, for reference:

state 92

72 variable: expr '[' . expr ']'

TOK_FALSE      shift, and go to state 14
TOK_TRUE       shift, and go to state 15
TOK_NULL       shift, and go to state 16
TOK_NEW        shift, and go to state 17
TOK_IDENT      shift, and go to state 53
TOK_INTCON     shift, and go to state 19
TOK_CHARCON    shift, and go to state 20
TOK_STRINGCON  shift, and go to state 21
TOK_ORD        shift, and go to state 22
TOK_CHR        shift, and go to state 23
'+'            shift, and go to state 24
'-'            shift, and go to state 25
'!'            shift, and go to state 26
'('            shift, and go to state 29

expr       go to state 125
allocator  go to state 44
call       go to state 45
callargs   go to state 46
variable   go to state 47
constant   go to state 48


state 93

73 variable: expr '.' . TOK_IDENT

我不明白为什么会有班次/减少冲突.我的语法清楚地定义了索引和字段访问的优先级比ord高，但这似乎还不够.

I don't understand why there is a shift/reduce conflict. My grammar clearly defines index and field access to have higher precedence than ord, but that doesn't seem to be enough.

如果您想知道，是的，这是家庭作业，但是作业已经上交并评分了.我正在重新尝试并尝试解决班次/减少冲突，以便我可以更好地了解正在发生的事情.

In case you're wondering, yes, this is homework, but the assignment has already been turned in and graded. I'm going back through and trying to fix shift/reduce conflicts so I can better understand what's going on.

推荐答案

通过将生产的优先级(或简化，如果您愿意)与优先级进行比较，可以解决移位/减少冲突的优先级令牌(超前令牌)的标记.

Precedence resolution of shift/reduce conflicts works by comparing the precedence of a production (or reduction, if you prefer) with the precedence of a token (the lookahead token).

这个简单的事实有些模糊，因为bison会根据生产中最后一个标记的优先级来设置生产的优先级(默认情况下)，因此看来优先级值仅分配给了标记，并且优先级比较为标记优先级之间.但这是不准确的:优先级比较总是在生产(可能会减少)和令牌(可能会转移)之间进行.

This simple fact is slightly obscured because bison sets the precedence of a production based on the precedence of the last token in the production (by default), so it appears that precedence values are only being assigned to tokens and the precedence comparison is between token precedences. But that's not accurate: the precedence comparison is always between a production (which might be reduced) and a token (which might be shifted).

如野牛手册所述:

…解决冲突的方法是比较 与先行规则一起考虑的规则的优先级 令牌.如果令牌的优先级较高，则选择转移. 如果规则的优先级较高，则选择减少.

…the resolution of conflicts works by comparing the precedence of the rule being considered with that of the lookahead token. If the token's precedence is higher, the choice is to shift. If the rule's precedence is higher, the choice is to reduce.

现在，您使用显式声明定义两个variable产生式的优先级:

Now, you define the precedence of the two variable productions using explicit declarations:

variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }

但是这些作品从未参与过转变/减少冲突.当variable规则中的任何一个结束时，都不会移动.可以减少这些产量的项目集没有班次动作.

But those productions never participate in shift/reduce conflicts. When the end of either of the variable rules is reached, there is no possibility of shifting. The itemsets in which those productions can be reduced have no shift actions.

在包含转移/减少冲突的状态下，冲突发生在电位降低之间:

In the state which contains the shift/reduce conflict, the conflict is between the potential reduction:

 expr: TOK_ORD expr

以及涉及超前标记.和[的可能转移.通过分别将TOK_ORD减少的优先级与先行标记.和[的优先级进行比较，可以解决这些冲突.如果这些标记没有声明的优先级，则无法使用优先级机制解决移位/减少冲突.

and the possible shifts involving lookahead tokens . and [. These conflicts will be resolved by comparing the precedence of the TOK_ORD reduction with the precedences of the lookahead tokens . and [, respectively. If those tokens do not have declared precedences, then the shift/reduce conflict cannot be resolved using the precedence mechanism.

但是，在那种情况下，我希望在其他状态下会有大量的移位/减少冲突，其中的选择是减少二进制运算符(例如expr: expr '+' expr)或移位. /[扩展最右边的expr.因此，如果没有这种移位/减少冲突，则说明会更加复杂，我需要看更多的语法来理解它.

In that case, though, I would expect there to be a large number of shift/reduce conflicts in other states, where the options are to reduce a binary operator (such as expr: expr '+' expr) or to shift the ./[ to extend the rightmost expr. So if there are no such shift/reduce conflicts, the explanation is more complicated and I'd need to see a lot more of the grammar to understand it.

这篇关于尽管有优先权规则，但仍可转移/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！