1

我在 Happy（Haskell 的 Bison 等价物）中制作了一个简单的解析器，我偶然发现了这些规则中的 shift/reduce 冲突：

ClassBlock :
        "{" ClassAttributes  ClassConstructor ClassFunctions "}" {ClassBlock $2 $3 $4}

ClassAttributes :
        {- empty -} { ClassAttributesEmpty }
      | ClassAttributes ClassAttribute {ClassAttributes $1 $2}

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

ClassFunctions :
        {- empty -} { ClassFunctionsEmpty }
      | ClassFunctions ClassFunction {ClassFunctions $1 $2}

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

ClassConstructor :
       {- empty -} { ClassConstructorEmpty }
      | TypeFuncParams var_identifier Params Block {ClassConstructor $1 $2 $3 $4}

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

信息文件说明了移位/减少冲突：

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 }

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

4

1 回答 1

4

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

为了构建它，我删除了

  • 所有动作
  • 所有非终结符名称的前缀“Class”

我还简化了大部分规则。我这样做是为了说明如何构建一个最小的、完整的、可验证的示例，正​​如 StackOverflow 指南所建议的那样，这使得在仍然允许实际试验的同时更容易专注于问题。（我用过野牛，不开心，但语法很相似。）

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

现在，让我们玩解析器，并假设我们（不知何故）确定了一个可以匹配的前缀Attributes。（Attributes可以匹配空字符串，所以我们可以在输入的开头。）假设下一个标记是[+].

在这一点上，我们无法判断[+]will 后来是否是 an 的开头，Attribute或者它是否是Function一个 empty之后的 a 的开头Constructor。但是，我们需要知道这一点才能继续解析。

如果我们已经完成了 Attributes 并即将开始使用 Functions，那么这就是我们必须减少空 nonterminal 的时刻Constructor。除非我们现在这样做，否则我们无法继续识别Function. 另一方面，如果我们没有看到最后一个Attribute但我们确实减少了 a Constructor，那么解析最终将失败，因为下一个Attribute不能跟随Constructor我们刚刚减少的。

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

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"

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

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

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

一个简单的解决方案是：

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

但这并没有将 Block 限制为最多一个 Constructor，这似乎是一种语法要求。但是，只要Constructor不能以 a 开头[+]，您就可以通过以下方式实现“最多一个构造函数”限制：

Block      : "{" Things Constructor Things "}"
           | "{" Things "}"
Things     : {- empty -} | Things Attribute | Things Function
Attribute  : "[+]" "attribute"
Constructor: "constructor"
Function   : "[+]" "function"
于 2018-02-14T23:06:24.997 回答