本文主要是介绍《计算机程序的构造和解释》阅读笔记：准备（3）【python3简单实现lisp解释器（3）】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
下面是我在原基础上添加了一些功能的解释器代码（超详细的注释）
################ python3 实现 lisp 解释器
'''
语言的语法是指组成正确的语句或表达式的顺序，语义指那些表达式或语句的内在含义。解释器流程
程序 => 解析 => 抽象语法树 => 执行(语义) => 结果1:解析语法
2:添加环境
3:执行
4:添加交互式
5: 将Env重定义为Class
6:添加符合Schema的语法形式(quote，set!，lambda)
其实还有一个begin，它是按从左到右的顺序对表达式进行求值，并返回最终的结果，但是已经在环境中定义了
'''# from __future__ import division
import math, readline, sys, re
import operator as op################ 类型Symbol = str # 字符串
List = list # 列表
Number = (int, float) # 数字
# Env = dict # 环境# ======= 第一步 解析语法 =======# ======== 解析语法 ========
def parse(program):'''语法解析函数参数：语句字符串返回：抽象语法树，多维数组形式展示嵌套关系'''return read_from_tokens(tokenize(program))def tokenize(s):'''字符串转list词法分析：也就是将输入字符串分成一系列 token，返回一个语法列表参数：语句字符串返回：一个简单的语法列表，tokens'''# 默认空格分隔。所以需要将括号添加空格，以便分隔出来tokens = s.replace('(',' ( ').replace(')',' ) ').split()# 判断括号对if tokens.count('(') != tokens.count(')'):print('括号对不一致！')returnreturn tokensdef read_from_tokens(tokens):'''解析list语义分析：将tokens组装成抽象语法树参数：语法列表返回：抽象语法树列表如果tokens长度为零直接返回去掉tokens第一个字符如果第一个字符是（ ，定义一个空列表用来存放语法树，如果tokens第一个字符不是 ），循环将同级语法树存到列表，碰到 ）直接去掉，返回这一层语法树其它情况返回字符，如果是数字就返回数字，其它的返回字符串'''if not isinstance(tokens, List):return if len(tokens) == 0:print('不能为空')return# list去掉第一位元素，如果不是（ 就将它转换类型后加入列表中token = tokens.pop(0)# 第一个字符是(，然后建立表达式列表，直到匹配到 ）if '(' == token:# 这里定义空list是为了抽象语法树的嵌套关系L = []# 语法树第一个字符是）一定是错误语法while tokens[0] != ')':# 将括号以外的字符加进list中# 这里的递归是为了用多维数组展示抽象语法树的嵌套关系，同级的字符放在一个list中token_key = read_from_tokens(tokens)L.append(token_key)# 删除括号结束符 ）,如果不删除的话，碰到 ）就无法循环下去，只能得到部分语法树tokens.pop(0)# 返回同级数据return Lelif ')' == token:print('语法错误')else:# 返回字符，如果数字转成整数或者浮点类型，其它都是字符串return atom(token)def atom(token):'''字符串类型转换Lispy 的 tokens 是括号、标识符和数字'''try: return int(token)except ValueError:try: return float(token)except ValueError:return Symbol(token)# python3 不存在apply，所以这里自己定义一个
def apply(func, *args, **kwargs):return func(*args, **kwargs)def _add(*datas):# 加法，支持多数字，多字符串 (+ 1 2 3 4)，(+ "a" "b" "c")if len(datas) > 0:if isinstance(datas[0], int) or isinstance(datas[0], float):sum_num = 0for data in datas:sum_num = sum_num + datareturn sum_numif isinstance(datas[0], str):sum_num = ""for data in datas:sum_num = sum_num + data.replace('\"', '')return '\"' + sum_num + '\"'def _sub(*datas):# 减法，支持多数字 (- 9 2 1)sub_num = 0for data in datas:if len(datas) > 1 and sub_num == 0:sub_num = dataelse:sub_num = sub_num - datareturn sub_numdef _mul(*datas):# 乘法，支持多数字 (* 2 3 4)mul_num = 1for data in datas:mul_num = data * mul_numreturn mul_numdef _truediv(*datas):# 除法，支持多数字 (/ 8 4 2)truediv_num = 1for data in datas:if truediv_num == 1:truediv_num = dataelse:truediv_num = truediv_num / datareturn truediv_numdef _to_char(char_data):# char 转化 字符 #\a，字符 a，判断是否是charif isinstance(char_data, str):pattern = re.compile(r'(^#\\)([\S]{1})')match = pattern.search(char_data)if match:return char_datadef _to_string(str_data):# string 转化 字符串 "aa"，判断是否是字符串# 字符串，为了显示区分添加"if isinstance(str_data, str):pattern = re.compile(r'(^\")(\S*)(\"$)')match = pattern.search(str_data)if match:return str_datadef _map(fn, *datas):# python3的map返回一个迭代器，所以这里需要处理一下，返回listdatas = map(fn, *datas)new_datas = []# for data in datas:# new_datas.append(data)try:while True:line = next(datas)if line is None:breaknew_datas.append(line)except StopIteration:passreturn new_datas# ====== 第五步 重定义环境 =========# ====== 将Env环境定义成class =======
class Env(dict):'''Env继承dict类'''def __init__(self, parms=(), args=(), outer=None):# 构造函数# 初始化环境，zip可以直接转化成dictself.update(zip(parms, args))# 全局环境self.outer = outerdef find(self, var):# 查找环境，这个是为了后面的局部环境和全局环境# 如果存在在局部环境中返回局部环境，没有就去全局环境找return self if (var in self) else self.outer.find(var)class Procedure(object):'''这个可以看作一个创造局部环境和外部环境的函数'''def __init__(self, parms, body, env):# 构造函数'''parms 是参数名body 是表达式env 是外部环境'''self.parms = parms self.body = body self.env = envdef __call__(self, *args):# 调用对象的时候执行'''执行表达式，但是将上层的环境当作外部环境，将这一层的参数名与实际值设置为局部环境'''return eval(self.body, Env(self.parms, args, self.env))# ======= 第二步 设置环境 =======# ====== 环境 =======
'''
环境是指变量名与值之间的映射。eval 默认使用全局环境，包括一组标准函数的名称（如 sqrt 和 max，以及操作符 *）
'''
def standard_env():'''简单的标准环境环境是一个字典形式，将环境中添加标准库，或者自己定义的函数'''env = Env() # 环境是一个字典形式# vars函数是python自带函数 返回对象object的属性名和属性值的字典形式env.update(vars(math)) # sin, cos, sqrt, pi, ...# 添加一些符合Scheme标准的环境env.update({# '+':op.add, # '-':op.sub, # '*':op.mul, # '/':op.truediv,'+': _add,'-': _sub,'*': _mul, '/': _truediv, '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, '%': op.mod,# 'add': op.add,# 'sub': op.sub,# 'mul': op.mul,# 'truediv': op.truediv,# 'add': _add,# 'sub': _sub,# 'mul': _mul,# 'truediv': _truediv,'mod': op.mod,'abs': abs,'append': op.add, 'apply': apply,'begin': lambda *x: x[-1],'car': lambda x: x[0],'cdr': lambda x: x[1:], 'cons': lambda x, y: [x] + y if isinstance(y, List) else [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),'#t': True,'#f': False,# (vector 1 "2" 3 "4") 类似列表的，我就用列表表示了# 'vector': lambda *x: '#'+schemestr(list(x)), 'boolean?': lambda x: True if x else False,'string?': lambda x: True if _to_string(x) else False,'char?': lambda x: True if _to_char(x) else False,# 'display': print})# 返回这个环境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)quote 语句：(quote exp)例子：(quote (1 2 3))set! 语句：(set! var exp)例子：(set! x 1) 注意：set! 是修改已经定义的变量，没有定义就使用会报错lambda 语句：(lambda (var...) body)例子：(lambda (x) (+ x x))注意：lambda 匿名函数需要定义以后使用 (define xx (lambda (x) (+ x x)))，用(xx 4)方式调用let 语句：(let ((var val) ...) exp)例子：(let ((f +) (x 2)) (f x 3)) 其实就是把加法赋值给f，把3赋值给x，然后计算(let ((x 2) (y 3)) (+ x y)) x=2，y=3，x+y(let ((double (lambda (x) (+ x x))))(list (double (* 3 4))(double (/ 99 11))(double (- 2 7))))begin 语句：(degin exp....)例子：(define x 1)(begin (set! x 1) (set! x (+ x 1)) (* x 2))display 语句：例子：(display "a") 相当于python的print实现python的range函数：例子：(define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))(range 0 10)注意：Scheme 没有for，whlie，所以循环用递归代替map 语句：例子：(define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))(define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))(map fib (range 0 20))list ：例子 (list 1 2 3 4)实现python中list的count函数：例子：(define count (lambda (item L) (if L (+ (equal? item (car L)) (count item (cdr L)))(count 0 (list 0 1 2 3 0 0))'''if isinstance(x, Symbol):# 字符 #\a，字符 achar_data = _to_char(x)if char_data:# 返回字符return char_data# 字符串，为了显示区分添加"str_data = _to_string(x)if str_data:# 返回字符串return str_data# 如果是字符就去环境中找，返回变量值或者函数# 这样可以根据调用去局部环境或者外部环境查找data = env.find(x)[x]return data# 常量返回elif not isinstance(x, List):return x elif x[0] == 'quote':# (quote exp)# (quote (1 2))(_, exp) = x# quote 就是原样输出表达式return exp# if 语句，形式(if test conseq alt),test是判断条件,符合条件输出conseq,不符合输出altelif x[0] == 'if':# (if test conseq alt)# (if (> 1 2) 1 2)# 语句形式分别赋值(_, 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':# (define var exp)# (define x 1)(_, var, exp) = x# 用递归计算数据# 将定义的数据加进环境中# 用递归是因为如果exp是个表达式，就计算出它的值再加入环境env[var] = eval(exp, env)elif x[0] == 'set!':# (set! var exp)# (set! x 1)，注意这里的x必须先定义过，也就是环境中必须有(_, var, exp) = x# set! 其实是一个覆盖环境值的操作，用递归也是因为如果exp是个表达式，就计算出它的值再加入环境env.find(var)[var] = eval(exp, env)elif x[0] == 'lambda':# (lambda (var...) body)# (lambda (x) (+ x x))，这样其实无法调用，一般用(define xx (lambda (x) (+ x x))) 定义，(xx 3)调用(_, parms, body) = x'''这里就用到了Procedure类因为lambda匿名函数的参数都是局部的，外面是无法调用的，所以这里先保存参数名，表达式，将env当作外部环境(因为可能会用到外部环境的变量)当调用的时候将值传入，与参数名配对，当作局部环境'''return Procedure(parms, body, env)elif x[0] == 'let':# (let ((var val) ...) exp1 exp2 ...)(_, var, exp) = x# 将定义分别加进环境中for data in var:env[data[0]] = eval(data[1], env)# 最后执行return eval(exp, env)else:'''Schema 计算形式第一个元素是计算符号:(+ 1 2)'''# list第一个元素去环境里去找这个函数# (proc arg...)proc = eval(x[0], env)# list后面的元素是函数参数args = [eval(exp, env) for exp in x[1:]]# 将参数传入函数data = proc(*args)return data# ======== 交互式 ========
def repl(prompt='lis.py> '):'''终端交互式，死循环读取终端输入字符串，执行，转换成字符串，打印到终端'''# 这里学习python的交互式加入提示sys.stderr.write('-*- lispy 0.01 -*- Quit using \'exit()\'\n')# 死循环读取终端输入while True:data_str = input(prompt)# 防止不输入程序报错if data_str:# python交互式一样，输入exit()结束程序if data_str == 'exit()':sys.exit()# 执行val = eval(parse(data_str))if val is not None:# 打印 print(schemestr(val))def schemestr(exp):"""将数据转位字符串"""if isinstance(exp, List):# 将列表中所有元素转成字符串，用空格分隔，开始结束加上括号return '(' + ' '.join(map(schemestr, exp)) + ')'elif isinstance(exp, bool):# bool 转化 #t: true，#f: flaseif exp:return '#t'else:return '#f' else:# 转成字符串return Symbol(exp)repl()
以下是原文的测试，我自己跑过也是没有问题的，大家可以试试
lis.py> (define circle-area (lambda (r) (* pi (* r r))))
lis.py> (circle-area 3)
28.274333877
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
lis.py> (fact 10)
3628800
lis.py> (fact 100)
9332621544394415268169923885626670049071596826438162146859296389521759999322991
5608941463976156518286253697920827223758251185210916864000000000000000000000000
lis.py> (circle-area (fact 10))
4.1369087198e+13
lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4
lis.py> (define twice (lambda (x) (* 2 x)))
lis.py> (twice 5)
10
lis.py> (define repeat (lambda (f) (lambda (x) (f (f x)))))
lis.py> ((repeat twice) 10)
40
lis.py> ((repeat (repeat twice)) 10)
160
lis.py> ((repeat (repeat (repeat twice))) 10)
2560
lis.py> ((repeat (repeat (repeat (repeat twice)))) 10)
655360
lis.py> (pow 2 16)
65536.0
lis.py> (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
lis.py> (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
lis.py> (range 0 10)
(0 1 2 3 4 5 6 7 8 9)
lis.py> (map fib (range 0 10))
(1 1 2 3 5 8 13 21 34 55)
lis.py> (map fib (range 0 20))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)我在原有的基础上添加了一些函数，然后添加了字符串，因为布尔值的表示是#t，#f所以我也改变了显示方式，也增加了一些语法判断，然后是交互式的缓存和正常退出程序
最近几天一直学习这个教程，对于Scheme的语法大致有了一些了解，整个解释器其实很简单，也很简陋，只能算一个计算器
接下来就要开始学习《计算机程序的构造和解释》这本书了，加油！！！！
这里还有一个几十种语言实现lisp解释器的项目，有一步步实现解释器的步骤，也有别人实现的源码
github地址
中文翻译github地址
这篇关于《计算机程序的构造和解释》阅读笔记：准备（3）【python3简单实现lisp解释器（3）】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
