一起来写个简单的解释器(3):任意数量的加法和减法


今早起来我就想:“为什么我们学习一项新技能这么困难?”

我不认为这仅仅是因为艰苦的工作。我认为其中一个原因是我们花费了很多时间和努力去阅读和观看,从而获取知识。然而并没有足够的时间通过实践将知识转换成技能。以游泳为例。你可以花很多时间去阅读数以百计关于游泳的书,与有经验的游泳运动员和教练聊上几个小时,看培训视频,然而在你第一次跳进游泳池里面时,你仍然会像石头一样往下沉。

最根本的是:不管你觉得你对某个科目有多了解——你必须把知识付诸实践,从而将知识转化成技能。为了帮助你去实践,我将一些练习放到了《一起来写个简单的解释器》系列文章的第一篇第二篇中。当然,你将会在今天的这篇文章或者以后的文章中看到更多的练习,我发誓 :)

好了,让我们开始今天的文章吧,好吗?

目前,你已经学习了如何解释像“7 + 3”或者“12 – 9”这样的两个整数相加或者相减的算术表达式。今天,我将会介绍关于如何解析(识别)和解释带有任意数量加法或者减法运算符的算术表达式,例如“7 – 3 + 2 – 1”。

可以用下面的语法图来表示这篇文章的算术表达式:

语法图是什么?语法图是指表示一种程序设计语言语法规则的示意图。本质上,一个语法图直观地显示了在你的程序设计语言中,允许使用哪些语句和不允许使用哪些语句。

语法图十分易于阅读:只需跟随箭头指示的路径。一些路径表示选择。另一些路径表示循环。

你可以像下面一样阅读上面的语法图:一个 term 有选择地接着一个加号或者减号,再跟着另一个 term,依次是有选择地接着一个加号或者减号,再跟着另一个 term 等等。你可能会好奇一个“term”是什么。对于本文,一个“term”就是一个整数。

语法图的两个主要目的:

  • 它们以图表的形式表示一种程序设计语言的规范(语法)。
  • 它们可以帮助你编写解析器,你可以通过遵循简单的规则将一个图表映射成代码。

你已经知道在一连串 token 中识别出一个短语的过程称作 parsing。一个解释器或者编译器用于处理工作的部分称作 parser。parsing 也叫作语法分析syntax analysis),而 parser 贴切地称为,你猜对了,一个语法分析器syntax analyzer)。

根据上面的语法图,下面所有的算术表达式都是有效的:

  • 3
  • 3 + 4
  • 7 – 3 + 2 – 1

因为在不同的程序设计语言中,算术表达式的语法规则十分相似,所以我们可以使用 Python shell 来“测试”我们的语法图。启动 Python shell 并且查看结果:

这里没什么特别之处。

然而表达式“3 + ”并不是一个有效的算术表达式,因为根据语法图,加号后面必须跟着一个 term(整数),否则将会是一个语法错误。再次,用 Python shell 尝试一下并且查看结果:

能够用 Python shell 来做一些测试当然很好,但是还是让我们将上述语法图映射成代码并使用我们自己的解释器来测试,如何?

从以前的文章(第一篇第二篇)中,你已经知道我们的 parser 和 interpreter 位于 expr 方法中。再次说明,parser 仅仅识别结构并确保这个结构符合一些规范,一旦 parser 成功识别(解析)出结构,interpreter 会对表达式求值。

下面的代码片段介绍了相应于语法图的 parser 代码。语法图中的矩形(term)变成解析一个整数的 term 方法,而 expr 方法则遵循语法图流程:

可以看到 expr 首先调用了 term 方法。然后,expr 方法有一个可以执行 0 次或者多次的 while 循环。在循环中,parser 根据 token 进行判断(是一个加号还是减号)。花一些时间自行验证上面的代码的确遵循算术表达式的语法图流程。

然而 parser 本身并不会解释所有东西:如果它识别到表达式,它会沉默。如果它识别不到,它会抛出一个语法错误。下面让我们修改 expr 方法并添加 interpreter 代码:

因为 interpreter 需要求表达式的值,因此修改 term 方法使之返回一个整数值,修改 expr 方法使之在适当的地方执行加法和减法并且返回解释的结果。尽管代码非常简单,我还是建议你花一点时间去学习一下。

现在让我们继续往下,看看 interpreter 完整的代码,可以不?

下面是新版本计算器的源代码,该计算器可以处理包含整数和任意数量加法和减法运算符的有效的算术表达式:

将上面的代码保存到 calc3.py 文件中,或者直接在 GitHub 上下载。尝试一下。亲自看看,它可以处理从前面展示的语法图中获得的算术表达式。

下面是我在我的笔记本上运行的示例会话:

记得我在文章开头提到的那些练习么:下面就是啦,言出必行哦 :)

  • 画一个只包含乘法和除法的算术表达式语法图,例如“7 * 4 / 2 * 3”。请认真对待,拿起一支笔或者铅笔尝试画一个。
  • 修改计算器的源代码,使之可以解释只包含乘法和除法的算术表达式,例如“7 * 4 / 2 * 3”。
  • 从头开始写一个 interpreter 来处理像“7 – 3 + 2 – 1”这样的算术表达式。使用任何你运用自如的程序设计语言,在不看例子的情况下写出来。当你这样做时,想一下有关的组件:lexer 带着一个输入并将其转换成一连串 token,parser 获取 lexer 提供的一连串 token 并且尝试在流中识别出一个结构,在 parser 成功地解析(识别)出一个有效的算术表达式之后,interpreter 会产生结果。把这些片段串在一起。花一些时间将你学到的知识转化成一个可以工作的算术表达式解释器。

检查你的理解。

  1. 语法图是什么?
  2. 语法分析是什么?
  3. 语法分析器是什么?

Hey,看!你读到文章的结尾了。谢谢今天呆在这里,不过不要忘记做练习哦。:) 下次我会带来一篇新的文章——敬请期待。

下面是我推荐的一些书籍,它们可以帮助你学习解释器和编译器:

  1. 《Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)》
  2. 《Writing Compilers and Interpreters: A Software Engineering Approach》
  3. 《Modern Compiler Implementation in Java》
  4. 《Modern Compiler Design》
  5. 《Compilers: Principles, Techniques, and Tools (2nd Edition)》

打赏支持我翻译更多好文章,谢谢!

打赏译者

打赏支持我翻译更多好文章,谢谢!

3 10 收藏 评论

关于作者:Sam Lin

伪程序员 个人主页 · 我的文章 · 43 ·   

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部