在 Happy/Bison 中解决此 Shift/Reduce 冲突

Question

我正在 Happy 中制作一个简单的解析器（Bison 相当于 Haskell），我偶然发现这些规则中存在 shift/reduce 冲突：

ClassBlock :
        "{" ClassAttributes  ClassConstructor ClassFunctions "}" {ClassBlock   }

ClassAttributes :
        {- empty -} { ClassAttributesEmpty }
      | ClassAttributes ClassAttribute {ClassAttributes  }

ClassAttribute :
        "[+]" Variable {ClassAttributePublic  }
      | "[-]" Variable {ClassAttributePrivate  }

ClassFunctions :
        {- empty -} { ClassFunctionsEmpty }
      | ClassFunctions ClassFunction {ClassFunctions  }

ClassFunction :
        "[+]" Function {ClassFunctionPublic }
      | "[-]" Function {ClassFunctionPrivate }

ClassConstructor :
       {- empty -} { ClassConstructorEmpty }
      | TypeFuncParams var_identifier Params Block {ClassConstructor    }

TypeFuncParams :
      Primitive ClosingBracketsNoIdentifier { TypeFuncParamsPrimitive  }
    | class_identifier ClosingBracketsNoIdentifier { TypeFuncParamsClassId  }
    | ListType {TypeFuncParamsList }

信息文件指出 shift/reduce 冲突：

ClassBlock -> "{" ClassAttributes . ClassConstructor ClassFunctions "}"    (rule 52)
    ClassAttributes -> ClassAttributes . ClassAttribute    (rule 54)

    "[+]"          shift, and enter state 85
            (reduce using rule 61)

    "[-]"          shift, and enter state 86
            (reduce using rule 61)

规则 61 是这条：

ClassConstructor :
   {- empty -} { ClassConstructorEmpty }

我不太确定如何解决这个问题。我尝试使用优先规则来消除警告，但没有达到我的预期。

Answer 1

下面是一个简化的语法，它表现出同样的问题。

为了构建它，我删除了

所有操作
来自所有非终端名称的前缀 "Class"

我还简化了大部分规则。我这样做是为了说明如何按照 Whosebug 指南的建议构建 minimal, complete, verifiable example，这样可以更轻松地关注问题，同时仍允许进行实际试验。（我用的是bison，不开心，但是语法很相似。）

Block      : "{" Attributes Constructor Functions "}"
Attributes : {- empty -} | Attributes Attribute
Constructor: {- empty -} | "constructor"
Functions  : {- empty -} | Functions Function
Attribute  : "[+]" "attribute"
Function   : "[+]" "function"

现在，让我们来玩解析器，假设我们已经（以某种方式）识别出可以匹配 Attributes 的前缀。（Attributes 可以匹配空字符串，所以我们可以在输入的开头。）假设下一个标记是 [+].

在这一点上，我们无法判断 [+] 稍后是否会成为 Attribute 的开头，或者它是否是 Function 的开头空 Constructor。但是，为了继续解析，我们需要知道这一点。

如果我们已经完成了属性并即将开始函数，那么此时我们必须减少空的非终结符 Constructor。除非我们现在这样做，否则我们无法继续识别 Function。另一方面，如果我们没有看到最后一个 Attribute 但我们确实减少了一个 Constructor，那么解析最终会失败，因为下一个 Attribute 不能跟在 [=21= 之后] 我们只是减少了。

在这种情况下，通过将选项分解到使用非终端的地方来删除空产生式通常很有用：

Block      : "{" Attributes "constructor" Functions "}"
           | "{" Attributes Functions "}"
Attributes : {- empty -} | Attributes Attribute
Functions  : {- empty -} | Functions Function
Attribute  : "[+]" "attribute"
Function   : "[+]" "function"

但这里仅删除 Constructor 是不够的。为了开始解析函数列表，我们需要先减少一个空的 Functions 来提供 Functions 递归的基本情况，所以我们仍然需要猜测 Functions 从哪里开始为了找到正确的解析。如果我们将这两个列表写成右递归而不是左递归，我们将需要一个空的 Attributes 来终止 Attributes 递归的递归。

在这种特殊情况下，我们可以做的是使用左递归和右递归的巧妙组合：

Block      : "{" Attributes "constructor" Functions "}"
           | "{" Attributes Functions "}"
Attributes : {- empty -} | Attributes Attribute
Functions  : {- empty -} | Function Functions
Attribute  : "[+]" "attribute"
Function   : "[+]" "function"

通过使第一个列表为左递归列表和第二个列表为右递归列表，我们避免了减少两个列表之间的空非终结符的需要。反过来，这允许解析器在看到短语后决定短语是 Attribute 还是 Function，此时不再需要咨询 oracle。

但是，由于多种原因，该解决方案不是很漂亮，其中最重要的是它仅适用于连接两个可选列表。如果我们想添加另一个也可以以 [+] 标记开头的不同类型项目的列表，则需要不同的解决方案..

许多语言都使用的最简单的方法是允许程序员混合各种列表元素。您可能会认为这种风格很糟糕，但并不总是需要通过将其作为语法错误来谴责这种糟糕的风格。

一个简单的解决方案是：

Block      : "{" Things "}"
Things     : {- empty -} | Things Attribute | Things Function | Things Constructor
Attribute  : "[+]" "attribute"
Constructor: "constructor"
Function   : "[+]" "function"

但这并没有限制一个块最多只能有一个构造函数，这似乎是一个语法要求。但是，只要 Constructor 不能以 [+] 开头，您就可以通过以下方式实施 "at most one Constructor" 限制：

Block      : "{" Things Constructor Things "}"
           | "{" Things "}"
Things     : {- empty -} | Things Attribute | Things Function
Attribute  : "[+]" "attribute"
Constructor: "constructor"
Function   : "[+]" "function"

在 Happy/Bison 中解决此 Shift/Reduce 冲突

Solving this Shift/Reduce Conflict in Happy/Bison

haskell

grammar

bison

happy