为什么％prec在此野牛语法中没有效果?

本文介绍了为什么％prec在此野牛语法中没有效果?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

考虑以下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文档的期望相反，Bison文档说(默认情况下)，规则的优先级是其最后一个标记的优先级.

解决方案

通过对 令牌和规则都具有优先级，可以有效地解决移位/减少冲突的野牛优先级.当发现移位/减少冲突时，野牛会比较要减少的规则的优先级和要移位的令牌的优先级，并选择较高的优先级. %prec指令仅设置规则的优先级；它对令牌的优先级没有影响.

语法中的冲突(歧义)来自类似

的输入

ident '+' ident '(' ')'

可以解析为第二个操作数为调用的add，也可以解析为被调用的expr为添加的call.它在shift/reduce解析器中显示为shift/reduce冲突 减少add规则和在看到expr + expr输入后移动'('令牌之间的关系.因此，重要的是add规则的优先级和'('令牌-call规则的优先级是无关紧要的，因为尚未识别出呼叫.

在您的情况下，您会收到第二条警告，因为调用规则的显式设置优先级从未用于解决任何冲突.

我想到了编写yacc变体的想法，该变体将以更符合大多数人的直觉的方式处理优先级.代替优先于令牌，它将优先于规则 .当发生移位/减少冲突时，它将比较要减少的规则的优先级和移位令牌后可以减少的规则的优先级.这可能无法解决冲突(如果这种转变导致可以减少多个规则，则优先级更高，而某些规则则更低)，但通常更灵活，并且不太可能通过以意想不到的方式解决冲突而给人们带来麻烦. >

Consider the following Bison grammar (this is stripped down from a much larger grammar I'm working on):

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

Obviously without precedence there's a s/r conflict when parsing an expression like foo + bar(). I'm trying to understand why the %prec declaration doesn't resolve that conflict. I'm using Bison 3.0.2, which seems to think the directive is useless:

$ 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]

Oddly, eliminating the %prec CALLPREC and declaring %left '(' resolves the conflict, but declaring %left ')' does not. This is the opposite of what I'd expect from the Bison docs, which say that [by] default, the precedence of a rule is that of its last token.

解决方案

Bison precedence resolution of shift/reduce conflicts works by having precedence level on both tokens and rules. When it finds a shift/reduce conflict, bison compares the precedence of the rule to be reduced and the precedence of the token to be shifted and chooses the higher precedence one. A %prec directive just sets the precedence of a rule; it has no effect on the precedence of tokens.

The conflict (ambiguity) in your grammar comes from input like

ident '+' ident '(' ')'

which can be parsed as either an add where the second operand is a call, or as a call where the called expr is an add. It manifests in a shift/reduce parser as a shift/reduce conflict between reducing the add rule and shifting a '(' token after seeing an expr + expr input. As such, all that matters is the precedence of the add rule and the '(' token -- the precedence of the call rule is irrelevant as a call has not yet been recognized.

You get the second warning in your case as the explicitly set precedence of the call rule is never used to resolve any conflicts.

I've toyed with the idea of writing a yacc variant that would handle precedence in a way more in line with most people's intuition. Instead of having precedence on tokens, it would have predecence only on rules. When a shift/reduce conflict ocurred, it would compare the precedence of the rule to be reduced with the precedences of rules that could be reduced after shifting the token. This might not resolve the conflict (if the shift leads to multiple rules that could be reduced, some higher precedence and some lower), but would generally be more flexible and less likely to get people in trouble by resolving conflicts in unexpected ways.