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

本系列:

今天是个好日子 :) 你可能会问:“为什么?”。原因是今天我们会在文法中添加括号表达式和实现可以计算像 7 + 3 * (10 / (12 / (3 + 1) – 1)) 这样任意深度嵌套的括号表达式的解释器,然后结束关于算术表达式的讨论(好吧,差不多)。

让我们开始吧,好吗?

首先,修改文法以支持带有圆括号的表达式。记得在《一起来写个简单的解释器(5)》曾经提到,factor 规则是表达式的基本单位。在那篇文章中,我们只有一个整数作为基本单位。今天我们将会添加另一个基本单位——一个括号表达式。那么开始吧。

下面是更新后的文法:

exprterm 表达式与《一起来写个简单的解释器(5)》中的完全一样,唯一的变化是在 factor 产生式中,终结符 LPAREN 代表左括号 ‘(’,终结符 RPAREN 代表右括号 ‘)’,在圆括号里面的非终结符 expr 代表 expr 规则。

下面是更新过的 factor 语法图,语法图现在包括两项:

因为 exprterm 的文法规则没有改变,所以它们的语法图与《一起来写个简单的解释器(5)》中的是一样的:

新的文法中有一个有趣的特点——它是递归的。如果你尝试得到表达式 2 * (7 + 3),那么你会以开始符号 expr 开始,最后你还是会再次递归地使用 expr 规则,从而得到原来算术表达式的一部分 (7 + 3)。

下面根据文法来分解表达式 2 * (7 + 3) 并看下它是如何工作的:

一段题外话:如果你需要关于递归的资料,那么你可以看一下 Daniel P. Friedman 和 Matthias Felleisen 的这本书《The Little Schemer》——它真的写得很好。

好了,让我们继续将新的更新后的文法翻译成代码。

下面是对比上篇文章的代码主要修改的地方:

  1. 修改 Lexer 使之返回两个以上的标记:代表左括号的 LPAREN 和代表右括号的 PAREN。
  2. Interpreterfactor 方法被稍微更新成除了可以解析整数之外,还可以解析括号表达式。

下面是一个计算器的全部代码,该计算器可以计算包含整数、任意数量的加法、减法、乘法和除法(整除)运算符和任意深度嵌套的括号表达式的算术表达式:

将上述的代码保存到 calc6.py 文件,自己尝试一下,看下新的解释器是否可以正确地计算出带有不同运算符和括号的算术表达式。

下面是一段简单的会话:

下面是今天的新练习:

  • 像这篇文章中介绍的一样,写一个你自己的算术表达式解释器。记住:重复是学习之母。

嘿,你读到最后了!恭喜,你刚学习了如何创建(如果你完成了练习,那么你事实上编写了)一个基本的、可以计算相当复杂的算术表达式的递归下降解析器/解释器

下一篇文章我将会谈及更多关于递归下降解析器的细节。我还会介绍一种重要的、在解释器和编译器构造中被广泛使用的数据结构,该数据结构将会贯穿后续的系列文章。

敬请期待和很快再见。直到那时,继续编写你的解释器,最重要的是:享受这个过程!

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

  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)

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

打赏译者

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

2 8 收藏 2 评论

关于作者:Sam Lin

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

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部