解析右结合运算符（指数）

Question

我一直在为我自己的语言编写词法分析器/解析器/解释器，到目前为止一切都在工作。我一直在关注Ruslan Spivak 博客上的示例（每篇文章的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

在解析tokens方面，我使用的方法与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**5parse as5**2给出我25而不是预期的32.

我可以尝试的任何方法？