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

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

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

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

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    55 引用 • 85 回帖
  • Solo

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

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

    1434 引用 • 10054 回帖 • 490 关注
  • Lute

    Lute 是一款结构化的 Markdown 引擎,支持 Go 和 JavaScript。

    25 引用 • 191 回帖 • 16 关注
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 339 关注
  • Bug

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

    75 引用 • 1737 回帖 • 5 关注
  • IBM

    IBM(国际商业机器公司)或万国商业机器公司,简称 IBM(International Business Machines Corporation),总公司在纽约州阿蒙克市。1911 年托马斯·沃森创立于美国,是全球最大的信息技术和业务解决方案公司,拥有全球雇员 30 多万人,业务遍及 160 多个国家和地区。

    17 引用 • 53 回帖 • 136 关注
  • 微服务

    微服务架构是一种架构模式,它提倡将单一应用划分成一组小的服务。服务之间互相协调,互相配合,为用户提供最终价值。每个服务运行在独立的进程中。服务于服务之间才用轻量级的通信机制互相沟通。每个服务都围绕着具体业务构建,能够被独立的部署。

    96 引用 • 155 回帖 • 1 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    190 引用 • 1057 回帖
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    85 引用 • 139 回帖 • 1 关注
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖
  • FlowUs

    FlowUs.息流 个人及团队的新一代生产力工具。

    让复杂的信息管理更轻松、自由、充满创意。

    1 引用 • 1 关注
  • Eclipse

    Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。

    75 引用 • 258 回帖 • 617 关注
  • 互联网

    互联网(Internet),又称网际网络,或音译因特网、英特网。互联网始于 1969 年美国的阿帕网,是网络与网络之间所串连成的庞大网络,这些网络以一组通用的协议相连,形成逻辑上的单一巨大国际网络。

    98 引用 • 344 回帖
  • 开源中国

    开源中国是目前中国最大的开源技术社区。传播开源的理念,推广开源项目,为 IT 开发者提供了一个发现、使用、并交流开源技术的平台。目前开源中国社区已收录超过两万款开源软件。

    7 引用 • 86 回帖
  • 创业

    你比 99% 的人都优秀么?

    84 引用 • 1399 回帖
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 680 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 787 关注
  • 心情

    心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。

    59 引用 • 369 回帖
  • 新人

    让我们欢迎这对新人。哦,不好意思说错了,让我们欢迎这位新人!
    新手上路,请谨慎驾驶!

    52 引用 • 228 回帖
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    21 引用 • 245 回帖 • 241 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 724 关注
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    2 引用 • 14 回帖
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    287 引用 • 4484 回帖 • 669 关注
  • SEO

    发布对别人有帮助的原创内容是最好的 SEO 方式。

    35 引用 • 200 回帖 • 22 关注
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖
  • Dubbo

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

    60 引用 • 82 回帖 • 595 关注