本教程使用 Python 实现了一个小型 Python 解释器。它能够解释执行以下代码
def manda(m, a): def sky(s): return s + 4 def sea(s): return s * 2 return m + a - sea(m) * sky(a) x = 4 y = 2 manda(x, y)给出缩进不当的代码，如下面的 d = c + 1
b = 10 def sky(a): c = b * 2 d = c + 1 return d * a sky(b)标准 Python 的错误提示为
File "error.py", line 4 d = c + 1 ^ IndentationError: unexpected indent本项目的错误提示为
Exception: bad indent in row 4, col 7很不错吧？只要多写几行代码，就可以复现标准 Python 的错误提示了 ：）
总代码量
psp.py : 345 test_psp.py : 113 ---------------------------- total : 458 不到 400 行的代码里可塞不下很多东西呢。鉴于之前的 EoC 系列介绍了许多解释器和编译器的内容，为了与之互补，这次教程的重点在于编译器的前端，也即 lexer 和 parser。解释器方面支持以下内容：
- 数据类型：整型
- 词法作用域的函数，支持嵌套
- 变量定义
- 二元操作符（+-*/）及小括号
如你所见，这个项目还有广阔的天地可以拓展呢！比如 if，for，布尔运算等等……
我将详细解释以下内容
- 一个简单而不失强大的 scanner (lexer)
- Python 缩进代码块的解析
- message passing 范式的环境表示
- 基于优先级的二元运算符的解析
- Python 函数的解释运行
如果你在玩的时候发现解释错误，很可能是一些边边角角没有被覆盖，比如不支持写成一行代码块def my(f): return f，相信你可以完善它！
scan 阶段分两步走：第一步，先把所有类型的 token 都保留下来，包括所有的空格和换行。其中，需要特别注意的是运算符的解析，比如
a = fn(x+b, c*d)注意到+、*两边不存在空格，所以不能依赖空格来分 token，而且这样的运算符可以包含多个字符，如+=，<=。实际上，这些运算符分开了多个操作数，所以我称之为delimiter，用一个标记parse_delimiter来指导解析。
第二步，得到基础的 token 流之后，我们只保留每行第一个空白区域，因为 Python 的缩进只关心第一个。同时，计算出每一个 token 的位置，即行与列。
让我们先写scan，建立一个叫psp.py的文件，写入
def scan(s): delimiter = '~+-*/=<>%' # 支持的符号 parse_delimiter = False # 标识是否正在解析 delimiter token = '' # 初始 token现在我们遍历字符串 s，以下是 for 语句的主体
for c in s: if parse_delimiter: # 当前正在解析 delimiter if c in delimiter # 遇到 c 仍然是 delimiter，加到原来的 token 上 token += c # 可以解析如 <= => += 这样的 token else: # 遇到 c 不是 delimiter parse_delimiter = False # 说明 delimiter 解析完毕，返回 yield token # NOTE: 代码块1... else: # 当前没有解析 delimiter if c in delimiter: # 遇到一个 delimiter yield token # 说明当前的 token 解析完毕，返回 parse_delimiter = True # token = c # 可以解析如 + - * / 这样的 token else: # NOTE: 代码块2...我们现在已经搞定 delimiter 的解析了，现在看看其他的符号。我们先写代码块1的情况。（注意，我忽略了代码的缩进）
if is_num_alpha(c) or c == ' ': token = c elif c in '()' or c == ':' or c == ',' or c == '\n': yield c token = ''因为字母和空格都可以累加（即多个写在一起），所以我们先把c存到token中，以等待后续相同的字符。其他如括号，冒号，逗号，换行，不能叠加，所以必须返回，同时将 token 清空。
这里的is_num_alpha定义
import string def is_num_alpha(c): return c in string.ascii_letters or c in string.digits现在我们看看代码块2，先看数字字母的解析
if is_num_alpha(c): if token and all_space(token): # token 是空白，而 c 是数字或者字母 yield token # 说明空白解析完成，返回 token = '' # token += c # 否则，正在解析数字字母，需要累加然后是空白的解析
elif c == ' ': if all_space(token): # parse space token += c else: yield token # 原 token 解析完成 token = c # 开始解析空白括号、换行、冒号、逗号。这四个家伙又组团了。
elif c in '\n():,': if token != '': # 只要当前不为空，即视为 token 解析完成 yield token token = '' yield c # 本身作为独立符号返回这就是代码块2的全部了，我们忽略了其余的符号。
最后加一句
def scan(s): # .. if token: yield token确保最后一个 token 也被返回了。这是函数 scan。我们用到了一个简单的函数all_space。
def all_space(s): return all(c==' ' for c in s)接下来，我们做第二步，即保留必须的 indent（缩进），忽略其他空白符，并计算每个 token 的位置信息。我们将之命为rescan
虽然叫
rescan，但scan返回了一个生成器，rescan直接对着生成器的每个输出操作，因此，我们只遍历了一次s而已。
我们的思路是这样子的：对于每个 token
- 如果是空白符，检测是否为行首；如果是，则计算它的行列信息并一起返回，如果不是，则忽略，但仍更新列信息
- 如果是换行符，设行首标志为真，连同它的行列信息一起返回，同时更新行列信息
- 如果是其他符号，只计算行列信息并一起返回
def rescan(self, tokstream): "re-scan to remove useless token and generate start and end mark for every token" row = 1 col_s = 1 col_e = 0 newline = False for token in tokstream: if all_space(token): # 空白符，且处于行首 if newline: newline = False col_e = col_s + len(token) yield token, [row, col_s, col_e] # 这里返回了行首的缩进 col_s = col_e else: # 如果不是行首的空白符，就忽略掉 col_s = col_s + len(token) # 但仍要更新列起始坐标 elif token == '\n': newline = True col_e = col_s + 1 # 换行符，需要更新行坐标和列坐标 yield token, [row, col_s, col_e] row += 1 col_s = 1 else: # 其他符号，更新坐标即可 newline = False col_e = col_s + len(token) yield token, [row, col_s, col_e] col_s = col_e yield None, [0, 0, 0]最后，当 tokenstream 结束了，我返回 None 作为标志。
这就是了！
因为在后文，我采用的是递归下降的方法来解析，需要缓存当前的一个 token，所以我用一个类包装起上面俩函数。定义如下：
class Scanner: def __init__(self, s): self.s = s self.tokstream = self.rescan(self.scan(s)) self.token = None def next_token(self): self.token = next(self.tokstream) return self.token def scan(self, s): # .. def rescan(self, tokstream): # ..这里，token 成为一个缓存！现在测试一下吧！
建一个叫test_psp.py的文件，写入
from psp import Scanner def test_scanner1(): s = "y = (x + 1)" scan = Scanner(s) assert("y" == scan.next_token()[0]) assert("=" == scan.next_token()[0]) assert("(" == scan.next_token()[0]) assert("x" == scan.next_token()[0]) assert("+" == scan.next_token()[0]) assert("1" == scan.next_token()[0]) assert(")" == scan.next_token()[0])需要安装好pytest，然后运行
pytest测试通过即是胜利！更多的测试用例可见代码
这一节，我们定义抽象语法树，也即语言的语义。我们支持一种数据类型（整型），变量及函数的定义。此外，支持二元运算和函数调用。所有这些，我都称之为表达式。
class PyExpr: pass定义变量
class PyVar(PyExpr): def __init__(self, name): super().__init__() # 可省略 self.name = name def __repr__(self): return f"PyVar({self.name})" def __eq__(self, other): return other.name == self.name通过实现__eq__，我重载了==运算符。__repr__指定了使用print时输出的格式，间接地指定了使用str时输出的格式。
定义整型
class PyInt(PyExpr): def __init__(self, val): super().__init__() self.val = val def __repr__(self): return f"{self.val}" def __eq__(self, other): return self.val == other.val def __add__(self, other): return PyInt(self.val + other.val) def __sub__(self, other): return PyInt(self.val - other.val) def __mul__(self, other): return PyInt(self.val * other.val) def __truediv__(self, other): return PyInt(self.val // other.val)我重载了额外四个算术运算符，注意/重载时使用了整除运算//。
Python 的每个函数都会有返回值，如果没有return语句，返回值为None。我采用了这个语义，所以我们也需要一个Null
class PyNull(PyExpr): def __init__(self): super().__init__() def __repr__(self): return "PyNull"接着是赋值语句
class PyDefvar(PyExpr): def __init__(self, var, val): super().__init__() self.var = var self.val = val def __repr__(self): return f"PyDefvar({self.var}, {self.val})"函数定义
class PyDefun(PyExpr): def __init__(self, name, args, body, env): super().__init__() self.name = name self.args = args self.body = body self.env = env def __call__(self, params): assert(len(params) == len(self.args)) for (name, val) in zip(self.args, params): self.env = extend(name, val, self.env) # function always have a return value res = list(interpret(self.body, self.env)) return res[-1] def __repr__(self): return f"PyDefun({self.name})"我这里的定义不是很好，因为我把函数定义本身变成了一个函数，而这两者是有所不同的。但就这样吧，读者可任意更改。
函数的定义，我们需要函数名，参数，函数体，以及它被定义时的环境，因为我们实现的是词法作用域的函数。我重载了__call__，这使得PyDefun可以调用。调用时，先将参数传入环境，然后逐行解释body的内容。这里的interpret是解释器入口函数，我们返回body中最后一行的运行结果。等我们写到interpret时，读者可回看这一部分的内容，相信会更加清晰。
最后，我们还需要函数调用以及二元运算
class PyCall(PyExpr): def __init__(self, fn, args): super().__init__() self.fn = fn self.args = args def __repr__(self): return f"PyCall({self.fn})"class PyOp2(PyExpr): def __init__(self, op, e1, e2): self.op = op self.e1 = e1 self.e2 = e2 def __repr__(self): return f"({self.op} {self.e1} {self.e2})"注意到二元运算的__repr__中，采用了LISP的格式。
现在来到本次教程的重点部分了。我们可以先分析一下 Python 的代码组织形式。
一个 Python 程序是由许多的表达式（expr）构成的。通常来讲，一个 expr 占一行。多个 expr 可以以代码块的方式组织。以冒号:标识代码块的开始。每个代码块都有它的缩进（indent）。可以声明新的块的语句有def、if、for、while、class等等。
一个块可以包含多个块。如下示例代码中，全局块含了四个 expr：一个 PyDefun，两个PyDefvar，一个PyCall。其中的PyDefun又包含了两个PyDefun和一个PyOp2，而这个PyOp2又包含了更多的PyOp2和PyCall。全局块的缩进为 0，manda的缩进为 4，而sky和sea的缩进为 8。
def manda(m, a): def sky(s): return s + 4 def sea(s): return s * 2 return m + a - sea(m) * sky(a) x = 4 y = 2 manda(myadd(x, y), mysub(y, x))这个例子展示了我们将定义的语言方方面面的特性，如果在解析时有所困惑，可以回来看看这个例子。
我将采用递归下降的方式来解析，这里采用的文法也被称为LR(1)。
def parse_expr(scanner, indent='', simple=False): """ parse expr without blank and leave `\n` """ token, [row, col, _] = scanner.toke我们从全局块开始，因此indent为空串，indent只会在解析PyDefun时用到。simple只会在解析PyOp2的时候用到，举个例子：对于以下这一个复合语句来说，当前的 token 位于 a 处。如果simple==True，则只会解析a，返回一个PyVar，否则，将解析整个式子，返回一个PyOp2。
m = a - sea(m) * sky(a) ^ token好了，思想准备工作做完了。现在开始解析。我们先建立全局观：
def parse_expr(scanner, indent='', simple=False): """ parse expr without blank and leave `\n` """ token, [row, col, _] = scanner.token if token == 'def': # 遇到关键字 def，肯定是函数定义 return parse_defun(scanner, indent) elif token == '(': # 遇到 ( ，肯定是括号表达式 expr = parse_parent(scanner) if simple: return expr # 如果 simple == True，就直接返回 return parse_op2(expr, scanner) # 否则，接着解析一个 PyOp2 elif all_num(token): # expr = parse_num(scanner) # 解析数字 if simple: return expr # return parse_op2(expr, scanner) elif is_var(token): # ...这里解析了看一眼就能识别的表达式。由于数字和括号表达式是可以组合成PyOp2的，所以我们多了一个判断。
除了以上情况，我们发现 token 是一个变量，那有可能是a，a + b，a()等很多种情况。这时我们需要多看一眼。
def parse_expr(scanner, indent='', simple=False): token, [row, col, _] = scanner.token # 已完成 elif is_var(token): sym = PyVar(token) scanner.next_token() # 未完成 else: raise Exception(f"unrecognize: `{token}` in row {row} col {col} ")我们先将当前的 token 转成一个PyVar，然后我们读下一个token。（注意，我将忽略缩进）
第一种情况是，已经到达文件尾了。
if scanner.token[0] is None: # input end return sym第二，我们遇到了左括号，这意味着函数调用，而函数调用也是可以组合到PyOp2中的。
elif scanner.token[0] == '(': # funcall start expr = parse_funcall(sym, scanner) if simple: return expr return parse_op2(expr, scanner)第三，发现逗号，这意味着我们在解析函数调用时的参数。读者可能有疑问：为什么不能是函数定义时的参数呢？这两者最大的区别在于，定义时的形式参数只能是PyVar，而调用时的参数可以是多种表达式，如PyOp2，PyInt等。
elif scanner.token[0] == ',': # funcall argslist return sym第四，发现右括号。这意味着函数调用结束了。
elif scanner.token[0] == ')': # funcall finish return sym第五，发现等号=，意味着这是一个赋值语句。
elif scanner.token[0] == '=': # defvar return parse_defvar(sym, scanner)第六，发现换行符，这意味着一行的结束。注意，我们并不解析换行符。
elif scanner.token[0] == '\n': return sym第七，是运算符。如果不是，就是语法错误。
elif scanner.token[0] in '+-*/': return parse_op2(sym, scanner) else: token, [row, col, _] = scanner.token raise Exception(f"unrecognize: `{sym.name} {token}` in row {row} col {col} ")这样，我们完成了parse_expr。总体的结构也清晰了。
现在，我们逐个完成那些parse_*函数。
最简单的两个： int， var。我们在 parse 的同时，吃掉了当前的 token 。这是递归下降的标准做法。
def parse_num(scanner): pyint = PyInt(int(scanner.token[0])) scanner.next_token() return pyint def parse_var(scanner): var = PyVar(scanner.token[0]) scanner.next_token() return var这里我想先定义一个辅助函数，以便提升代码可读性。
def match(scanner, e): token, [row, col_s, _] = scanner.token assert token == e, f"expect {e} in row {row} column {col_s}" scanner.next_token()match判断当前的 token 与 e 是否相同，如果相同，则把当前的 token 吃掉，不同则报错。我们将频繁使用这个函数。
下面解析赋值语句，回顾一下，sym 已经保存了等号左边的变量，当前的 token 应该是一个等号。我们需要解析右边的表达式，并赋值给左边的变量。
def parse_defvar(sym, scanner): match(scanner, '=') expr = parse_expr(scanner) return PyDefvar(sym, expr)下面解析括号。当前的 token 是一个左括号。我们解析括号中的表达式，并吃掉右边的括号。
def parse_parent(scanner): match(scanner, '(') expr = parse_expr(scanner) match(scanner, ')') return expr下面解析函数调用，我们已经解析了一个函数名fn，且当前的 token 是一个左括号，我们解析它的参数列表，并吃掉它的右括号。
def parse_funcall(fn, scanner): # fn (???) match(scanner, '(') args = [] while scanner.token[0] != ')': arg = parse_expr(scanner) args.append(arg) if scanner.token[0] == ')': break match(scanner, ',') match(scanner, ')') return PyCall(fn, args)现在，我们剩下最难的两个 PyOp2 和 PyDefun 的解析。
我将使用运算符优先级的方法来解析 PyOp2，这一部分的内容，我参考了这份 llvm 教程。
precedure = { '+': 20, '-': 20, '*': 40, '/': 40 } def parse_op2(expr, scanner, expr_prec=0): # [op, expr]* # ...这个函数只会在解析了第一个表达式之后被调用，也即参数中的 expr。它会往下解析可能存在的「二元运算对」，即[op, expr]*。我们以一个具体的例子来说明。假设我们将解析以下式子。显然，1 被解析，并移动 token 位于 + 处。
1 + 2 * 3 - 4 ^ token剩下的是二元运算对 [+,2]，[*,3]，[-,4] 。参数中的 expr_prec 指的是表达式的优先级。初始为 0 。我们逐行解释代码：
一开始，我们需要判断接下来的内容是否是二元运算对。（注意，我忽略了缩进）
if not scanner.token[0] or scanner.token[0] not in '+-*/': return expr如果是，我们则需要读出当前的运算符，并与运算符的优先级跟表达式的优先级作对比。如果运算符的优先级低于表达式的优先级，则不再解析，直接返回。这样做的理由，希望在后文可以解释清楚。
op, _ = scanner.token op_prec = precedure[op] if op_prec < expr_prec: return expr以我们的例子来说，当前的表达式是1，其优先级为0，运算符为+，其优先级为20，显然要继续往下解析。但是，我们只要取出下一个简单表达式就行了！
scanner.next_token() next_expr = parse_expr(scanner, simple=True) # 只取简单表达式这里我们将取到2。
这时我们需要判断 token 是否已经位于行尾了。如果是这样，则表示解析结束，我们返回当前的PyOp2。
if not scanner.token[0] or scanner.token[0] not in '+-*/': return PyOp2(op, expr, next_expr)但在我们这个例子中，token 实际上还在*处。
1 + 2 * 3 - 4 ^ token所以我们必须比较+和*的优先级。显然*优先级更高，意味着2要跟*的后面的语句结合。这时候，我们看到
2 * 3 - 4 ^ token刚好是一个二元运算的复合语句，我们可以用parse_op2来递归解析。
next_op, _ = scanner.token next_op_prec = precedure[next_op] if op_prec < next_op_prec: next_expr = parse_op2(next_expr, scanner, op_prec+1)注意到，我们的表达式优先级为op_prec+1，具体而言，是+的优先级加1，为21。这会使得语句解析到后面的-处停下，使得+比-更早被解析。也就是说，使得同等级的语句从左到右按顺序解析。
1 + 2 * 3 - 4 ^ ^^^^^ ^ 0 21 20最后，等*解析完了，跟+相结合，并继续解析剩下的-号。
expr = PyOp2(op, expr, next_expr) return parse_op2(expr, scanner, expr_prec)这次，我们传的是表达式的优先级，也即是0，所以后面的-可以被正确地解析。这样我们完成了parse_op2。
现在来看看parse_defun。
def parse_defun(scanner, preindent): match(scanner, 'def') fn, [row, col, _] = scanner.token assert is_var(fn), f"`{fn}` in row {row} col {col} is not a valid function name" scanner.next_token() # ...这个函数需要额外一个preindemt参数，表明它的上级代码块的缩进。以上代码解析了函数名。接下来我们解析参数列表，这与之前的函数调用很像。
# parse args args = [] match(scanner, '(') while scanner.token[0] != ')': token, [row, col, _] = scanner.token assert is_var(token), f"bad variable name in row {row} col {col}" arg = PyVar(scanner.token[0]) args.append(arg) scanner.next_token() if scanner.token[0] == ')': break match(scanner, ',') match(scanner, ')')在这之后，我们期待有一个冒号和换行，同时，忽略多余的换行。
match(scanner, ':') match(scanner, '\n') # this is necessary newline while scanner.token[0] == '\n': scanner.next_token() # skip extra newline现在我们开始解析函数体了。我们的 token 位于行首表示缩进，我们期待 indent 会大于它上一级代码块的缩进，否则报错。
body = [] indent, [row, _, col] = scanner.token if not all_space(indent) or indent < preindent: raise Exception(f"bad indent in row {row}, col {col}")因为我们函数体的语句是任意多的，所以用一个无限循环来解析。首先判断当前的语句是否为return
while True: scanner.next_token() # eat indent if scanner.token[0] == 'return': scanner.next_token() last_expr = parse_expr(scanner, indent) body.append(last_expr) break否则，为任意一个普通的语句，先解析它。
expr = parse_expr(scanner, indent) body.append(expr)之后，我们要判断下一个语句是否属于当前代码块。我们需要先跳过换行符。
# if expr is a defun, it will leave indent # else it will leave \n while scanner.token[0] == '\n': scanner.next_token(现在，我们来到了非空行的行首，若为当前的缩进，则继续循环解析。
next_indent, [row, _, col] = scanner.token if next_indent == indent: continue否则，我们可能到达了文件尾，或者当前的代码块已经结束了，也有可能是下一行的符号。不管怎么样，说明我们的解析结束，以Null作为最后一个语句返回。除此之外，就是语法错误了。
elif next_indent is None or next_indent < indent or not all_space(next_indent): last_expr = PyNull() body.append(last_expr) break else: raise Exception(f"bad indent in row {row}, col {col}")最后，我们返回一个PyDefun
# now, fn, args, and body is ready, env will be appended when interpreted return PyDefun(PyVar(fn), args, body, PyNull())写些测试吧！
# test_psp.py def test_parse3(): s = "(1 + 2) - 3 / 4" scan = Scanner(s) scan.next_token() expr = parse_expr(scan) assert isinstance(expr, PyOp2) assert str(expr) == '(- (+ 1 2) (/ 3 4))'我们再写个入口函数
def parse(prog): scanner = Scanner(prog) scanner.next_token() abs_prog = [] while scanner.token[0] != None: while scanner.token[0] == '\n': scanner.next_token() expr = parse_expr(scanner) while scanner.token[0] == '\n': scanner.next_token() abs_prog.append(expr) return abs_prog至此，parser 完成！
本教程最后一个内容是解释器。因为在之前的 EoC 中，我们实现过四个解释器了，所以这里不会很详细解释。言归正传，我们先看看环境表示
def empty_env(): def search(v: str): raise Exception(f"variable {v} not found!") return search def extend(saved_var, saved_val, env): def search(v: str): if v == saved_var: return saved_val return lookup(env, v) return search def lookup(env, v: str): return env(v)这是 message-passing 风格的环境表示。env 本身是一个函数search，或者说闭包(closure)。拓展环境使用 extend，传入的 var、val 和 env 被 search 捕获了。查找变量时，先与闭包中捕获的 var 对比，如果没有，再从它捕获的 env 中查找。
好了。现在来看看解释器
def interpret(exprs, env): for expr in exprs: if isinstance(expr, PyDefvar): val = interpret_helper(expr.val, env) env = extend(expr.var, val, env) elif isinstance(expr, PyDefun): expr.env = env # bind runtime environment env = extend(expr.name, expr, env) else: yield interpret_helper(expr, env)在我们的语句中，有两种修改环境的语句，其余都是有返回值的语句，我们用一个 helper 来解释。
def interpret_helper(expr, env): if isinstance(expr, PyVar): return lookup(env, expr) elif isinstance(expr, (PyInt, PyNull)): return expr elif isinstance(expr, PyCall): fn = lookup(env, expr.fn) args = [interpret_helper(arg, env) for arg in expr.args] return fn(args) elif isinstance(expr, PyOp2): e1 = interpret_helper(expr.e1, env) e2 = interpret_helper(expr.e2, env) if expr.op == '+': return e1 + e2 elif expr.op == '-': return e1 - e2 elif expr.op == '*': return e1 * e2 elif expr.op == '/': return e1 / e2 else: raise Exception(f"Unknown operation `{expr.op}`") else: raise Exception("Invalid Expr")这样，我们的小 Python 语言总算完成了！
以下是一个使用示例。
def interp_demo(filename): with open(filename) as f: source = f.read() ast = parse(source) res = interpret(ast, empty_env()) for (i, x) in enumerate(res): print(f"Out[{i}]: {x}") if __name__ == '__main__': interp_demo('demo.py')让我们测试一下吧！
def test_interpret1(): s = """\ def haha(a, b): def hahaha(z): return z * 2 return hahaha(a) + b * b - a / b y = 1 x = 2 z = haha(x, y) z """ cfg = parse(s) res = list(interpret(cfg, empty_env())) assert res[-1] == PyInt(3) def test_interpret2(): s = "1 + 2 * 3 - 4 / 5" cfg = parse(s) res = list(interpret(cfg, empty_env())) assert res[-1] == PyInt(7)这份教程源于我对 llvm 官网上一份教程的学习。那份教程中实现了一门语法类似 Python 的小语言。当时我就想，是否能实现成「真」的 Python 呢？然后时不时会思考如何解析 Python 的语法。直到最近有点时间，我才着手实现。因为收获颇丰，遂有此文。
纸上得到终觉浅，绝知此事要躬行。 本教程定价 ￥32，可自愿购买，可使用自定义折扣券。
