代码之家 › 专栏 › 技术社区 › Eddtothefullest

解决这种转变/减少快乐/野牛的冲突

happy bison grammar haskell

Eddtothefullest · 技术社区 · 7 年前

我正在Happy中制作一个简单的解析器(Bison相当于Haskell),我偶然发现了这些规则中的移位/减少冲突:

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 }

我真的不知道如何解决这个问题。我尝试使用优先规则来消除警告,但结果并没有达到我的预期。

1 回复 | 直到 7 年前

rici 7 年前

下面是一个简化的语法,它显示了相同的问题。

为了建造它,我删除了

所有操作
所有非终结名的前缀“Class”

我还简化了大部分规则。我这样做是为了说明如何构建 minimal, complete, verifiable example ,正如StackOverflow指南所建议的那样,这使得在仍然允许实际试验的情况下更容易关注问题。(我用的是bison,不是happy,但语法非常相似。)

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

现在,让我们使用解析器,并假设我们(以某种方式)确定了一个可以匹配的前缀 Attributes . ( 属性 可以匹配空字符串,因此我们可以正好位于输入的开头。)假设下一个标记是 [+] .

此时,我们无法判断 [+] 将成为 Attribute 或者如果这是 Function 在一个空的 Constructor . 然而,为了继续解析,我们需要知道这一点。

如果我们已经完成了属性并即将开始函数,那么现在我们必须减少空的非终结符 建造师 . 除非我们现在这样做,否则我们无法继续识别 作用 . 另一方面,如果我们没有看到最后一个 属性 但我们确实减少了 建造师 ,则解析最终将失败,因为下一个 属性 无法遵循 建造师 我们只是减少了。

在这样的情况下,通过将选项分解到使用非终端的地方来删除空产品通常很有用:

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

但只是移除 建造师 这还不够。为了开始解析函数列表,我们需要首先减少一个空 Functions 提供 功能 递归,所以我们仍然需要猜测 功能 开始以找到正确的解析。如果我们将这两个列表写为右递归而不是左递归,那么我们需要一个空的 属性 终止 属性 递归。

在这种特殊情况下,我们可以做的是巧妙地结合使用左递归和右递归:

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

通过使第一个列表左递归,第二个列表右递归,我们避免了减少两个列表之间的空非终结符的需要。这反过来又允许解析器决定一个短语是否是 属性 或a 作用 在它看到这个短语之后,就不再需要咨询甲骨文了。

然而,由于许多原因,该解决方案不是很好,其中最重要的原因是它只适用于两个可选列表的串联。如果我们想添加另一个不同类型项目的列表,也可以从 [+] 令牌,则需要另一种解决方案。。

许多语言使用的最简单的方法是允许程序员混合各种列表元素。您可能会认为这是一种糟糕的样式,但并不总是需要通过将其设置为语法错误来惩罚糟糕的样式。

一个简单的解决方案是:

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

但这并没有将一个块限制为最多一个构造函数,这似乎是一个语法要求。但是,只要 建造师 不能以开头 [+] ,您可以通过以下方式实现“最多一个构造函数”限制:

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