一起来写个简单的解释器(4):任意数量的乘法和除法

你是在被动地学习这几篇文章中的材料,还是主动地去做练习?我希望你主动地去练习。我真的希望哦 :)

记得孔子说过的话么?

“听而易忘”

“见而易记”

“做而易懂”

上一篇文章中,你已经学会了如何解析(识别)和解释带有任意数量加法或者减法运算符的算术表达式,例如“7 – 3 + 2 – 1”。你也学习了语法图以及如何使用语法图来指定一种程序设计语言的语法。

本文你将会学习如何解析(识别)和解释带有任意数量乘法或者除法运算符的算术表达式,例如“7 * 4 / 2 * 3”。这篇文章讨论的除法是整数除法,所以如果表达式是“9 / 4”,那么答案将会是一个整数:2。

今天我也会讨论不少有关另一种被广泛使用的、用于指定一种程序设计语言语法的表示法。它叫做上下文无关文法(简称文法)或者 BNF(Backus-Naur Form 巴科斯-诺尔范式)。在这篇文章中,我不会使用纯净的 BNF 表示法,而是使用类似的修改过的 EBNF 表示法。

下面是使用文法的几个原因:

  1. 文法以简明的方式说明一种程序设计语言的语法。不像语法图,文法十分简洁。你将会看到我在未来的文章中越来越多地使用文法。
  2. 文法可以用作很好的文档。
  3. 即使你从零开始编写你的解析器,文法也是一个很好的起点。通常,你可以通过遵循一系列简单的规则将文法转换成代码。
  4. 有一组工具叫做解析器生成器,它接收一段文法作为输入,并且根据那段文法自动地生成一个解析器。我会在系列后面的文章中讨论那些工具。

现在,让我们谈一下文法的原理,好吗?

下面是描述像“7 * 4 / 2 * 3”(它只是众多可以由文法生成的表达式之一)这样的算术表达式的一段文法:

一段文法由一系列规则(rule)组成,也称为 产生式(productions)。在我们的文法中有两条规则:

一条规则由一个非终结符(称为产生式的或者左边)、一个冒号和一系列终结符(和 | 或者)非终结符(称为产生式的主体或者右边)组成:

上面介绍的文法中,像 MUL、DIV 和 INTEGER 这样的标记称为终结符(terminals),像 exprfactor 这样的变量称为非终结符(non-terminals)。非终结符通常由一系列终结符(和 | 或者)非终结符组成:

第一条规则左边的非终结符符号称为开始符号(start symbol)。在我们的文法例子中,开始符号是 expr

你可以这样读 expr 规则:“expr 可以是一个 factor 可选地接着一个乘法或者除法运算符,再接着另一个 factor,依次可选地接着一个乘法或者除法运算符,再接着另一个 factor……”

factor 是什么?就本文而言,factor 就是一个整数。

让我们快速地回顾一下文法中用到的符号和它们的含义。

  • | – 多选一。表示“或”。所以 (MUL | DIV) 表示要么是 MUL,要么是 DIV。
  • ( … ) – 一对圆括号表示把终结符(和 | 或者)非终结符组合起来,就像 (MUL | DIV) 一样。
  • ( … )* – 匹配组合里面的内容 0 次或者多次。

如果你以前了解过正则表达式,那么 |()(…)* 这些符号对于你来说应该会比较熟悉。

一段文法通过说明它可以组成什么句子来定义一种语言(language)。这是如何使用文法推导出算术表达式:首先以开始符号 expr 开始,然后反复地用一个非终结符所在规则的主体替代该非终结符,直到产生一个只包含终结符的句子。那些句子组成了由文法定义的语言

如果文法不能得到一条确定的算术表达式,那么它不支持该表达式,并且当解析器尝试识别该表达式时,解析器会生成一个语法错误。

我依次想了几个例子。下面是文法如何得到表达式 3 的例子:

这是文法如何得到表达式 3 * 7 的例子:

这是文法如何得到表达式 3 * 7 / 2 的例子:

哇,这里有相当多的理论!

我想当我第一次阅读关于文法相关的术语和诸如此类的东西,我有这样一种感觉:

我可以向你保证我肯定不会像这样:

我花费了一些时间来适应这种表示法,它是如何工作的和它与解析器、语法分析器的关系。但是我必须告诉你,从长远来看,学习它是值得的。因为它在实际中被广泛应用,你也一定会遇到一些编译器文献在某些时候会用到它。所以,为何不早点学呢?:)

现在,让我们将文法映射成代码,可以么?

这里是用于将文法转换成源代码的准则。遵循这些准则,你可以逐字逐句地把文法翻译给正在工作的分析器:

  1. 文法中定义的每条规则,R,会变成一个同名的方法,而对那条规则的引用变成一个方法调用:R()。方法的主体跟着同一套准则的规则的主体流。
  2. 多个可选项 (a1 | a2 | aN) 变成 if-elif-else 语句。
  3. 可选的 (…)* 集合变成 while 语句,该语句可以循环 0 次或者多次。
  4. 每个符号引用 T 变成对 eat 方法的调用:eat(T)eat 方法的工作方式是如果该方法匹配当前的 lookahead 符号,那么 eat 方法会传入符号 T,然后它会从词法分析器中得到一个新的符号,并且把该符号分配给内部变量 current_token

这些准则直观上看起来像这样:

让我们继续前进,遵循上述准则将我们的文法转换成代码。

在我们的文法中有两条规则:expr 规则和 factor 规则。我们以 factor 规则(产生式)开始。根据准则,你需要创建一个名为 factor 的方法(准则 1),该方法有一个对以 INTEGER 符号为参数的 eat 方法的调用(准则 4):

这很简单,不是吗?

继续!

expr 规则变成 expr 方法(再次依据准则 1)。该规则开始是对变成了 factor() 方法调用的 factor 的引用。可选的集合 (…)* 变成一个 while 循环,(MUL | DIV) 变成 if-elif-else 语句。把那些代码段组合在一起,我们得到了下面的 expr 方法:

请花点时间学习一下我是如何将文法映射成源代码的。确保你弄懂了那部分的内容,因为在以后会派上用场的。

为了方便,我将上述的代码放到 parser.py 文件中,它包含一个词法分析器和一个解析器,不包含解释器。你可以直接从 GitHub 下载文件并使用它。该程序有交互式提示,你可以在提示中输入表达式并查看表达式是否可用:也就是说,依据文法构建的解析器是否可以识别该表达式。

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

试一下!

我忍不住再次提到语法图。这是对于同一个 expr 规则的语法图:

我们是时候专研一下新的算术表达式解释器的源代码了。下面的代码是一个计算器,该计算器可以处理包含整数和任意数量的乘法和除法(整除)运算符的有效算术表达式。你也可以看到我把词法分析器重构成一个 Lexer 类,并且把 Lexer 实例作为参数更新 Interpreter 类:

将上面的代码保存到 calc4.py 文件或者直接从 GitHub 上下载。像往常一样,亲自试一下并看下它是如何工作的。

这是运行在我的笔记本上一段简单的会话:

我知道你迫不及待这一部分了 :) 这是今天新的练习:

  • 写一段文法来描述包含任意数量的 +、-、* 或者 / 运算符的算术表达式。你应该有能力从文法中得到像“2 + 7 * 4”、“7 – 8 / 4”、“14 + 2 * 3 – 6 / 2” 等这样的表达式。
  • 使用文法,编写一个解释器,该解释器可以计算包含任意数量的 +、-、* 或者 / 运算符的算术表达式。你的解释器应该可以处理像“2 + 7 * 4”、“7 – 8 / 4”、“14 + 2 * 3 – 6 / 2” 等这样的表达式。
  • 如果你完成了上述的联系,那么放松一下把 :)

检测你的理解。

牢记今天这篇文章介绍的文法,回答下面的几个问题,需要时可以参考下面的图片:

lsbasi_part4_bnf1

  1. 什么是上下文无关文法?
  2. 文法有多少条规则或者产生式?
  3. 什么是终结符?(在图片中找到所有的终结符)
  4. 什么是非终结符?(在图片中找到所有的非终结符)
  5. 什么是一条规则的头部?(在图片中找到所有的头部或者左边)
  6. 什么是一条规则的主体?(在图片中找到所有的主体或者右边)
  7. 文法的开始符号是什么?

嘿,你读到最后了!这篇文章包含了相当多理论,所以我真的为你读完这篇文章而感到骄傲。

下次我会带来一篇新的文章——敬请期待,不要忘记做练习哦,它们对你有好处的。

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

  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 3 收藏 评论

关于作者:Sam Lin

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

相关文章

可能感兴趣的话题



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