攻克编译器(1)

1.2.1 代码

本书是关于制作解释器的,所以这本书包含真实的代码。所需的每一行代码都包括在内,每个代码片段都会告诉您需要将不断增长的实现代码插入哪个位置。

许多其他语言书籍和语言实现使用诸如 Lex 和 Yacc 之类的工具,即所谓的编译器-编译器,它们会根据某些更高级别的(语法)描述自动生成一些源文件。这样的工具各有利弊,而且各方都有强烈的主张——有些人可能会说是信仰。

我们避免在这里使用这些工具。我想确保没有魔法和困惑藏在黑暗角落,所以我们将手写所有代码。正如您将看到的,它并不像听起来那么糟糕,这意味着您将真正理解每一行代码以及两个解释器的工作方式。

一本书与“现实世界”有不同的限制,因此这里的编码风格可能并不是可维护生产软件的最佳方式。我在省略私有变量或声明全局变量方面显得有点无所谓,请理解我这样做是为了让代码更容易阅读。书籍页面没有你的IDE那么宽,每个字符的空间都是很珍贵的。

此外,代码没有太多注释。那是因为每一部分代码前都用一些简介的文字进行解释,当你写一本书来配合你的程序时,你也可以省略注释。否则,您可能应该比我多使用更多注释符号(//)。

虽然这本书包含每一行代码实现,并说明每行代码的含义,但它没有描述编译和运行解释器所需的机制。我假设您可以在您选择的 IDE 中将一个 makefile 或一个项目放在一起,以便让代码运行。这些说明很快就会过时,我希望这本书能像 XO 白兰地一样历久弥新,而不是自家酿的酒一样容易过期。

1.2.2 代码片段

这本书实际上包含了实现所需的每一行代码,因此这些代码片段非常准确。 另外,即使缺少主要功能,我也会尝试让程序保持在可运行状态,因此有时我们会添加临时代码,这些代码会在以后的代码片段中被替换。

一个完整的代码片段如下所示:

您可以在其中添加新代码。 它可能在上方或下方有一些淡出的行,用来显示它在相关代码中的位置。如果该简介说“replace x lines”,则在浅色的行之间存在一些现有代码需要删除并替换为新的代码段。

1.2.3 旁白

旁白包含传记简介、历史背景、对相关主题的引用以及其他领域的探索建议。您不需要了解就可以理解本书后面的部分,所以如果你愿意,你可以跳过它们。 我不加评判,但可能会有点难过。

1.2.4 挑战

每章结尾都有一些练习题。 与教科书习题集不同,这些习题集往往会复习您已经学习的材料,这些习题集旨在帮助您学习比本章更加丰富的内容。 他们引导您离开文章引导路径并自行探索。 它们会让你研究其他语言,弄清楚如何实现功能,或者让你走出舒适区。

克服挑战,您将获得更广泛的认知,可能还会遇到一些挫折。 如果您想留在旅游巴士舒适区内,也可以跳过它们。 这是你的书。

1.2.5 设计说明

大多数“编程语言”书籍都是严格意义上的编程语言实现书籍。他们很少讨论如何设计正在实现的语言。实现之所以有趣,是因为它的定义如此精确。程序员似乎更喜欢黑与白、1 和 0 这样的内容。

就个人而言,我认为世界只需要一些 FORTRAN 77 的实现。在某些时候,您会发现自己正在设计一种新语言,一旦开始这样做,表达式中更舒适、更人性化的一面就变得至关重要。诸如哪些功能易于学习,创新和熟悉程度需要取得平衡,哪种语法更易读以及面向哪些用户。

所有这些都对新语言的成功有深远的影响。我希望你的语言能够取得成功,所以在某些章节中,我以“设计笔记”结尾,这是一篇关于编程语言人文某些方面的讨论。我不是这方面的专家,我不知道是否有人真的精通这些内容。所以把这些思考的食材和调料一起烹饪,这应该使它们变得更美味,值得深思,这是我的主要目标。

1.3 第一个解释器

我们将用 Java 编写我们的第一个解释器 jlox。关注的重点是概念。我们将编写最简单、最干净的代码来正确实现语言的语义。这将使我们熟悉基本技术,并磨练我们正确理解语言应表现形式。

Java 是一种很好的语言。它足够高级,我们不会被繁琐的实现细节所淹没,代码仍然非常明确。与脚本语言不同,隐藏在引擎盖下的机器往往不太复杂,并且您可以使用静态类型来查看正在使用的数据结构。

我特别选择了 Java,因为它是一种面向对象的语言。这种编程范式在 90 年代席卷了编程世界,现在是数百万程序员的主要思维方式。很有可能你已经习惯于将代码组织成类和方法,所以我们会让你保持在这个舒适区。

虽然学术性语言专家有时看不起面向对象的语言,但现实中它们广泛用于语言工作中。 GCC 和 LLVM 是用 C++ 编写的,大多数 JavaScript 虚拟机也是如此。面向对象的语言无处不在,一种语言的工具和编译器通常是用同一种语言编写的。

最后,Java 非常受欢迎。这意味着你很有可能已经知道它,所以你要学习的东西就更少了。如果您对 Java 不太熟悉,也不用担心。我尽量只使用它的一个最小子集。我使用 Java 7 中的菱形运算符使代码变得更简洁,但就“高级”功能而言,仅此而已。如果您了解另一种面向对象的语言,例如 C# 或 C++,您可以应对自如。

在第二部分结束时,我们将有一个简单易读的计时器实现。它的运行速度不是很快,但它是正确运行的,因为只能利用在 Java 虚拟机自身运行时基础上构建的实现。我们想了解 Java 本身是如何实现这些东西的。

1.4 第二个解释器

所以在下一部分,我们从头开始,但这次是使用C语言。C 是理解实现如何真正工作的完美语言,它深入到内存中的字节和流经 CPU 的代码。

我们使用 C 的一个重要原因是我可以向你展示 C 特别擅长的东西,但这确实意味着你需要对它非常熟悉。你不必是丹尼斯·里奇的转世,但你也不应该被指针吓到。

如果您还没有非常熟悉C语言,请找一本关于 C 的介绍性书籍并仔细阅读,然后在完成后返回这里。作为回报,从本书中您将成为一个优秀的 C 程序员。可以想象有多少语言实现是用 C 编写的,例如:Lua、CPython 和 Ruby 的 MRI 等等。

在我们的 C 解释器 clox 中,我们不得不自己实现 Java 免费提供给我们的东西。我们将编写自己的动态数组和哈希表。我们将决定对象在内存中的表示方式,并构建一个垃圾收集器来回收它们。

我们的 Java 实现专注于正确性。既然我们已经做到了,我们将转向提高运行速度。我们的 C 解释器将包含一个编译器,该编译器将 Lox 转换为有效的字节码表示(别担心,我很快就会讲解明白这意味着什么),然后它会执行。这与 Lua、Python、Ruby、PHP 和许多其他成功语言的实现所使用的技术相同。

我们甚至会尝试进行基准测试和优化。 到最后,我们将拥有一个强大、准确、快速的语言解释器,能够跟其他专业水准的实现媲美。 对于一本书和几千行代码来说还不错。

挑战

1. 在我编写和出版这本书中的系统中至少使用了六种特定领域的语言。 是哪些?

2.用Java编写和运行一个“hello world!”的程序。 设置您需要的 makefile 或 IDE 项目以使其正常工作。 如果您有调试器,请熟悉它并在程序运行时对代码进行单步调试。

3. 对 C 做同样的操作。为了练习指针,定义一个在堆中分配字符串的双向链表。 编写函数在其中插入、查找和删除项目。 测试编写的函数。

攻克编译器

编译器作为软件由代码至可执行文件的中间过程,是软件研发非常重要的技术。在软件开发人员中,仅有极少数的人能够真正的了解相关技术。最近非常偶然看到一本关于编译器技术的数据,非常适合进行相关技术的学习,相关的数据如下:

本系列的文章将对本书进行相关的解读和翻译,对相关的技术在我可以理解的情况下进行说明,对于有兴趣了解编译器的工程师,将会有很大的帮助。

前言

我真的很兴奋我们将一起踏上这段旅程。这是一本关于为编程语言实现解释器的书。这也是一本关于如何设计一种值得实现的语言的书。这是我刚开始接触编程语言时希望拥有的书,也是我近十年来一直在脑海中构思的书。

本书中,我们将逐步介绍两个完整的解释器,以实现功能齐全的编程语言。我假设这是您第一次涉足语言领域,因此我将介绍构建一个完整、可用、快速的语言所需的每个概念和代码。

为了在一本书中塞入两个完整的实现,而且避免这变成一个门槛,本文在理论上比其他文章更轻松。在我们构建系统的每一部分时,我将介绍它背后的历史和概念。我尽力让你熟悉这些术语,这样如果你发现自己参加了一个充满 PL(编程语言)研究人员的鸡尾酒会,也能融入其中。

我们主要会费尽脑汁来让这个语言运转起来。 这并不是说理论不重要。 能够准确而正式地推理语法和语义是研究语言时的一项重要技能。 但是,就个人而言,我通过实践学习效果最好。 我很难通过充满抽象概念的段落真正理解它们。 但是,如果我编写了一些代码、运行并调试代码,那么我就理解了。

这就是我给你设定目标。 我希望你能直观了解到真正的编程语言是如何生活和呼吸的。 我希望,当你以后再读其他理论性更强的书时,这些概念会牢牢地印在你的脑海里,附着在这个有形的基础上。

1.1 为什么要学习这些内容?

每本编译器书籍的介绍似乎都有这一章节。 我不知道为什么编程语言会引起这种观念存在性的怀疑。 我不认为鸟类学书籍会担心证明鸟类的存在。 他们假设读者喜欢鸟类,并开始教授内容。

但是编程语言有点不同。 我认为,对于我们中的任何人来说创建一种广泛成功的通用编程语言的可能性确实很小。 世界上广泛使用的编程语言的设计者一辆大众巴士就能装得下,甚至都不需要加装额外的露营车。 如果加入这个精英群体是学习语言的唯一原因,那将很难证明其合理性。 幸运的是,事实并非如此。

1.1.1 小型语言无处不在

对于每一种成功的通用语言,对应着都有一千种成功的小众语言。 我们曾经称它们为“小众语言”,但术语泛滥的今天产生了“特定领域语言”的名称。 这些是为特定任务量身定制的 混合语言,如应用程序脚本语言、模板引擎、标记格式和配置文件。

几乎每个大型软件项目都需要一些这样的语言。 如果可以,最好重用现有的,而不是实现自己的。 如果你考虑到文档、调试器、编辑器支持、语法高亮和所有其他可能存在的问题,自己实现就变成很艰巨的任务了。

但是,当前没有库符合现有需求时,仍然很有可能会发现自己需要开发解析器或其他工具。 即使你重用了一些现有的实现,最终也不可避免地需要调试和维护它们,并在它们内部进行探索。

1.1.2 语言是很好的练习方式

长跑运动员有时会将重物绑在脚踝上,或在空气稀薄的高海拔地区进行训练。 随后当他们卸下这些负担时,轻巧的四肢和富含氧气的空气带来了相对轻松的舒适度,使他们能够跑得更远更快。

实现一种语言是对编程技能的真正考验。 代码复杂且性能至关重要。 您必须掌握递归、动态数组、树、图形和哈希表。 您可能至少在日常编程中使用哈希表,但您真的了解它们吗? 好吧,等我们从头开始完成自己的作品之后,我保证你会的理解的。

虽然我打算向您展示解释器并不像想象的那样令人生畏,但实现一个解释器仍然是一个挑战。 坚持下去,你会成为一个更强大的程序员,并且在你日常工作中也能更加聪明的使用数据结构和算法。

1.1.3 另一个原因

最后一个原因我很难承认,因为它是我内心的理由。自从我小时候学会编程以来,我就觉得语言有一些神奇的东西。当我第一次编写 BASIC 程序时,我无法想象 BASIC 本身是如何制作出来的。

后来,当我的大学朋友谈论他们的编译器课程时,他们脸上敬畏和恐惧的表情,足以让我相信语言黑客是另一种人,—某种被授予访问通向神秘艺术特权的巫师。

这是一个令人着迷的场景,但它也有阴暗的一面。我不觉得自己像个巫师,所以我觉得我缺乏加入这个团体所需的与生俱来品质。虽然自从我在学校笔记本上涂鸦些关键词后,就对语言着迷,但我花了几十年的时间才鼓起勇气尝试真正学习它们。那种“神奇”的品质,那种排他性的感觉,把我排除在外。

当我终于开始拼凑我自己的小编译器时,我很快就意识到,根本没有魔法。它只是代码,而掌握语言的人也只是人。

有一些技术你在语言之外不经常遇到,有些部分有点困难。但并不比克服的其他障碍更困难。我希望,如果你对编程语言感到恐惧,这本书可以帮助你克服这种恐惧,也许我会让你比以前更勇敢一点。

而且,谁知道呢,也许你会创造下一个伟大的编程语言。毕竟总有人这样做。

1.2 本书的组织方式

本书分为三个部分。你现在正在阅读第一部分。这部的几章可以让你掌握大方向,教你一些语言黑客使用的术语,并向你介绍我们要实现的语言 Lox。

其他两部分中则分别构建了一个完整的 Lox 解释器。在这些部分中,每个章节的结构都相同。每一章选择一个语言功能点,向您介绍其背后的概念,并逐步完成实现。

我花了很多时间试错,设法将两个解释器按章节组织,每一章建立在前面的章节之上,但不需要后面章节的内容。从第一章开始,您将拥有一个可以运行和使用的程序。随着每一章的深入,它的功能越来越丰富,直到你最终拥有一门完整的语言。