《计算机程序的构造和解释》阅读笔记：准备（1）【python3简单实现lisp解释器（1）】

心已赠人 2022-12-03 05:22 90阅读 0赞

打算深入阅读一下《计算机程序的构造和解释》，这应该会是一个比较漫长的过程，虽然这本书章节不多，但信息量挺大的，书的最后还会编写一个简单的解释器，也可以当作编译原理的简单入门。

这是对于《计算机程序的构造和解释》这本书阅读的准备，因为书用lisp语言，所以我先看了一下(How to Write a (Lisp) Interpreter (in Python))（如何用python实现一个lisp解释器）为什么用这个作为准备呢，因为这个代码量很少适合入门，也能让我了解一些lisp语法。

[(How to Write a (Lisp) Interpreter (in Python))][How to Write a _Lisp_ Interpreter _in Python]网站

[完整的代码][Link 1]在网站最下面也可以下载

原本中应该使用python2编写的，因为apply，raw\_input 在python3已经弃用，我会用python3编写，遇到这些python2的语法会修改掉

CSDN上有几篇译文，但是不知道为啥代码写错了，比如elif isinstance(x, Number):写成了elif not isinstance(x, Number):

解释器流程  
程序(一段字符串) => 解析(语法) => 生成抽象语法树(语义) => 执行(语义) => 结果

一：解析

'''
    语言的语法是指组成正确的语句或表达式的顺序，语义指那些表达式或语句的内在含义。
    
    解释器流程
    程序 => 解析 => 抽象语法树 => 执行(语义) => 结果
    
    1:解析语法
    
    '''
    
    Symbol = str  # 字符串
    List   = list  # 列表
    Number = (int, float)  # 数字
    
    # ======= 第一步 解析语法 =======
    
    # ======== 解析语法 ========
    def parse(program):
        '''
        语法解析函数
        返回抽象语法树，多维数组形式展示嵌套关系
        '''
        return read_from_tokens(tokenize(program))
    
    def tokenize(str):
        '''
        字符串转list
        词法分析：也就是将输入字符串分成一系列 token，返回一个语法列表
        '''
        # 默认空格分隔。所以需要将括号添加空格，以便分隔出来
        # 获取一个简单的语法列表，tokens
        return str.replace('(', ' ( ').replace(')', ' ) ').split()
    
    def read_from_tokens(tokens):
        '''
        解析list
        语义分析：将tokens组装成抽象语法树
        参数：语法列表
        返回：抽象语法树列表
        如果tokens长度为零直接返回
        去掉tokens第一个字符
        如果第一个字符是（ ，定义一个空列表用来存放语法树，如果tokens第一个字符不是 ），循环将同级语法树存到列表，碰到 ）直接去掉，返回这一层语法树
        其它情况返回字符，如果是数字就返回数字，其它的返回字符串
        '''
        if len(tokens) == 0:
            return '长度为零！'
    
        # list去掉第一位元素，如果不是（ 就将它转换类型后加入列表中
        token = tokens.pop(0)
        # 第一个字符是(，然后建立表达式列表，直到匹配到 ）
        if token == '(':
            # 这里定义空list是为了抽象语法树的嵌套关系
            L = []
            # 语法树第一个字符是）一定是错误语法
            while tokens[0] != ')':
                # 将括号以外的字符加进list中
                # 这里的递归是为了用多维数组展示抽象语法树嵌套关系，同级的字符放在一个list中
                L.append(read_from_tokens(tokens))
                # print(L)
            # 删除括号结束符 ）,如果不删除的话，碰到 ）就无法循环下去，只能得到部分语法树
            tokens.pop(0)
            # 返回同级数据
            return L
        else:
            # 返回字符，如果数字转成整数或者浮点类型，其它都是字符串
            return atom(token)
    
    def atom(token):
        '''
        字符串类型转换
        Lispy 的 tokens 是括号、标识符和数字
        '''
        try: return int(token)
        except ValueError:
            try: return float(token)
            except ValueError:
                return Symbol(token)
    
    
    # ======= 测试 ========
    # data_str = '(define circle-area (lambda (r) (* pi (* r r))))'
    # data_str = '(+ 1 1)'
    # data_str = '(+ 2 (* 3 4))'
    # data_str = '(+ 2 (* 3 (- 6 2)))'
    # data_str = '(define (a x)(* x x))'
    data_str = '(define fib (lambda (n) (if (n > 0)(- x) x)))'
    
    # a = tokenize(data_str)
    a =parse(data_str)
    print(a)

![20200901221303766.png][]

这里也有一点问题，就是开始括号多几个会报错，结束括号多几个语法树会少很多数据，于是我想加一个简单判断，括号对是否正确（提醒：这样写可能不兼容后面的代码，到时候还需要修改）

def tokenize(str):
        '''
        字符串转list
        词法分析：也就是将输入字符串分成一系列 token，返回一个语法列表
        '''
        # 默认空格分隔。所以需要将括号添加空格，以便分隔出来
        # 获取一个简单的语法列表，tokens
        tokens = str.replace('(', ' ( ').replace(')', ' ) ').split()
        # 判断括号对
        if tokens.count('(') != tokens.count(')'):
            return '括号意外结束'
        return tokens

read\_from\_tokens 函数中也加一个判断：

if not isinstance(tokens, list):
        return tokens

二：环境

'''
    语言的语法是指组成正确的语句或表达式的顺序，语义指那些表达式或语句的内在含义。
    
    解释器流程
    程序 => 解析 => 抽象语法树 => 执行(语义) => 结果
    
    1:解析语法
    2:添加环境
    
    '''
    
    import math 
    import operator as op
    
    Symbol = str  # 字符串
    List   = list  # 列表
    Number = (int, float)  # 数字
    Env = dict  # 环境
    
    # ======= 第一步 解析语法 =======
    
    # ======== 解析语法 ========
    def parse(program):
        '''
        语法解析函数
        返回抽象语法树，多维数组形式展示嵌套关系
        '''
        return read_from_tokens(tokenize(program))
    
    def tokenize(str):
        '''
        字符串转list
        词法分析：也就是将输入字符串分成一系列 token，返回一个语法列表
        '''
        # 默认空格分隔。所以需要将括号添加空格，以便分隔出来
        # 获取一个简单的语法列表，tokens
        return str.replace('(', ' ( ').replace(')', ' ) ').split()
    
    def read_from_tokens(tokens):
        '''
        解析list
        语义分析：将tokens组装成抽象语法树
        参数：语法列表
        返回：抽象语法树列表
        如果tokens长度为零直接返回
        去掉tokens第一个字符
        如果第一个字符是（ ，定义一个空列表用来存放语法树，如果tokens第一个字符不是 ），循环将同级语法树存到列表，碰到 ）直接去掉，返回这一层语法树
        其它情况返回字符，如果是数字就返回数字，其它的返回字符串
        '''
        if len(tokens) == 0:
            return '长度为零！'
    
        # list去掉第一位元素，如果不是（ 就将它转换类型后加入列表中
        token = tokens.pop(0)
        # 第一个字符是(，然后建立表达式列表，直到匹配到 ）
        if token == '(':
            # 这里定义空list是为了抽象语法树的嵌套关系
            L = []
            # 语法树第一个字符是）一定是错误语法
            while tokens[0] != ')':
                # 将括号以外的字符加进list中
                # 这里的递归是为了用多维数组展示抽象语法树嵌套关系，同级的字符放在一个list中
                L.append(read_from_tokens(tokens))
                # print(L)
            # 删除括号结束符 ）,如果不删除的话，碰到 ）就无法循环下去，只能得到部分语法树
            tokens.pop(0)
            # 返回同级数据
            return L
        else:
            # 返回字符，如果数字转成整数或者浮点类型，其它都是字符串
            return atom(token)
    
    def atom(token):
        '''
        字符串类型转换
        Lispy 的 tokens 是括号、标识符和数字
        '''
        try: return int(token)
        except ValueError:
            try: return float(token)
            except ValueError:
                return Symbol(token)
    
    
    # ======= 第二步 设置环境 =======
    
    # ====== 环境 =======
    '''
    环境是指变量名与值之间的映射。eval 默认使用全局环境，包括一组标准函数的名称（如 sqrt 和 max，以及操作符 *）
    '''
    
    def standard_env():
        '''
        简单的标准环境
        环境是一个字典形式，将环境中添加标准库，或者自己定义的函数
        '''
        env = Env()  # 环境是一个字典形式
        # vars函数是python自带函数 返回对象object的属性名和属性值的字典形式
        env.update(vars(math))
        # 添加一些符合Scheme标准的环境
        env.update({
            '+':op.add, 
            '-':op.sub, 
            '*':op.mul, 
            '/':op.truediv,
            '>':op.gt, 
            '<':op.lt, 
            '>=':op.ge, 
            '<=':op.le, 
            '=':op.eq,
            'abs':     abs,
            'append':  op.add,  
            # 'apply':   apply,  # python3 没这个函数
            'begin':   lambda *x: x[-1],
            'car':     lambda x: x[0],
            'cdr':     lambda x: x[1:], 
            'cons':    lambda x,y: [x] + y,
            'eq?':     op.is_, 
            'equal?':  op.eq, 
            'length':  len, 
            'list':    lambda *x: list(x), 
            'list?':   lambda x: isinstance(x,list), 
            'map':     map,
            'max':     max,
            'min':     min,
            'not':     op.not_,
            'null?':   lambda x: x == [], 
            'number?': lambda x: isinstance(x, Number),   
            'procedure?': callable,
            'round':   round,
            'symbol?': lambda x: isinstance(x, Symbol),
        })
        # 返回这个环境
        return env
    
    # 作为全局环境
    global_env = standard_env()
    
    
    # ======= 测试 ========
    # data_str = '(define circle-area (lambda (r) (* pi (* r r))))'
    # data_str = '(+ 1 1)'
    # data_str = '(+ 2 (* 3 4))'
    # data_str = '(+ 2 (* 3 (- 6 2)))'
    # data_str = '(define (a x)(* x x))'
    data_str = '(define fib (lambda (n) (if (n > 0)(- x) x)))'
    
    # a = tokenize(data_str)
    a =parse(data_str)
    print(a)

因为python3没有apply所以我们可以自己写一个

# python3 不存在apply，所以这里自己定义一个
    def apply(func, *args, **kwargs):
        return func(*args, **kwargs)

上面环境中其实还有一些问题，比如'cons': lambda x,y: \[x\] + y，list和int是无法相加的，我去查了一下cons函数是一个将两个参数放到一个list中，所以我就改成了：

'cons': lambda x, y: [x] + y if isinstance(y, list) else [x] + [y],

等到执行函数写完以后可以用下面的例子测试一下：

(cons 1 2)
    
    (apply cons 1 1)
    
    (cons 1 (list 2 3))
    
    (length (cons 1 (list 2 3)))

python自带的加减乘除只能执行两个数的运算，我自己也改了一下，代替自带的四则运算就可以支持多参数运算了

def _add(*datas):
        sum_num = 0
        for data in datas:
            sum_num = sum_num + data
        return sum_num
    
    def _sub(*datas):
        sub_num = 0
        for data in datas:
            if len(datas) > 1 and sub_num == 0:
                sub_num = data
            else:
                sub_num = sub_num - data
        return sub_num
    
    def _mul(*datas):
        mul_num = 1
        for data in datas:
            mul_num = data * mul_num
        return mul_num
    
    def _truediv(*datas):
        truediv_num = 1
        for data in datas:
            if truediv_num == 1:
                truediv_num = data
            else:
                truediv_num = truediv_num / data
        return truediv_num

三：执行

'''
    语言的语法是指组成正确的语句或表达式的顺序，语义指那些表达式或语句的内在含义。
    
    解释器流程
    程序 => 解析 => 抽象语法树 => 执行(语义) => 结果
    
    1:解析语法
    2:添加环境
    3:执行
    
    '''
    
    import math 
    import operator as op
    
    Symbol = str  # 字符串
    List   = list  # 列表
    Number = (int, float)  # 数字
    Env = dict  # 环境
    
    # ======= 第一步 解析语法 =======
    
    # ======== 解析语法 ========
    def parse(program):
        '''
        语法解析函数
        参数：语句字符串
        返回：抽象语法树，多维数组形式展示嵌套关系
        '''
        return read_from_tokens(tokenize(program))
    
    def tokenize(str):
        '''
        字符串转list
        词法分析：也就是将输入字符串分成一系列 token，返回一个语法列表
        参数：语句字符串
        返回：一个简单的语法列表，tokens
        '''
        # 默认空格分隔。所以需要将括号添加空格，以便分隔出来
        return str.replace('(', ' ( ').replace(')', ' ) ').split()
    
    def read_from_tokens(tokens):
        '''
        解析list
        语义分析：将tokens组装成抽象语法树
        参数：语法列表
        返回：抽象语法树列表
        如果tokens长度为零直接返回
        去掉tokens第一个字符
        如果第一个字符是（ ，定义一个空列表用来存放语法树，如果tokens第一个字符不是 ），循环将同级语法树存到列表，碰到 ）直接去掉，返回这一层语法树
        其它情况返回字符，如果是数字就返回数字，其它的返回字符串
        '''
        if len(tokens) == 0:
            return '长度为零！'
    
        # list去掉第一位元素，如果不是（ 就将它转换类型后加入列表中
        token = tokens.pop(0)
        # 第一个字符是(，然后建立表达式列表，直到匹配到 ）
        if token == '(':
            # 这里定义空list是为了抽象语法树的嵌套关系
            L = []
            # 语法树第一个字符是）一定是错误语法
            while tokens[0] != ')':
                # 将括号以外的字符加进list中
                # 这里的递归是为了用多维数组展示抽象语法树嵌套关系，同级的字符放在一个list中
                L.append(read_from_tokens(tokens))
                # print(L)
            # 删除括号结束符 ）,如果不删除的话，碰到 ）就无法循环下去，只能得到部分语法树
            tokens.pop(0)
            # 返回同级数据
            return L
        else:
            # 返回字符，如果数字转成整数或者浮点类型，其它都是字符串
            return atom(token)
    
    def atom(token):
        '''
        字符串类型转换
        Lispy 的 tokens 是括号、标识符和数字
        '''
        try: return int(token)
        except ValueError:
            try: return float(token)
            except ValueError:
                return Symbol(token)
    
    # ======= 第二步 设置环境 =======
    
    # ====== 环境 =======
    '''
    环境是指变量名与值之间的映射。eval 默认使用全局环境，包括一组标准函数的名称（如 sqrt 和 max，以及操作符 *）
    '''
    def standard_env():
        '''
        简单的标准环境
        环境是一个字典形式，将环境中添加标准库，或者自己定义的函数
        '''
        env = Env()  # 环境是一个字典形式
        # vars函数是python自带函数 返回对象object的属性名和属性值的字典形式
        env.update(vars(math))
        # 添加一些符合Scheme标准的环境
        env.update({
            '+':op.add, 
            '-':op.sub, 
            '*':op.mul, 
            '/':op.truediv,
            '>':op.gt, 
            '<':op.lt, 
            '>=':op.ge, 
            '<=':op.le, 
            '=':op.eq,
            'abs':     abs,
            'append':  op.add,  
            # 'apply':   apply,  # python3 没这个函数
            'begin':   lambda *x: x[-1],
            'car':     lambda x: x[0],
            'cdr':     lambda x: x[1:], 
            'cons':    lambda x,y: [x] + [y],
            'eq?':     op.is_, 
            'equal?':  op.eq, 
            'length':  len, 
            'list':    lambda *x: list(x), 
            'list?':   lambda x: isinstance(x,list), 
            'map':     map,
            'max':     max,
            'min':     min,
            'not':     op.not_,
            'null?':   lambda x: x == [], 
            'number?': lambda x: isinstance(x, Number),   
            'procedure?': callable,
            'round':   round,
            'symbol?': lambda x: isinstance(x, Symbol),
        })
        # 返回这个环境
        return env
    
    # 作为全局环境
    global_env = standard_env()
    
    # ======= 第三步 执行 ========
    
    # ======= 执行 ========
    def eval(x, env=global_env):
        '''
        执行语义
        如果是字符，去环境中查找变量值或者函数
        如果是数字直接输出
        如果第一个字符是if先递归计算判断条件的值，然后递归计算输出值
        如果第一个字符是define递归计算出值，然后加入环境中
        其它的情况先用第一个字符去环境中查找函数，然后递归将后面的字符存入列表，最后执行函数参数是之前列表
    
        if 语句：
            (if test conseq alt)
            test是判断条件，如果符合输出conseq，否则输出alt
            例子：
                (if (> 1 0) 1 0)
                (if (> 1 0) (+ 1 2) (- 9 3))
        define 语句：
            (define symbol exp)
            例子：
                (define x 1)
        '''
        # 变量引用
        if isinstance(x, Symbol):
            # 如果是字符就去环境中找，返回变量值或者函数
            return env[x]
        # 常量
        elif isinstance(x, Number):
            # 数字就直接返回
            return x
        # if 语句，形式(if test conseq alt),test是判断条件,符合条件输出conseq,不符合输出alt
        elif x[0] == 'if':
            # 语句形式分别赋值
            (_, test, conseq, alt) = x
            # 用递归计算条件
            exp = (conseq if eval(test, env) else alt)  
            return eval(exp, env)
        # define 定义变量，形式(define symbol exp),sybol是变量，exp是值
        elif x[0] == 'define':
            (_, symbol, exp) = x
            # 用递归计算数据
            # 将定义的数据加进环境中
            env[symbol] = eval(exp, env)    
        else:
            '''
            Schema 计算形式第一个元素是计算符号:(+ 1 2)
            '''
            # list第一个元素去环境里去找这个函数
            # print(x[0], 1111)
            proc = eval(x[0], env)
            # list后面的元素是函数参数  
            args = [eval(arg, env) for arg in x[1:]]
            # 将参数传入函数    
            return proc(*args)
    
    
    # ======= 测试 ========
    # data_str = '(define circle-area (lambda (r) (* pi (* r r))))'
    # data_str = '(+ 1 1)'
    # data_str = '(+ 2 (* 3 4))'
    # data_str = '(+ 2 (* 3 (- 6 2)))'
    # data_str = '(define (a x)(* x x))'
    # data_str = '(define s 1)'
    data_str = '(begin (define r 10) (* pi (* r r)))'
    # data_str = '(if (> 1 0) 1 0)'
    
    # a = tokenize(data_str)
    a =parse(data_str)
    print(a)
    a = eval(a)
    print(a)

![20200901221700855.png][]

可以看到不论是解析还是执行，程序中都使用了递归，递归在程序中可以清晰表现逻辑，虽然第一次看到的时候自己也是有点懵，不过跑一下数据基本就可以理解了，这也能帮助自己加深一下递归理解，毕竟现实项目中递归着实碰到的比较少！

[How to Write a _Lisp_ Interpreter _in Python]: http://norvig.com/lispy.html
[Link 1]: http://norvig.com/lis.py
[20200901221303766.png]: /images/20221123/6396a1a6aa394bbab39f69aeff7ea0ac.png
[20200901221700855.png]: /images/20221123/98f618bd80f545f3b6eb2cb134ab60e1.png