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

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

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

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

在之前的文章中,我们一起学习了如何实现对两个数字加减法表达式的解释。

这一篇文章,我们一起来学习对多个数字加减法表达式的解释。

例如:12 + 8 – 6 – 10

在编写代码之前,我们先来看一张图。

这张图是语法图。

语法图是表示一种程序设计语言语法规则的示意图。

实际上,语法图体现了语法分析器(Parser)的运行规则。

一张语法图能够直观地体现在我们的程序设计语言中,允许使用哪些语句和不允许使用哪些语句。

那么,怎么阅读这张语法图呢?

我们只需跟随箭头所指的路径去了解程序的运行。

在语法图中,有些路径表示选择,例如:加法表达式和减法表达式需要选择不同的路径。

另外,有的路径表示循环,例如:多次进行加减运算的过程。

为了把这张图看的更明白,我将不同的表达式对应语法图中的路径,做了几张示意图。

其中橙色路径就是当前表达式运行的路径。

例如:

>>>3

当我们只输入一个数字,此时程序只找到了一个操作数,那就只需要把这个操作数传递出去。

例如:

>>>3+6

当我们输入了一个完整的两位数加法表达式,此时程序会先找到一个操作数,然后选择加法操作符,再找到另外一个操作数,最终识别出一个完整的短语传递出去。

例如:

>>>3+5-4-2+6

当我们输入了一个多个数字的加减法表达式,此时程序会先找到一个操作数,然后选择加法操作符,再找到另外一个操作数;此时,程序发现还有新的记号,就开始循环的过程;再次选择操作符,找到操作数,直到找不到新的记号,将完整的短语传递出去。

相信到这里,大家都应该理解了这张语法图的含义。

那么,这里我们看到了一个新的英文单词“Term”,中文含义是“术语”,但是这很难理解。

不要搞那么复杂,在这篇文章中,Term就是一个整数。

根据上面的语法图,以下表达式都是合法的:

  • 3
  • 5+16
  • 33-15+7

实际上,因为在不同的程序设计语言中,算术表达式的语法规则十分相似。

所以,在Python的Shell中,我们运行这些表达式看到的结果也没有什么区别。

然而,对于我们的解释器,表达式“3 + ”并不是一个有效的表达式。

因为,根据语法图,加号后面必须跟着一个Term(整数),否则将会是一个语法错误。

在上一篇文章中,我们知道一连串Token(Token流)中识别出一个短语的过程叫做Parsing”(语法分析)。一个解释器或者编译器用于语法分析的部分叫“Parser”(语法分析器)。

其实,“Parsing”也叫做“Syntax Analysis”,而“parser ”也叫做Syntax Analyzer

而且,我们也知道“Parser”和“Interpreter”位于“expr()”方法中。

“Parser”只负责识别结构并确保结构符合规范,当“Parser”成功识别(解析)出结构,Interpreter 会对表达式进行求值计算。

根据上面的语法图,我们重写“Parser”部分的代码。

这里我们添加一个新的方法“term()”,用于解析一个整数。

示例代码:

 

def term(self):
    self.eat(INTEGER)  # 验证整数

def expr(self):
    self.current_token = self.get_next_token()  # 获取记号
    self.term()  # 验证第一个整数
    while self.current_token.value_type in (PLUS, MINUS):  # 循环
        if self.current_token.value_type == PLUS:  # 选择加法运算符
            self.eat(PLUS)  # 验证运算符
            self.term()  # 验证下一个整数
        if self.current_token.value_type == MINUS:  # 选择减法运算符
            self.eat(MINUS)  # 验证运算符
            self.term()  # 验证下一个整数

上方代码就是根据语法图重写的代码。

不过很显然,“Parser”不会完成全部解释工作,它正确的识别表达式之后没有任何结果,只有在表达式识别失败的时候会抛出异常。

提示:大家可以尝试运行程序,输入“1+2”和“1+”进行验证。

因为,Interpreter需要表达式的值,所以,我们可以修改“term()”方法,让它返回一个整数值。

并且,我们还要修改“expr()”方法,让它在适当的位置执行加法和减法的计算,并且返回解释的结果。

示例代码:

def term(self):
    token = self.current_token  # 获取记号
    self.eat(INTEGER)
    return token.value  # 返回记号中的整数值

def expr(self):
    self.current_token = self.get_next_token()
    result = self.term()  # 获取第一个整数(Term)
    while self.current_token.value_type in (PLUS, MINUS):
        if self.current_token.value_type == PLUS:
            self.eat(PLUS)
            result += self.term()  # 已有结果加上新获取的整数(Term)
        if self.current_token.value_type == MINUS:
            self.eat(MINUS)  # 已有结果减去新获取的整数(Term)
            result -= self.term()
    return result

到这里,我们的解释器就可以完成多个数字的加减法表达式运算了。

在这篇内容的基础上,大家可以尝试进行以下功能的扩展:

  • 画一个只包含乘法和除法的算术表达式语法图,例如“7 * 4 / 2 * 3”;(不要认为很简单就不去做)
  • 重写Interpreter类的所有源代码,不要再参考写过的代码和文章,只靠自己的思考,让它可以解释只包含乘法和除法的算术表达式。

而且,当学习完这篇文章,请大家自我检查一下,是否了解了以下内容:

  • 什么是语法图?
  • 什么是语法分析?
  • 什么是语法分析器?

项目源代码下载:【点此下载

转载请注明:魔力Python » 一起来写个简单的解释器(3)

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

表情

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

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