一起来写个简单的解释器(5):加减乘除表达式

本系列:


如何创建一个解释器或编译器这么复杂的问题,你会如何处理呢?开始的时候它很像是一团乱糟糟的毛线,你得重新梳理展开,然后缠成一个完美的毛线球 。

达到上述目的的方法只需一次解开一根线、一个结。虽然有时候你可能会觉得你无法马上理解某些事情,但是你必须坚持下去。我保证如果你足够坚持,最后你会“豁然开朗”(哎呀呀,如果每次我不能马上弄懂某些事情的时候,我都存 25美分,那么我早就变成富豪了 :))。

关于理解如何创建一个解释器和编译器,也许我能给你的最好建议之一就说阅读本系列文章的解释、代码,然后自己去编写代码,甚至在一段时间内多次编写同样的代码,使得这些材料和代码对于你来说是很自然的。直到那时才继续学习新的主题。不要着急,请慢下来,花时间去深刻地理解基础概念。虽然这种方法看起来有点慢,但是你会受益匪浅。相信我。

你在最后终究会得到完美的毛线球。你知道吗?即使它不够完美,但是总比什么都不做和不学习这些课题,或者走马观花然后几天之后就忘记了要好。

记住——只需要坚持不懈地解开缠绕:一次一根线、一个结,并且通过编写大量代码来实践你所学过的:

今天你将会用到在本系列前面几篇文章中学到的所有知识,并且学习如何解析和解释带有任意数量的加法、减法、乘法和除法运算符的算术表达式。你将会编写一个可以计算像“14 + 2 * 3 – 6 / 2”这样的表达式的解释器。

在深入研究和编写代码之前,让我们讨论一下运算符的结合律优先级

按照约定,7 + 3 + 1 等同 (7 + 3) + 1,7 – 3 – 1 等同 (7 – 3) – 1。这里没有什么可惊讶的。我们在某个时候学过那些约定,并且从那以后把那些约定当作是理所当然的。如果我们把 7 – 3 – 1 当作是 7 – (3 – 1),那么结果会是 5 而不是预期的 3。

在普通的算术运算和大部分编程语言中,加法、减法、乘法和除法都是左结合

一个运算符是左结合是什么意思?

当一个操作数像表达式 7 + 3 + 1 中的 3 一样两边都有加号时,我们需要一个约定来决定哪个运算符适用于 3。是操作数 3 左边的运算符还是右边的?因为两边都有加号的操作数属于它左边的运算符,所以 + 运算符结合左边的操作数。因此我们说运算符 + 是左结合。那就是为什么根据结合律,7 + 3 + 1 等同于 (7 + 3) + 1。

好,那么像 7 + 5 * 2 这样的表达式中的操作数 5,两边有着不同种类的运算符会是怎样呢?该表达式等同于 7 + (5 * 2) 还是 (7 + 5) * 2?我们如何解决这个歧义呢?

在这个例子中,结合律对我们已经没有帮助了。因为它只适用于同一种运算符,要么是加法类(+、-),要么是乘法类(*、/)。当在同一条表达式中有不同种类的运算符时,我们需要另一个约定来解决歧义。我们需要定义了运算符相对优先级的约定。

这就是了:如果运算符 * 比 + 先接受操作数,那么我们说 * 有更高的优先级。在我们知道和使用的算术运算中,乘法和除法比加法和减法优先级更高。所以表达式 7 + 5 * 2 等同于 7 + (5 * 2),表达式 7 – 8 / 4 等同于 7 – (8 / 4)。

在一个例子中,表达式的运算符有同样的优先级,我们只需运用结合律并且从左到右执行运算符:

讨论这么多关于运算符的结合律和优先级,我希望你不要认为我想让你无聊死。那些约定的好处是我们可以从一个展示算术运算符的结合律和优先级的表格中构建算术表达式的文法。然后我们可以遵循我在《一起来写个简单的解释器(4)》文章中概括的准则,将文法翻译成代码,我们的解释器也有能力处理除了结合律之外的运算符优先级。

好了,下面是我们的优先级表格:

在表格中,运算符 + 和 – 有着相同的优先级,它们都是左结合的。你也可以看到运算符 * 和 / 也是左结合,有着相同的优先级,但是它们的优先级比加法和减法运算符的优先级要高。

下面是如何根据优先级表格构建文法的规则:

  1. 为每个优先级定义一个非终结符。非终结符所在产生式的主体应该包含同等级的算术运算符和优先级高一级的非终结符。
  2. 为表达式创建一个额外的非终结符 factor 作为基本单位,在我们的例子中该基本单位是整数。通用的规则是如果你有 N 层优先级,那么你总共需要 N + 1 个非终结符:每层优先级需要一个非终结符,加上一个用作表达式基本单位的非终结符。

继续前进!

下面我们根据这些规则来构造文法。

根据规则 1,我们要定义两个非终结符:用于等级 2 的非终结符称为 expr,用于等级 1 的非终结符称为 term。而根据规则 2,我们将定义一个 factor (即一个整数)用作算术表达式的基本单位。

新文法的开始符号exprexpr 产生式包含一个主体,该主体使用来自等级 2 的运算符(在我们的例子中是 + 和 – 运算符)。同时 expr 产生式也包含更高优先级(等级 1)的 term 非终结符:

term 表达式包含一个主体,该主题使用来自等级 1 的运算符(在我们的例子中是 * 和 /)。同时 term 产生式也包含用作表达式基本单位的 factor(即整数):

而非终结符 factor 的产生式是:

我们已经在前几篇文章中看过上述产生式的文法和语法图形式,下面我们将会把它们结合到一个文法中,该文法会关注到运算符的结合律和优先级:

下面是与上述文法相对应的语法图:

框图中的每个矩形框是对另一个框图的“方法调用”。对于表达式 7 + 5 * 2,如果你从最上面的框图 expr 开始一直往下看到最下面的框图 factor,那么你应该可以看到较下面的框图中更高级的运算符 * 和 / 会比较上面的框图中运算符 + 和 – 先执行。

为了彻底地说明运算符的优先级,下面我们看一下根据上述的文法和语法图对同一个算术表达式 7 + 5 * 2 的分解。这只是从另一方面展示更高优先级的运算符会比低优先级运算符先执行:

好的,下面根据《一起来写个简单的解释器(4)》中的准则将文法转换成代码,再看下我们的新解释器是怎么工作的,好吗?

再次列出文法:

下面是一个计算器的全部代码,该计算器可以处理包含整数和任意数量的加法、减法、乘法和除法(整除)运算符的有效算术表达式。

下面是对比《一起来写个简单的解释器(4)》中的代码的主要修改:

  • Lexer 类现在可以标记 +、-、* 和 /(这里没有新的东西,我们只是把以前的代码整合到一个类中,从而支持所有的标记)
  • 回想一下,文法中定义的每条规则(产生式),R,会变成一个同名的方法,而对那条规则的引用变成一个方法调用:R()。因此 Interpreter 类现在有三个方法,分别对应文法中的非终结符:exprtermfactor

源代码:

将上述代码保存到 calc5.py 文件中,或者直接从 GitHub 上下载。像往常一样,自己尝试一下,看下解释器是否可以正确地计算出带有不同优先级运算符的算术表达式。

下面是运行在我的电脑上一段简单的会话:

下面是今天的练习:

  • 不要窥视文章中的代码,不假思索地编写一个类似这篇文章中描述的解释器。为你的解释器写一些测试,确保都通过这些测试。
  • 扩展解释器来处理包含括号的算术表达式,使得你的解释器可以计算像 7 + 3 * (10 / (12 / (3 + 1) – 1)) 这样深层嵌套的算术表达式。

检测你的理解。

  1. 运算符是左结合是什么意思?
  2. 运算符 + 和 – 是左结合还是右结合?运算符 * 和 / 呢?
  3. 运算符 + 的优先级比 * 高么?

嘿,你读到最后了!真是太棒了。下次我会带来一篇新的文章——敬请期待,还有不要忘记做练习哦。

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

  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)

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

打赏译者

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

1 4 收藏 评论

关于作者:Sam Lin

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

相关文章

可能感兴趣的话题



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