从零开始写个简单的解释器（5）

原文：Let’s Build A Simple Interpreter. Part 5.

译文：

理解如何创建解释器或编译器是一个复杂的过程。最初，这可能像是一团需要解开的乱线团，需要一步步将它整理成一个完美的球。

实现这一目标的方法是一步步解开每一根线、每一个结。有时候，你可能觉得自己一时理解不了，但只要坚持下去，最终会“豁然开朗”。相信我，如果每次我理解不了的时候都能存25美分，我早就成了富翁 :）。

我能给你在理解如何创建解释器和编译器方面最好的建议是：阅读文章中的解释，阅读代码，然后自己写代码，甚至在一段时间内多次写同样的代码，使材料和代码对你来说变得自然，再继续学习新内容。不要急，慢慢来，花时间深刻理解基本概念。这种方法看似慢，但最终会有回报。

最终，你会得到一个完美的线团。即使它不那么完美，也比不做任何事情、不学习这一主题或者快速浏览后几天就忘记要好得多。

记住，只需继续解开每一根线、每一个结，并通过写大量代码来练习你所学到的知识。

今天你将利用前几篇文章中学到的所有知识，学习如何解析和解释包含任意数量加法、减法、乘法和除法运算符的算术表达式。你将编写一个解释器，能够评估像“14 + 2 * 3 - 6 / 2”这样的表达式。

结合性和优先级

在编写代码之前，我们先来讨论一下运算符的结合性和优先级。

按照惯例，7 + 3 + 1 与 (7 + 3) + 1 相同，而 7 - 3 - 1 等价于 (7 - 3) - 1。这没有什么意外。我们都在某个时候学到了这一点，并从那时起就理所当然了。如果我们把 7 - 3 - 1 看作 7 - (3 - 1)，结果将是意外的 5，而不是预期的 3。

在普通算术和大多数编程语言中，加法、减法、乘法和除法是左结合的：

7 + 3 + 1 等价于 (7 + 3) + 1
7 - 3 - 1 等价于 (7 - 3) - 1
8 * 4 * 2 等价于 (8 * 4) * 2
8 / 4 / 2 等价于 (8 / 4) / 2

运算符左结合是什么意思？

当像 7 + 3 + 1 这样的表达式中，3 的两边都有加号时，我们需要一个约定来决定哪个运算符作用于 3。是左边的还是右边的运算符？运算符 + 是左结合的，因为有加号两边的操作数属于左边的运算符，所以我们说运算符 + 是左结合的。这就是为什么根据结合性约定，7 + 3 + 1 等价于 (7 + 3) + 1。

好的，那么像 7 + 5 * 2 这样的表达式呢？我们在操作数 5 的两边有不同种类的运算符。这个表达式是等价于 7 + (5 * 2) 还是 (7 + 5) * 2？我们如何解决这种歧义？

在这种情况下，结合性约定对我们没有帮助，因为它只适用于一种类型的运算符，无论是加法（+，-）还是乘法（*，/）。我们需要另一个约定来解决当表达式中有不同种类的运算符时的歧义。我们需要一个定义运算符相对优先级的约定。

我们说，如果运算符 * 比 + 更先作用于其操作数，那么它具有更高的优先级。在我们知道和使用的算术中，乘法和除法的优先级高于加法和减法。因此，表达式 7 + 5 * 2 等价于 7 + (5 * 2)，而表达式 7 - 8 / 4 等价于 7 - (8 / 4)。

在具有相同优先级的运算符的表达式中，我们只需使用结合性约定，从左到右执行运算符：

1
2
3

7 + 3 - 1 等价于 (7 + 3) - 1
8 / 4 * 2 等价于 (8 / 4) * 2

语法构建

关于这些约定的好处是，我们可以从一个显示运算符结合性和优先级的表格中构建算术表达式的语法。然后，我们可以按照我在第4部分中概述的指南将语法翻译成代码，我们的解释器将能够处理运算符的优先级和结合性。

好了，这是我们的优先级表：

从表中可以看出，运算符 + 和 - 具有相同的优先级，并且都是左结合的。你还可以看到，运算符 * 和 / 也是左结合的，它们之间的优先级相同，但高于加法和减法运算符。

下面是从优先级表构建语法的规则：

为每个优先级级别定义一个非终结符。非终结符的产生式体应包含该级别的运算符和下一个更高优先级级别的非终结符。
为基本表达式单元创建一个附加的非终结符，在我们的例子中是整数。一般规则是，如果有 N 个优先级级别，你将需要总共 N + 1 个非终结符：每个级别一个非终结符，再加一个基本表达式单元的非终结符。

让我们按照规则构建语法。

根据规则1，我们将定义两个非终结符：一个用于第2级的非终结符expr，一个用于第1级的非终结符term。根据规则2，我们将为基本算术表达式单元（整数）定义一个非终结符factor。

新语法的起始符号是expr，expr的内容将包含第2级运算符（在我们的例子中是运算符 + 和 -），并将包含下一个更高优先级级别，第1级别的非终结符term：

term的内容将包含第1级运算符（在我们的例子中是运算符 * 和 /），并将包含基本表达式单元的非终结符factor。

factor非终结符的内容将是：

你已经在前几篇文章中看到过这些产生式作为语法和语法图的一部分，但这里我们将它们组合成一个处理运算符结合性和优先级的语法。

下面是对应于上述语法的语法图：

图中的每个矩形框都是对另一个图的“方法调用”。如果你以表达式 7 + 5 * 2 为例，从顶部图 expr 开始，向下走到最底部图 factor，你应该能够看到下级图中的高优先级运算符 * 和 / 在上级图中的运算符 + 和 - 之前执行。

为了强调运算符优先级的重要性，让我们看看按照我们的语法和语法图分解的同一个算术表达式 7 + 5 * 2。这是另一种显示高优先级运算符在低优先级运算符之前执行的方法：

好了，让我们按照第4部分的指南将语法转换为代码，看看我们新的解释器是如何工作的，好吗？

这是我们的语法：

这是一个能够处理包含整数和任意数量的加法、减法、乘法和除法运算符的有效算。

代码实现

术表达式的计算器的完整代码。

与第4部分的代码相比，主要变化如下：

Lexer 类现在可以标记 +，-，* 和 /（这没有什么新内容，我们只是将前几篇文章中的代码组合成一个支持所有这些标记的类）
回想一下语法中定义的每个规则（产生式）R 都变成一个同名的方法，对该规则的引用变成一个方法调用：R()。因此，Interpreter 类现在有三个对应于语法中非终结符的方法：expr**，term 和 factor。

# 标记类型
#
# EOF（文件结束）标记用于指示词法分析已没有输入
INTEGER, PLUS, MINUS, MUL, DIV, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', 'EOF'
)


class Token(object):
    def __init__(self, type, value):
        # 标记类型：INTEGER, PLUS, MINUS, MUL, DIV, 或 EOF
        self.type = type
        # 标记值：非负整数值，'+', '-', '*', '/', 或 None
        self.value = value

    def __str__(self):
        """类实例的字符串表示。

        示例：
            Token(INTEGER, 3)
            Token(PLUS, '+')
            Token(MUL, '*')
        """
        return 'Token({type}, {value})'.format(
            type=self.type,
            value=repr(self.value)
        )

    def __repr__(self):
        return self.__str__()


class Lexer(object):
    def __init__(self, text):
        # 客户端输入的字符串，例如："3 * 5", "12 / 3 * 4" 等
        self.text = text
        # self.pos 是 self.text 的索引
        self.pos = 0
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('无效字符')

    def advance(self):
        """推进 `pos` 指针并设置 `current_char` 变量。"""
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None  # 表示输入结束
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):
        """返回从输入中消耗的（多位数）整数。"""
        result = ''
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        return int(result)

    def get_next_token(self):
        """词法分析器（也称为扫描器或标记器）

        此方法负责将句子分解成标记。一次一个标记。
        """
        while self.current_char is not None:

            if self.current_char.isspace():
                self.skip_whitespace()
                continue

            if self.current_char.isdigit():
                return Token(INTEGER, self.integer())

            if self.current_char == '+':
                self.advance()
                return Token(PLUS, '+')

            if self.current_char == '-':
                self.advance()
                return Token(MINUS, '-')

            if self.current_char == '*':
                self.advance()
                return Token(MUL, '*')

            if self.current_char == '/':
                self.advance()
                return Token(DIV, '/')

            self.error()

        return Token(EOF, None)


class Interpreter(object):
    def __init__(self, lexer):
        self.lexer = lexer
        # 将当前标记设置为从输入中获取的第一个标记
        self.current_token = self.lexer.get_next_token()

    def error(self):
        raise Exception('无效语法')

    def eat(self, token_type):
        # 比较当前标记类型与传递的标记类型，
        # 如果匹配，则“吃掉”当前标记并获取下一个标记赋值给 self.current_token，
        # 否则抛出异常。
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            self.error()

    def factor(self):
        """factor : INTEGER"""
        token = self.current_token
        self.eat(INTEGER)
        return token.value

    def term(self):
        """term : factor ((MUL | DIV) factor)*"""
        result = self.factor()

        while self.current_token.type in (MUL, DIV):
            token = self.current_token
            if token.type == MUL:
                self.eat(MUL)
                result = result * self.factor()
            elif token type == DIV:
                self.eat(DIV)
                result = result / self.factor()

        return result

    def expr(self):
        """算术表达式解析器/解释器。

        calc>  14 + 2 * 3 - 6 / 2
        17

        expr   : term ((PLUS | MINUS) term)*
        term   : factor ((MUL | DIV) factor)*
        factor : INTEGER
        """
        result = self.term()

        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            if token.type == PLUS:
                self.eat(PLUS)
                result = result + self.term()
            elif token type == MINUS:
                self.eat(MINUS)
                result = result - self.term()

        return result


def main():
    while True:
        try:
            # 在 Python3 下运行时，将 'raw_input' 替换为 'input'
            text = raw_input('calc> ')
        except EOFError:
            break
        if not text:
            continue
        lexer = Lexer(text)
        interpreter = Interpreter(lexer)
        result = interpreter.expr()
        print(result)


if __name__ == '__main__':
    main()

将上面的代码保存为 calc5.py 文件，或者直接从 GitHub 下载。和往常一样，试试看，看看解释器是否正确评估包含不同优先级运算符的算术表达式。

这是我在笔记本电脑上的一个示例会话：

$ python calc5.py
calc> 3
3
calc> 2 + 7 * 4
30
calc> 7 - 8 / 4
5
calc> 14 + 2 * 3 - 6 / 2
17

练习与巩固

以下是今天的新练习：

写一个解释器，如本文所述，不看文章中的代码。为你的解释器编写一些测试，确保它们通过。扩展解释器以处理包含括号的算术表达式，以便你的解释器能够评估深度嵌套的算术表达式，例如：7 + 3 * (10 / (12 / (3 + 1) - 1))。

检查你的理解。

什么是左结合运算符？
运算符 + 和 - 是左结合还是右结合？* 和 / 呢？
运算符 + 的优先级是否高于运算符 *？

嘿，你读到最后了！太好了。我下次会带着新文章回来——敬请期待，继续努力，一如既往，不要忘记做练习。

～加斯东's blog～

从零开始写个简单的解释器（5）

结合性和优先级

语法构建

代码实现

练习与巩固

推荐书单