解析右关联运算符（指数）

Question

我一直在为自己的语言写一个词法分析器/解析器/解释器，到目前为止一直都在工作。我一直在关注Ruslan Spivak's blog上的例子（Github链接到每篇文章）。

我希望扩展我的语言语法，使其超出文章中的内容，包括更多的运算符，如比较（<，>=等）以及指数（**或^，在我的语言中）。我有这个语法：

expression        : exponent ((ADD | SUB) exponent)*
exponent          : term ((POWER) term)*
# this one is right-associative (powers **)

term              : comparison ((MUL | DIV) comparison)*
comparison        : factor ((EQUAl   | L_EQUAL | LESS
                             N_EQUAL | G_EQUAL | GREATER) factor)*
# these are all binary operations



factor            : NUM | STR        | variable
                        | ADD factor | SUB factor
                        | LPAREN expr RPAREN
# different types of 'base' types like integers
# also contains parenthesised expressions which are evalutaed first

在解析令牌方面，我使用与Ruslan博客中使用的方法相同的方法。这是一个将解析exponent行，它处理加法和减法，尽管它的名称，因为语法说表达式被解析为exponent_expr (+ / -) exponent_expr

def exponent(self):
    node = self.term()
    while self.current_token.type in (ADD, SUB):
        token = self.current_token

        if token.type == ADD:
            self.consume_token(ADD)
        elif token.type == SUB:
            self.consume_token(SUB)

        node = BinaryOperation(left_node=node,
                               operator=token,
                               right_node=self.term())

    return node

现在这解析左关联标记就好了（因为标记流自然地左右移动），但我仍然坚持如何解析右关联指数。请查看此预期输入/输出以供参考：

>>> 2 ** 3 ** 2
# should be parsed as...
>>> 2 ** (3 ** 2)
# which is...
>>> 2 ** 9
# which returns...
512

# Mine, at the moment, parses it as...
>>> (2 ** 3) ** 2
# which is...
>>> 8 ** 2
# which returns...
64

为了解决这个问题，我尝试切换BinaryOperation()构造函数的左右节点，使当前节点为右，新节点为左，但这只是使2**5解析为5**2，它给了我25而不是预期的32。

我可以尝试任何方法吗？

Answer 1

你的exponent函数实际上解析expressions的事实应该是一个红旗。事实上，你需要的是一个解析表达式的expression函数和一个解析指数的exponent函数。

你也混淆了取幂和乘法（和其他操作）的优先级，因为2 * x ** 4并不意味着(2 * x) ** 4（这将是16x⁴），而是2 * (x ** 4)。出于同样的原因，x * 3 < 17并不意味着x * (3 < 17)，这就是你的语法将如何解析它。

通常，算术的优先级看起来像这样：

 comparison     <, <=, ==, ... ( lowest precedence)
 additive       +, -
 multiplicative *, /, %
 unary          +, -
 exponentiation **
 atoms          numbers, variables, parenthesized expressions, etc.

（如果你有像函数调用这样的后缀运算符，它们将介于取幂和原子之间。）

一旦你以这种形式重写了你的语法，指数解析器将看起来像这样：

def exponent(self):
    node = self.term()
    while self.current_token.type is POWER:
        self.consume_token(ADD)
        node = BinaryOperation(left_node=node,
                               operator=token,
                               right_node=self.exponent())
    return node

最后的递归调用产生了正确的关联性。在这种情况下，递归是可以接受的，因为左操作数和运算符已被使用。因此递归调用不能产生无限循环。