Shift/reduce 尽管优先规则发生冲突

Question

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

这是我的优先规则的摘录：

%right TOK_ORD
%left  PREC_INDEX PREC_MEMBER

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

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 */ }
         ;

这是来自 bison 输出文件的关于 shift/reduce 冲突的信息：

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，供参考：

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

我不明白为什么会有 shift/reduce 冲突。我的语法明确定义索引和字段访问具有比 ord 更高的优先级，但这似乎还不够。

如果您想知道，是的，这是家庭作业，但作业已经上交并已评分。我正在回过头来尝试解决 shift/reduce 冲突，以便我可以更好地理解发生了什么。

Answer 1

通过比较 production（或减少，如果你愿意）的优先级与 的优先级来解决 shift/reduce 冲突的优先级token（先行标记）。

这个简单的事实有点模糊，因为 bison 根据产生式中最后一个标记的优先级设置产生式的优先级（默认情况下），因此优先级值似乎只分配给标记和优先级比较是在令牌优先级之间进行的。但这并不准确：优先级比较总是在产生式（可能减少）和标记（可能移动）之间进行。

正如野牛手册所说：

…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 产生式的优先级：

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

但这些作品从未参与 shift/reduce 冲突。当到达任一 variable 规则的末尾时，就不可能进行移位。可以减少这些产生式的项目集没有移位动作。

在包含shift/reduce冲突的状态下，冲突在潜在的减少之间：

 expr: TOK_ORD expr

以及涉及前瞻标记 . 和 [ 的可能转变。这些冲突将通过将 TOK_ORD 缩减的优先级分别与前瞻标记 . 和 [ 的优先级进行比较来解决。如果这些标记没有声明优先级，那么 shift/reduce 冲突无法使用优先级机制解决。

不过，在那种情况下，我预计在其他州会有大量 shift/reduce 冲突，其中选项是减少二元运算符（例如 expr: expr '+' expr）或移动 ./[ 以扩展最右边的表达式。所以如果没有这样的 shift/reduce 冲突，解释会更复杂，我需要看更多的语法才能理解它。

Shift/reduce 尽管优先规则发生冲突

Shift/reduce conflict despite precedence rules

parsing

bison

shift-reduce-conflict