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

本文主要是介绍《计算机程序的构造和解释》阅读笔记:准备(1)【python3简单实现lisp解释器(1)】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

(How to Write a (Lisp) Interpreter (in Python))网站

完整的代码在网站最下面也可以下载

原本中应该使用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,返回一个语法列表'''# 默认空格分隔。所以需要将括号添加空格,以便分隔出来# 获取一个简单的语法列表,tokensreturn 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 Lelse:# 返回字符,如果数字转成整数或者浮点类型,其它都是字符串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)

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

def tokenize(str):'''字符串转list词法分析:也就是将输入字符串分成一系列 token,返回一个语法列表'''# 默认空格分隔。所以需要将括号添加空格,以便分隔出来# 获取一个简单的语法列表,tokenstokens = 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 opSymbol = str  # 字符串
List   = list  # 列表
Number = (int, float)  # 数字
Env = dict  # 环境# ======= 第一步 解析语法 =======# ======== 解析语法 ========
def parse(program):'''语法解析函数返回抽象语法树,多维数组形式展示嵌套关系'''return read_from_tokens(tokenize(program))def tokenize(str):'''字符串转list词法分析:也就是将输入字符串分成一系列 token,返回一个语法列表'''# 默认空格分隔。所以需要将括号添加空格,以便分隔出来# 获取一个简单的语法列表,tokensreturn 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 Lelse:# 返回字符,如果数字转成整数或者浮点类型,其它都是字符串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 = 0for data in datas:sum_num = sum_num + datareturn sum_numdef _sub(*datas):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):mul_num = 1for data in datas:mul_num = data * mul_numreturn mul_numdef _truediv(*datas):truediv_num = 1for data in datas:if truediv_num == 1:truediv_num = dataelse:truediv_num = truediv_num / datareturn truediv_num

 

三:执行

'''
语言的语法是指组成正确的语句或表达式的顺序,语义指那些表达式或语句的内在含义。解释器流程
程序 => 解析 => 抽象语法树 => 执行(语义) => 结果1:解析语法
2:添加环境
3:执行'''import math 
import operator as opSymbol = 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 Lelse:# 返回字符,如果数字转成整数或者浮点类型,其它都是字符串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,不符合输出altelif 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)

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

 

这篇关于《计算机程序的构造和解释》阅读笔记:准备(1)【python3简单实现lisp解释器(1)】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110767

相关文章

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一