0

我有以下 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，但无济于事。鉴于野牛根据需要解决了冲突（例如，转变而不是减少），这还不错，但我想知道我们如何在不改变公认语言的情况下摆脱冲突。

4

1 回答 1

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"是集合的一部分，在这种情况下，关联性很重要。）

于 2018-05-29T16:58:26.460 回答