使用 space 分隔的表达式列表 + if/then/else 解决 bison 语法中的冲突

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 给出明确的优先级声明来解决冲突，但无济于事。鉴于 bison 按需要解决冲突（例如移位而不是减少），这还不错，但我想知道我们如何在不改变接受的语言的情况下摆脱冲突。

Answer 1

从bison报告中可以看出，冲突的终端true和false，并没有列在优先级关系中。因此，优先规则不适用于这些冲突。

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

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

%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 声明（在最近的 bison 版本中可用）并不意味着左结合性或右结合性；在这种情况下，结合性不适用，因为不存在冲突涉及同等优先级的产生式和终止符的情况。如果 Happy 没有实现它，出于同样的原因，可以使用 %left 或 %right（关联性无关紧要），但我认为 %precedence 更好地记录了这种情况。

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

使用 space 分隔的表达式列表 + if/then/else 解决 bison 语法中的冲突

Resolve conflict in bison grammar with space separated expression lists + if/then/else

yacc

bison

parser-generator

shift-reduce-conflict

happy