Shift/Reduce 使用 Python 创建解析器时发生冲突

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

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

我不明白我的语法中怎么会有 shift/reduce 冲突，因为我的规则没有任何部分是模棱两可的。

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]

Shift/Reduce 使用 Python 创建解析器时发生冲突

Shift/Reduce Conflict when making parser with Python

python

parsing

yacc

ply