Python写Lisp解释器（一、parse部分）

May 16, 2017

这是一篇Lisp解释器的教程。参考国外某大神的Lisp（其实是其中的一种叫做Scheme的方言）的解释器的过程。

正好在学编译原理，准备搞一些事情，这个project纯当一个搞事情的前奏。因为一年多前简略的看过了SICP，所以对LISP语言有一定小小的理解，所以开一个LISP语言的解释器，对编译上的理解可能会非常的有帮助。

另外，国内能够自主写出编译器的人实在是太少，这一行业上可能更多的引用国外大神的博客内容，所以搬运和翻译加上自主原创的这种过程也是极有必要的。

作者：岐山凤鸣，引用请加上本站域名

内容：作者原创

参考：http://norvig.com/lispy.html

参考：http://blog.jobbole.com/47659/

插曲：这么久没有更新，很大一部分原因因为数据丢失，有道云笔记略坑。

概述

整个项目分成三个部分来运作，parse, eval和lis，代表的意思分别是解析，执行和两者的结合。

Scheme语法很神奇，每一个块都是(操作类型 操作数1 操作数2)这样的前缀表达式的构造，和C++那种语言不一样，但很强大。其中操作数可以嵌套，比如4+5+6可以写作:

(+ 4 (+ 5 6))

关于Scheme的语法这里不作赘述，想要了解者可以看看SICP，或者参考我未来会写的整体的翻译教程

parse的作用就是将Scheme代码翻译成树状，在Python中，可以参考如下过程：

>>> code = '(+ 4 (+ 5 6))'
>>> parse(code)
['+', 4, ['+', 5, 6]]

>>> code = '(define x 123)'
>>> parse(code)
['define', 'x', 123]

>>> code = '(display "hello world")'
>>> parse(code)
['display', ['quote', '"hello world"']]

而eval的作用就是将parse形成的list执行，得到正确的返回结果，可以参考如下过程：

>>> code = '(+ 4 (+ 5 6))'
>>> eval(parse(code))
15

>>> code = '(define x 123)'
>>> eval(parse(code))
123

>>> code = 'display "hello world"'
>>> eval(parse(code))
hello world

那么lis的作用就很有趣了，也就是起到一个eval(parse(code))的作用，提供一个交互，这里最后再说。

所以我们今天这一节开始的就是Parse部分，将输入的code形成一棵列表树。

前置工作

(操作类型 操作数1 操作数2)的这种模式，首先要有一些操作类型，这里前置工作先定义一批操作类型，都用字符串来表示：

Symbol = str
symbolTable = {}
def Sym(s):
	if s not in symbolTable:
		symbolTable[s] = Symbol(s)

_quote = Sym('quote')
_if = Sym('if')
_set = Sym('set!')
_define = Sym('define')
_lambda = Sym('lambda')
_begin = Sym('begin')
_definemacro = Sym('define-marco')
_quasiquote = Sym('quasiquote')
_unquote = Sym('unquote')
_unquotesplicing = Sym('unquote-solicing')
_checkexpect = Sym('check-expect')
_checkwithin = Sym('check-within')
_member = Sym('member?')
_struct = Sym('struct')

这上面定义了一系列的符号，如果操作类型不在这些符号里，那么说明语法就出错了。

然后就是收集传入的代码，根据空格分割成一个正常的记号流：

def tokenize(code):
	code = code.replace('(', ' ( ').replace(')', ' ) ')
	code = code.replace('\"', ' \" ').replace(';', ' ;').split()
	return code

>>> tokenize('(+ 4 (/ 5 6))')
['(', '+', 4, '(', '/', 5, '6', ')', ')']

到这里前置工作也就结束了。

将记号流转换为树形结构

根据上面的tokenize(code)可以得到code的记号流，那么接下来就是解析成树形列表结构，先上代码：

def read_from_tokens(tokens):
	if len(tokens) == 0:
		raise SyntaxError('*** Unexpected EOF while reading')

	token = tokens.pop(0)
	
	if '(' == token:
		L = []
		while tokens[0] != ')':
			L.append(read_from_tokens(tokens))
		tokens.pop(0)
		return L

	elif '"' == token:
		L = []
		while tokens[0] != '"':
			L.append(read_from_tokens(tokens))
		end_quote = tokens.pop(0)
		string = token
		string += " ".join(L)
		string += end_quote
		return ["quote", string]

	elif ';' == token:
		L = []
		L.append(token)
		while tokens[0] != '\n':
			L.append(read_from_tokens(tokens))
		new_line = tokens.pop(0)
		L.append(new_line)
		string = " ".join(L)
		return ["quote", string]

	elif ')' == token:
		raise SyntaxError('*** Unexpected ) appears')
	else 
		return atom(token)

解释起来也很简单，首先先判断传入的列表tokens是否为空，为空铁定出错了。

然后拿出token的首元，进行下列的树形解析：

如果首元是左括号(，那么返回直到右括号的解析后的列表

如果首元是双引号，那么返回到另一个双引号的位置的列表为止后，加上双引号和quote表示字符串

如果首元是分号，那么返回这一行结束为止的所有的，因为分号是行注释的意思，你懂得。

如果出现了不该出现的反括号，干掉它

如果是其他的东西，那么应该就是原子符号了，调用atom函数得到原子符号，atom函数定义如下：

def atom(token):
	try: return int(token)
	except ValueError:
		try: return float(token)
		except: ValueError:
			return Symbol(token)

意思很简单，先尝试返回整数，不对就返回浮点，再不对就返回定义的那一批符号，还不对就结束。

那么我们也就写完了parse,

def parse(code):
	return read_from_tokens(tokenize(code))

举几个例子

还是举我们开头的几个例子：

>>> code = '(+ 4 (+ 5 6))'
>>> parse(code)
['+', 4, ['+', 5, 6]]

首先tokenize函数将code做成记号流：

>>> tokenize(code)
['(', '+', 4, '(', '+', '5', '6', ')', ')']

然后read_from_tokens函数将tokenize得到的记号流解析成树形:

>>> read_from_tokens(tokenize(code))
['+', 4, ['+', 5, 6]]
  • 在read_from_tokens中的调用情况如下：
    • step1: 首先tokens弹出(,然后找到它配对的右括号，将中间内容保存在L中，这个过程入栈后发现内嵌的第二个(
    • step2: 在第二个(同样操作，L = [’+’, 5, 6], 然后弹栈返回step1, 得到step1的L = [’+’, 4, [’+’, 5, 6]]

到此结束

其他的情况也如上述过程一样，比较简单。

至此，我们一个简易解析器的parse就已经做完了。

parse部分所有代码（v1.1版本）：

# parse.py

Symbol = str
symbolTable = {}
def Sym(s):
	if s not in symbolTable:
		symbolTable[s] = Symbol(s)

_quote = Sym('quote')
_if = Sym('if')
_set = Sym('set!')
_define = Sym('define')
_lambda = Sym('lambda')
_begin = Sym('begin')
_definemacro = Sym('define-marco')
_quasiquote = Sym('quasiquote')
_unquote = Sym('unquote')
_unquotesplicing = Sym('unquote-solicing')
_checkexpect = Sym('check-expect')
_checkwithin = Sym('check-within')
_member = Sym('member?')
_struct = Sym('struct')

def tokenize(code):
	code = code.replace('(', ' ( ').replace(')', ' ) ')
	code = code.replace('\"', ' \" ').replace(';', ' ;').split()
	return code
def read_from_tokens(tokens):
	if len(tokens) == 0:
		raise SyntaxError('*** Unexpected EOF while reading')

	token = tokens.pop(0)
	
	if '(' == token:
		L = []
		while tokens[0] != ')':
			L.append(read_from_tokens(tokens))
		tokens.pop(0)
		return L

	elif '"' == token:
		L = []
		while tokens[0] != '"':
			L.append(read_from_tokens(tokens))
		end_quote = tokens.pop(0)
		string = token
		string += " ".join(L)
		string += end_quote
		return ["quote", string]

	elif ';' == token:
		L = []
		L.append(token)
		while tokens[0] != '\n':
			L.append(read_from_tokens(tokens))
		new_line = tokens.pop(0)
		L.append(new_line)
		string = " ".join(L)
		return ["quote", string]

	elif ')' == token:
		raise SyntaxError('*** Unexpected ) appears')
	else:
		return atom(token)

def atom(token):
	try: return int(token)
	except ValueError:
		try: return float(token)
		except ValueError:
			return Symbol(token)

def parse(code):
	return read_from_tokens(tokenize(code))

# test

parse('(+ 4 (+ 5 6))')