3.4.带有组合的语言的解释器

3.4 带有组合的语言的解释器(\(Interpreters\;for\;Languages\;with\;Combination\))

一、概述

  在程序中，我们不仅可以定义一个新语言，还可以通过构建解释器(\(interpreter\)) 来实现这些语言。而编程语言的解释器就是一个函数，这个函数在用在表达式或语言上时，可以表现出相应的行为来执行它们。

  \(scheme\)语言计算器(\(Scheme-Syntax\;Calculator\))是用于加减乘除操作的表达式语言。它使用\(scheme\)的句法规则与\(operator\)行为：

> (+ 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

  调用表达式(\(call\;expression\))的计算方法是计算它的子表达式，然后将运算符用于计算后的结果：

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

二、表达式树\(Expression\;Trees\)

  一个最原始的表达式是一个单独的数字或字符串，其数据类型为int或float或operator symbol.而一个调用表达式是一个\(scheme\;list\)，表达式的第一个元素是操作符\(operator\)，后面是\(0\)或者更多的操作元表达式(\(operand\;expression\))。所有的组合表达式都是调用表达式。

1.Pair

  List是嵌套的Pair，反之则不然。因此有必要定义一个单独的Pair型。

  在\(scheme\)中，Pair类是用\(python\)表示的\(scheme\)值，它们有repr的\(python\)表达式和str的\(scheme\)表达式：

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

  它们实现了长度、元素选择等基本的\(python\)序列接口，其中的map方法会返回一个映射后的\(scheme\)列表：

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

2.嵌套列表

  嵌套Pair能够表达List，而List自身也可以通过嵌套得到新的List。因此，Pair足够表示所有的List型数据，也因此足够表示所有的\(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\)List。我们的计算器解释器将会读入这些嵌套的\(Scheme\)List，将它们转化为用嵌套Pair实例代表的表达式树，然后通过计算表达式树来产生值。

三、对表达式的语法分析

1.概述

  语法分析(\(parsing\))是从原始文本输入产生表达式的过程。

  语法翻译器由两部分构成：词法分析器(\(lexical\;analyzer\)) 和句法分析器(\(syntactic\;analyzer\))。首先，词法分析器将输入文本分成标记(\(tokens\))。标记是最小的句法单元，如name、symbol类型。然后，句法分析器通过标记序列(\(tokens\;sequence\))搭建表达式树，消耗掉词法分析器产生的标记序列。

2.词法分析

  将字符串解释为标记序列的部分称为标记器(\(tokenizer\))或词法分析器。在我们的实现中，标记器是tokenize_line函数。

  \(scheme\)的标记间由空格、逗号、点等符号相隔。标记器一个字符一个字符地分析句子，验证其中符号(\(symbol\))与数字(\(numeral\))的格式。下面是一个标记器的分析结果：

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

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

3.句法分析

  将标记序列转化为表达式树的部分被称为句法分析器。句法分析是一个树形递归(\(tree-recursive\))的过程，它不仅要考虑行内表达式，还要考虑扩张到多个行的表达式。

  句法分析是通过scheme_read函数实现的。它是树形递归的，因为分析一个标记序列经常需要将它的一些子列分析进一个子表达式中，子表达式本身充当较大表达式树的分支。递归生成了计算器使用的层次结构(\(hierarchical\;structure\))。

  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函数先检查众多基础的情况，包括空的输入(\(empty\;input\))(这会导致\(end-of-file\)错误，即EOFError)和基本表达式。只要(标记了列表的开头，read_tail就被递归地调用。

  read_tail函数也从同样的src中读取，但它希望在List的开头被调用。它的基本情况(\(base\;cases\))是一个空输入(EOF)或者一个结束括号())终止列表。它的递归调用会先使用scheme_read读取List中的第一个元素，再用read_tail读入List中的剩余元素，然后返回一个用Pair表示的列表。

  提供信息的句法错误大大提高了解释器的可用性，它引发的SyntaxError异常包括了所遇到问题的声明。

四、计算器的计算

1.计算器表达式的转换

  对于计算器，唯一的两个合法的句法形式是数字(\(numbers\))和调用表达式(\(call\;expressions\))，即经过良好组织的\(scheme\)List，它们是以Pair形式存在的。数字自己就可以计算出一个值，它们可以直接被calc_eval返回。而调用表达式需要对其应用函数(\(function\;application\))才可返回值：

def calc_eval(exp):
        """Evaluate a Calculator expression."""
        # number type
        if type(exp) in (int, float):
            return simplify(exp)
        # list type as pair instance
        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')

  这里，当传入的参数为\(call\;expression\)时，argument对Pair除了第一个元素外的所有元素调用calc_eval函数，并通过map操作将结果映射到原来的Pair中，最后对只有两个元素的Pair进行最后的化简。

  calc_eval的结构是根据类型分派的典型例子：根据表达式形式分派。

  这里引入一个新的概念：不需要多余计算步骤的原始表达式叫作“自我计算式”(\(self-evaluating\))，除了数字，字符串、布尔值都是自我计算式。

2.计算器的计算

  可以通过如下程序实现表达式的计算，其中的每一个条件语句分别作用于一个操作符：

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')

  calc_apply函数可以直接调用，但传入的参数必须是值的列表而不是操作数表达式(\(a\;list\;of\;operand\;expressions\))：

>>> 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_eval可以接受嵌套表达式作为参数：

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

3.“读取-计算-打印”流程

  \(a.\)解释器的一般范式

  与解释器交互的一般流程是 “读取-计算-打印”流程，即：先读入表达式，再计算表达式，最后打印计算出的值。

  下面展示这一流程的一般实现。read_eval_print_loop函数先将用户的输入\(buffer\)化，然后用特定语言函数(\(language-specific\))构建表达式，最后打印通过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))

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

  \(b.\)优化

  上述交互接口包含所有接口必须的要素，但是缺少终止与错误处理机制。我们可以通过将错误报告给用户对其进行优化：

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

  这一流程实现报告用户的错误，但不退出流程：

> )
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被解析函数、计算函数、错误输出语句参数化了。除了这些差别，所有的\(REPLs\)都可以用相同的框架实现。