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

本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。

在鲁斯兰文章的原文中，有这样的内容：

Remember what Confucius said?

“I hear and I forget.”

“I see and I remember.”

“I do and I understand.”

这几句话的意思是：

记得孔夫子说过的话吗？

听而易忘。

学而易记。

行而易懂。

虽然，这几句话并不是孔子曾经说过的。

但是，在儒家文化中，确实有相似的言论，它是荀子说的。

“闻之而不见，虽博必谬；见之而不知，虽识必妄；知之而不行，虽敦必困。”

这句话的意思是：只是耳闻，不曾亲见，知识虽多，必有谬误；只是眼见，不能懂得，见识虽广，必多虚妄；只是懂得，不去实践，学问虽深，必会受挫。

这句话出自《荀子•儒效》，指学习、思考和实践，应该环环相扣。

鲁斯兰的意思很明白了。

我们学习编程的过程中，不仅仅要能看懂代码，更重要的是要亲自动手练习，因为即便能看懂，未必能够写得出来。

好了，进入正题。

这一篇文章中，我们一起学习如何识别（解析）和解释带有任意数量乘法或者除法运算符的表达式，例如：5*6/7*8。

需要说明一点，这篇文章中提到的除法是整除，例如，“15/4”的结果是“3”，也就是不包含小数部分。

但这些并不是这篇文章的重点，这篇文章的重点是一种新的知识：文法（BNF）。

确切来说，是上下文无关文法（Backus-Naur Form 巴科斯-诺尔范式）。

这篇文章中介绍的是基于BNF的扩展文法EBNF。

不要头疼这些看似深奥的名称，继续往下看。

首先，我们通过一张图来看一下，如何通过文法描述乘除法的表达式。

看不太懂是吧？

那好，给一些提示：

MUL：表示乘；

DIV：表示除；

INTEGER：表示整数；

factor：表示因数的变量；（如果不知道什么是因数，请去看望一下你的小学数学老师。）

| ：表示或者；

( … ) ：表示多个可选项的组合；

( … )*：表示括号中的内容出现0~N次。

如果还是不太懂，我们把第二句代入第一句进行替换，并且将( … )*展开。

为了方便理解，我把循环的部分的每一次循环用了彩色的文字表示。

阅读一下：整数（乘以或除以）整数（乘以或除以）整数（乘以或除以）整数…

所以，我们看到的语法，简洁的表达了类似“3”、“3*5”或者“3*8/4”乃至“3*9/2*4*5”这样的乘除法表达式。

还记得语法图吗？

对于同一个 expr 规则的语法图：

好了，现在我们再来说概念。

一段文法由一系列的规则（Rule）组成，规则也称为产生式（Productions）。

第一条规则左边的非终结符是开始符号（Start Symbol）。

每一个产生式，都是由产生式的头（左边）、一个冒号和产生式的主体（右边）组成。

产生式的左边是一个非终结符，右边由多个终结符或非终结符组成。

听上去很拗口，实际上我们可以这么理解，非终结符是变量，都有自己的主体，而终结符（Token）是非终结符的主体组成部分。

观察一下上图，大家能够看到，终结符是不可在被替换的，当它出现之后，对它的操作就终结了；而非终结符出现在其它非终结符主体中（引用）时，可以替换为自己的主体，也就是说对它的操作还未终结。

如果还不明白这个原理，我们再来看几个例子。

1、通过文法得到表达式“3”。

2、通过文法得到表达式“3*7”。

3、通过文法得到表达式“3*7/2”。

到这里，我们已经了解了文法的原理，这也是使用文法的原因。

1、文法以简明的方式指定一种编程语言的语法；不像语法图，文法十分简洁。

2、文法可以当做很好的文档。

3、通常可以通过遵循一系列简单的规则将文法转换成代码。

文法通过解释它可以形成的语句来定义语言（Language）。

就如同大家在前面看到的带有彩色字体的那张示意图以及刚刚的几个例子，从expr开始，反复地用一个非终结符的主体替换非终结符，直到产生一个只包含终结符的语句。

那些语句形式就是由文法定义的语言。

如果文法不能得到一条确定的算术表达式，那么它不支持该表达式，并且当Parser（语法分析器）尝试识别该表达式时，会生成一个语法错误。

文法在实际应用中非常广泛，特别是在编译器和解释器的相关文献中。

这是非常值得学习的内容。

这也是这篇文章为什么如此详细的解释文法的工作原理以及它和语法分析器以及词法分析器的关系。

接下来，我们将文法转换成代码。

下面是将文法转换成代码的准则：

每条规则（Rule）的头部（非终结符），都要变成一个同名的方法（例如：factor），而对规则的引用变成一个方法调用（例如：factor()）;方法的主体是同一条规则的主体。

(…)包含多个可选项，例如“(PLUS|MINUS|MUL|DIV) ”，变成“if…elif…else”语句。

(…)*包含可重复的内容，变成循环（while）语句，可以循环0~N次。

每个终结符的引用 （例如：INTEGER），变成对“eat()”方法的调用，例如“eat（INTEGER）”。

这些准则直观上看起来像这样：

接下来，我们参考上面的准则，完成代码片段。

示例代码：

def factor(self): self.eat(INTEGER)def expr(self): self.factor() while self.current_token.value_type in (MUL, DIV): token = self.current_token if token.value_type == MUL: self.eat(MUL) self.factor() elif token.value_type == DIV: self.eat(DIV) self.factor()

上面的代码我没有添加任何注释，但是，如果大家认真的完成了以往的练习，这段代码能够轻易读懂。

而且，最好不要看这段代码，参照上面的准则，自己思考写出这段代码。

在这篇文章的最后，我们应该能够通过自己的理解，独立完成任意数量乘法和除法表达式的解释代码。

并且，此时我们可以把词法分析器独立出来成为一个Lexer类，将一个Lexer的实例作为参数更新Interpreter类。

还有，不要忘了主函数“main()”需要略作修改。