最新消息:欢迎光临 魔力 • Python!大家可以点开导航菜单中的【学习目录】,这个目录类似图书目录,更加方便学习!

一起来写个简单的解释器(6)

Python教程 小楼一夜听春语 1143浏览 0评论

本系列文章参考国外编程高手鲁斯兰的博客文章《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)

头像
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网站 (可选)