手把手教你从零实现一个编译器（一）
个人其它平台技术文章：
知乎ID：砖一块一块搬（戳我传送）小红书ID：码农有道
“如果你不了解编译器是如何工作的，那你就不了解计算机是如何工作的。如果你不能百分之百确定自己是否已经了了解编译器的工作原理，那就说明你还不真正了解它。”—— Steve Yegge
这句话一点都不夸张。不管你是一个刚刚才接触编程的初学者，还是一个已经有多年开发经验的程序员，如果你不清楚编译器和解释器的原理，那就等于你还没真正理解计算机的核心本质。事情就是这么简单。
所以，你真的了解编译器和解释器是怎么工作的吗？我是说，你能百分之百肯定自己理解了吗？如果不能……
或者说，你现在还不太了解，但你非常想要了解它。
不用担心，只要你愿意跟着这个系列一步步学下去，一起动手实现一个解释器和编译器，最终你一定能真正理解它们是如何工作的。
为什么要学习解释器和编译器呢？我可以给你三个理由。
首先，编写一个解释器或编译器需要综合运用大量技术技能，比如词法分析、语法解析、抽象语法树、作用域管理、内存模型等等。这个过程会极大地锻炼你的综合能力，帮助你成为更优秀的软件开发者。而且，这些技能不仅仅在写解释器或编译器时有用，几乎在开发任何软件时都能派上用场。其次，如果你真的想深入了解计算机是如何工作的，编译器和解释器是绕不开的知识点。它们看起来像“魔法”一样，但作为开发者，你不应该满足于只会“用魔法”，而要主动去揭开“魔法”的面纱，搞懂它的底层逻辑，真正掌控它。如果你也想创造一门自己的语言，你就必须同时为它开发一个解释器或编译器。
那么，解释器和编译器到底是什么呢？
简单来说，解释器和编译器的任务是把高级语言写成的源程序，翻译成另一种形式。听起来是不是有点模糊？别急，请耐心阅读，在后续的内容中你会逐步弄清楚：这个“源程序”到底被翻译成了什么，以及这个过程到底是怎么完成的。
说到这儿，你可能还想知道解释器和编译器之间有什么区别。
在我们这个系列的学习中，先达成一个简单的共识：
如果一个“翻译器”把源程序翻译成机器语言，那它就是编译器；如果一个“翻译器”不把源程序直接翻译成机器语言，而是边处理边执行源程序，那它就是解释器。
希望现在你已经意识到，学习并亲手实现一个解释器和编译器，确实是一件既有价值又充满挑战的事情。那么接下来，我们这一系列文章会带来些什么内容呢？
我们要做的事情是这样的：我们将一起动手，一起为 Pascal 语言的一个大子集做一个简单的解释器。在这个系列结束的时候，你将能做出一个可以运行的 Pascal 解释器，并且还能实现一个类似 Python 的 pdb 那样的的源码级调试器。
你可能会问：我们为什么选择 Pascal 呢？
首先，Pascal 并不是我为了这个系列随便编出来的一门语言，它是真实存在的编程语言，而且拥有很多重要的语言结构和概念。虽然现在它不是主流语言，但它在计算机科学的发展历史中有着举足轻重的地位。
另外，还有不少经典但仍然很有价值的计算机书籍，使用的例子就是用 Pascal 写的，我觉得换一种思维方式、接触一门非主流但结构清晰的语言，也未尝不是一种有趣又特别的学习体验。
下面这段 Pascal 代码展示了一个阶乘函数的例子——等你完成这个系列的学习之后，你将能够用自己亲手写的解释器来“运行”这段代码，还能用你自己实现的源码级调试器，对它进行单步调试，就像使用 Python 的 pdb 一样。
program factorial;
function factorial(n: integer): longint;
begin
if n = 0 then
factorial := 1
else
factorial := n * factorial(n - 1);
end;
var
n: integer;
begin
for n := 0 to 16 do
writeln(n, '! = ', factorial(n));
end.
我们将使用 Python 语言来实现这个 Pascal 解释器。不过别担心，如果你更熟悉其他语言，也完全可以用你喜欢的语言来实现，因为我们讲解的核心思想和原理，是不依赖于具体编程语言的。
好了，话不多说，是时候开始正经的学习了——准备好了吗？来吧，出发！🚀
下面你会从编写一个简单的算术表达式解释器，也就是常说的计算器，开始学习解释器和编译器。
今天的目标非常简单：让这个解释器能够处理两个个位整数相加的表达式，比如 3+5。
以下是这个解释器的源码：
# 标记类型
#
# EOF（文件结束）标记用于表示没有更多的输入用于词法分析
INTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF'
class Token(object):
def __init__(self, type, value):
# 标记类型：INTEGER、PLUS 或 EOF
self.type = type
# 标记值：0、1、2、3、4、5、6、7、8、9、'+' 或 None
self.value = value
def __str__(self):
"""类实例的字符串表示。
例子：
Token(INTEGER, 3)
Token(PLUS, '+')
"""
return 'Token({type}, {value})'.format(
type=self.type,
value=repr(self.value)
)
def __repr__(self):
return self.__str__()
class Interpreter(object):
def __init__(self, text):
# 客户端字符串输入，例如 "3+5"
self.text = text
# self.pos 是 self.text 中的索引
self.pos = 0
# 当前标记实例
self.current_token = None
def error(self):
raise Exception('Error parsing input')
def get_next_token(self):
"""词法分析器（也称为扫描器或标记器）
此方法负责将句子分解成标记。一次一个标记。
"""
text = self.text
# self.pos 索引是否超过了 self.text 的末尾？
# 如果是，则返回 EOF 标记，因为没有更多的输入可以转换为标记
if self.pos > len(text) - 1:
return Token(EOF, None)
# 获取 self.pos 位置的字符，并根据单个字符决定创建什么标记
current_char = text[self.pos]
# 如果字符是数字，则将其转换为整数，创建一个 INTEGER 标记，增加 self.pos 索引以指向数字后的下一个字符，并返回 INTEGER 标记
if current_char.isdigit():
token = Token(INTEGER, int(current_char))
self.pos += 1
return token
if current_char == '+':
token = Token(PLUS, current_char)
self.pos += 1
return token
self.error()
def eat(self, token_type):
# 将当前标记类型与传递的标记类型进行比较，如果匹配，则“吃”当前标记并分配下一个标记到 self.current_token，否则引发异常。
if self.current_token.type == token_type:
self.current_token = self.get_next_token()
else:
self.error()
def expr(self):
"""表达式 -> 整数 加 整数"""
# 将当前标记设置为从输入中获取的第一个标记
self.current_token = self.get_next_token()
# 我们期望当前标记是一个一位数整数
left = self.current_token
self.eat(INTEGER)
# 我们期望当前标记是一个 '+' 标记
op = self.current_token
self.eat(PLUS)
# 我们期望当前标记是一个一位数整数
right = self.current_token
self.eat(INTEGER)
# 以上调用后，self.current_token 设置为 EOF 标记
# 此时，整数 加 整数的标记序列已成功找到，方法只需返回两个整数相加的结果，从而有效地解释客户端输入
result = left.value + right.value
return result
def main():
while True:
try:
# 在 Python3 下运行时，将 'raw_input' 调用替换为 'input'
text = raw_input('calc> ')
except EOFError:
break
if not text:
continue
interpreter = Interpreter(text)
result = interpreter.expr()
print(result)
if __name__ == '__main__':
main()
将上述代码保存到calc1.py文件，在深入研究代码之前，先在命令行运行一下这个简单的计算器，感受一下它的效果，试着玩一玩。
以下是在我电脑上运行的一个示例过程（如果你用的是 Python3，需要将代码中的 raw_input 替换为 input）：
$ python calc1.py
calc> 3+4
7
calc> 3+5
8
calc> 3+9
12
calc>
为了让你这个简单的计算器能够正常运行、不报错，用户的输入必须遵循以下几个规则：
输入中只能包含 单个数字 的整数（比如 3+5* ，不能是 12+7）当前只支持一种运算：加法（+）输入中不能有空格（例如，3 + 5 是非法的）
这些限制是为了让我们一开始可以专注在解释器的核心逻辑上，保持代码简单。不用担心，后面我们会逐步添加更多功能，让它变得越来越强大、复杂。
好了，现在我们来深入了解一下这个解释器的运行机制，看看它是如何一步一步地“理解”并计算这个简单的加法表达式的。
当你在命令行中输入表达式 3+5 时，你的解释器接收到的是一个字符串 “3+5”。但解释器并不能直接理解这个字符串的含义，它需要先把这个字符串拆解成一些“组件”，这些组件我们称为 token（标记）。
每一个 token 都是一个包含“类型”和“值”的对象。比如，对于字符串中的 “3”，它会被解释器识别为一个类型是 INTEGER 的 token，而它的值就是整数 3。
将输入的字符串拆解成一个个 token 的过程，称为 词法分析（lexical analysis）。
因此，解释器在处理用户输入时，第一步就是要读取这些字符，并将它们转换为一个个 token 流。完成这一步工作的模块叫做 词法分析器（lexical analyzer），我们通常简称为 lexer。
你也可能会看到其他的叫法，比如 scanner（扫描器） 或 tokenizer（标记器），这些名称本质上是一个意思——都是负责把字符输入转换成 token 流的那一部分。
Interpreter 类中的 get_next_token 方法就是我们实现的词法分析器。每次调用它时，它都会从传递给解释器的字符输入中提取出一个新的 token。
我们一起来深入看看这个方法是怎么工作的，了解它是如何把一连串字符转换成 token 的。
输入内容保存在变量 text 中，而 pos 是一个索引值，用来指向 text 中的某个字符（你可以把这个字符串想象成一个字符数组）。
一开始，pos 被设为 0，指向的是字符串中的第一个字符 ‘3’。方法首先会判断当前字符是不是数字，如果是，它就会把 pos 向后移动一个位置，并返回一个 Token 实例，这个实例的类型是 INTEGER，值就是字符串 ‘3’ 所代表的数字 3（也就是整数 3）。
此时，pos 已经指向了输入字符串中的 ‘+’ 字符。
当你下一次调用 get_next_token 方法时，它会先判断当前位置的字符是不是一个数字，发现不是之后，再继续判断该字符是否是加号 +。结果发现正好是加号，于是方法会将 pos 再向后移动一位，并返回一个新的 Token 实例，这个实例的类型是 PLUS，值就是字符 ‘+’。
此时，pos 已经指向了字符 ‘5’。
当你再次调用 get_next_token 方法时，方法首先会判断当前位置的字符是不是一个数字。因为 ‘5’ 是数字，所以判断成立。于是方法会将 pos 向后移动一位，并返回一个新的 Token 实例，其类型为 INTEGER，值为整数 5。
现在pos 索引已经越过了字符串 “3+5” 的末尾，再次调用 get_next_token 方法时，它会返回一个 EOF（End Of File，文件结束）类型的 Token。
也就是说，只要 pos 超出了输入字符串的范围，词法分析器就会认为输入已经结束，不再有更多的字符可以分析，此时就会生成一个表示结束的 EOF Token。
你可以亲自试试看，观察这个词法分析器是如何一步步把输入的字符串拆解成不同的 Token 的。通过这个过程，你就能更清楚地理解解释器是如何“理解”我们输入的表达式的。
>>> from calc1 import Interpreter
>>>
>>> interpreter = Interpreter('3+5')
>>> interpreter.get_next_token()
Token(INTEGER, 3)
>>>
>>> interpreter.get_next_token()
Token(PLUS, '+')
>>>
>>> interpreter.get_next_token()
Token(INTEGER, 5)
>>>
>>> interpreter.get_next_token()
Token(EOF, None)
>>>
现在，解释器已经可以从词法分析器（即 get_next_token 方法）那里获取由输入字符生成的一串 Token 了，接下来它要做的就是：在这串“扁平化”的 Token 流中，识别出具有特定结构的内容。
解释器期望在这串 Token 中找到这样一个结构：整数 -> 加号 -> 整数。也就是说，它会尝试匹配这样一个顺序的 Token 序列：一个整数，接着是一个加号，然后是另一个整数。
只有当输入符合这个固定的结构时，解释器才能正确地“理解”并执行你输入的表达式。这个过程其实就是解释器在做“语法分析”。
负责识别并解释这个结构的方法是 expr。这个方法会检查输入的 Token 序列是否确实符合我们期望的格式——也就是 整数 -> 加号 -> 整数。
当 expr 方法成功验证了这个结构之后，它就会执行加法运算：将加号左边的整数 Token 的值与右边的整数 Token 的值相加，并返回结果。这样，解释器就成功地“理解”并“执行”了你输入的算术表达式。
expr 方法本身会调用一个辅助方法 eat，用于验证当前的 Token 类型是否与传入的 Token 类型匹配。如果匹配，eat 方法就会从输入中获取下一个 Token，并把它赋值给 current_token，也就是说它“吃掉”了当前匹配的 Token，同时在 Token 流中向前推进一步。
如果 Token 流中的结构并不符合我们期望的 整数 -> 加号 -> 整数 的模式，eat 方法就会抛出一个异常，表示输入不合法或者表达式格式错误。
让我们来回顾一下，这个解释器是如何对一个算术表达式进行求值的：
首先，解释器接收一段输入字符串，比如 “3+5”。然后，解释器调用 expr 方法来分析从词法分析器 get_next_token 返回的 Token 流。它会尝试找到一种特定的结构：整数 -> 加号 -> 整数。一旦确认输入符合这种结构，解释器就会对表达式进行求值 —— 将两个整数 Token 的值相加。因为到这一步，解释器已经明确知道它需要做的是：将两个整数 3 和 5 相加。
恭喜你！你已经学会了如何构建你人生中第一个解释器！
接下来，是练习的时间了～
你不会以为只看完这篇文章就完事了吧？当然没这么简单！现在该动手实操一下了，来完成下面这几个练习题：
修改代码，使其支持多位数的整数，比如输入 “12+3” 也能正常计算，而不仅限于一位数。添加一个方法用于跳过空白字符，这样你的计算器就能处理带有空格的输入了，比如 " 12 + 3"。修改代码，让它可以处理减法运算，也就是说输入 “7-5” 时，解释器能够正确计算出结果。
最后来检查一下你对这篇文章的理解吧：
什么是解释器？什么是编译器？解释器和编译器有什么区别？什么是token？把输入拆解成 token 的过程叫什么？解释器中负责词法分析的部分叫什么？词法分析器还有哪些常见的别名？
这些基础知识掌握好了，后面学起来就会顺利很多！继续加油！💡