蚊章汇 - Ruslan Spivak
type: channel
link: https://linuxcn.bwsl.wang/author/874/
description: Ruslan Spivak
items: 让我们做个简单的解释器（三）
items: 让我们做个简单的解释器（二）
items: 让我们做个简单的解释器（一）

让我们做个简单的解释器（三）
type: item
date: 2018-04-09T17:01:00+08:00
description: 早上醒来的时候，我就在想：“为什么我们学习一个新技能这么难？”我不认为那是因为它很难。我认为原因可能在于我们花了太多的时间，而这件难事需要有丰富的阅历和足够的知识，然而我们要把这样的知识转换成技能所用的练习时间又不够。拿游泳来说，你可以花上几天时间来阅读很多有关游泳的书籍，花几个小时和资深的游泳者和教练交流，观看所有可以获得的训练视频，但你第一次跳进水池的时候，仍然会像一个石头那样沉入水中，要点在于：你认为自己有多了解那件事都无关紧要 —— 你得通过练习把知识变成技能。为了帮你练习，我把训练放在了这个系列的 第一部分 和 第二部分 了。当然，你会在今后的文章中看到更多练习，我保证 ：)好，让我们开始今天的学习。到现在为止，你已经知道了怎样解释像 “7 + 3” 或者 “12 - 9” 这样的两个整数相加减的算术表达式。今天我要说的是怎么解析（识别）、解释有多个数字相加减的算术表达式，比如 “7 - 3 + 2 - 1”。文中的这个算术表达式可以用下面的这个语法图表示：什么是 语法图 syntax diagram ？ 语法图 是对一门编程语言中的语法规则进行图像化的表示。基本上，一个语法图就能告诉你哪些语句可以在程序中出现，哪些不能出现。语法图很容易读懂：按照箭头指向的路径。某些路径表示的是判断，有些表示的是循环。你可以按照以下的方式读上面的语法图：一个 term 后面可以是加号或者减号，接着可以是另一个 term，这个 term 后面又可以是一个加号或者减号，后面又是一个 term，如此循环。从字面上你就能读懂这个图片了。或许你会奇怪，“term” 是什么、对于本文来说，“term” 就是个整数。语法图有两个主要的作用：它们用图形的方式表示一个编程语言的特性（语法）。它们可以用来帮你写出解析器 —— 你可以根据下列简单规则把图片转换成代码。你已经知道，识别出记号流中的词组的过程就叫做 解析。解释器或者编译器执行这个任务的部分叫做 解析器。解析也称为 语法分析，并且解析器这个名字很合适，你猜的对，就是 语法分析器。根据上面的语法图，下面这些表达式都是合法的：33 + 47 - 3 + 2 - 1因为算术表达式的语法规则在不同的编程语言里面是很相近的，我们可以用 Python shell 来“测试”语法图。打开 Python shell，运行下面的代码：>>> 3 3 >>> 3 + 4 7 >>> 7 - 3 + 2 - 1 5 意料之中。表达式 “3 + ” 不是一个有效的数学表达式，根据语法图，加号后面必须要有个 term （整数），否则就是语法错误。然后，自己在 Python shell 里面运行：>>> 3 + File "<stdin>", line 1 3 + ^ SyntaxError: invalid syntax 能用 Python shell 来做这样的测试非常棒，让我们把上面的语法图转换成代码，用我们自己的解释器来测试，怎么样？从之前的文章里（第一部分 和 第二部分）你知道 expr 方法包含了我们的解析器和解释器。再说一遍，解析器仅仅识别出结构，确保它与某些特性对应，而解释器实际上是在解析器成功识别（解析）特性之后，就立即对表达式进行评估。以下代码片段显示了对应于图表的解析器代码。语法图里面的矩形方框（term）变成了 term 方法，用于解析整数，expr 方法和语法图的流程一致：def term(self): self.eat(INTEGER) def expr(self): # 把当前标记设为从输入中拿到的第一个标记 self.current_token = self.get_next_token() self.term() while self.current_token.type in (PLUS, MINUS): token = self.current_token if token.type == PLUS: self.eat(PLUS) self.term() elif token.type == MINUS: self.eat(MINUS) self.term() 你能看到 expr 首先调用了 term 方法。然后 expr 方法里面的 while 循环可以执行 0 或多次。在循环里面解析器基于标记做出判断（是加号还是减号）。花一些时间，你就知道，上述代码确实是遵循着语法图的算术表达式流程。解析器并不解释任何东西：如果它识别出了一个表达式，它就静默着，如果没有识别出来，就会抛出一个语法错误。改一下 expr 方法，加入解释器的代码：def term(self): """Return an INTEGER token value""" token = self.current_token…

让我们做个简单的解释器（二）
type: item
date: 2018-04-07T18:31:05+08:00
description: 在一本叫做 《高效思考的 5 要素》 的书中，作者 Burger 和 Starbird 讲述了一个关于他们如何研究 Tony Plog 的故事，他是一位举世闻名的交响曲名家，为一些有才华的演奏者开创了一个大师班。这些学生一开始演奏复杂的乐曲，他们演奏的非常好。然后他们被要求演奏非常基础简单的乐曲。当他们演奏这些乐曲时，与之前所演奏的相比，听起来非常幼稚。在他们结束演奏后，老师也演奏了同样的乐曲，但是听上去非常娴熟。差别令人震惊。Tony 解释道，精通简单音符可以让人更好的掌握复杂的部分。这个例子很清晰 —— 要成为真正的名家，必须要掌握简单基础的思想。故事中的例子明显不仅仅适用于音乐，而且适用于软件开发。这个故事告诉我们不要忽视繁琐工作中简单基础的概念的重要性，哪怕有时候这让人感觉是一种倒退。尽管熟练掌握一门工具或者框架非常重要，了解它们背后的原理也是极其重要的。正如 Palph Waldo Emerson 所说：“如果你只学习方法，你就会被方法束缚。但如果你知道原理，就可以发明自己的方法。”有鉴于此，让我们再次深入了解解释器和编译器。今天我会向你们展示一个全新的计算器，与 第一部分 相比，它可以做到：处理输入字符串任意位置的空白符识别输入字符串中的多位整数做两个整数之间的减法（目前它仅能加减整数）新版本计算器的源代码在这里，它可以做到上述的所有事情：# 标记类型 # EOF （end-of-file 文件末尾）标记是用来表示所有输入都解析完成 INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF' class Token(object): def __init__(self, type, value): # token 类型: INTEGER, PLUS, MINUS, or EOF self.type = type # token 值: 非负整数值, '+', '-', 或无 self.value = value def __str__(self): """String representation of the class instance. Examples: 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", "12 - 5", self.text = text # self.pos 是 self.text 的索引 self.pos = 0 # 当前标记实例 self.current_token = None self.current_char = self.text[self.pos] def error(self): raise Exception('Error parsing input') def advance(self): """Advance the 'pos' pointer and set the 'current_char' variable.""" self.pos += 1 if self.pos > len(self.text) - 1: self.current_char = None # Indicates end of input else: self.current_char = self.text[self.pos] def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance() def integer(self): """Return a (multidigit) integer consumed from the input.""" result = '' while self.current_char is not None and self.current_char.isdigit(): result += self.current_char self.advance() return int(result) def get_next_token(self): """Lexical analyzer (also known as sca…

让我们做个简单的解释器（一）
type: item
date: 2018-03-04T17:41:00+08:00
description: “如果你不知道编译器是怎么工作的，那你就不知道电脑是怎么工作的。如果你不能百分百确定，那就是不知道它们是如何工作的。” --Steve Yegge就是这样。想一想。你是萌新还是一个资深的软件开发者实际上都无关紧要：如果你不知道 编译器 compiler 和 解释器 interpreter 是怎么工作的，那么你就不知道电脑是怎么工作的。就这么简单。所以，你知道编译器和解释器是怎么工作的吗？我是说，你百分百确定自己知道他们怎么工作吗？如果不知道。或者如果你不知道但你非常想要了解它。不用担心。如果你能坚持跟着这个系列做下去，和我一起构建一个解释器和编译器，最后你将会知道他们是怎么工作的。并且你会变成一个自信满满的快乐的人。至少我希望如此。为什么要学习编译器和解释器？有三点理由。要写出一个解释器或编译器，你需要有很多的专业知识，并能融会贯通。写一个解释器或编译器能帮你加强这些能力，成为一个更厉害的软件开发者。而且，你要学的技能对编写软件非常有用，而不是仅仅局限于解释器或编译器。你确实想要了解电脑是怎么工作的。通常解释器和编译器看上去很魔幻。你或许不习惯这种魔力。你会想去揭开构建解释器和编译器那层神秘的面纱，了解它们的原理，把事情做好。你想要创建自己的编程语言或者特定领域的语言。如果你创建了一个，你还要为它创建一个解释器或者编译器。最近，兴起了对新的编程语言的兴趣。你能看到几乎每天都有一门新的编程语言横空出世：Elixir，Go，Rust，还有很多。好，但什么是解释器和编译器？解释器 和 编译器 的任务是把用高级语言写的源程序翻译成其他的格式。很奇怪，是不是？忍一忍，稍后你会在这个系列学到到底把源程序翻译成什么东西。这时你可能会奇怪解释器和编译器之间有什么区别。为了实现这个系列的目的，我们规定一下，如果有个翻译器把源程序翻译成机器语言，那它就是 编译器。如果一个翻译器可以处理并执行源程序，却不用把它翻译器机器语言，那它就是 解释器。直观上它看起来像这样：我希望你现在确信你很想学习构建一个编译器和解释器。你期望在这个教程里学习解释器的哪些知识呢？你看这样如何。你和我一起为 Pascal 语言的一个大子集做一个简单的解释器。在这个系列结束的时候你能做出一个可以运行的 Pascal 解释器和一个像 Python 的 pdb 那样的源代码级别的调试器。你或许会问，为什么是 Pascal？一方面，它不是我为了这个系列而提出的一个虚构的语言：它是真实存在的一门编程语言，有很多重要的语言结构。有些陈旧但有用的计算机书籍使用 Pascal 编程语言作为示例（我知道对于选择一门语言来构建解释器，这个理由并不令人信服，但我认为学一门非主流的语言也不错 :））。这有个 Pascal 中的阶乘函数示例，你将能用自己的解释器解释代码，还能够用可交互的源码级调试器进行调试，你可以这样创造：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. 这个 Pascal 解释器的实现语言会使用 Python，但你也可以用其他任何语言，因为这里展示的思想不依赖任何特殊的实现语言。好，让我们开始干活。准备好了，出发！你会从编写一个简单的算术表达式解析器，也就是常说的计算器，开始学习解释器和编译器。今天的目标非常简单：让你的计算器能处理两个个位数相加，比如 3+5。下面是你的计算器的源代码——不好意思，是解释器：# 标记类型 # # EOF （end-of-file 文件末尾）标记是用来表示所有输入都解析完成 INTEGER, PLUS, EOF = 'INTEGER', 'PLUS', 'EOF' class Token(object): def __init__(self, type, value): # token 类型: INTEGER, PLUS, MINUS, or EOF self.type = type # token 值: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, '+', 或 None self.value = value def __str__(self): """String representation of the class instance. Examples: Token(INTEGER, 3) Token(PLUS '+') """ return…