3.4 组合语言解释器

我们现在开始一段以其他语言为基础建立语言的技术之旅。 元语言抽象——建立新的语言——在工程设计的各个分支中都起着重要的作用。 这对计算机程序设计尤其重要，因为在程序设计中，我们不仅可以制定新的语言，而且可以通过构造解释器来实现这些语言。 编程语言的解释器是一个函数，当它应用于该语言的表达式时，执行对该表达式求值所需的操作。

我们将首先定义一种语言的解释器，它是Scheme的一个有限子集，称为计算器。 然后，我们将为整个Scheme开发一个解释器的草图。 我们创建的解释器将是完整的，因为它将允许我们用Scheme编写完全通用的程序。 为此，它将实现我们在第一章中为Python程序引入的相同的求值环境模型。

本节中的许多示例都包含在配套的scheme语法计算器示例中，因为它们太复杂，无法自然地适应本文的格式。

3.4.1 Scheme-语法计算器

scheme语法计算器(或简单的计算器)是一种用于加、减、乘和除的算术运算的表达式语言。计算器共享Scheme的调用表达式语法和操作符行为。加法(+)和乘法(*)操作都有任意数量的参数：

> (+ 1 2 3 4)
10
> (+)
0
> (* 1 2 3 4)
24
> (*)
1

减法(-)有两个行为。一个参数减去另一个参数。至少有两个参数，它从第一个参数中减去除第一个参数外的所有参数。除法(/)有类似的两种行为：计算单个参数的乘式倒数或用第一个参数除以第一个参数外的所有参数：

> (- 10 1 2 3)
4
> (- 3)
-3
> (/ 15 12)
1.25
> (/ 30 5 2)
3
> (/ 10)
0.1

调用表达式的求值方式是求其操作数子表达式的值，然后将运算符应用到结果实参：

> (- 100 (* 7 (+ 8 (/ -12 -3))))
16.0

我们将用Python实现计算器语言的解释器。也就是说，我们将编写一个Python程序，它接受字符串行作为输入，并将这些行求值的结果作为计算器表达式返回。如果计算器表达式格式不正确，解释器将引发一个适当的异常。

3.4.2 表达式树

在此之前，表达式树一直是概念实体，我们在描述求值过程时提到过它；在我们的程序中，我们从来没有显式地将表达式树表示为数据。 为了编写解释器，我们必须将表达式作为数据来操作。

原始表达式在计算器中只是一个数字或字符串：可以是int或float，也可以是运算符符号。 所有的组合表达式都是调用表达式。 调用表达式是一个Scheme列表，其第一个元素(操作符)后跟零个或多个操作数表达式。

Scheme对。 在Scheme中，列表是嵌套的对，但不是所有的对都是列表。为了在Python中表示模式对和列表，我们将定义一个类对，类似于本章前面的Rlist类。 实现出现在scheme_reader中。

空列表由一个名为nil的对象表示，该对象是nil类的实例。 我们假设只会创建一个nil实例。

Pair类和nil对象是Python中表示的Scheme值。 它们有repr字符串是Python表达式，而str字符串是Scheme表达式。

>>> s = Pair(1, Pair(2, nil))
>>> s
Pair(1, Pair(2, nil))
>>> print(s)
(1 2)

它们实现了长度和元素选择的基本Python序列接口，以及返回Scheme列表的map方法。

>>> len(s)
2
>>> s[1]
2
>>> print(s.map(lambda x: x+4))
(5 6)

嵌套列表。嵌套对可以表示列表，但是列表的元素本身也可以是列表。因此，为了足以表示Scheme表达式，而Scheme表达式实际上是嵌套列表。

>>> expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
>>> print(expr)
(+ (* 3 4) 5)
>>> print(expr.second.first)
(* 3 4)
>>> expr.second.first.second.first
3

这个例子演示了所有计算器表达式都是嵌套的Scheme列表。我们的计算器解释器将读取嵌套的Scheme列表，将它们转换为表示为嵌套的Pair实例的表达式树(下面解析表达式)，然后计算表达式树以产生值(下面的计算器计算)。

3.4.3 解析表达式

解析是从原始文本输入生成表达式树的过程。 解析器由两个组件组成：词法分析器和语法分析器。 首先，词法分析器将输入字符串划分为标记，标记是语言的最小语法单元，如名称和符号。 其次，语法分析器从这个标记序列构造一个表达式树。 词法分析程序生成的标记序列由语法分析程序使用。

词法分析。 将字符串解释为标记序列的组件称为标记分析器或词法分析器。 在我们的实现中，标记器是scheme_tokens中称为tokenize_line的函数。 Scheme标记由空格、圆括号、点或单引号分隔。 分隔符是记号，符号和数字也是。 标记器逐个分析一行字符，验证符号和数字的格式。

对一个格式良好的计算器表达式进行标记可以分隔所有符号和分隔符，但可以识别多字符数字(如2.3)并将它们转换为数字类型。

>>> tokenize_line('(+ 1 (* 2.3 45))')
['(', '+', 1, '(', '*', 2.3, 45, ')', ')']

词法分析是一个迭代过程，它可以单独应用于输入程序的每一行。

语法分析。将标记序列解释为表达式树的组件称为语法分析器。语法分析是一个树递归过程，它必须考虑可能跨多行的整个表达式。

语法分析是通过scheme_reader中的scheme_read函数实现的。 它是树递归的，因为分析一个标记序列经常涉及到将这些标记的子序列分析到子表达式中，子表达式本身作为一个更大的表达式树的分支(例如，操作数)。递归生成由求值器使用的层次结构。

scheme_read函数期望它的输入src是一个缓冲区实例，该实例允许访问一系列令牌。 Buffer在Buffer模块中定义，它将跨多行的标记收集到一个可以从语法上分析的单个对象中。

>>> lines = ['(+ 1', '   (* 2.3 45))']
>>> expression = scheme_read(Buffer(tokenize_lines(lines)))
>>> expression
Pair('+', Pair(1, Pair(Pair('*', Pair(2.3, Pair(45, nil))), nil)))
>>> print(expression)
(+ 1 (* 2.3 45))

scheme_read函数首先检查各种基本情况，包括空输入(这会引发文件结束异常，在Python中称为EOFError)和原始表达式。每当(token表示列表的开始时，就会调用对read_tail的递归调用。

read_tail函数继续从相同的输入src读取数据，但是希望在列表开始后调用它。 它的基本情况是空输入(错误)或结束列表的右括号。 它的递归调用使用scheme_read读取列表的第一个元素，使用read_tail读取列表的其余部分，然后返回一个表示为一对的列表。

scheme_read的这个实现可以读取格式良好的Scheme列表，这正是我们在计算器语言中所需要的。 解析虚线列表和带引号的表单将作为练习。

信息语法错误大大提高了解释器的可用性。 所引发的SyntaxError异常包括所遇到问题的描述。

3.4.4 计算器计算

scalc模块为计算器语言实现了一个求值器。calc_eval函数接受一个表达式作为参数并返回它的值。helper函数的定义simplify、reduce和as_scheme_list出现在模型中，下面将使用它们。

对于Calculator，表达式的唯一两种合法语法形式是numbers和call表达式，它们是表示格式良好的Scheme列表的成对实例。数字是自我评估；它们可以直接从calc_eval返回。调用表达式需要函数应用程序。

>>> def calc_eval(exp):
        """Evaluate a Calculator expression."""
        if type(exp) in (int, float):
            return simplify(exp)
        elif isinstance(exp, Pair):
            arguments = exp.second.map(calc_eval)
            return simplify(calc_apply(exp.first, arguments))
        else:
            raise TypeError(exp + ' is not a number or call expression')

计算调用表达式的方法是，首先递归地将calc_eval函数映射到计算实参列表的操作数列表。然后，将运算符应用于第二个函数calc_apply中的这些实参。

计算器语言非常简单，我们可以很容易地在单个函数体中表达应用每个操作符的逻辑。在calc_apply中，每个条件子句对应于应用一个操作符。

>>> def calc_apply(operator, args):
        """Apply the named operator to a list of args."""
        if not isinstance(operator, str):
            raise TypeError(str(operator) + ' is not a symbol')
        if operator == '+':
            return reduce(add, args, 0)
        elif operator == '-':
            if len(args) == 0:
                raise TypeError(operator + ' requires at least 1 argument')
            elif len(args) == 1:
                return -args.first
            else:
                return reduce(sub, args.second, args.first)
        elif operator == '*':
            return reduce(mul, args, 1)
        elif operator == '/':
            if len(args) == 0:
                raise TypeError(operator + ' requires at least 1 argument')
            elif len(args) == 1:
                return 1/args.first
            else:
                return reduce(truediv, args.second, args.first)
        else:
            raise TypeError(operator + ' is an unknown operator')

上面，每个套件计算不同操作符的结果，或者在给出错误的参数数量时抛出适当的TypeError。可以直接应用calc_apply函数，但必须将一组值作为参数传递给它，而不是将一组操作数表达式传递给它。

>>> calc_apply('+', as_scheme_list(1, 2, 3))
6
>>> calc_apply('-', as_scheme_list(10, 1, 2, 3))
4
>>> calc_apply('*', nil)
1
>>> calc_apply('*', as_scheme_list(1, 2, 3, 4, 5))
120
>>> calc_apply('/', as_scheme_list(40, 5))
8.0

calc_eval的作用是在将操作数子表达式作为参数传递给calc_apply之前，首先计算它们的值，从而正确调用calc_apply。因此，calc_eval可以接受嵌套表达式。

>>> print(exp)
(+ (* 3 4) 5)
>>> calc_eval(exp)
17

calc_eval的结构是根据类型(即表达式的形式)进行分派的一个例子。第一种形式的表达式是一个数字，它不需要额外的求值步骤。通常，不需要额外求值步骤的原语表达式称为自求值。计算器语言中唯一的自求值表达式是数字，但是一般的编程语言也可能包括字符串、布尔值等。

Read-eval-print循环。与解释器交互的一种典型方法是通过read-eval-print循环(REPL)，这是一种交互模式，读取表达式，求值，然后为用户打印结果。Python交互会话就是这种循环的一个例子。

REPL的实现可以在很大程度上独立于它所使用的解释器。下面的read_eval_print_loop函数缓冲来自用户的输入，使用特定于语言的scheme_read函数构造一个表达式，然后打印将calc_eval应用到该表达式的结果。

>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            src = buffer_input()
            while src.more_on_line:
                expression = scheme_read(src)
                print(calc_eval(expression))

这个版本的read_eval_print_loop包含了交互接口的所有基本组件。一个示例会话如下所示：

> (* 1 2 3)
6
> (+)
0
> (+ 2 (/ 4 8))
2.5
> (+ 2 2) (* 3 3)
4
9
> (+ 1
     (- 23)
     (* 4 2.5))
-12

这个循环实现没有终止或错误处理的机制。我们可以通过向用户报告错误来改进界面。我们还可以允许用户通过发送键盘中断信号(UNIX上是Control-C)或文件结束异常(UNIX上是Control-D)来退出循环。为了实现这些改进，我们将原始的while语句集放置在try语句中。第一个except子句处理scheme_read引发的SyntaxError和ValueError异常，以及calc_eval引发的TypeError和ZeroDivisionError异常。

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

这个循环实现在不退出循环的情况下报告错误。不是在出现错误时退出程序，而是在出现错误消息后重新启动循环，允许用户修改他们的表达式。在导入readline模块时，用户甚至可以使用向上箭头或Control-P来回忆他们之前的输入。最终结果提供了一个信息丰富的错误报告接口：

> )
SyntaxError: unexpected token: )
> 2.3.4
ValueError: invalid numeral: 2.3.4
> +
TypeError: + is not a number or call expression
> (/ 5)
TypeError: / requires exactly 2 arguments
> (/ 1 0)
ZeroDivisionError: division by zero

当我们将解释器推广到计算器以外的新语言时，我们将看到read_eval_print_loop由一个解析函数、一个求值函数和try语句处理的异常类型参数化。除了这些变化之外，所有的REPLs都可以使用相同的结构来实现。