篇1中可以将字符串解析成Python的list的形式, 用编程术语叫做: 解析出语法树.
篇2中可以实现表达式的求值. 根据操作符, 跳转到相应的求值分支.
以上功能, 仅仅实现了一个计算器的功能. 离变成编程语言还差了: 函数定义和调用. 那么,
篇3来实现函数定义, 即lambda的定义与解释.
import re
# 解析字符串(源代码), 生成树法树(AST)
def parse(expt, exception=True):
expt = re.sub("\(", " ( ", expt)
expt = re.sub("\)", " ) ", expt)
res = []
for i in expt.strip().split():
if i != ')':
if re.match("^[0-9]+$", i):
i = int(i)
elif re.match("^[0-9][0-9.]*$", i):
i = float(i)
res.append(i)
if i == ')':
tmp = []
while res and res[-1] != '(':
tmp.insert(0, res.pop())
if res: res[-1] = tmp
if '(' in res:
if exception:
print('parse error: 括号不匹配')
raise ValueError()
return res
# 求值函数eval(): 解析每个语句中的基本元素, 函数名,变量名,立即数,运算符号等.
# 然后调用apply()执行
global_env={}
def eval(expt, env):
if type(expt) is list:
if expt[0] == 'define': # 添加一个全局条目
env[expt[1]] = eval(expt[2], env)
print('new symbol defined: %s'% expt[1])
elif expt[0] == 'quote':
return expt[1]
elif expt[0] == 'lambda': # lambda和当时的环境形成一个闭包!
saved_env = env.copy() # (变量的捕获)
return [expt[0], expt[1], expt[2:], saved_env]
elif expt[0] == 'cond': # 分支结构,相当于switch...case
for p,t in expt[1:]: # 遍历所有条件,找到第一个True,或else
if p=='else' or eval(p, env)==True:
return eval(t, env)
else: # # 递归解析所有符号, 然后apply执行
expt = [eval(i, env) for i in expt]
return apply(expt[0], expt[1:])
elif type(expt) is int or type(expt) is float:
return expt # int/float条目返回自身即可
elif expt in ['+','-','*','/','=','<','>', 'zero?', 'null?']:
return [expt] # 基本运算符返回自身
elif expt in env:
return env[expt] # 先搜索: 局部变量/符号
elif expt in global_env:
return global_env[expt] # 后搜索: 全局变量/符号, 所以局部变量覆盖全局变量
else:
print('symbol not defined: %s'%expt)
raise NameError()
def apply(expr, args):
if expr[0] == '+': return args[0] + args[1]
elif expr[0] == '-': return args[0] - args[1]
elif expr[0] == '*': return args[0] * args[1]
elif expr[0] == '/': return args[0] / args[1]
elif expr[0] == '=': return args[0] == args[1]
elif expr[0] == '<': return args[0] < args[1]
elif expr[0] == '>': return args[0] > args[1]
elif expr[0] == 'zero?': return 0 == args[0]
elif expr[0] == 'null?': return 0 == len(args[0])
elif expr[0] == 'lambda':
pars, body, env = expr[1:]
for k,v in zip(pars, args): env[k] = v # 形参/实参->env表
##print ('lambda', pars, body, '----', env) # debug
for i in body: ret = eval(i, env) # 求值
return ret # 返回
def run(code):
try:
ast = parse(code) # 解析语法树
for i in ast: # 爬树求值
v = eval(i, global_env)
if v is not None: print(v)
except:
pass
if __name__ == '__main__':
print ('-'*60)
print ('welcome to yet another lisp interpreter by jia.')
print ('version 0.01')
print ('have fun!')
print ('-' * 60)
while True:
code = input("jia-λ > ") #提示符:输入代码
for i in range(99):
ast = parse(code, exception=False) #预解析
unfold = (ast.count('(')) #未配对的'('表示未完待续
indent = (9+3*unfold)*' ' #按未配对的'('的个数缩进
if unfold == 0 or ';' in code:
break
code += ' ' + input(indent) #下一行继续输入,自动缩进
run(code)
以上代码和一上篇的代码, 主要增加了lambda的处理, 新增加代码如下:
def eval(expt, env):
if type(expt) is list:
... ...
elif expt[0] == 'lambda': # lambda和当时的环境形成一个闭包!
saved_env = env.copy() # (变量的捕获)
return [expt[0], expt[1], expt[2:], saved_env]
处理lambda段, 是在当下环境构造一个闭包. 并返回这个闭包. 这里不求值.
碰到lambda关键字, 说明这一个段落为一个closure, 一些编程语言叫它闭包. 则在定义lambda的当下, 将当前的现场环境保存起来, 这个在一些编程语言中叫做变量捕获.
这里仅仅是把环境存起来, 并不着急着求出值. 这在一些编程语言中叫: 惰性求值.
那么在那里求值呢, 可以看到Apply一节有增加几行代码, 如下:
def apply(expr, args):
... ...
elif expr[0] == 'lambda':
pars, body, env = expr[1:]
for k,v in zip(pars, args): env[k] = v # 形参/实参->env表
for i in body: ret = eval(i, env) # 求值
return ret # 返回
处理闭包, 则是解开闭包, 取出保存的环境, 完成求值并返回值.
lambda关键字后面是pars参数表, body函数体, env刚才打包的变量捕获. 这里pars/body/env都不是一个简单的值, 可能是一组值.
完成这些工作, 先code=‘(+ 2 3)’, 再run(code). 便 可以执行代码, 并输出结果了.
但感觉不优雅啊.
最后面的__main__函数, 则是写了一个主循环, 不停在从命令行接收用户输入的lisp语句, 并执行.
有了命令行输入的处理, 这便更像一个解释器了.
舒服了.
以上代码保存为xxx.py, 直接运行即可. 效果如下:
