使用空格分隔的表达式列表 + if/then/else 解决野牛语法中的冲突

Question

我有以下yacc/bison/happy语法：

%token 
if              TokenIf
then            TokenThen
else            TokenElse
true            TokenTrue
false           TokenFalse
%left APP
%right IF
%%
Hungry
: NoHungry
| Hungry NoHungry %prec APP
| if Hungry then Hungry else Hungry %prec IF
NoHungry
: true
| false

bison -v告诉我，在以下情况下有两个冲突：

State 12
2 Hungry: Hungry . NoHungry
3       | if Hungry then Hungry else Hungry .
true   shift, and go to state 2
false  shift, and go to state 3
true      [reduce using rule 3 (Hungry)]
false     [reduce using rule 3 (Hungry)]
$default  reduce using rule 3 (Hungry)
NoHungry  go to state 8

我试图通过%prec给出明确的优先声明来解决冲突，但无济于事。鉴于野牛按照想要的方式解决冲突(例如转移而不是减少(，这还不错，但我想知道我们如何在不改变公认的语言的情况下摆脱冲突。

Answer 1

从野牛报告中可以看出，冲突与终端true和false，它们未列在优先级关系中。因此，优先规则不适用于这些冲突。

回想一下，在生产和终端之间定义了优先关系。它不涉及两个终端或两个产品(因此不能用于解决减少-减少冲突(。可以减少的生产优先级与前瞻终端之间的比较决定了是减少还是转移。为了符号方便，作品由终端名称表示，通常是生产中唯一的终端;这对应于一个常见的用例，但有时会令人困惑。特别是，%prec声明只是用来给规则一个名称，以便在优先声明中使用，最好以这种方式考虑它，而不是作为"明确"声明来考虑。

简而言之，可以通过在优先级关系中显式添加适当的终端来解决问题中简化语法中的冲突：

%precedence "if"
%precedence "true" "false"
%%
Hungry
: NoHungry
| Hungry NoHungry
| "if" Hungry "then" Hungry "else" Hungry %prec "if"
NoHungry
: "true"
| "false"

摘自-v输出：

State 12
2 Hungry: Hungry . NoHungry
3       | "if" Hungry "then" Hungry "else" Hungry .
"true"   shift, and go to state 2
"false"  shift, and go to state 3
$default  reduce using rule 3 (Hungry)
NoHungry  go to state 8

通过使用-r solved而不是-v，您可以更明确地查看分辨率：

Conflict between rule 3 and token "true" resolved as shift ("if" < "true").
Conflict between rule 3 and token "false" resolved as shift ("if" < "false").

我本可以使用"else"作为if生产的名称，如果没有%prec声明，这将是默认值，但"if"似乎更直观。

%precedence声明(在最近的野牛版本中可用(并不意味着左结合性或右结合性;在这种情况下，结合性不适用，因为不存在冲突涉及同等优先权的生产和终端的情况。如果 Happy 没有实现它，%left或%right都可以出于同样的原因使用(关联性无关紧要(，但我认为%precedence更好地记录情况。

由于这无疑是一个简化的示例，因此值得注意的是，更完整的语法需要一些语法分析。特别是，优先级大于"if"的终端列表必须包括FIRST(NoHungry)中的所有终端，并且bison不提供自动工具来执行该计算，尽管您通常可以从shift-reduce冲突报告中提取列表。(甚至可能是"if"是集合的一部分，在这种情况下，结合性很重要。