本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。
如果没有完成上一篇文章的练习，请先关闭这篇文章去思考。
即便想不出解决方案也没有问题，至少思考会加强你的逻辑，在阅读这篇文章时，能够更快理解，获取到更多的感悟。
回顾一下上一篇的练习内容：
- 写一段文法来解释包含任意数量加减乘除运算的算术表达式；从文法中可以得到类似“2+7*4”、“7–8/4”、“14+2* 3–6/2”这样的表达式。
- 对应文法编写解释器，该解释器可以计算包含任意数量加减乘除运算的算术表达式（注意运算顺序）。
这个练习，如果能够写出文法，那么代码就不会困难。
关键在于，文法怎么写出？
练习中，我们看到类“2+7*4”这样的算术表达式。
它的结果应该是“(2+7)*4”的结果，还是“2+(7*4)”的结果呢？
显而易见是后者。
但是，我们当前的解释器还不会做“2+(7*4)”这样的解释运算。
很可能，你会发现写好的解释器，给出的是“(2+7)*4”的结果。
这是结合律的影响。
什么是结合律呢？
例如：1+2+3
计算的时候的顺序是先得到“1+2”的和，再和“3”相加，得到结果。
也就是“(1+2)+3”。
例如：3*6*9
计算的时候的顺序是先得到“3*6”的和，再和“9”相乘，得到结果。
也就是“(3*6）*9”。
相信大家都已明白左侧计算优先，或者说左结合。
当一个操作数两边都有相同的运算符号时（例如：表达式“1+2+3”中的 “2”），我们需要约定左右的两个运算符号“+”哪个适用于“2”。因为两边都有加号的操作数属于它左边的运算符，所以“2”通过左侧的“+”运算符结合左边的操作数“1”。因此我们说运算符“+”是左结合，也就是“（1+2）+3”的意思。
在普通的算术运算和大部分编程语言中，加法、减法、乘法和除法都是左结合。
不过，刚才的算术表达式有一个相同的特点，就是运算符都是相同的。
这个时候左结合的运算方式是正确的，但是如果运算符不同呢？
例如练习中的“2+7*4”。
很显然，我们不希望先算出“2+7”的结果再去和“4”相乘。
我们希望它的运算是“2+(7*4)”。
这个时候就涉及到了优先级。
大家都该知道乘除法的优先级高于加减法，在算术表达式中，如果只存在同一种运算符，那么结合律就是左结合。
下面的表格表示了各种运算符的优先级和结合律。
| 优先级 | 结合律 | 运算符 |
| 1 | 左结合 | */ |
| 2 | 左结合 | +- |
那么，当算术表达式中，同时出现了优先级不同的运算符，这个时候的文法该如何表达呢？
规则如下：
根据优先级表格构建文法的规则：
- 为每个优先级定义一个非终结符（头）。
- 非终结符所在产生式的主体应该包含同等级的算术运算符和优先级高一级的非终结符（引用）。
- 创建一个终结符“factor ”作为基本单位。
- 如果有 N 层优先级，则需要定义 N（优先级） + 1 （基本单位）个非终结符。
了解了这些规则，我们来构建文法。
根据规则，我们需要定义三个非终结符：expr（加减法）、term（乘除法）和factor（整数）。
factor比较容易定义。
factor：INTEGER
term如何定义呢？
参考之前我们定义的文法，运算的过程是一个循环。
term：factor((MUL|DIV)factor)*
最后是expr，运算过程同样是一个循序，不过非终结符是优先级更高的term。
expr：term((PLUS|MINUS)term)*
好了，我们把这几句的顺序倒过来，就是最终的文法。
expr：term((PLUS|MINUS)term)*
term：factor((MUL|DIV)factor)*
factor：INTEGER
有了这个文法的指导，我们就可以修改代码了。
一、增加加减法的常量
示例代码：
INTEGER, PLUS, MINUS, MUL, DIV, EOF = 'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', 'EOF' # 新增加减法常量
二、增加获取加减法的记号
示例代码：
def get_next_token(self):
while self.current_char is not None:
...省略部分代码...
if self.current_char == '+': # 新增
self.advance()
return Token(PLUS, '+')
if self.current_char == '-': # 新增
self.advance()
return Token(MINUS, '-')
...省略部分代码...
return Token(EOF, None)
三、增加进行乘除法解析与运算的方法
示例代码：
def term(self): # 定义乘除法的语法分析与计算方法
result = self.factor() # 引用factor
while self.current_token.value_type in (MUL, DIV):
token = self.current_token
if token.value_type == MUL:
self.eat(MUL)
result *= self.factor() # 引用factor
elif token.value_type == DIV:
self.eat(DIV)
result //= self.factor() # 引用factor
return result
四、修改expr方法用于加减法的解析与运算
示例代码：
def expr(self): # 修改为加减法的语法分析与运算
result = self.term() # 引用term
while self.current_token.value_type in (PLUS, MINUS):
token = self.current_token
if token.value_type == PLUS:
self.eat(PLUS)
result += self.term() # 引用term
elif token.value_type == MINUS:
self.eat(MINUS)
result -= self.term() # 引用term
return result
到这里，我们就能够正常的实现多个数字的加减乘除混合运算了。
为了更清晰的表达，简述一个运算的过程。
以“2+3*4-5”为例。
1、当解释器的“expr()”方法运行时，会先进入优先级最高的计算方法“term()”；
2、在“term()”方法中，引用“factor()”方法获取到第1个记号“2”，然后再获取到第2个记号“+”的类型，此时发现不符合运算要求，会将“2”作为结果返回给“expr()”方法；
3、“expr()”方法得到了“term()”方法的结果，完成了第1次对“term()”方法的引用，开始对第2个记号进行验证；发现记号是加号后，再次引用“term()”方法；
4、“term()”方法引用“factor()”方法获取到第3个记号“3”，并获取第4个记号“*”的类型，发现“*”符合运算要求，就引用“factor()”方法获取第5个记号“4”，完成一次乘法运算；
5、“term()”方法继续获取第6个记号“-”的类型，此时发现不符合运算要求，会将当前的运算结果作为结果返回给“expr()”方法；
6、“expr()”方法完成了对“term()”方法的第2次引用，获取到了“3*4”的结果，进行和第1个记号“2”的加法运算，并将结果暂存；
7、“expr()”方法对第6个记号“-”进行验证，并开始第3次引用“term()”方法；
8、在“term()”方法中，引用“factor()”方法获取到第7个记号“5”，然后发现表达式已结束，直接将“5”作为结果返回给“expr()”方法；
9、“expr()”方法完成了对“term()”方法的第3次引用，获取到了“5”之后，和暂存的计算结果进行减法运算，得到最终的运算结果；
10、“expr()”方法再次获取记号类型，发现表达式已结束，返回最终结果。
描述的很长，画张示意图可能更好理解。
除了上面要练习的内容，大家还需要进行以下练习：
- 不做任何参考，完全独立的编写一个类似这篇文章中描述的解释器，并且能够通过测试。
- 扩展解释器，让它能够处理类似“ 7 + 3 * (10 / (12 / (3 + 1) – 1))” 这样多层嵌套的带有括号的算术表达式。
而且，当学习完这篇文章，请大家自我检查一下，是否了解了以下内容：（送分题）
- 什么是运算符左结合？
- 运算符 + 和 – 是左结合还是右结合？运算符 * 和 / 呢？
- 运算符 + 的优先级比 * 高么？
项目源代码下载：【点此下载】
转载请注明：魔力Python » 一起来写个简单的解释器（5）