《Let's Build a Simple Interpreter》系列文章翻译: Part 2

本贴最后更新于 1779 天前,其中的信息可能已经时移世改

在他们的神奇的书《有效思考的五个因素》中,作者 Burger1和 Starbird 分享了一个关于如何观察 Tony Plog 这位国际小号演奏大师的故事,他为出色的小号演奏家举办了一个大师班。在这里,学生们首先演奏复杂的、那些他们已经可以演奏的很好的乐章。然后当他们被要求演奏非常基本、简单的乐章时,与之前复杂的乐章相比,那些音符听起来却显得非常幼稚。学生们演奏完后,大师也演奏了这些基本的乐章,但是却并不显得幼稚。这其中的差异是惊人的。Tony 解释说,掌握简单音符的演奏可以让一个人在演奏复杂乐曲时有更大的控制力。这个教训很清楚——要想拥有真正的艺术技能,你必须专注于掌握简单的、基本的思想。

这个故事中的道理不仅仅适用于音乐,而且也适用于软件开发。这个故事很好的提醒了我们所有人,不要忽视基本思想在深入工作的重要性,即便是有时感觉像后退了一步似的。虽然精通你使用的工具和框架很重要,但是了解其背后的原理也很重要。正如 Ralph Waldo Emerson 说的那样:

“如果你只学习方法,那么你将会被方法困扰;不过你若学习原理,那么你可以拥有自己的方法。”

关于这一点,让我们再次更深入的去学习解释器和编译器。

今天我会展示给你基于 Part 1 的计算器的新版本,它即将可以做到:

  1. 处理输入字符串中任意的空白字符
  2. 处理输入中的多位整形数字
  3. 支持两个整形的减法(目前只支持加法)

这是你的新版计算器的源代码,它已经实现了上述所有功能:

# Token types # EOF (end-of-file) token is used to indicate that # there is no more input left for lexical analysis INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF' class Token(object): def __init__(self, type, value): # token type: INTEGER, PLUS, MINUS, or EOF self.type = type # token value: non-negative integer value, '+', '-', or None self.value = value def __str__(self): """String representation of the class instance. Examples: Token(INTEGER, 3) Token(PLUS '+') """ return 'Token({type}, {value})'.format( type=self.type, value=repr(self.value) ) def __repr__(self): return self.__str__() class Interpreter(object): def __init__(self, text): # client string input, e.g. "3 + 5", "12 - 5", etc self.text = text # self.pos is an index into self.text self.pos = 0 # current token instance self.current_token = None self.current_char = self.text[self.pos] def error(self): raise Exception('Error parsing input') def advance(self): """Advance the 'pos' pointer and set the 'current_char' variable.""" self.pos += 1 if self.pos > len(self.text) - 1: self.current_char = None # Indicates end of input else: self.current_char = self.text[self.pos] def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance() def integer(self): """Return a (multidigit) integer consumed from the input.""" result = '' while self.current_char is not None and self.current_char.isdigit(): result += self.current_char self.advance() return int(result) def get_next_token(self): """Lexical analyzer (also known as scanner or tokenizer) This method is responsible for breaking a sentence apart into tokens. """ while self.current_char is not None: if self.current_char.isspace(): self.skip_whitespace() continue if self.current_char.isdigit(): return Token(INTEGER, self.integer()) if self.current_char == '+': self.advance() return Token(PLUS, '+') if self.current_char == '-': self.advance() return Token(MINUS, '-') self.error() return Token(EOF, None) def eat(self, token_type): # compare the current token type with the passed token # type and if they match then "eat" the current token # and assign the next token to the self.current_token, # otherwise raise an exception. if self.current_token.type == token_type: self.current_token = self.get_next_token() else: self.error() def expr(self): """Parser / Interpreter expr -> INTEGER PLUS INTEGER expr -> INTEGER MINUS INTEGER """ # set current token to the first token taken from the input self.current_token = self.get_next_token() # we expect the current token to be an integer left = self.current_token self.eat(INTEGER) # we expect the current token to be either a '+' or '-' op = self.current_token if op.type == PLUS: self.eat(PLUS) else: self.eat(MINUS) # we expect the current token to be an integer right = self.current_token self.eat(INTEGER) # after the above call the self.current_token is set to # EOF token # at this point either the INTEGER PLUS INTEGER or # the INTEGER MINUS INTEGER sequence of tokens # has been successfully found and the method can just # return the result of adding or subtracting two integers, # thus effectively interpreting client input if op.type == PLUS: result = left.value + right.value else: result = left.value - right.value return result def main(): while True: try: # To run under Python3 replace 'raw_input' call # with 'input' text = raw_input('calc> ') except EOFError: break if not text: continue interpreter = Interpreter(text) result = interpreter.expr() print(result) if __name__ == '__main__': main()

把这段代码保存为 calc2.py 或者从我的 GitHub 下载。尝试运行它,并且自己观察它是否按照预期工作:它是否可以处理输入中任意位置、任意数量的空格?它是否可以接受两位及以上的整形?它是否可以像求两数之和那样求两数之差?

这是在我的笔记本上运行的结果:

$ python calc2.py calc> 27 + 3 30 calc> 27 - 7 20 calc>

与 Part 1 相比,代码的主要变动在于:

  1. 方法 get_next_token() 进行了轻微的重构。逻辑指针 pos 增加的逻辑被独立成为一个新的方法 advance()
  2. 添加了两个新方法,方法 skip_whitespace() 用于忽略空白字符,方法 integer() 用于处理输入中两位及以上的整形数字;
  3. 方法 expr() 在原来识别 INTEGER -> PLUS -> INTEGER 序列的基础上添加了对 INTEGER -> MINUS -> INTEGER 序列的识别。现在该方法可以在成功识别到正确的序列后执行加法或者减法运算。

在 Part 1 中你已经了解到两个重要的概念,即 Token 和词法分析器。今天我会讨论一些关于词素(Lexeme)、解析和解析器相关的知识。

你已经知道了 Token 的概念,但是为了能完美结束对 Token 的讨论,词素的概念是必不可少的。词素是什么?词素是从 Token 中提取到的一串字符序列。下图中你将可以看到一些 Token 和词素的示例,而且它将会使二者的关系更加清晰:

lexemes

现在,还记得我们的老朋友,expr() 方法吗?之前我说过这是算术表达式被实际解释执行的地方。但是在你解释执行表达式之前,你首先需要知道你到底识别到了什么样的表达式,例如,它是加法还是减法?这就是 expr() 实际上在做的:它从方法 get_next_token() 给出的 Token 流中搜索语法结构,然后对识别到的语法结构进行解释执行,并生成算是表达式的结果。

在 Token 流中寻找语法结构的过程,或者换句话说,识别 Token 流中“短语”的过程,叫做解析;解释器或编译器中执行这一部分工作的部分叫做解析器。

这样,你知道方法 expr() 在你的解释器中既充当解析器,也充当执行器——该方法首先尝试在 Token 流中识别(解析)INTEGER -> PLUS -> INTEGER 或者 INTEGER -> MINUS -> INTEGER,在成功识别(解析)到其中一个“短语”后,该方法就对它解释执行,并把两个整数进行加减运算的结果返回给调用者。

现在又到了做练习的时间了。

exersize again

  1. 扩展这个计算器,使之支持两个整数的乘法运算;
  2. 扩展这个计算器,使之支持两个整数的除法运算;
  3. 修改代码使之可以执行任意数目的数字进行加减运算,例如 $9 - 5 + 3 + 11$

检查你的理解程度:

  1. 词素是什么?
  2. 在 Token 流中寻找语法结构的过程,或者换句话说,识别 Token 流中“短语”的过程 被称作什么?
  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. 人名不做翻译,下同

  • Cs
    4 引用 • 2 回帖
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    554 引用 • 675 回帖 • 1 关注
  • 解释器
    2 引用
  • 译文
    7 引用

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
StephenZhang
我没有生来天赋过人,面对人山人海只剩一些诚恳

推荐标签 标签

  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 179 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖
  • Pipe

    Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    134 引用 • 1127 回帖 • 110 关注
  • jsoup

    jsoup 是一款 Java 的 HTML 解析器,可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API,可通过 DOM,CSS 以及类似于 jQuery 的操作方法来取出和操作数据。

    6 引用 • 1 回帖 • 497 关注
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    591 引用 • 3528 回帖
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    89 引用 • 113 回帖
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    240 引用 • 224 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 109 关注
  • 生活

    生活是指人类生存过程中的各项活动的总和,范畴较广,一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。

    230 引用 • 1432 回帖 • 1 关注
  • 架构

    我们平时所说的“架构”主要是指软件架构,这是有关软件整体结构与组件的抽象描述,用于指导软件系统各个方面的设计。另外还有“业务架构”、“网络架构”、“硬件架构”等细分领域。

    142 引用 • 442 回帖
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    32 引用 • 108 回帖 • 5 关注
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 263 关注
  • PostgreSQL

    PostgreSQL 是一款功能强大的企业级数据库系统,在 BSD 开源许可证下发布。

    22 引用 • 22 回帖
  • abitmean

    有点意思就行了

    36 关注
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    947 引用 • 1460 回帖 • 2 关注
  • 锤子科技

    锤子科技(Smartisan)成立于 2012 年 5 月,是一家制造移动互联网终端设备的公司,公司的使命是用完美主义的工匠精神,打造用户体验一流的数码消费类产品(智能手机为主),改善人们的生活质量。

    4 引用 • 31 回帖 • 4 关注
  • Sillot

    Insights(注意当前设置 master 为默认分支)

    汐洛彖夲肜矩阵(Sillot T☳Converbenk Matrix),致力于服务智慧新彖乄,具有彖乄驱动、极致优雅、开发者友好的特点。其中汐洛绞架(Sillot-Gibbet)基于自思源笔记(siyuan-note),前身是思源笔记汐洛版(更早是思源笔记汐洛分支),是智慧新录乄终端(多端融合,移动端优先)。

    主仓库地址:Hi-Windom/Sillot

    文档地址:sillot.db.sc.cn

    注意事项:

    1. ⚠️ 汐洛仍在早期开发阶段,尚不稳定
    2. ⚠️ 汐洛并非面向普通用户设计,使用前请了解风险
    3. ⚠️ 汐洛绞架基于思源笔记,开发者尽最大努力与思源笔记保持兼容,但无法实现 100% 兼容
    29 引用 • 25 回帖 • 130 关注
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖
  • 博客

    记录并分享人生的经历。

    273 引用 • 2389 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 3 关注
  • Visio
    1 引用 • 2 回帖
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 248 回帖 • 3 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖 • 2 关注
  • BAE

    百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。

    19 引用 • 75 回帖 • 678 关注
  • 创业

    你比 99% 的人都优秀么?

    82 引用 • 1395 回帖