[用Python进行解析器时的Shift / Reduce冲突

Question

我已经用sly（https://github.com/dabeaz/sly/）编写了一个解析器，但是它无缘无故地有两个shift / reduce冲突。我应该如何解决？

parser.py

@_("NAME ASSIGN primary")
    def statement(self, p):
        self.variables[p[0]] = p[2]

    @_("primary")
    def statement(self, p):
        return p[0]



    @_("primary PLUS secundary")
    def primary(self, p):
        return p[0] + p[2]

    @_("primary MINUS secundary")
    def primary(self, p):
        return p[0] - p[2]

    @_("secundary")
    def primary(self, p):
        return p[0]





    @_("secundary MULTIPLY tertiary")
    def secundary(self, p):
        return p[0] * p[2]

    @_("secundary FLOORDIV tertiary")
    def secundary(self, p):      
        return p[0] // p[2] 

    @_("secundary DIVIDE tertiary")
    def secundary(self, p):
        return p[0] / p[2]

    @_("secundary MOD tertiary")
    def secundary(self, p):
        return p[0] % p[2]

    @_("tertiary")
    def secundary(self, p):
        return p[0]




    @_("quaternary POWER tertiary")
    def tertiary(self, p):
        return p[0] ** p[2]

    @_("quaternary")
    def tertiary(self, p):
        return p[0]



    @_("tertiary quinary")   
    def quaternary(self, p):      
        return p[0] * p[1]

    @_("quinary")
    def quaternary(self, p):
        return p[0]




    @_("INTEGER")
    def quinary(self, p):
        return p[0]

    @_("LPAREN primary RPAREN")
    def quinary(self, p):
        return p[1]

debug.out

state 27

    (12) tertiary -> quaternary POWER tertiary .
    (14) quaternary -> tertiary . quinary
    (15) quinary -> . LPAREN primary RPAREN
    (16) quinary -> . INTEGER
  ! shift/reduce conflict for LPAREN resolved as shift
  ! shift/reduce conflict for INTEGER resolved as shift
    MOD             reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    DIVIDE          reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    FLOORDIV        reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    MULTIPLY        reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    MINUS           reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    PLUS            reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    $end            reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    RPAREN          reduce using rule 12 (tertiary -> quaternary POWER tertiary .)
    LPAREN          shift and go to state 8
    INTEGER         shift and go to state 9

    quinary                        shift and go to state 17

我只添加了调试文件的一部分，但是整个语法，因为我认为其他语法都不相关，请告诉我是否应该发布更多代码。

我不了解语法中如何有任何移位/减少冲突的地方，因为我的规则没有任何部分是模棱两可的。

Answer 1

您的语法肯定是模棱两可的，因为可以将1 POWER 2 3解析为(1 POWER 2) * 3或1 POWER (2 * 3)。为了修正语法，您需要确定这两种解释中的哪一种是您想要的，然后更改语法以仅允许正确的解释。

据我所知，关于隐式乘法运算符的优先级尚未达成共识。许多人认为它应具有与显式乘法完全相同的优先级和关联性。其他人则认为2a/7b应该解释为(2*a)/(7*b)，而不是((2*a)/7)*b，这导致了隐式乘法应该更紧密地绑定的想法。

引入幂运算后，事情变得更加复杂。在数学中，通常使用印刷效果以二维方式写指数。这使得指数的分组变得明确。在其他情况下，幂运算绑定更紧密（甚至比一元否定更紧密）的约定没有问题，我们有：

• （1）a2b => a * (2 POWER b)
• （2）a2b => a POWER (2 * b)。
• （（3）a2b => (a POWER 2) * b。

没有通过将指数写为上标而提供的隐式分组，以上最后两个示例将变得难以区分。如果指数运算符为^，则它们都将被写为a^2b，并且解析器将需要确定将两种可能的解释中的哪一种分配给字符串。

[将非括号表达式a2^b和a^2b解析为（1）和（2）的问题是优先顺序不同：在情况（1）中，我们的幂运算优先，而在实现情况（2）时）隐式乘法必须优先。我相信这就是您的语法正在尝试做的事情，并且它之所以失败，恰恰是因为这种形式的优先级反转非常棘手（通常会导致歧义）。将a^2b解释为（3）更为简单，因为优先顺序相同。

因此，我建议您接受解释（3）。语言设计的一项重要原则是，计算机难以消除歧义的事物通常也难以被人类消除歧义，因此通常最好避免使用困难的歧义消除规则。 （作为一个激励性的示例，请参见C ++中的所谓Most Vexing Parse。或者常见错误，这是许多C和C ++编译器发出警告的提示，建议在诸如a << n + 1之类的完美合法表达式中使用括号。）

---

解释（3）的实现非常简单，因为它只需要优先级组的通常级联：

# This version makes implicit multiplication bind more tightly
# than division. Otherwise, implicit multiplication would just be
# added to secondary.
@_("tertiary quaternary")   
def tertiary(self, p):      
    return p[0] * p[1]

@_("quaternary")
def tertiary(self, p):
    return p[0]

@_("quinary POWER quaternary"
def quaternary(self, p):
    return p[0] ** p[2]

@_("quinary")
def quaternary(self, p):
    return p[0]