parsing - 为什么 %prec 在这个 Bison 语法中没有效果？

Question

考虑以下 Bison 语法(这是从我正在研究的一个更大的语法中剥离出来的):

%token ident
%left '+'
%left CALLPREC

%%

start: add ';' ;
expr: ident | call |  add ;
call: expr '(' ')' %prec CALLPREC ;
add: expr '+' expr ;

在解析 foo + bar() 之类的表达式时，显然没有优先级存在 s/r 冲突。我试图理解为什么 %prec 声明不能解决该冲突。我用的是 Bison 3.0.2，好像觉得指令没用:

$ bison -r state,solved -Wall  ambigram.y 
ambigram.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
ambigram.y:5.1-5: warning: useless precedence and associativity for CALLPREC [-Wprecedence]

奇怪的是，消除 %prec CALLPREC 并声明 %left '(' 解决了冲突，但声明 %left ')' 可以不是。这与我对 Bison 文档的期望相反，它说 [by] default, the precedence of a rule is that of its last token .

Answer 1

移位/减少冲突的 Bison 优先级解决方案通过在 token 和规则上设置优先级来实现。当它发现 shift/reduce 冲突时，bison 会比较要减少的规则的优先级和要移动的 token 的优先级，并选择优先级较高的一个。 %prec 指令只是设置规则的优先级；它对 token 的优先级没有影响。

你的语法中的冲突(歧义)来自像这样的输入

ident '+' ident '(' ')'

它可以被解析为第二个操作数是调用的添加，或者被调用的 expr 是添加的调用。它在 shift/reduce 解析器中表现为 shift/reduce 冲突在减少 add 规则和在看到 expr + expr 输入之后移动 '(' 标记之间。因此，重要的是优先级add 规则和 '(' 标记的优先级 - call 规则的优先级不相关，因为尚未识别调用。

在您的情况下，您会收到第二个警告，因为调用规则的明确设置的优先级永远不会用于解决任何冲突。

我玩弄过编写一个 yacc 变体的想法，该变体将以更符合大多数人直觉的方式处理优先级。它不会在 token 上具有优先权，而是在规则上具有优先权only。当发生移位/减少冲突时，它会将要减少的规则的优先级与移位 token 后可以减少的规则的优先级进行比较。这可能无法解决冲突(如果转变导致可以减少的多个规则，一些优先级更高，一些优先级更低)，但通常会更加灵活，并且不太可能通过以意想不到的方式解决冲突而给人们带来麻烦。