抛开优先规则，转移/减少冲突

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

shift/reduce冲突的优先级解析是通过比较生成(如果您喜欢，也可以是reduction)与令牌 (forward令牌)的优先级来实现的。

这个简单的事实有点模糊，因为bison根据生产中最后一个令牌的优先级设置生产的优先级(默认情况下)，所以看起来优先级值只被分配给令牌，优先级比较是在令牌优先级之间进行的。但这是不准确的:优先级比较总是在结果(可能被减少)和令牌(可能被移动)之间进行。

正如野牛手册所说:

& help;冲突的解决是通过比较正在考虑的规则的优先级与前瞻规则的优先级令牌。如果令牌的优先级更高，则选择移位。如果规则的优先级更高，则选择reduce。

现在，使用显式声明定义两个variable结果的优先级:

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

但是这些产品从不参与shift/reduce冲突。当variable规则中的任何一个规则结束时，都不可能转移。可以减少这些产量的项集没有移位动作。

在包含shift/reduce冲突的状态下，冲突发生在潜在的reduce之间:

 expr: TOK_ORD expr

和可能的移位涉及前瞻性令牌.和[。这些冲突将通过比较TOK_ORD缩减的优先级与前瞻性令牌.和[的优先级来解决。如果这些令牌没有声明的优先级，那么shift/reduce冲突不能使用优先级机制来解决。

在这种情况下，我希望在其他状态下有大量的shift/reduce冲突，其中的选项是减少二进制操作符(如expr: expr '+' expr)或移动./[以扩展最右边的expr。因此，如果没有这种shift/reduce冲突，解释就会更复杂，我需要看到更多的语法才能理解它。