3.5 组合语言的解释器

来源：3.5 Interpreters for Languages with Combination

译者：飞龙

协议：CC BY-NC-SA 4.0

运行在任何现代计算机上的软件都以多种编程语言写成。其中有物理语言，例如用于特定计算机的机器语言。这些语言涉及到基于独立储存位和原始机器指令的数据表示和控制。机器语言的程序员涉及到使用提供的硬件，为资源有限的计算构建系统和功能的高效实现。高阶语言构建在机器语言之上，隐藏了表示为位集的数据，以及表示为原始指令序列的程序的细节。这些语言拥有例如过程定义的组合和抽象的手段，它们适用于组织大规模的软件系统。

元语言抽象 -- 建立了新的语言 -- 并在所有工程设计分支中起到重要作用。它对于计算机编程尤其重要，因为我们不仅仅可以在编程中构想出新的语言，我们也能够通过构建解释器来实现它们。编程语言的解释器是一个函数，它在语言的表达式上调用，执行求解表达式所需的操作。

我们现在已经开始了技术之旅，通过这种技术，编程语言可以建立在其它语言之上。我们首先会为计算器定义解释器，它是一种受限的语言，和 Python 调用表达式具有相同的语法。我们之后会从零开始开发 Scheme 和 Logo 语言的解释器，它们都是 Lisp 的方言，Lisp 是现在仍旧广泛使用的第二老的语言。我们所创建的解释器，在某种意义上，会让我们使用 Logo 编写完全通用的程序。为了这样做，它会实现我们已经在这门课中开发的求值环境模型。

3.5.1 计算器

我们的第一种新语言叫做计算器，一种用于加减乘除的算术运算的表达式语言。计算器拥有 Python 调用表达式的语法，但是它的运算符对于所接受的参数数量更加灵活。例如，计算器运算符mul和add可接受任何数量的参数：

calc> add(1, 2, 3, 4)
10
calc> mul()
1

sub运算符拥有两种行为：传入一个运算符，它会对运算符取反。传入至少两个，它会从第一个参数中减掉剩余的参数。div运算符拥有 Python 的operator.truediv的语义，只接受两个参数。

calc> sub(10, 1, 2, 3)
4
calc> sub(3)
-3
calc> div(15, 12)
1.25

就像 Python 中那样，调用表达式的嵌套提供了计算器语言中的组合手段。为了精简符号，我们使用运算符的标准符号来代替名称：

calc> sub(100, mul(7, add(8, div(-12, -3))))
16.0
calc> -(100, *(7, +(8, /(-12, -3))))
16.0

我们会使用 Python 实现计算器解释器。也就是说，我们会编写 Python 程序来接受字符串作为输入，并返回求值结果。如果输入是符合要求的计算器表达式，结果为字符串，反之会产生合适的异常。计算器语言解释器的核心是叫做calc_eval的递归函数，它会求解树形表达式对象。

表达式树。到目前为止，我们在描述求值过程中所引用的表达式树，还是概念上的实体。我们从没有显式将表达式树表示为程序中的数据。为了编写解释器，我们必须将表达式当做数据操作。在这一章中，许多我们之前介绍过的概念都会最终以代码实现。

计算器中的基本表达式只是一个数值，类型为int或float。所有复合表达式都是调用表达式。调用表达式表示为拥有两个属性实例的Exp类。计算器的operator总是字符串：算数运算符的名称或符号。operands要么是基本表达式，要么是Exp的实例本身。

>>> class Exp(object):
        """A call expression in Calculator."""
        def __init__(self, operator, operands):
            self.operator = operator
            self.operands = operands
        def __repr__(self):
            return 'Exp({0}, {1})'.format(repr(self.operator), repr(self.operands))
        def __str__(self):
            operand_strs = ', '.join(map(str, self.operands))
            return '{0}({1})'.format(self.operator, operand_strs)

Exp实例定义了两个字符串方法。__repr__方法返回 Python 表达式，而__str__方法返回计算器表达式。

>>> Exp('add', [1, 2])
Exp('add', [1, 2])
>>> str(Exp('add', [1, 2]))
'add(1, 2)'
>>> Exp('add', [1, Exp('mul', [2, 3, 4])])
Exp('add', [1, Exp('mul', [2, 3, 4])])
>>> str(Exp('add', [1, Exp('mul', [2, 3, 4])]))
'add(1, mul(2, 3, 4))'

最后的例子演示了Exp类如何通过包含作为operands元素的Exp的实例，来表示表达式树中的层次结构。

求值。calc_eval函数接受表达式作为参数，并返回它的值。它根据表达式的形式为表达式分类，并且指导它的求值。对于计算器来说，表达式的两种句法形式是数值或调用表达式，后者是Exp的实例。数值是自求值的，它们可以直接从calc_eval中返回。调用表达式需要使用函数。

调用表达式首先通过将calc_eval函数递归映射到操作数的列表，计算出参数列表来求值。之后，在第二个函数calc_apply中，运算符会作用于这些参数上。

计算器语言足够简单，我们可以轻易地在单一函数中表达每个运算符的使用逻辑。在calc_apply中，每种条件子句对应一个运算符。

>>> from operator import mul
>>> from functools import reduce
>>> def calc_apply(operator, args):
        """Apply the named operator to a list of args."""
        if operator in ('add', '+'):
            return sum(args)
        if operator in ('sub', '-'):
            if len(args) == 0:
                raise TypeError(operator + ' requires at least 1 argument')
            if len(args) == 1:
                return -args[0]
            return sum(args[:1] + [-arg for arg in args[1:]])
        if operator in ('mul', '*'):
            return reduce(mul, args, 1)
        if operator in ('div', '/'):
            if len(args) != 2:
                raise TypeError(operator + ' requires exactly 2 arguments')
            numer, denom = args
            return numer/denom

上面，每个语句组计算了不同运算符的结果，或者当参数错误时产生合适的TypeError。calc_apply函数可以直接调用，但是必须传入值的列表作为参数，而不是运算符表达式的列表。

>>> calc_apply('+', [1, 2, 3])
6
>>> calc_apply('-', [10, 1, 2, 3])
4
>>> calc_apply('*', [])
1
>>> calc_apply('/', [40, 5])
8.0

calc_eval的作用是，执行合适的calc_apply调用，通过首先计算操作数子表达式的值，之后将它们作为参数传入calc_apply。于是，calc_eval可以接受嵌套表达式。

>>> e = Exp('add', [2, Exp('mul', [4, 6])])
>>> str(e)
'add(2, mul(4, 6))'
>>> calc_eval(e)
26

calc_eval的结构是个类型（表达式的形式）分发的例子。第一种表达式是数值，不需要任何的额外求值步骤。通常，基本表达式不需要任何额外的求值步骤，这叫做自求值。计算器语言中唯一的自求值表达式就是数值，但是在通用语言中可能也包括字符串、布尔值，以及其它。

“读取-求值-打印”循环。和解释器交互的典型方式是“读取-求值-打印”循环（REPL），它是一种交互模式，读取表达式、对其求值，之后为用户打印出结果。Python 交互式会话就是这种循环的例子。

REPL 的实现与所使用的解释器无关。下面的read_eval_print_loop函数使用内建的input函数，从用户接受一行文本作为输入。它使用语言特定的calc_parse函数构建表达式树。calc_parse在随后的解析一节中定义。最后，它打印出对由calc_parse返回的表达式树调用calc_eval的结果。

>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            expression_tree = calc_parse(input('calc> '))
            print(calc_eval(expression_tree))

read_eval_print_loop的这个版本包含所有交互式界面的必要组件。一个样例会话可能像这样：

calc> mul(1, 2, 3)
6
calc> add()
0
calc> add(2, div(4, 8))
2.5

这个循环没有实现终端或者错误处理机制。我们可以通过向用户报告错误来改进这个界面。我们也可以允许用户通过发射键盘中断信号（Control-C），或文件末尾信号（Control-D）来退出循环。为了实现这些改进，我们将原始的while语句组放在try语句中。第一个except子句处理了由calc_parse产生的SyntaxError异常，也处理了由calc_eval产生的TypeError和ZeroDivisionError异常。

>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            try:
                expression_tree = calc_parse(input('calc> '))
                print(calc_eval(expression_tree))
            except (SyntaxError, TypeError, ZeroDivisionError) as err:
                print(type(err).__name__ + ':', err)
            except (KeyboardInterrupt, EOFError):  # <Control>-D, etc.
                print('Calculation completed.')
                return

这个循环实现报告错误而不退出循环。发生错误时不退出程序，而是在错误消息之后重新开始循环可以让用户回顾他们的表达式。通过导入readline模块，用户甚至可以使用上箭头或Control-P来回忆他们之前的输入。最终的结果提供了错误信息报告的界面：

calc> add
SyntaxError: expected ( after add
calc> div(5)
TypeError: div requires exactly 2 arguments
calc> div(1, 0)
ZeroDivisionError: division by zero
calc> ^DCalculation completed.

在我们将解释器推广到计算器之外的语言时，我们会看到，read_eval_print_loop由解析函数、求值函数，和由try语句处理的异常类型参数化。除了这些修改之外，任何 REPL 都可以使用相同的结构来实现。

3.5.2 解析

解析是从原始文本输入生成表达式树的过程。解释这些表达式树是求值函数的任务，但是解析器必须提供符合格式的表达式树给求值器。解析器实际上由两个组件组成，词法分析器和语法分析器。首先，词法分析器将输入字符串拆成标记（token），它们是语言的最小语法单元，就像名称和符号那样。其次，语法分析器从这个标记序列中构建表达式树。

>>> def calc_parse(line):
        """Parse a line of calculator input and return an expression tree."""
        tokens = tokenize(line)
        expression_tree = analyze(tokens)
        if len(tokens) > 0:
            raise SyntaxError('Extra token(s): ' + ' '.join(tokens))
        return expression_tree

标记序列由叫做tokenize的词法分析器产生，并被叫做analyze语法分析器使用。这里，我们定义了calc_parse，它只接受符合格式的计算器表达式。一些语言的解析器为接受以换行符、分号或空格分隔的多种表达式而设计。我们在引入 Logo 语言之前会推迟实现这种复杂性。

词法分析。用于将字符串解释为标记序列的组件叫做分词器（tokenizer ），或者词法分析器。在我们的视线中，分词器是个叫做tokenize的函数。计算器语言由包含数值、运算符名称和运算符类型的符号（比如+）组成。这些符号总是由两种分隔符划分：逗号和圆括号。每个符号本身都是标记，就像每个逗号和圆括号那样。标记可以通过向输入字符串添加空格，之后在每个空格处分割字符串来分开。

>>> def tokenize(line):
        """Convert a string into a list of tokens."""
        spaced = line.replace('(',' ( ').replace(')',' ) ').replace(',', ' , ')
        return spaced.split()

对符合格式的计算器表达式分词不会损坏名称，但是会分开所有符号和分隔符。

>>> tokenize('add(2, mul(4, 6))')
['add', '(', '2', ',', 'mul', '(', '4', ',', '6', ')', ')']

拥有更加复合语法的语言可能需要更复杂的分词器。特别是，许多分析器会解析每种返回标记的语法类型。例如，计算机中的标记类型可能是运算符、名称、数值或分隔符。这个分类可以简化标记序列的解析。

语法分析。将标记序列解释为表达式树的组件叫做语法分析器。在我们的实现中，语法分析由叫做analyze的递归函数完成。它是递归的，因为分析标记序列经常涉及到分析这些表达式树中的标记子序列，它本身作为更大的表达式树的子分支（比如操作数）。递归会生成由求值器使用的层次结构。

analyze函数接受标记列表，以符合格式的表达式开始。它会分析第一个标记，将表示数值的字符串强制转换为数字的值。之后要考虑计算机中的两个合法表达式类型。数字标记本身就是完整的基本表达式树。复合表达式以运算符开始，之后是操作数表达式的列表，由圆括号分隔。我们以一个不检查语法错误的实现开始。

>>> def analyze(tokens):
        """Create a tree of nested lists from a sequence of tokens."""
        token = analyze_token(tokens.pop(0))
        if type(token) in (int, float):
            return token
        else:
            tokens.pop(0)  # Remove (
            return Exp(token, analyze_operands(tokens))
>>> def analyze_operands(tokens):
        """Read a list of comma-separated operands."""
        operands = []
        while tokens[0] != ')':
            if operands:
                tokens.pop(0)  # Remove ,
            operands.append(analyze(tokens))
        tokens.pop(0)  # Remove )
        return operands

最后，我们需要实现analyze_token。analyze_token函数将数值文本转换为数值。我们并不自己实现这个逻辑，而是依靠内建的 Python 类型转换，使用int和float构造器来将标记转换为这种类型。

>>> def analyze_token(token):
        """Return the value of token if it can be analyzed as a number, or token."""
        try:
            return int(token)
        except (TypeError, ValueError):
            try:
                return float(token)
            except (TypeError, ValueError):
                return token

我们的analyze实现就完成了。它能够正确将符合格式的计算器表达式解析为表达式树。这些树由str函数转换回计算器表达式。

>>> expression = 'add(2, mul(4, 6))'
>>> analyze(tokenize(expression))
Exp('add', [2, Exp('mul', [4, 6])])
>>> str(analyze(tokenize(expression)))
'add(2, mul(4, 6))'

analyse函数只会返回符合格式的表达式树，并且它必须检测输入中的语法错误。特别是，它必须检测表达式是否完整、正确分隔，以及只含有已知的运算符。下面的修订版本确保了语法分析的每一步都找到了预期的标记。

>>> known_operators = ['add', 'sub', 'mul', 'div', '+', '-', '*', '/']
>>> def analyze(tokens):
        """Create a tree of nested lists from a sequence of tokens."""
        assert_non_empty(tokens)
        token = analyze_token(tokens.pop(0))
        if type(token) in (int, float):
            return token
        if token in known_operators:
            if len(tokens) == 0 or tokens.pop(0) != '(':
                raise SyntaxError('expected ( after ' + token)
            return Exp(token, analyze_operands(tokens))
        else:
            raise SyntaxError('unexpected ' + token)
>>> def analyze_operands(tokens):
        """Analyze a sequence of comma-separated operands."""
        assert_non_empty(tokens)
        operands = []
        while tokens[0] != ')':
            if operands and tokens.pop(0) != ',':
                raise SyntaxError('expected ,')
            operands.append(analyze(tokens))
            assert_non_empty(tokens)
        tokens.pop(0)  # Remove )
        return elements
>>> def assert_non_empty(tokens):
        """Raise an exception if tokens is empty."""
        if len(tokens) == 0:
            raise SyntaxError('unexpected end of line')

大量的语法错误在本质上提升了解释器的可用性。在上面，SyntaxError异常包含所发生的问题描述。这些错误字符串也用作这些分析函数的定义文档。

这个定义完成了我们的计算器解释器。你可以获取单独的 Python 3 源码 calc.py来测试。我们的解释器对错误健壮，用户在calc>提示符后面的每个输入都会求值为数值，或者产生合适的错误，描述输入为什么不是符合格式的计算器表达式。