一起来写个简单的解释器(2):两个整数相加或相减

Burger 和 Starbird 在其著作《高效思考的 5 要素》中分享了他们如何观察 Tony Plog 的故事。Tony Plog是一名享誉世界的小号艺术家,经营了一家针对熟练小号演奏者的高级讲习班。学生们一开始就可以熟练地演奏复杂的乐句,他们演奏得很棒。然后他们被要求演奏非常基础的、简单的音符。当他们演奏这些音符时,这些音符和先前被演奏的复杂乐句相比,听起来就很稚嫩了。他们演奏完毕后,主讲老师也演奏了同样的音符,不过他演奏时,这些音符听起来并不稚嫩。区别是令人震撼的。Tony 解释说掌握简单音符的演奏使得演奏者可以更完美地掌握复杂的片段。结论很清楚了:要想成为真正的艺术家,你必须集中精力掌握简单、基础的概念。

故事的意义很显然不仅适用于音乐,也适合软件开发。这个故事对我们所有人都是一个很好的提示:不要忽视去深入理解简单、基础的概念,即使有时候这看起来像是在走回头路。成为一个你所使用的工具或框架的专家固然重要,但了解背后的原理也是极为重要的。正如拉尔夫·沃尔多·爱默生所说:

“如果你仅仅学习方法,那么你将被方法所束缚。但是如果你学习原理,你将能够设计自己的方法。”

基于这样的观点,让我们再次深入解释器和编译器吧。

今天展示在第一篇中计算器的基础上出一个新版本,新版计算器能够:

1. 处理输入字符串中的空白字符;
2. 处理输入中的多位整数;
3. 两整数相减(现在只能相加);

这里是完成上述所有功能的新版计算器的源码:

将上述源码保存为 calc2.py 文件,或直接从 GitHub 下载。试一试,看看它是不是如想象中一样工作:它能够接受多位整数,并且它能够象两数相加一样将两数相减。

Here is a sample session that I ran on my laptop:

这里是我笔记本上运行的一个例子:

第一篇中版本相比,最主要的变化有:

  1. get_next_token 方法稍微重构了一点。pos 指针的自增逻辑放到了一个独立的 advance 方法。
  2. 增加了两个方法:skip_whitespace 方法用来忽略空白字符,integer 方法用来处理输入中的多位整数。
  3. 修改了 expr 方法,在识别 INTEGER -> PLUS -> INTEGER 短语的基础上,识别 INTEGER -> MINUS -> INTEGER 短语。在成功识别相应短语后,这个方法现在也能够解释加法和减法了。

第一部分,我们学习了两个重要的概念,那就是 token(记号) 和 lexical analyzer(词法分析器)。第二篇我们来浅谈一下 lexeme、parsing 和 parser。

你已经知道 token 了。但是为了完成对 token 的讨论我需要提到 lexeme。什么是 lexeme? lexeme 就是组成 token 的字符序列。在下面的图片中你可以看到一些 token 和 lexeme 的示例,希望已经把它们之间的关系表达清楚了:

现在,还记得我们的朋友 expr 方法吗?我曾经说过,这里是对一个算术表达式的解释真正发生的地方。但是在你对一个表达式进行解释之前,你首先需要识别短语的类型,例如:是加法还是减法。这是 expr 方法本质上干的活:它从 get_next_token 方法获取 token 流,找到 token 流的结构,解释识别出的短语,生成算术表达式的结果。

找到 token 流中的结构的过程,换句话说,识别 token 流中的短语的过程称之为 parsing(语法分析)。解释器或编译器中用以完成这样的工作的部分,称之为 parser(语法分析器)。

现在你知道了 expr 方法是解释器中既做了 parsing(语法分析)又做了 interpreting(解释)的部分。expr 方法首先试图识别(parsing)token 流中的 INTEGER -> PLUS -> INTEGER 或 INTEGER -> MINUS -> INTEGER 短语,成功完成识别(parsed)其中一种短语后,该方法解释它,并将两整数相加或相减的结果返回给调用者。

又到了练习时间。

  1. 扩展计算器,来处理两整数相乘
  2. 扩展计算器,来出来两整数相除
  3. 修改代码,以解释包含任意多加法和减法的表达式,例如:“9 – 5 + 3 + 11”

检查你是否已理解:

  1. 什么是 lexeme ?
  2. 找出 token 流中的结构的过程叫什么?换句话说,从 token 流中识别出特定短语的过程叫什么?
  3. 解释器(编译器)中做 parsing(语法分析)的部分的名称是什么?

我希望你喜欢今天的内容。在本系列的下篇文章中,你将扩展你的解释器来处理更加复杂的算术表达式。保持关注哦!

 

这有我推荐的一张有帮助的书单。

1.《编程语言实现模式》(实用主义程序员)
2.《Writing Compilers and Interpreters: A Software Engineering Approach》
3.《现代编译原理——java语言描述》
4.《现代编译程序设计》
5.《编译原理技术和工具》(第二版)

 

1 6 收藏 评论

关于作者:坐看云起

TO DREAM AND BUILD,TO FAIL AND TO SUCCEED.  博客园博客:坐看云起新浪微博:@撕烤兔 个人主页 · 我的文章 · 10

相关文章

可能感兴趣的话题



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