用空格分隔的表达式列表+ if/then/else解决野牛语法中的冲突 [英] Resolve conflict in bison grammar with space separated expression lists + if/then/else

问题描述

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

I have the following yacc/bison/happy grammar:

%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告诉我在以下情况下有两个冲突:

bison -v tells me there are two conflicts in the following situation:

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给出明确的优先级声明来解决冲突，但无济于事.鉴于野牛可以根据需要解决冲突(例如，转移而不是减少)，这还不错，但是我想知道如何在不更改可接受语言的情况下摆脱冲突.

I tried to resolve the conflict by giving explicit precedence declaration with %prec, but to no avail. Given that bison resolves the conflict as wanted (e.g. shifts rather than reduces), this is not so bad, but I wonder how we can get rid of the conflict without changing the accepted language.

推荐答案

从野牛报告中可以看到，冲突与端子true和false发生，它们没有在优先级关系中列出.因此，优先规则不适用于这些冲突.

As you can see from the bison report, the conflicts are with the terminals true and false, which are not listed in the precedence relations. Consequently, the precedence rules do not apply to these conflicts.

回想一下，在产品和终端之间定义了优先级关系.它既不涉及两个终端，也不涉及两个产品(因此不能用于解决减少-减少冲突).可以减少的生产优先级与超前的终端之间的比较确定是减少还是转移.为了符号上的方便，产品以终端的名称表示，通常是产品中唯一的终端；这对应于一个普通的用例，但有时会造成混淆.尤其是，%prec声明仅用于为规则指定优先级声明中使用的名称，以这种方式考虑它可能比将其作为显式"声明更好.

Recall that a precedence relation is defined between a production and a terminal. It does not relate two terminals nor two productions (and so cannot be used to resolve reduce-reduce conflicts). The comparison between precedence of the production which could be reduced and the lookahead terminal determines whether a reduce or a shift will occur. For notational convenience, productions are represented by the name of a terminal, usually the only terminal in the production; this corresponds to a common use case but it is sometimes confusing. In particular, the %prec declaration only serves to give a rule a name for use in precedence declarations, and it is probably better to think about it in that way rather than as an "explicit" declaration.

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

In short, the conflict in the simplified grammar in your question can be resolved by explicitly adding the appropriate terminals into the precedence relations:

%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，您可以更明确地看到分辨率:

By using -r solved instead of -v, you can see the resolution more explicitly:

    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"似乎更直观.

I could have used "else" as the name for the if production, which would have been the default without the %prec declaration, but "if" seems more intuitive.

%precedence声明(在最新的野牛版本中可用)并不暗示左或右关联.在这种情况下，不存在关联性，因为在任何情况下，冲突都不会涉及具有相同优先级的产生和终止.如果Happy不实现它，出于相同的原因(关联性无关)，可以使用%left或%right，但是我认为%precedence可以更好地记录这种情况.

The %precedence declaration (available in recent bison versions) does not imply either left or right associativity; in this case, associativity does not apply because there is no case in which a conflict involves a production and terminal of equal precedence. If Happy does not implement it, either %left or %right could be used for the same reason (associativity is irrelevant) but I think %precedence better documents the situation.

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

Since this is undoubtedly a reduced example, it's worth noting that a more complete grammar would require some grammar analysis. In particular, the list of terminals with precedence greater than "if" would have to include all terminals in FIRST(NoHungry), and bison does not provide an automatic tool to perform that computation, although you can usually extract the list from the shift-reduce conflict reports. (It could even be that "if" is part of the set, in which case associativity would matter.)

这篇关于用空格分隔的表达式列表+ if/then/else解决野牛语法中的冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！