本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。
在这一篇文章中，我们完成上一篇文章留下的练习，结束这个算术表达式解释器的任务。
练习的内容是：更新文法并扩展解释器，让它能够处理类似“ 7 + 3 * (10 / (12 / (3 + 1) – 1))” 这样多层嵌套的带有括号的算术表达式。
相信大家跟我一样，在思考新的文法上耗费了很长时间。
如果真正的去思考了，那么看到新的文法之后，就会恍然大悟。
当然，如果自己就写出了正确的文法，那就更棒了。
在新的文法中，关键点在于一个括号以及内部的表达式，我们如何在文法中做处理。
可能有朋友已经在处理过程上做了很多思考，想到了递归去层层处理括号和其中的表达式。
但是，递归如何体现在文法中？
答案是，括号和内部表达式，我们当做一个基本单位去处理。
我们来看更新后的语法：
expr：term((PLUS|MINUS)term)*
term：factor((MUL|DIV)factor)*
factor：INTEGER|LPAREN expr RPAREN
在新的语法中，基本单位不再仅仅是INTEGER，而是新增了一个LPAREN expr RPAREN。
LPAREN是一个表示左括号的终结符；
RPAREN是一个表示右括号的终结符；
而这两个终结符中间的expr是非终结符，引用expr这个规则。
这时的文法，已经能看出递归的存在。
当遇到左括号的时候，调用expr()方法计算括号内部的表达式，在遇到右括号时将括号内表达式的计算结果返回。
当然，在括号中的表达式也存在括号时，也会执行这样的过程，指到找不到再深一层的括号与表达式，将结果逐层向上返回。
举个例子：3*(2+(8/4))-1的计算过程。
得到了新的文法，我们就可以根据新的文法编写代码了。
一、添加左右括号的常量
示例代码：
INTEGER, PLUS, MINUS, MUL, DIV, EOF, LPAREN, RPAREN = 'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', 'EOF', 'LPAREN', 'RPAREN' # 新增加左右括号常量
二、增加获取左右括号的记号
示例代码：
def get_next_token(self):
while self.current_char is not None:
...省略部分代码...
if self.current_char == '(': # 新增
self.advance()
return Token(LPAREN, '(')
if self.current_char == ')': # 新增
self.advance()
return Token(RPAREN, ')')
self.error()
return Token(EOF, None)
三、更新处理基本单位的方法
def factor(self):
current_token = self.current_token
if current_token.value_type == INTEGER: # 处理整数
self.eat(INTEGER)
return current_token.value
elif current_token.value_type == LPAREN: # 处理括号内表达式
self.eat(LPAREN) # 验证左括号
result = self.expr() # 计算括号内的表达式
self.eat(RPAREN) # 验证右括号
return result # 返回括号内表达式的值
代码经过以上的添加和修改，就能够满足我们解释多层嵌套并且带有括号算术表达式的要求了。
下一篇文章开始，我们会接触到更多关于递归下降语法分析器的细节。
并且，会接触到一种重要的、在解释器和编译器构造中被广泛使用的数据结构，这种数据结构将会贯穿本系列的后续文章。
项目源代码下载：【点此下载】
转载请注明：魔力Python » 一起来写个简单的解释器（6）