下载掌阅APP，畅读海量书库
立即打开
本书将告诉读者如何建立个人所需的编程语言。但是，我们应该首先自问：为何想要这样做？对于少部分人来说，答案很简单：因为这个过程实在是非常有趣！但对其他人来说，建立一种编程语言实际上是一项艰巨的工作，在开始这项工作之前，我们需要明确这一点。我们是否具备构建编程语言所需的耐心和毅力呢？
本章将指出构建编程语言的一些很好的理由，并说明在什么情况下不必构建另一种编程语言。毕竟，为应用程序领域设计一个类库可能更简单，而且同样有效。然而，类库也有其缺点，有时只有构建一种新的编程语言才能起作用。
在本章之后，本书的其余部分内容将在仔细考虑之后，理所当然地认为你已经决定构建一种编程语言。在这种情况下，你应该确定编程语言的一些要求。
我们从编写动机开始。
当然，一些编程语言发明者简直就是计算机科学的摇滚巨星，例如丹尼斯·里奇（Dennis Ritchie）和吉多·范罗苏姆（Guido van Rossum）！但在当时，成为计算机科学的摇滚明星反而更容易。很久以前，我从第二届编程语言史会议一位参会者那里听到了以下报告： 大家一致认为编程语言领域已经灭亡了，所有重要的语言都已经发明出来了！ 这一论断直到一两年后Java问世才被证明是大错特错的。从那时起，诸如Go语言之类的编程语言出现了十几次。仅仅过了60年，就声称编程领域已经成熟，并且没有什么新发明可以让你成名，这是不明智的。
不过，名誉并不是构建编程语言的好理由，从编程语言发明中获得名誉或财富的机会微乎其微。只要有时间和兴趣，好奇和渴望知道事物的工作原理都是发明编程语言的正当理由，但也许需求和必要性才是要构建编程语言的最佳理由。
有些人需要构建一种新的编程语言或实现对现有编程语言的新突破，以面向新的处理器或与对手公司竞争。如果你不需要，那么也许你已经找到了可用于你想要开发的程序的某些领域的最佳语言（以及编译器或解释器），但它们缺失你的工作需要的一些关键功能，而正是这些缺失的功能给你带来了痛苦。每隔一段时间，就会有人提出需要一种全新的计算风格，新的编程范式需要新的编程语言来实现。
在讨论构建语言的动机时，我们先谈谈不同类型的语言、组织以及本书中使用的示例，这些主题都值得仔细介绍。
不论原因是什么，在构建一种编程语言之前，我们都应该选择能找到的最佳工具和技术来完成这项工作。在本书的案例中，我们将对这些工具和技术进行挑选。首先，在构建编程语言的过程中，有一个关于其语言实现的问题。编程语言学者喜欢吹嘘自己用了某种语言编写自己的语言，但这通常只是半真半假（或者有人非常不切实际，同时又在炫耀自己）。还有一个问题是要构建什么样的编程语言实现：
❑执行源代码本身的纯 解释器 。
❑ 本机编译器 和运行时系统，例如在C语言中。
❑将编程语言翻译成其他高级语言的 转译器 。
❑带有字节码机器的 字节码编译器 ，例如Java。
第一个选项很有趣，但通常太慢；第二个选项是最好的，但通常太费力了，一个好的本机编译器可能需要很多人多年的努力。
虽然第三个选项是迄今为止最简单、可能也是最有趣的，并且我以前也成功地使用过它，然而如果这不是一个原型，那么这就是骗人的。当然，C++的第一个版本是一个转译器，但这让路给了编译器，而不仅仅是因为它有缺陷。奇怪的是，生成高级代码似乎使你的语言比其他选项更依赖于底层语言，而且语言是移动的目标。好的语言之所以消亡，是因为对其潜在的依赖性消失了，或者已对其造成了无法修复的损坏，这也许是大量小修改不断累积造成的。
本书选择了第四个选项：我们将构建一个附带一个字节码机器的字节码编译器，因为这是一种最佳选择，它在提供最大灵活性的同时仍提供了相当不错的性能。本章将介绍本机代码编译，适用于那些需要最快执行速度的用户。
字节码机器的概念非常古老，它因UCSD的Pascal实现和经典的SmallTalk-80实现等而闻名。随着Java的JVM的发布，它变得无处不在，甚至可以成为普通的英语词汇。字节码机器是由软件解释的抽象处理器，通常称为 虚拟机 （如 Java虚拟机 ），而我不会使用这个术语，因为它有时也指使用真实硬件指令集的软件工具，例如，IBM的经典平台或更现代的工具，如 Virtual Box 。
字节码机器通常比一块硬件高出一点，因此字节码的实现提供了很大的灵活性，我们下面快速了解一下字节码。
在很大程度上，本书的结构遵循字节码编译器及其相应虚拟机的经典组织结构。这些组件定义如下，图1.1进行了总结：
图1.1 简单编程语言中的各阶段和数据流
❑ 词法分析器 （lexical analyzer）读入源代码字符并计算出它们是如何组合成一系列单词或标记的。
❑ 语法分析器 （syntax analyzer）读入一系列标记，并根据语言的文法判断该序列是否合法。如果标记的顺序是合法的，则会生成一个语法树。
❑ 语义分析器 （semantic analyzer）检查并确保所有正在使用的名称对于正使用它们的操作都是合法的。它检查它们的类型，以精准确认正在执行的操作。所有这些检查都会让语法树变得繁重，充满了关于变量声明位置和类型的额外信息。
❑ 中间代码生成器 （intermediate code generator）计算出所有变量的内存位置以及程序可能突然改变执行流程的所有位置，例如循环和函数调用。中间代码生成器将这些位置添加到语法树中，然后在构建与机器无关的中间代码指令列表之前遍历这棵更大的树。
❑ 最终代码生成器 （final code generator）将中间代码指令列表转换为文件格式的实际字节码，这样可以有效地加载和执行。
在这个字节码虚拟机编译器的步骤之外，可以编写一个 字节码解释器 （bytecode interpreter）来加载和执行程序。这是一个包含switch语句的巨大循环，但对于外来编程语言来说，编译器可能没什么大不了的，所有的魔法都将发生在字节码解释器中，整个组织可以通过图1.1进行总结。
说明如何构建编程语言的字节码机器实现将需要大量代码。代码的呈现方式很重要，它将告诉我们需要了解的内容，以及我们可能会从本书中学到的许多内容。
本书使用 并行翻译模型 同时提供两种编程语言的代码示例。第一种示例语言是 Java ，因为这种语言无处不在。希望读者已了解Java或C++语言，并能够以中等熟练程度阅读示例。第二种示例语言是作者自己的编程语言 Unicon 。在阅读本书时，读者可以自己判断哪种语言更适合构建自己的编程语言。本书将以这两种语言提供尽可能多的示例，并且两种语言的示例将尽可能类似地编写，这样做有时对较小的语言有利。
Java和Unicon之间的差异是显而易见的，但我们要使用的编译器构建工具在一定程度上降低了这种差异的重要性。我们将使用久负盛名的Lex和YACC的最新衍生工具来生成扫描器和解析器。通过坚持使用与原始Lex和YACC尽可能兼容的Java和Unicon工具，我们的编译器的前端在两种语言中几乎相同。Lex和YACC是声明性编程语言，它们在比Java或Unicon更高的级别上解决了一些难题。
当使用Java和Unicon作为实现语言时，我们还需要讨论另外一种语言，即我们正在构建的示例语言。它是我们决定要构建的编程语言的一种替代。出于某种随意性，我将为此引入一种称为 Jzero 的语言。Niklaus Wirth发明了一种称为 PL/0 的“玩具”语言（ 编程语言zero ，该名称是 PL/1 语言名称的一个翻版），用于编译器构造课程。Jzero是Java的一个很小的子集，用于类似的目的。我进行了非常仔细的查找（也就是说，我搜索了Jzero，然后搜索了Jzero编译器），想看看是否有人已经发布了一个我们可以使用的Jzero定义，但我没有找到一个同名的定义，所以我们会在工作过程中进行弥补。
本书中的Java示例将使用OpenJDK 14进行测试。也许其他版本的Java（如OpenJDK 12或Oracle Java JDK）也会同样工作，也可能不会。可以从http://openjdk.java.net网站获得OpenJDK。或者，如果在Linux操作系统上，则可能有一个可以安装的OpenJDK包。Java示例所需的其他编程语言构造工具（JFlex和BYACC/J）将在后续章节中介绍。我们支持的Java实现可能更受运行这些语言构造工具的版本的限制。
本书中的Unicon示例使用Unicon版本13.2，可从http://unicon.org中获得。要在Windows上安装Unicon，必须下载.msi文件并运行安装程序。要在Linux上安装，通常要对源代码做git克隆，然后输入make，还要把unicon/bin目录添加到PATH中，如下所示：
在了解了本书如何组织和要使用的实现语言之后，也许我们应该再看看什么时候需要设计编程语言，什么时候可以通过开发库来避免另外设计编程语言。
当库可以完成某项工作时，不用构造编程语言。库是迄今为止扩展现有编程语言以执行新任务的最常用方法。 库 是一组可以一起用于为某些硬件或软件技术编写应用程序的函数或类。很多编程语言（包括C和Java）几乎完全围绕一组丰富的库设计。该语言本身非常简单和通用，而开发人员开发应用程序必须学习的大部分内容包括如何使用各种库。
库可以完成以下任务：
❑引入新的数据类型（类），并提供用于操作这些数据类型或类的公共函数（API）。
❑在一组硬件或操作系统调用的基础上提供抽象层。
库不能完成以下任务：
❑引入新的控制结构和语法，以支持新的应用程序域。
❑在现有编程语言运行系统中嵌入/支持新的语义。
库在某些方面做得很糟糕，正因为如此，我们可能最终更喜欢创建一种新的语言：
❑库往往会变得更大、更复杂，但不是必要的。
❑与编程语言相比，库的学习曲线更陡峭，文档更差。
❑库经常与其他库发生冲突，版本不兼容常常会破坏使用库的应用程序。
从库到编程语言有一条自然的进化路径。构建新语言以支持应用程序域的一种合理方法是首先制作或购买该应用程序域可用的最佳库。如果结果不支持所在领域，以及在简化为该领域编写程序的任务方面也不符合我们的要求，那么我们就有一个强有力的论据来证明：我们需要设计一种新的编程语言。
本书主要讲解构建自己的编程语言，而不仅仅是构建自己的库。事实证明，学习这些工具和技术在其他情况下是有用的。
从构建自己的编程语言中学到的工具和技术，可以应用于一系列其他软件工程任务。例如，可以将几乎所有文件或网络输入处理任务分为三类：
❑使用XML库读取XML数据。
❑使用JSON库读取JSON数据。
❑通过编写代码解析其原始格式来读取其他数据。
本书中介绍的技术在各种软件工程任务中都很有用，这也是其中第三类技术所遇到的问题。通常结构化数据必须以自定义文件格式读取。
对一些人来说，构建编程语言可能是迄今为止所写的最大的一个程序。如果坚持并完成了它，那么除了可以学到有关编译器和解释器的知识外，还会学到很多实用的软件工程技能，包括处理大型动态数据结构、软件测试和调试复杂问题等技能。
这已经足够鼓舞人心了！我们下面来谈谈首先应该做什么：确定语言需求。
在确定我们所做的工作需要一种新的编程语言之后，我们需要花几分钟来确定需求。这个工作是无止境的，取决于要求项目取得什么样的结果。聪明的语言发明者不会从头开始创建全新的语法。相反，他们根据对一种现有流行语言的一系列修改来定义它。许多伟大的编程语言（Lisp、Forth、SmallTalk等）的成功都受到了极大的限制，因为它们的语法与主流语言有着不必要的差异。不过，我们的语言需求包括它看起来像什么，以及语法。
更重要的是，必须在编程语言需要超越现有语言的地方定义一组控制结构或语义。这有时会包括对现有语言及其库不能很好地服务的应用程序域的特殊支持。这种 领域特定语言 比较常见，整本书都在关注这个话题。我们这本书的目标是专注于为这种语言构建编译器和运行时系统的核心内容，与我们可能从事的领域无关。
在正常的软件工程过程中，需求分析将从功能性和非功能性需求的头脑风暴列表开始。编程语言的功能性需求涉及最终用户开发人员将如何与之交互的细节。我们可能无法预先考虑到语言的所有命令行选项，但可能知道是否需要交互性，或者单独的编译步骤是否可行。1.3节中对解释器和编译器的讨论，以及本书对编译器的介绍，可能会让我们做出这样的选择，但是Python语言是一个提供完全交互式接口的语言示例，即便输入的源代码被压缩成字节码，而不是加以解释。
非功能性需求是编程语言必须实现的属性，这些属性并不直接与最终用户开发人员的交互相关。非功能性需求包括诸如必须在什么操作系统上运行、执行速度必须多快，或者用此编程语言编写的程序必须在多小的空间内运行等。
关于执行速度必须多快的非功能性需求通常决定了我们是可以以软件（字节码）机器为目标还是需要以本机代码为目标。本机代码执行速度更快，但也很难生成，而且它可能会使编程语言在运行时系统特性方面的灵活性大大降低。我们可以选择先以字节码为目标，然后再使用本机代码生成器。
我学习的第一种编程语言是BASIC解释器，其程序必须能够在大小为4KB的内存中运行。当时BASIC对内存占用的要求很低。但是，即使在现代，在一个默认情况下Java无法运行的平台上发现自己也是很常见的！例如，在为用户进程配置了内存限制的虚拟机上，我们可能不得不学习一些笨拙的命令行选项，来编译或运行哪怕是简单的Java程序。
许多需求分析过程也定义了一组用例，并要求开发者为这些用例写说明。发明一种编程语言不同于一般的软件工程项目，但直到发明编程语言的任务完成，我们都有可能把路走偏。用例是我们使用软件应用程序执行的任务。当软件应用程序是一种编程语言时，如果不小心，用例可能过于笼统而没有用处，例如“编写我的应用程序”以及“运行我的程序”。虽然这两种语言可能不是很有用，但我们可能需要考虑编程语言实现是否必须支持程序开发、调试、单独编译和链接，以及与外部语言和库的集成等。虽然这些话题大多超出了本书的讨论范围，但我们将对其中一些话题展开讨论。
由于本书将介绍一种名为Jzero的语言的实现，这里提出一些对它的要求。其中一些要求可能看起来很随意。如果你不清楚其中某个要求来自哪里，那么答案是它要么来自我们的源灵感语言（plzero），要么来自以前教授编译器构造的经验：
❑Jzero应该是Java的严格子集。所有合法的Jzero程序同样应该是合法的Java程序。这个要求允许我们在调试语言实现时检查测试程序的行为。
❑Jzero应该提供足够的特性，以允许实现有趣的计算，包括if语句、while循环、多个函数以及参数。
❑Jzero应该支持一些数据类型，包括布尔、整数、数组和字符串类型。如后文所述，它只需要支持其功能的一个子集。这些类型足以允许将感兴趣的值输入和输出到计算中。
❑Jzero应该发出适当的错误消息，显示文件名和行号，包括试图使用Jzero中没有的Java特性的消息。我们需要合理的错误消息来调试该实现。
❑Jzero应该运行得足够快，以达到实用目的。这个要求很模糊，但它意味着我们不会只做一个纯粹的解释器。纯粹的解释器是一种非常复古的东西，让人想起20世纪60年代和70年代。
❑Jzero应该尽可能简单，这样我们才能对其加以解释。不幸的是，这排除了生成本机代码甚至JVM字节码的可能性。我们将提供自己的简单字节码机器。
随着过程进一步发展，可能还会出现更多的需求，但这也只是一个开始。由于受时间和空间的限制，也许这个需求列表对于还没考虑到的内容，而不是已经考虑到的内容更为重要。通过比较，以下是一些要创建Unicon编程语言的需求。
本书将使用Unicon编程语言（http://unicon.org），以对运行用例进行深入分析。我们可以从合理的问题开始，例如，为什么要建立Unicon，其需求是什么？我们将先从第二个问题开始，再回过头来研究第一个问题。
Unicon源于亚利桑那大学的早期编程语言Icon（http://www.cs.arizona.edu/icon/）。Icon具有特别好的字符串和列表处理能力，用于构建许多脚本和实用程序，以及编程语言和自然语言处理项目。Icon奇妙的内置数据类型，包括列表和（哈希）表等结构类型，影响了很多编程语言，包括Python和Unicon。Icon的标志性研究贡献是将目标导向评估（包括回溯和生成器自动恢复）集成到熟悉的主流语法中。Unicon需求#1是保留Icon的这些好特性。
人们喜爱Icon的原因之一是它的表达式语义，包括其生成器和目标导向的评估。Icon还提供了一组丰富的内置函数和数据类型，以便许多甚至大多数程序都可以直接从源代码中加以理解。Unicon的目标是与Icon达到100%兼容。最终我们实现了99%的兼容性。
从保留最好的代码到确保旧源代码能永久运行的终极目标，这是一个小小的飞跃，对于Unicon来说，我们将其包含在需求#1中。与大多数现代语言相比，我们对向后兼容性提出了更严格的要求。虽然C语言向后兼容性很好，但C++、Java、Python和Perl都偏离了向后兼容，这些语言在某些情况下已经远远不能与它们辉煌时期编写的程序兼容。对于Unicon，可能99%的Icon程序未经修改就可以作为Unicon程序运行了。
Icon旨在最大限度地提高程序员在小型项目中的工作效率，一个典型的Icon程序通常不到1000行代码，但Icon是非常高级的，只需几百行代码就可以进行大量计算！尽管如此，计算机的功能仍然越来越强大，用户希望编写比Icon能处理的程序大得多的程序。Unicon需求#2是支持大型项目中的编程。
出于这个原因，Unicon将类和包添加到Icon中，就像C++将它们添加到C中一样。Unicon还改进了字节码目标文件格式，并对编译器和运行时系统进行了大量可扩展性改进。它还改进了Icon的现有实现，使其在许多特定项目中更具可扩展性，例如采用更复杂的哈希函数。
Icon专为本地文件的经典UNIX管道过滤器文本处理而设计。随着时间的推移，越来越多的人想要使用它编写程序，并且需要更复杂的输入/输出形式，例如网络或图形。Unicon需求#3是在与内置类型相同的高级别上支持无处不在的输入/输出功能。
对I/O的支持是一个不断变化的目标。首先，I/O包括网络设施、GDBM和ODBC数据库设施，以配合Icon的2D图形。然后，I/O发展到包括各种流行的互联网协议和3D图形。I/O功能的定义无处不在，且在不断发展，并因平台而异，例如，触摸输入、手势或着色器编程功能在目前也已经相当普遍。
毫无疑问，尽管CPU速度和内存大小提高了数十亿倍，但1970年的编程和2020年的编程之间的最大区别在于，我们希望现代应用程序能使用各种复杂的I/O形式：图形、网络以及数据库等。库可以提供对此类I/O的访问，但语言级别的支持可以使其更简单、更直观。
Icon具有很强的可移植性，可以在Amigas、Crays、带有EBCDIC字符集的IBM大型机上运行。尽管这些年来平台发生了难以置信的变化，但Unicon仍然保留了Icon最大限度地提高源代码可移植性的目标：用Unicon编写的代码应该可以继续在各种重要的计算机平台上未经修改即可运行。由此产生了Unicon需求#4。
长期以来，可移植性意味着程序在PC、Mac和UNIX工作站上都可以运行。不过，计算平台是不断变化的。一段时间以来，Unicon不断得到改进，以支持Android和iOS，如果将它们也算作计算平台的话。它们是否算计算平台，取决于它们是否足够开放并用于一般计算任务，而它们确实能够如此使用。
所有针对需求#3实现的丰富的I/O设施必须设计为可以跨所有主要平台进行多平台移植。
在说明Unicon的一些主要需求之后，下面是对这个问题的回答：为什么要构建Unicon？其中一个答案是，在学习了许多语言之后，我们得出结论：Icon的生成器和目标导向的评估（需求#1）是我们从现在开始编写程序时想要的特性。但在允许我们在编程语言中添加2D图形后，Icon的发明者不再愿意考虑进一步添加特性，以满足需求#2和需求#3。另一个答案则是公众对新功能的需求，包括志愿者合作伙伴和一些财政支持，于是，Unicon诞生了。
在本章中，我们了解了创建编程语言和创建库API以支持想要做的各种类型的计算之间的区别，并讨论了几种不同形式的编程语言实现。本章让我们思考想创建的编程语言的功能性和非功能性需求。这些需求可能不同于针对Java子集Jzero和Unicon编程语言（这两种语言我们已经做过介绍）讨论的示例需求。
需求非常重要，因为需求允许我们设定目标并定义成功的样子。对于编程语言实现，这些需求包括呈现给使用该编程语言的程序员的外观和感觉，以及必须运行的硬件和软件平台要求。编程语言给程序员的外观和感觉既包括回答有关如何调用语言实现和用该语言编写的程序的一些外部问题，也包括回答诸如冗长性等内部问题：程序员必须编写多少代码才能完成给定的计算任务？
你可能热衷于直接进入编码部分。尽管初级程序员经典的“边做边改”思维可能对处理脚本和短程序有用，但对于编程语言这样大的软件，我们首先需要更多的规划。在本章介绍语言需求之后，第2章将构建一个详细的实现计划，本书的剩余部分将主要介绍实现过程。
1.编写生成C代码的语言转译器而不是生成汇编程序或本机代码的传统编译器有什么优点和缺点？
2.传统编译器中有哪些主要组件或阶段？
3.根据你的经验，编程比想象中更难的痛点是什么？哪些新的编程语言特性可以解决这些痛点？
4.为新的编程语言编写一组功能需求。