用 Python 从零开始写一个简单的解释器（1）
大学里计算机科学最吸引我的地方就是编译器。最神奇的是，编译器是如何读出我写的那些烂代码，并且还能生成那么复杂的程序。当我终于选了一门编译方面的课程时，我发现这个过程比我想的要简单得多。
在本系列的文章中，我会试着通过为一种基本命令语言IMP写一个解释器，来展示这种简易性。因为IMP是一个简单广为人知的语言，所以打算用 Python写这个解释器。Python代码看起来很像伪代码，所以即使你不认识 Python，你也能理解它。解析可以通过一套从头开始实现的解析器组合完成（在本系列的下一篇文章中会有解释）。除了sys（用于I/O）、re（用于解析正则表达式）以及unittest（用于确保一切工作正常）库，没有使用其他额外的库。
IMP 语言
在开始写之前，我们先来讨论一下将要解释的语言。IMP是拥有下面结构的最小命令语言：
赋值语句（所有变量都是全局的，而且只能存储整数）：
| 1 | x := 1 |
条件语句：
| 12345 | if x = 1 then y := 2 else y := 3end |
while循环：
| 123 | while x < 10 do x := x + 1end |
复合语句（分号分隔）：
| 12 | x := 1; y := 2 |
OK，所以它只是一门工具语言，但你可以很容易就把它扩展成比Lua或python更有用的语言。我希望能把这份教程能保持尽量简单。
下面这个例子是计算阶乘的程序：
| 123456 | n := 5;p := 1;while n > 0 do p := p * n; n := n – 1end |
IMP没有读取输入的方式，所以初始状态必须是在程序最开始写一系列的赋值语句。也没有打印结果的方式，所以解释器必须在程序的结尾打印所有变量的值。
解释器的结构
解释器的核心是「中间表示」（Intermediate representation，IR）。这就是如何在内存中表示IMP程序。因为IMP是一个很简单的语言，中间表示将直接对应于语言的语法；每一种表达和语句都有对应的类。在一种更复杂的语言中，你不仅需要一个「语法表示」，还需要一个更容易分析或运行的「语义表示」。
解释器将会执行三个阶段：
- 将源码中的字符分割成标记符（token）
- 将标记符组织成一棵抽象语法树（AST）。抽象语法树就是中间表示。
- 评估这棵抽象语法树，并在最后打印这棵树的状态
将字符串分割成标记符的过程叫做「词法分析」，通过一个词法分析器完成。关键字是很短，易于理解的字符串，包含程序中最基本的部分，如数字、标识符、关键字和操作符。词法分析器会除去空格和注释，因为它们都会被解释器忽略。
将标记符组织成抽象语法树（AST）的过程称为「解析过程」。解析器将程序的结构提取成一张我们可以评估的表格。
实际执行这个解析过的抽象语法树的过程称为评估。这实际上是这个解析器中最简单的部分了。
本文会把重点放在词法分析器上。我们将编写一个通用的词汇库，然后用它来为IMP创建一个词法分析器。下一篇文章将会重点打造一个语法分析器和评估计算器。
词汇库
词法分析器的操作相当简单。它是基于正则表达式的，所以如果你不熟悉它们，你可能需要读一些资料。简单来说，正则表达式就是一种能描述其他字符串的特殊的格式化的字符串。你可以使用它们去匹配电话号码或是邮箱地址，或者是像我们遇到在这种情况，不同类型的标记符。
词法分析器的输入可能只是一个字符串。简单起见，我们将整个输入文件都读到内存中。输出是一个标记符列表。每个标记符包括一个值（它代表的字符串）和一个标记（表示它是一个什么类型的标记符）。语法分析器会使用这两个数据来决定如何构建一棵抽象语法树。
由于不论何种语言的词法分析器，其操作都大同小异，我们将创建一个通用的词法分析器，包括一个正则表达式列表和对应的标签（tag）。对每一个表达式，它都会检查是否和当前位置的输入文本匹配。如果匹配，匹配文本就会作为一个标记符被提取出来，并且被加上该正则表达式的标签。如果该正则表达式没有标签，那么这段文本将会被丢弃。这样免得我们被诸如注释和空格之类的垃圾字符干扰。如果没有匹配的正则表达式，程序就要报错并终止。这个过程会不断循环直到没有字符可匹配。
下面是一段来自词汇库的代码：
| 123456789101112131415161718192021222324 | import sysimport re def lex(characters, token_exprs): pos = 0 tokens = [] while pos < len(characters): match = None for token_expr in token_exprs: pattern, tag = token_expr regex = re.compile(pattern) match = regex.match(characters, pos) if match: text = match.group(0) if tag: token = (text, tag) tokens.append(token) break if not match: sys.stderr.write(\’Illegal character: %sn\’ % characters[pos]) sys.exit(1) else:>翻译组。
大学里计算机科学最吸引我的地方就是编译器。最神奇的是，编译器是如何读出我写的那些烂代码，并且还能生成那么复杂的程序。当我终于选了一门编译方面的课程时，我发现这个过程比我想的要简单得多。 在本系列的文章中，我会试着通过为一种基本命令语言IMP写一个解释器，来展示这种简易性。因为IMP是一个简单广为人知的语言，所以打算用 Python写这个解释器。Python代码看起来很像伪代码，所以即使你不认识 Python，你也能理解它。解析可以通过一套从头开始实现的解析器组合完成（在本系列的下一篇文章中会有解释）。除了 IMP 语言在开始写之前，我们先来讨论一下将要解释的语言。IMP是拥有下面结构的最小命令语言： 赋值语句（所有变量都是全局的，而且只能存储整数）：
条件语句：
while循环：
复合语句（分号分隔）：
OK，所以它只是一门工具语言，但你可以很容易就把它扩展成比Lua或python更有用的语言。我希望能把这份教程能保持尽量简单。 下面这个例子是计算阶乘的程序：
IMP没有读取输入的方式，所以初始状态必须是在程序最开始写一系列的赋值语句。也没有打印结果的方式，所以解释器必须在程序的结尾打印所有变量的值。 解释器的结构解释器的核心是「中间表示」（Intermediate representation，IR）。这就是如何在内存中表示IMP程序。因为IMP是一个很简单的语言，中间表示将直接对应于语言的语法；每一种表达和语句都有对应的类。在一种更复杂的语言中，你不仅需要一个「语法表示」，还需要一个更容易分析或运行的「语义表示」。 解释器将会执行三个阶段：
将字符串分割成标记符的过程叫做「词法分析」，通过一个词法分析器完成。关键字是很短，易于理解的字符串，包含程序中最基本的部分，如数字、标识符、关键字和操作符。词法分析器会除去空格和注释，因为它们都会被解释器忽略。
将标记符组织成抽象语法树（AST）的过程称为「解析过程」。解析器将程序的结构提取成一张我们可以评估的表格。
实际执行这个解析过的抽象语法树的过程称为评估。这实际上是这个解析器中最简单的部分了。 本文会把重点放在词法分析器上。我们将编写一个通用的词汇库，然后用它来为IMP创建一个词法分析器。下一篇文章将会重点打造一个语法分析器和评估计算器。 词汇库词法分析器的操作相当简单。它是基于正则表达式的，所以如果你不熟悉它们，你可能需要读一些资料。简单来说，正则表达式就是一种能描述其他字符串的特殊的格式化的字符串。你可以使用它们去匹配电话号码或是邮箱地址，或者是像我们遇到在这种情况，不同类型的标记符。 词法分析器的输入可能只是一个字符串。简单起见，我们将整个输入文件都读到内存中。输出是一个标记符列表。每个标记符包括一个值（它代表的字符串）和一个标记（表示它是一个什么类型的标记符）。语法分析器会使用这两个数据来决定如何构建一棵抽象语法树。 由于不论何种语言的词法分析器，其操作都大同小异，我们将创建一个通用的词法分析器，包括一个正则表达式列表和对应的标签（tag）。对每一个表达式，它都会检查是否和当前位置的输入文本匹配。如果匹配，匹配文本就会作为一个标记符被提取出来，并且被加上该正则表达式的标签。如果该正则表达式没有标签，那么这段文本将会被丢弃。这样免得我们被诸如注释和空格之类的垃圾字符干扰。如果没有匹配的正则表达式，程序就要报错并终止。这个过程会不断循环直到没有字符可匹配。 下面是一段来自词汇库的代码：
|
上一篇：从头开始实现神经网络：入门