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

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

在他们的神奇的书《有效思考的五个因素》中,作者 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 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    541 引用 • 672 回帖 • 1 关注
  • 解释器
    2 引用
  • 译文
    7 引用

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 宕机

    宕机,多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态,也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态,也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 52 关注
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 383 关注
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 754 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 596 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • JVM

    JVM(Java Virtual Machine)Java 虚拟机是一个微型操作系统,有自己的硬件构架体系,还有相应的指令系统。能够识别 Java 独特的 .class 文件(字节码),能够将这些文件中的信息读取出来,使得 Java 程序只需要生成 Java 虚拟机上的字节码后就能在不同操作系统平台上进行运行。

    180 引用 • 120 回帖 • 2 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1705 回帖
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    75 引用 • 1737 回帖
  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    186 引用 • 318 回帖 • 306 关注
  • Pipe

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

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

    131 引用 • 1114 回帖 • 131 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 30 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • GraphQL

    GraphQL 是一个用于 API 的查询语言,是一个使用基于类型系统来执行查询的服务端运行时(类型系统由你的数据定义)。GraphQL 并没有和任何特定数据库或者存储引擎绑定,而是依靠你现有的代码和数据支撑。

    4 引用 • 3 回帖 • 8 关注
  • 30Seconds

    📙 前端知识精选集,包含 HTML、CSS、JavaScript、React、Node、安全等方面,每天仅需 30 秒。

    • 精选常见面试题,帮助您准备下一次面试
    • 精选常见交互,帮助您拥有简洁酷炫的站点
    • 精选有用的 React 片段,帮助你获取最佳实践
    • 精选常见代码集,帮助您提高打码效率
    • 整理前端界的最新资讯,邀您一同探索新世界
    488 引用 • 383 回帖 • 5 关注
  • 微软

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

    8 引用 • 44 回帖 • 1 关注
  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖
  • Python

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

    541 引用 • 672 回帖 • 1 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 615 关注
  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 637 关注
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    200 引用 • 120 回帖 • 1 关注
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 63 关注
  • 架构

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

    142 引用 • 442 回帖
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    176 引用 • 995 回帖 • 1 关注
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    20 引用 • 7 回帖 • 3 关注
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 613 关注
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1347 回帖