一起写个简单的解释器（2）（3）（4）

一起写个简单的解释器（2）

第二版代码，已加中文注释。github

处理输入字符串中的空白字符；
处理输入中的多位整数；
两整数相减（第一版只能相加）；

成为一个你所使用的工具或框架的专家固然重要，但了解背后的原理也是极为重要的。正如拉尔夫·沃尔多·爱默生所说：

“如果你仅仅学习方法，那么你将被方法所束缚。但是如果你学习原理，你将能够设计自己的方法。”

与第一版代码相比，最主要的变化有：

get_next_token 方法稍微重构了一点。pos 指针的自增逻辑放到了一个独立的 advance 方法。
增加了两个方法：skip_whitespace 方法用来忽略空白字符，integer 方法用来处理输入中的多位整数。
修改了 expr 方法，在识别 INTEGER -> PLUS -> INTEGER 短语的基础上，识别 INTEGER -> MINUS -> INTEGER 短语。在成功识别相应短语后，这个方法现在也能够解释加法和减法了。

练习

什么是 lexeme ？
找出 token 流中的结构的过程叫什么？换句话说，从 token 流中识别出特定短语的过程叫什么？

3.解释器（编译器）中做 parsing（语法分析）的部分的名称是什么？

解答

lexeme 就是组成 token 的字符序列。
找到 token 流中的结构的过程，换句话说，识别 token 流中的短语的过程称之为 parsing（语法分析）。试图识别（parsing）token 流中的 INTEGER -> PLUS -> INTEGER 或 INTEGER -> MINUS -> INTEGER 短语。
解释器或编译器中用以完成这样的工作的部分，称之为 parser（语法分析器）。

一起写个简单的解释器（3）

第三版代码，已加中文注释。github

语法图

语法图是什么？语法图是指表示一种程序设计语言语法规则的示意图。本质上，一个语法图直观地显示了在你的程序设计语言中，允许使用哪些语句和不允许使用哪些语句。

语法图的两个主要目的：

它们以图表的形式表示一种程序设计语言的规范（语法）。

它们可以帮助你编写解析器，你可以通过遵循简单的规则将一个图表映射成代码。

新版本计算器的源代码，该计算器可以处理包含整数和任意数量加法和减法运算符的有效的算术表达式。

expr 方法有一个可以执行 0 次或者多次的 while 循环。在循环中，parser 根据 token 进行判断（是一个加号还是减号）。然而 parser 本身并不会解释所有东西：识别到表达式，不做什么处理。如果它识别不到，它会抛出一个语法错误。在 expr 中添加 interpreter 代码，因为 interpreter 需要求表达式的值，因此修改 term 方法使之返回一个整数值，修改 expr 方法使之在适当的地方执行加法和减法并且返回解释的结果。

一起写个简单的解释器（4）

第四版代码，已加中文注释。github

上下文无关文法

另一种被广泛使用的、用于指定一种程序设计语言语法的表示法。它叫做上下文无关文法（简称文法）或者 BNF（Backus-Naur Form 巴科斯-诺尔范式）。

下面是使用文法的几个原因：

文法以简明的方式说明一种程序设计语言的语法。不像语法图，文法十分简洁。你将会看到我在未来的文章中越来越多地使用文法。
文法可以用作很好的文档。
即使你从零开始编写你的解析器，文法也是一个很好的起点。通常，你可以通过遵循一系列简单的规则将文法转换成代码。
有一组工具叫做解析器生成器，它接收一段文法作为输入，并且根据那段文法自动地生成一个解析器。我会在系列后面的文章中讨论那些工具。

下面是描述像“7 * 4 / 2 * 3”（它只是众多可以由文法生成的表达式之一）这样的算术表达式的一段文法：

expr : factor((mul|div)factor)*
factor : INTEGER

一段文法由一系列规则（rule）组成，也称为产生式（productions）。在我们的文法中有两条规则。

一条规则由一个非终结符（称为产生式的头或者左边）、一个冒号和一系列终结符，如’(‘、 ‘|’ 、’)’、非终结符（称为产生式的主体或者右边）组成。

上面介绍的文法中，像 MUL、DIV 和 INTEGER 这样的标记称为终结符（terminals），像 expr 和 factor 这样的变量称为非终结符（non-terminals）。

第一条规则左边的非终结符符号称为开始符号（start symbol）。在我们的文法例子中，开始符号是 expr。

一起写个简单的解释器（2）（3）（4）