HUJ nans2tetrics 笔记（三）
- 宽松的类型转换可以被巧妙地利用，以实现各种高级编程技巧，从而让我们能够控制底层硬件平台。这在课程后期我们着手开发操作系统时将变得非常方便。这个操作系统将用Jack编写，就像Unix用C编写一样。你将发现，Jack的弱类型特性将允许我们构思各种巧妙的“黑客”技巧，没有这些技巧，我们将无法使用高级语言（或至少是Jack）来编写操作系统。
顺便一提，这也是操作系统通常用C语言开发的原因之一。并非C语言是弱类型的（事实上C是强类型语言），而是它提供了各种机制，允许程序员在有意时故意弱化类型系统。这种自由的类型转换在编写操作系统、嵌入式系统以及通常靠近硬件层运行的软件时非常有用。
Jack的语法约定：let 与 do
接下来，我们探讨Jack语言中两个独特的语法约定。
Jack有一些语法约定，例如 let 和 do，这在其他现代编程语言中并不常见（尽管在一些古老的语言中存在）。为什么要在语言中引入这些语法约定呢？
确实，在Jack中，如果你想给变量赋值，你必须写 let x = 10;，而不是简单的 x = 10;。如果你想调用一个子程序，你必须写 do foo();，而不是像在Java或Python中那样直接写 foo();。
引入这些前缀标记只有一个目的：允许开发优雅、简单且极简的Jack编译器，正如你们将在下两个模块中所做的那样。编译器最基础的操作之一称为语法分析。语法分析是分析我们试图编译的程序的语法结构的行为。事实证明，当你尝试对任何语言的源代码进行语法分析时，如果给定代码的第一个标记能揭示或表明我们正在处理的是哪种语句（是 while、if、let、do、return、函数声明还是其他），这将非常有帮助。
因此，尽管 let 和 do 在编写Jack代码和应用程序时有点麻烦，但当你在课程后期（实际上是下一个模块）必须编写Jack编译器的语法分析器时，你会对这些前缀标记感激不尽。
关于Jack操作系统的说明
最后，我们来谈谈Jack操作系统。正如你所知，基本的Jack语言通过Jack操作系统的完整功能得到了显著增强。这个操作系统被打包为Jack语言的标准类库。作为一个类库，它可以被随意扩展。这种模块化和开放式的架构在现代语言（如Java、Python和C++）中非常典型。
以Java为例。我记得大约20年前，我帮助在IDC Herzliya（我现在任教的地方）建立了一个新的计算机科学学院。我们当时做出的一个决定是采用Java作为学生学习计算机科学的第一门编程语言。这在当时是一个相当大胆的赌注，因为1996年时Java还非常新，并且只带有一个非常小的类库。自那时起，Java当然已经成为一门强大的语言，如今Java类库包含了超过4000个类。然而，在这二十年功能和特性惊人增长的过程中，基本的Java语言却几乎保持不变。
我希望我已经向你们传达了这种软件架构的美妙和实用性。作为语言设计者，你指定了一种简单、优雅、紧凑的语言。然后，利用类和子程序的抽象，你允许人们使用这种语言以无限种方式扩展它本身。在我看来，这种简单性与无限可扩展性的结合，或许是现代编程语言最显著的特征。
总结
本节课中我们一起学习了：
-
Jack语言的定位：它是一个为教学目的设计的极简语言，包含了核心编程概念，但省略了继承等高级特性以聚焦本质。
-
弱类型系统：Jack采用弱类型，允许灵活的类型转换，这简化了语言设计，并为底层系统编程（如操作系统开发）提供了便利。
-
独特的语法：
let和do等前缀标记旨在简化编译器的语法分析器实现。 -
可扩展的架构：通过标准类库（操作系统）的形式，Jack语言具备了强大的可扩展能力，这体现了现代语言“核心简洁，外围丰富”的设计哲学。
关于高级语言，当然还有更多可以探讨的内容，但时间有限，本模块到此结束。在下一个模块中，我们将从语法分析开始，着手编写我们自己的编译器。
045：语法分析
在本节课中，我们将要学习编译器的构建，特别是语法分析器的开发。我们将从宏观视角了解编译过程，并深入探讨语法分析的第一步：词法分析。
概述
我们想要将高级语言程序翻译成机器码，以便执行它们并获得计算结果。程序通常由多个类组成，这没有问题。我们的目标是将这些代码编译成机器语言，然后执行可执行代码以获得预期结果。
如果一切正常，屏幕上显示的结果将是程序设计所要产生的。
编译过程
正如课程之前多次提到的，在Java、C#以及Jack等现代编程语言中，存在一个两级编译过程。
-
程序首先被编译成某种中间代码。在Java中称为字节码，在C#中称为IL（中间语言），而在Jack中我们简单地称之为VM代码。
-
然后，另一个过程会获取VM代码，并将其翻译成最终的目标机器语言。
VM翻译器是一个已解决的问题，我们在前两个模块中已经实现了它。因此，剩下的工作就是编写编译器，即编写将高级语言翻译成VM代码的程序。这将是我们在本模块（模块4）和下一个模块（模块5）中要做的事情。
开发路线图
我们想要构建一个编译器。Nor和我决定将这个重要的整体开发工作分成两个独立的模块。
-
在当前的模块4中，我们将开发一个语法分析器。
-
在下一个模块5中，我们将为其添加一个代码生成器模块。
现在有了两个不同的模块，一个有趣的问题出现了：我们如何独立于第二个模块来测试第一个模块？为此，我们决定让语法分析器输出一个用XML编写的文件（稍后会描述）。通过查看这个文件，你将能够确信并验证语法分析器确实“理解”了输入代码，并为下一个项目生成代码做好了必要的准备。
生成这个XML输出文件的工作将在项目10中完成，该项目将在本模块的最后一个单元中描述。因此，目前我们在本模块中要做的是开发分词器和解析器，它们共同构成了语法分析器。
本模块有许多重要的知识点，包括分词、语法、解析等。你可以在列表末尾继续阅读。
学习动机
我猜你们中有些人会问自己：为什么我必须学习所有这些知识？我又不打算以编写编译器为生，我将成为一名应用程序员，做其他事情。我可能永远都不需要写一个编译器。
我同意你的看法，你们中只有少数人会在职业生涯中需要编写编译器。然而，通过理解编译器是如何构建的，并能够自己编写一个，你将成为一个更加成熟和有能力的高级程序员。
此外，你必须理解，在当今的经济环境中，我们必须处理大量具有预定结构化格式的文件。这些文件来自生物信息学、遗传代码，一直到以特定方式构建的金融信息等应用领域。通信网络产生的文件也具有预定的结构。如今的应用程序员必须常规地处理这些文件，将它们拆分、从一种格式转换为另一种格式、合并它们，并执行许多涉及大数据和分析数据文件、数据挖掘等任务。
在每一项如今普遍存在的任务中，你可以用两种不同的方式来完成。
-
一种是糟糕的方式，即在不了解正确做法的情况下开始编写程序。你的程序可能完成你需要做的事情，但代码会写得非常糟糕，难以维护和扩展。
-
或者，你可以学习计算机科学中所有这些经典技术，它们让你不仅能以优雅、美观和令人满意的方式完成工作，还能创造出对你和他人来说都易于使用的代码。
这就是学习如何编写编译器的动机。
模块路线图
以下是本模块的整体路线图，我们要做的第一件事是专注于编写一个分词器。
这将在编译理论与实践的一个更大背景下完成，即词法分析。
总结
本节课我们一起学习了编译器构建的宏观过程，特别是两级编译的概念。我们明确了本模块（模块4）的目标是开发语法分析器，并了解了将其分为分词器和解析器两部分的原因。我们还探讨了学习编译器构建对于提升编程能力和处理结构化数据文件的重要性。接下来，我们将深入词法分析，开始构建分词器。
046：词法分析
在本节课中，我们将要学习词法分析。词法分析是编译器前端的关键步骤，它负责将原始的字符流转换为有意义的“词法单元”或“标记”流，为后续的语法分析做好准备。
上一节我们介绍了语法分析器的整体结构，它由词法分析器和语法分析器两个主要模块组成。本节中，我们来看看其中的第一个模块——词法分析器。
什么是词法分析？
词法分析，通常由一个称为“词法分析器”或“标记器”的程序模块完成。它的核心任务是将输入的、仅由字符组成的原始数据流，转换成一个由有意义的“标记”组成的流。这里的“有意义”是针对我们正在分析的语言（例如Jack语言）而言的。
一旦我们得到了这个标记流，就可以将其交给编译器的后续阶段（如语法分析器）。从这一刻起，我们可以完全忘记原始的输入文件。这非常有用，因为原始文件包含了许多对编译器无关的“噪音”，例如空格、制表符、换行符和注释。因此，词法分析是对文件进行的一种简单而重要的预处理，为编译过程奠定了良好的基础。
什么是标记？
一个标记，是在目标语言中有意义的一个字符串或字符序列。不同的编程语言对标记有不同的定义。
例如，考虑语句 x++。在C语言中，这个语句很有意义，因为它可以被分解为两个有意义的标记：x 和 ++。然而，如果将完全相同的输入交给一个Jack语言的标记器，它虽然也能将其分解为标记（得到三个标记：x、+ 和 +），但在后续的编译过程中，语法分析器会报错，因为在Jack语言中并没有 ++ 这个运算符。
因此，如果你要编写一个标记器，必须获得一份明确的语言规范文档，其中清晰定义了该语言中哪些字符序列构成合法的标记。
Jack语言的标记类别
在Jack语言中，标记被明确地分为以下五类：
以下是Jack语言中定义的标记类别：
-
关键字：例如
class、method、if、while等，约有20个。 -
符号：例如
+、-、*、/、=、{、}、;等。 -
整型常量：范围在
0到32767之间的数字。 -
字符串常量：由一对双引号
"包围的任何字符序列。 -
标识符：用于命名变量、方法、类等，由字母、数字和下划线组成，且不以数字开头。
每一类标记都有清晰、无歧义的定义。基于这份词法定义，我们就可以编写程序来实现标记器。
标记器的功能与使用
标记器通常被实现为一个类或模块。它会提供一系列有用的服务，允许我们将输入视为一个标记流来操作。
以下是标记器提供的主要服务：
-
判断：是否还有更多标记需要处理？
-
获取：获取下一个标记。
-
查询：当前标记的类型是什么？其值是什么？
下面是一个使用这些服务的程序示例。程序 TokenizeTest 会构造一个标记器对象，然后处理输入文件。
// 伪代码示例
tokenizer = new JackTokenizer(inputFile);
while (tokenizer.hasMoreTokens()) {
tokenizer.advance(); // 前进到下一个标记
tokenType = tokenizer.tokenType(); // 获取当前标记类型
tokenValue = tokenizer.getValue(); // 获取当前标记值
// 输出：<tokenType> tokenValue </tokenType>
outputFile.writeLine("<" + tokenType + "> " + tokenValue + " </" + tokenType + ">");
}
对于输入文件中的每一个标记，程序会将其输出，并用标签包围以说明其类型。这样生成的结果不仅列出了程序中的所有标记，也清晰地标明了它们的类型。这个测试并非随意举例，它实际上正是后续我们的语法分析器使用标记器的方式。这里生成的信息对编译器至关重要，而标记器让我们能够轻松地获取它。
请注意，完成此过程后，我们就不再需要源代码文件了。因为从现在开始，标记器对象将成为编译器的输入源。
总结
本节课中我们一起学习了词法分析。我们了解到，标记器是语法分析器中的第一个模块，它负责根据语言规范将字符流分组为有意义的标记（如关键字、符号、常量等）。现在我们已经知道了如何将字符分组为标记，接下来就可以继续讨论语法分析了。
但在深入语法分析之前，我们需要先了解一些关于“文法”的知识，这将是下一单元的主题。
047：文法 🧩
在本节课中，我们将要学习文法的概念。文法定义了如何将有效的单词（即词法单元）组合成有意义的句子或程序语句。理解文法是进行语法分析的基础。
在上一单元，我们讨论了词法分析，并建立了将程序视为一系列词法单元的概念能力。现在，你可能会同意，仅仅拥有一组有效的词法单元，并不一定意味着我们拥有一个有效的文本或程序。例如，在英语中，考虑以下一组词法单元：“Red drives a he”。这毫无意义，尽管每个词法单元本身都是合法的英语单词。然而，它们的顺序不正确。如果说“He drives a red car”，一切就变得清晰明了。因此，不仅词法单元本身重要，它们的顺序也至关重要。
定义词法单元如何合法组合的规则集合，就称为文法。从技术上讲，文法是一组规则，每条规则定义了一种模式，指示如何将词法单元串联起来，以构成底层语言中有意义的句子或语句。
文法示例：英语子集
以下是一个英语语言的子集文法示例。在这个文法中，我们有句子。每个句子由一个名词短语后跟一个动词短语构成。
-
句子 → 名词短语 动词短语
-
名词短语 → 限定词? 名词
-
动词短语 → 动词 名词短语
-
名词 →
dog|school|dinner|Dina| … -
动词 →
went|ate|said| … -
限定词 →
the|my|a| …
这个文法具有递归性。这个子集足够丰富，可以接受诸如“Dina went to school”、“She said”、“The dog ate my homework”等输入。例如，分析“The dog ate my homework”：
-
“The”是限定词，“dog”是名词，它们构成一个名词短语。
-
“ate”是动词，“my homework”是另一个名词短语，它们构成一个动词短语。
-
因此，我们有一个名词短语后跟一个动词短语，根据此文法，这是一个合法的句子。
文法的规则类型
观察这个文法，可以发现它由一组规则构成。这些规则可以分为两大类：
-
终结符规则：规则的右侧仅由常量（即具体的词法单元）构成。
-
非终结符规则：规则的右侧包含其他规则的名称，也可能包含常量。
一个文法就是由终结符规则和非终结符规则组成的集合。这个观察在我们后续的工作中会很有用。
聚焦Jack语言文法
现在，让我们将注意力转向Jack语言的文法。本课程不是关于一般计算语言学，而是关于编译。因此，我们关注Jack程序的文法。
一个Jack程序由一系列语句构成。我们聚焦于Jack语言的一个子集，其中包含三种可能的语句：if、while和let。以下是该子集的文法定义：
-
statements→statement* -
statement→ifStatement|whileStatement|letStatement -
ifStatement→if(expression){statements} -
whileStatement→while(expression){statements} -
letStatement→letvarName=expression; -
expression→term(opterm)? -
term→varName|constant -
varName→ 一个不以数字开头的字符串 -
constant→ 任意十进制数字 -
op→+|-|*|/|&|||<|>|=
以上构成了Jack语言一个子集的完整文法。现在我们可以开始考虑各种输入，并判断它们是否符合此文法。
文法分析示例
以下是几个输入示例及其是否符合文法的分析：
-
输入：
let x = 100;- 分析：以
let开头，符合letStatement模式。x是有效的varName。接着是=符号。100是constant，因此是term，进而构成expression。最后是;。所有部分都匹配letStatement规则。结论：接受。
- 分析：以
-
输入：
let x = x + 1;- 分析：
let x =部分同上。x + 1中，x是term，+是op，1是constant（即term），因此x + 1匹配expression规则（termopterm）。结论：接受。
- 分析：
-
输入：
while ( n < limit )- 分析：以
while开头，符合whileStatement模式。接着是(。n < limit可以分析为expression。接着是)。然而，whileStatement规则要求后面必须有{statements}，但输入在此处结束。结论：拒绝（语法错误）。
- 分析：以
-
输入：
if (key = 81) { let exit = true; do Output.printString("Bye"); }- 分析：这是一个
ifStatement。括号内的key = 81是expression。花括号{}内包含两个statement（一个letStatement和一个do语句，虽然do不在我们当前子集但原理相同），这符合statements（零个或多个statement）的定义。结论：接受。
- 分析：这是一个
-
输入：
let x = 5 * (y + 3);- 分析：你可以尝试自行分析。它同样符合
letStatement的规则，因为5 * (y + 3)是一个合法的expression。结论：接受。
- 分析：你可以尝试自行分析。它同样符合
语法分析的作用
语法分析就是判断给定输入是否符合特定文法的艺术与科学。请注意，在这个确认过程中，我们同时也揭示了输入的全部语法结构，因为我们分析了输入如何对应规则的各个组成部分。通过这样做，我们构建了输入底层的语法结构树。
顺便一提，我们的大脑正是以某种神秘的方式（尽管越来越可被理解）在做类似的事情。当我们听到一个句子时，我们会尝试将其与我们大脑中固有的、通过一生语言学习形成的模式进行匹配。我们的大脑拥有这种理解句子的卓越能力，即使句子不完全符合语法。如果没有这种能力，世界上所有的诗人都会失业。但是，计算机程序和编译器没有这种卓越的能力。当你处理编译器时，输入必须完美匹配文法。如果有任何不符，编译器就会报错并提示“语法错误，你必须修复你的程序”。
本节课中我们一起学习了文法的基本概念，包括其定义、规则类型（终结符与非终结符），并通过英语和Jack语言的例子了解了如何使用文法来判断输入的有效性。语法分析是编译过程中的关键步骤，它确保程序在结构上是正确的。
下一单元，我们将讨论语法分析树的概念，这是一种我们用来描述输入语法结构的数据结构。
048：语法分析树 📚
在本节课中，我们将学习语法分析树的概念。语法分析树是一种用于表示输入文本（无论是自然语言还是编程语言）语法结构的树形图。我们将通过对比英语和Jack编程语言的例子，来理解其工作原理和表现形式。
语法分析树的概念
上一节我们介绍了语法的概念。本节中我们来看看如何用结构化的方式表示一个符合语法的句子的形态。
语法分析树是一种在计算语言学中用于记录输入文本完整语法结构的方法。它本质上是一种经典的计算机科学数据结构——树。树是一种递归结构，它从一个根节点开始，然后分支成子树，依此类推。
输入的语法结构同样是递归的。具体来说，如果我们自上而下地观察这个形态，它会记录一个事实：我们有一个句子，这个句子由诸如名词短语和动词短语等子树描述。而这些子树本身又由更低层级的子树构成，我们可以持续扩展这棵树，直到到达树的边界。
树的边界有时被称为叶子节点或终结节点。在词法分析的语境下，终结节点就是构成输入的实际标记。因此，语法结构是位于输入之上的一种上层结构，用于描述其语言形态。
从英语到Jack语言
以上是关于像英语这样的语言的故事，当然，这是一个非常简单的例子。现在让我们转向Jack语言。
在Jack语言中，我们有一套不同的语法，以及对应编程语言（即Jack语言）中某些语句子集的不同类型的输入。
以下是这个特定输入对应的语法分析树示例。
我们可以看到，这里再次得到了一棵树。虽然我使用了曲线而非直线，但实际上，这与之前的概念完全相同。
语法分析树的表示形式
我想请大家注意，语法分析树的概念是一个抽象的产物，它位于所有这些漂亮图表之上。而我在这里绘制的图表，只是描述这个语法分析树的一种方式。
为了说明这一点，让我们聚焦于此处看到的语法分析树的某个子集，放大观察这个小部分。请注意，这个子树描述或对应于输入 count + 1。
我想向大家展示描述这同一个语法分析树的另一种方式，如下所示。
这里我们看到的是一种叫做XML的格式。XML格式是一种公认的描述结构化数据的方式。基本上，我们使用标记标签来描述数据的结构或构成数据的项的结构。
在这个例子中，我们使用了一些尚未定义的约定，但我们可以大致猜测其含义。我们记录了这样一个事实：这里有一个表达式，该表达式由一个项、后跟一个符号、再跟另一个项组成。而这些项本身也由更低层级的结构构成：第一个项由一个标识符构成，第二个项由一个整型常量构成，依此类推。
因此，如果我愿意，可以选择使用这里展示的格式，即某种约定的XML文本来创建我的语法分析树。
重要观察与总结
在结束之前，我想提出两个重要的观察。
首先，我们在这里看到的是对应于输入 count + 1 的XML文件。可以想象，如果我们需要为一个完整的Jack程序创建语法分析树，最终将得到一个庞大的XML文件，而这完全没有问题。
其次，我尚未提及实际构建这个文件的过程。我们如何做到呢？从输入开始，到最终得到这个结构良好的输出，其背后的逻辑是什么？这个逻辑正是下一单元即将讨论的主题：语法分析逻辑。
本节课中我们一起学习了语法分析树的概念。我们了解到它是一种表示句子语法结构的树形图，具有递归特性，并且可以用图表或XML等结构化格式来描述。它为下一阶段理解语法分析的具体逻辑奠定了基础。
049：解析器逻辑 🧩
在本单元中，我们将探讨解析器（Parser）的逻辑。我们将了解如何根据给定的语法规则，将输入的源代码（如Jack语言代码）转换成一个结构化的、描述其语法成分的树状表示（例如XML格式）。
在上一单元，我们讨论了语法分析树（Parse Tree），并看到了英语句子和Jack代码的解析示例。我们指出，既可以用图示来表示语法树，也可以用一种约定的格式（如XML）来描述输入的结构。那么，核心问题自然是：我们如何从一个原始的输入开始，最终得到这样一个结构清晰、描述输入语法结构的输出呢？
解析器的实现逻辑
为了解答这个问题，我们直接来看实现解析器将要用到的代码逻辑。在本模块后续部分，我们将开发一个名为“解析器”的程序，实际上这个模块的名称将是“编译引擎”（Compilation Engine）。
这个编译引擎将由一系列方法构成。几乎对应语法中的每一个非终结符规则，我们都会有一个方法。例如，语法中有一个名为 statements 的规则，相应地我们就有一个 compileStatements 方法；有一个 ifStatement 规则，就有一个 compileIfStatement 方法，依此类推。
这些方法负责解析输入中对应特定规则的部分。虽然有些规则没有专门的方法，但它们会在其他规则的上下文中被隐式处理，这个细节我们稍后会讨论。
方法的工作原理
为了说明，让我们聚焦于其中一个方法：compileWhileStatement，它对应 whileStatement 规则。我们来看看这个子程序在实践中如何工作。
总的来说，这些方法的编写逻辑直接来源于语法规则。具体做法如下：
-
遵循规则的右侧：我们严格按照规则右侧描述的“模式”来编写代码。
-
处理终结符：如果规则右侧指定了一个终结符（Token，如
while、(），我们就检查输入中的当前Token是否匹配。如果匹配，就将其记录到输出文件中，然后让输入前进到下一个Token。 -
处理非终结符：如果规则右侧指定了一个非终结符规则（如
expression），我们就调用专门处理这个非终结符的对应方法（如compileExpression）。
可以看到，整个过程是高度递归的。我们不断递归调用，直到耗尽输入中的所有Token，这样就完成了对给定输入的解析。
解析过程模拟
让我们通过一个具体的 while 循环示例，来模拟解析器的完整工作流程。假设输入是 while (count < 10) { let count = count + 1; }。
以下是解析步骤的详细模拟：
-
启动：我们启动词法分析器（Tokenizer），它负责将输入分解为Token序列。第一个Token是
while。 -
调用
compileWhileStatement：由于第一个Token是while，我们调用compileWhileStatement方法。该方法开始运行，并在输出中写入开始标签<whileStatement>。 -
处理
while：规则说第一个应该是whileToken。检查当前Token，确实是while。将其记录到输出（如<keyword> while </keyword>），然后让输入前进。 -
处理
(：规则说下一个应该是(。检查当前Token，确实是(。记录并前进。 -
处理
expression：规则说下一个应该是expression。我们调用compileExpression方法。-
compileExpression查看其规则，发现应以一个term开始。于是调用compileTerm。 -
compileTerm查看其规则，发现当前Tokencount是一个varName。记录count并前进。 -
控制权回到
compileExpression。它检查规则，发现后面可能有一个可选的op和另一个term。当前Token是<，是一个操作符。记录<并前进。 -
再次调用
compileTerm来处理下一个term。当前Token10是一个constant。记录10并前进。 -
compileTerm结束，compileExpression也结束。
-
-
处理
)：控制权回到compileWhileStatement。规则说下一个应该是)。检查当前Token，确实是)。记录并前进。 -
处理
{：规则说下一个应该是{。检查当前Token，确实是{。记录并前进。 -
处理
statements：规则说下一个应该是statements。我们调用compileStatements方法。-
compileStatements查看其规则，寻找一个statement。当前Token是let，表明是一个letStatement。于是调用compileLetStatement。 -
compileLetStatement按照其规则依次处理let、varName(count)、=、expression(count + 1)、;。每处理一个Token就记录并前进。 -
compileLetStatement结束，compileStatements发现没有更多statement，也结束。
-
-
处理
}：控制权回到compileWhileStatement。规则说下一个应该是}。检查当前Token，确实是}。记录并前进。 -
结束：没有更多Token需要处理。
compileWhileStatement方法结束，并在输出中写入结束标签</whileStatement>。至此，解析完成，我们得到了描述输入结构的XML文件。
代码结构示例
现在，让我们更具体地看看 compileWhileStatement 方法的代码结构。开发者会以语法规则为指导来编写解析器代码。
以下是 compileWhileStatement 方法的一个伪代码示例：
// 伪代码示例
public void compileWhileStatement() {
// 写入开始标签
output.write("<whileStatement>");
// 1. 处理 'while' 关键字
eat("while"); // 期望并消耗掉 "while" 这个Token
// 2. 处理 '('
eat("(");
// 3. 处理表达式
compileExpression();
// 4. 处理 ')'
eat(")");
// 5. 处理 '{'
eat("{");
// 6. 处理语句序列
compileStatements();
// 7. 处理 '}'
eat("}");
// 写入结束标签
output.write("</whileStatement>");
}
// 一个私有的辅助方法
private void eat(String expectedToken) {
if (currentToken.equals(expectedToken)) {
// 将当前Token写入输出（带适当标签）
output.writeToken(currentToken);
// 前进到下一个Token
advance();
} else {
// 如果不匹配，抛出语法错误
throw new SyntaxError("Expected: " + expectedToken + ", but found: " + currentToken);
}
}
如你所见，每个 compileXxx 方法的代码都严格遵循对应 xxx 规则的右侧描述。每个方法都负责推进并处理属于该规则的所有Token。通过这些方法的递归调用，我们就能完成对整个输入的解析。
关于语法的理论说明
最后，我们以一些关于所用语法类型的理论说明来结束本单元。
首先，引入 LL 文法 的概念。LL文法是一种可以被递归下降解析算法（即我们正在使用的这种算法）无回溯地解析的文法。这意味着这种文法非常“友好”：一旦你开始解析某部分，就永远不需要回头。当你判定当前是一个 while 语句还是一个 if 语句时，你不必撤销进度、重新分析。这个特性使得解析器的实现相对简单。
其次，是 LL(k) 的概念。一个LL(k)解析器在确定使用哪条规则之前，最多需要向前查看 k 个Token。幸运的是，我们目前看到的Jack语法是 LL(1) 的。这意味着，只要我手中有一个特定的Token（如 while、let、do），我就能立即知道应该调用哪条规则，无需回溯。
这与自然语言（如英语）形成鲜明对比。英语不是LL(1)。例如，听到单词“Lift”时，你无法确定其语法角色。它可能是一个动词（如“Lift me”），也可能是一个形容词（如“Lift operator”）。你可能需要向前查看多个单词，甚至可能需要回溯，才能确定正确的语法结构。人类大脑能以惊人的速度完成这种解析，但用计算机程序实现则极其困难，因为英语可能是类似LL(5)或LL(6)的文法。而大多数编程语言被设计成LL(1)，这使得解析它们比解析自然语言要容易得多。
总结
在本单元中，我们一起学习了解析器的核心逻辑。我们了解到，解析器通过一系列与语法规则对应的方法，以递归下降的方式工作。每个方法负责处理输入中符合特定规则的部分，通过检查、记录Token和递归调用其他方法，最终将线性的Token序列转换为结构化的语法树表示。我们还了解到，像Jack这样的编程语言通常采用LL(1)文法，这使得其解析过程可以高效、无回溯地进行，大大简化了解析器的实现。在接下来的部分，我们将具体审视Jack语言的完整语法规则。
050：Jack文法 🧩
在本单元中，我们将深入探讨Jack编程语言的文法。我们将学习如何形式化地描述Jack语言的结构，并理解这些文法规则如何指导我们后续构建语法分析器。
文法符号定义 📝
上一节我们介绍了文法和语法分析的一般概念。本节中，我们来看看Jack文法所使用的具体符号表示法。
以下是描述Jack文法时使用的符号规则：
-
字面量：用黑色字体和引号表示，例如
"class"。这表示输入中必须原样出现的特定词法单元。 -
元语言：所有非字面量的绿色部分，是我们为描述Jack文法而发明的描述符。
-
分组：使用圆括号
()对词法单元进行分组。 -
选择：使用竖线
|表示在多个选项中选择一个。 -
可选：使用问号
?表示某个元素出现零次或一次。 -
重复：使用星号
*表示某个元素出现零次或多次。
这些简单的规则足以描述编程语言的结构。
Jack文法全貌 🗺️
掌握了符号规则后，我们现在可以完整地展示Jack文法。它看起来可能有些复杂，但这只是因为我们将整个语言压缩到了一张幻灯片上。实际上，整个文法非常简洁，分为四个主要部分。
1. 词法元素
Jack程序由以下基本的词法单元（或称为“原子”）构成：
-
关键字：例如
class，constructor，function，method，field，static，var，int，char，boolean，void，true，false，null，this，let，do，if，else，while，return。 -
符号：例如
{，}，(，)，[，]，.，,，;，+，-，*，/，&，|，<，>，=，~。 -
整数常量：例如
123，0，4567。 -
字符串常量：例如
"Hello, World!"。 -
标识符：由字母、数字和下划线组成的序列，且不以数字开头，例如
myVariable，_temp，Screen12。
2. 程序结构
一个Jack程序由一个或多个类组成，每个类被单独存储、处理和编译。
以下是类的结构定义：
class ::= ‘class’ className ‘{‘ classVarDec* subroutineDec* ‘}’
-
class是关键字。 -
className是一个标识符。 -
{和}是必须的符号。 -
classVarDec*表示零个或多个类变量声明。 -
subroutineDec*表示零个或多个子程序声明。
类变量声明的规则如下：
classVarDec ::= (‘static’ | ‘field’) type varName ( ‘,’ varName )* ‘;’
例如，static int x, y, z; 符合此规则。
类型定义如下：
type ::= ‘int’ | ‘char’ | ‘boolean’ | className
Jack只有三种基本类型（int， char， boolean），也支持类名作为类型。
子程序声明的规则如下：
subroutineDec ::= (‘constructor’ | ‘function’ | ‘method’) (‘void’ | type) subroutineName ‘(‘ parameterList ‘)’ subroutineBody
子程序可以是构造函数、函数或方法，可以返回void或某种类型。
参数列表是可选的：
parameterList ::= ((type varName) ( ‘,’ type varName )*)?
? 表示整个参数列表可能出现零次或一次。
3. 语句
Jack程序包含多种语句，以下是语句的总体和具体定义：
statements ::= statement*
statement ::= letStatement | ifStatement | whileStatement | doStatement | returnStatement
以下是各类语句的规则：
-
赋值语句：
letStatement ::= ‘let’ varName ( ‘[‘ expression ‘]’ )? ‘=’ expression ‘;’ -
条件语句：
ifStatement ::= ‘if’ ‘(‘ expression ‘)’ ‘{‘ statements ‘}’ ( ‘else’ ‘{‘ statements ‘}’ )? -
循环语句：
whileStatement ::= ‘while’ ‘(‘ expression ‘)’ ‘{‘ statements ‘}’ -
过程调用语句：
doStatement ::= ‘do’ subroutineCall ‘;’ -
返回语句：
returnStatement ::= ‘return’ expression? ‘;’
4. 表达式
表达式是文法中相对复杂的部分，其定义如下：
expression ::= term (op term)*
表达式由一个term（项）开头，后面可以跟零个或多个由运算符op连接的term。
使表达式变得复杂的是term规则本身：
term ::= integerConstant | stringConstant | keywordConstant | varName | varName ‘[‘ expression ‘]’ | subroutineCall | ‘(‘ expression ‘)’ | unaryOp term
term可以是整数常量、字符串常量、关键字常量、变量名、数组访问、子程序调用、括号表达式或一元运算表达式。
处理表达式的挑战在于，当遇到一个标识符（变量名）时，它可能代表多种情况（简单变量、数组元素、子程序调用等）。为了确定具体是哪一种，语法分析器需要“向前看”下一个词法单元。这是Jack语言中唯一需要LL(2)分析能力的地方，其他部分都是LL(1)的。
文法与语法分析器的关系 🔗
我们给出完整的Jack文法，是因为它将作为我们编写语法分析器的“配方”。
语法分析器将由一组编译例程构成，几乎对应文法中的每一个非终结符规则。每个分析例程将根据对应规则的右侧部分来编写，负责生成所需的XML输出，并在此过程中调用其他分析例程。这体现了文法与依其运作的语法分析器之间紧密的关系。
总结 📚
本节课中我们一起学习了Jack编程语言的完整文法。我们了解了用于描述文法的符号系统，并将文法分解为四个主要部分：词法元素、程序结构、语句和表达式。我们特别注意到，表达式中term规则的处理相对复杂，因为遇到标识符时需要“向前看”一个词法单元来确定其具体角色。理解这些文法是后续动手构建Jack语法分析器的关键基础。在下一个单元，我们将开始讨论如何编写这个分析器本身。
051：Jack分析器输出规范
在本单元中，我们将详细说明Jack语法分析器（或称解析器）应输出的具体内容。我们将了解如何通过生成结构化的XML输出来验证分析器对源代码的语法理解，而无需等待代码生成器的开发。
概述
在之前的单元中，我们泛泛地讨论了语法树和解析器逻辑。本单元将具体说明Jack分析器应输出的内容。我们正在开发一个编译器，但当前模块仅关注语法分析器。一个有趣的问题是：如何独立地对语法分析器进行单元测试？如何在不生成代码的情况下，确认分析器正确理解了源代码？答案是：我们可以将代码生成器的开发推迟到后续阶段。目前，我们可以要求分析器以预定的方式输出源代码的结构化表示，具体来说，就是生成XML代码。
终端规则的输出处理
首先，我们来看如何处理符合语法中终端规则的输入。根据Jack语法，终端元素包括关键字、符号、整数常量、字符串常量或标识符。
以下是处理此类输入的方法：
-
对于关键字（如
method），输出格式为：<keyword> method </keyword>。 -
对于符号、整数常量等，只需用相应的XML标签将其包裹并输出即可。
处理终端规则的输出非常简单直接。
非终端规则的输出处理（主要部分）
接下来，我们讨论非终端规则。非终端规则可分为两个子集。首先，我们看构成语法中绝大部分规则的那个子集。
当输入符合此类规则时，处理方法如下：
-
在输出开始处写入该非终端规则的名称作为开始标签。
-
然后，递归地输出构成该规则主体的所有内容。
-
最后，写入结束标签。
例如，对于输入 return x;：
-
分析器识别出这是一个
returnStatement，输出<returnStatement>。 -
根据语法规则，
returnStatement应以关键字return开始。分析器输出<keyword> return </keyword>。 -
接着应有一个
expression。分析器递归处理，发现表达式由term构成，而term在这里是标识符x。因此输出<identifier> x </identifier>。 -
最后输出
</returnStatement>。
分析器必须递归地发出构成规则主体的所有输出，这些输出本身可能是嵌套的，因此解析器必须是一个递归程序。
非终端规则的输出处理（浅层规则）
现在，我们来看第二个非终端规则子集，我有时称之为浅层规则或从语法角度看“不那么有趣”的规则。
处理符合此类规则的输入时，分析器不会生成任何相关的XML标记。让我举例说明。
让我们关注描述 let 语句和 varName 的这部分Jack语法。varName 就是一条我们决定不在XML输出中包含的非终端规则。
例如，处理输入 let x = 17;：
-
分析器记录这是一个
letStatement，输出<letStatement>。 -
记录
let关键字，输出<keyword> let </keyword>。 -
根据规则，接下来应有一个
varName。但是，查看输出示例，我们不会输出<varName>标签。 我们跳过了varName规则，直接深入处理其右侧的标识符x，输出<identifier> x </identifier>。
再次注意，varName 规则不生成任何标记。我们决定这样做，是因为此处列出的一些规则（如 varName）在结构上非常简单（例如，一个规则的名称只是另一个规则主体的名称）。我们允许自己跳过解析这些简单规则，以避免如果不采取这些快捷方式可能产生的一些冗余输出。
总结
本节课我们一起学习了Jack语法分析器应输出的具体规范。我们了解到，分析器通过生成反映Jack语法结构的XML输出来证明其对源代码的理解。对于终端规则，直接输出带标签的内容；对于主要的非终端规则，递归输出其完整结构；而对于一些浅层规则，则选择跳过其标记以简化输出。在单元4.5中，我们已从宏观上讨论了分析器生成输出的方法（即为每个规则配备一个处理方法），下一个单元将提供Jack分析器的参考实现。结合这两个单元，你将获得编写自己的Jack分析器所需的全部信息。
052：Jack分析器建议实现方案 🛠️
在本节课中，我们将学习如何构建一个Jack语法分析器。我们将讨论其核心模块：Jack分词器、编译引擎以及驱动它们的主程序Jack分析器。
概述
到目前为止，我们以Jack语言为例，讨论了语法分析的一般概念。在本单元及下一单元，我们将实际动手构建一个Jack分析器。我们的最终目标是开发一个编译器，并决定将编译器的开发分为两个独立项目。在当前项目中，我们开发语法分析器；在下一个项目（模块）中，我们将开发代码生成器。
为了独立于系统其他部分对语法分析器进行单元测试，我们决定让语法分析器生成一个XML代码文件。通过检查这个文件，我们可以判断语法分析器是否正常工作。关于“正常工作”的具体定义，我们将在下一单元详细讨论项目10时给出。
我们建议的语法分析器实现将包含三个模块：一个Jack分词器模块、一个编译引擎以及一个名为Jack分析器的主程序。本单元我们将讨论每个模块，并给出其API，以便你能够按照我们的建议实现自己的分析器。
Jack分析器的使用方式
首先，让我们从最终如何使用Jack分析器开始说明。假设这个程序是用Java编写的，那么在命令行中，我们会输入程序名 JackAnalyzer，并提供一个输入参数。
输入参数可以是以下两种之一：
-
一个
.jack文件（例如MyProgram.jack）。 -
一个包含零个或多个
.jack文件的目录名。
输出结果如下：
-
如果输入是单个
.jack文件，输出将是一个同名的.xml文件。 -
如果输入是一个目录名，将为该目录中的每个
.jack文件生成一个对应的.xml文件，并保存在同一目录下。
这就是我们的Jack分析器期望的行为。
模块架构与工作流程
Jack分析器将使用Jack分词器和编译引擎的服务。分词器和编译引擎都需要你根据Jack语法和本模块之前给出的所有指导原则来开发。
Jack语法的第一部分描述了语言的词法元素（即标记）。语言共有五类标记：关键字、符号、整型常量、字符串常量和标识符。Jack分词器将负责处理这些标记。
语法的其余部分将由编译引擎处理。
因此，从现在到本单元结束，我们将讨论这两个模块：首先介绍如何开发分词器，然后介绍如何开发编译引擎。
Jack分词器模块 🔤
分词器在编译引擎的上下文中运行。编译引擎使用分词器的服务。分词器封装了输入文件，使我们无需再关心原始文件本身。对我们而言，分词器就是输入源。我们可以让它前进到下一个标记，询问当前标记的类型等信息。
最终，分词器将是一个软件模块，包含一个构造函数和一系列方法。
编写分词器意味着编写一个类（如果用Java、C#或C++等语言），该类包含这些方法。它使用输入文件作为输入，逐个读取字符并将其分组为标记。
其中最具挑战性的方法是 advance，因为它负责将字符分组为标记，并判断标记的类型。这并不十分复杂，但需要考虑一些特殊情况。例如，一连串没有空格的字符并不一定代表一个标记，可能包含多个标记（如 getX() 包含三个标记：getX、( 和 )）。分词器必须足够智能来区分它们。
实现逻辑是：从第一个字符开始构建标记，当遇到不属于当前标记类型的字符时（例如，标识符后遇到符号 (），就结束当前标记的构建，并开始下一个标记。我们可以通过查询语法定义中的合法字符集来判断。
Jack分词器API
以下是Jack分词器的应用程序接口：
-
构造函数
JackTokenizer(inputFile)- 打开输入文件/流并准备进行标记化。
-
boolean hasMoreTokens()- 判断输入中是否还有更多标记。
-
void advance()- 从输入中获取下一个标记，并将其设为当前标记。只有在
hasMoreTokens()为真时才能调用此方法。
- 从输入中获取下一个标记，并将其设为当前标记。只有在
-
tokenType tokenType()- 返回当前标记的类型。
tokenType是以下常量之一：KEYWORD，SYMBOL，IDENTIFIER，INT_CONST，STRING_CONST。
- 返回当前标记的类型。
-
keyword keyword()- 返回当前标记的关键字。仅当
tokenType()为KEYWORD时调用。
- 返回当前标记的关键字。仅当
-
char symbol()- 返回当前标记的字符。仅当
tokenType()为SYMBOL时调用。
- 返回当前标记的字符。仅当
-
string identifier()- 返回当前标记的标识符。仅当
tokenType()为IDENTIFIER时调用。
- 返回当前标记的标识符。仅当
-
int intVal()- 返回当前标记的整数值。仅当
tokenType()为INT_CONST时调用。
- 返回当前标记的整数值。仅当
-
string stringVal()- 返回当前标记的字符串值（不含双引号）。仅当
tokenType()为STRING_CONST时调用。
- 返回当前标记的字符串值（不含双引号）。仅当
实现这些方法相对简单。你可以自由使用编程语言提供的字符串处理工具，如正则表达式。
编译引擎模块 ⚙️
与分词器类似，编译引擎也以语法为指导进行设计。简而言之，我们将开发一个名为 CompilationEngine 的类或模块。
编译引擎从Jack分词器获取输入，因此我们无需再关心原始输入文件。它可以愉快地询问当前标记、在输入中前进等。
它将有一个构造函数和一系列 compileXxx 例程，几乎对应语法中的每一个 xxx 规则。每个例程负责处理对应规则右侧的所有标记。
我们在第4.5单元专门模拟了编译引擎的逻辑和操作。如果你需要更多关于如何实现编译引擎的指导，强烈建议回顾第4.5单元。
编译引擎API
以下是编译引擎的应用程序接口：
-
构造函数
CompilationEngine(inputTokenizer, outputFile)- 创建一个新的编译引擎，并指定其输入（分词器）和输出文件/流。
-
void compileClass()- 编译一个完整的类。
-
void compileClassVarDec()- 编译一个静态变量声明或字段声明。
-
void compileSubroutine()- 编译一个完整的方法、函数或构造函数。
-
void compileParameterList()- 编译一个（可能为空的）参数列表，不包括括号
()。
- 编译一个（可能为空的）参数列表，不包括括号
-
void compileVarDec()- 编译一个
var声明。
- 编译一个
-
void compileStatements()- 编译一系列语句，不包含花括号
{}。
- 编译一系列语句，不包含花括号
-
void compileDo()- 编译一个
do语句。
- 编译一个
-
void compileLet()- 编译一个
let语句。
- 编译一个
-
void compileWhile()- 编译一个
while语句。
- 编译一个
-
void compileReturn()- 编译一个
return语句。
- 编译一个
-
void compileIf()- 编译一个
if语句，可能包含else分支。
- 编译一个
-
void compileExpression()- 编译一个表达式。
-
void compileTerm()- 编译一个项。如果当前标记是标识符，此例程必须区分变量、数组元素还是子程序调用。
-
void compileExpressionList()- 编译一个（可能为空的）逗号分隔的表达式列表，不包含括号
()。
- 编译一个（可能为空的）逗号分隔的表达式列表，不包含括号
关于未覆盖的语法规则
Jack语法中有一些规则没有对应的独立 compile 方法。语法大约有21条非终结符规则，而上面的API只有15个编译方法。缺少的6条规则（如 statement、subroutineCall 等）的逻辑，由调用它们的上层方法处理。
我们之所以不直接为这些规则创建方法，是因为它们在整体语法中的作用相对次要或浅显。例如，statements 规则由 compileStatements() 方法处理，该方法使用循环处理零个或多个 statement 实例，并根据每个语句的第一个标记来决定调用 compileIf、compileWhile 等具体方法。因此，没有单独的 compileStatement 方法。
Jack分析器主程序 🚀
Jack分析器模块相对简单，因为它只是通过使用我们之前讨论过的、更具挑战性的分词器和编译引擎的服务来驱动整个流程。
Jack分析器是我们程序的最顶层模块。它接收一个 .jack 文件名或一个包含多个 .jack 文件的目录名。
对于每个输入文件，它执行以下流程：
-
根据输入文件名（
.jack）创建一个Jack分词器对象。 -
创建一个输出文件，其名称与输入文件相同，但扩展名为
.xml，并准备写入。 -
创建并使用一个编译引擎，将输入（Jack分词器）编译到输出文件。
这就是Jack分析器的全部设计工作。
总结
本节课我们一起学习了Jack语法分析器的建议实现方案。我们详细介绍了三个核心组件：
-
Jack分词器：负责读取源代码并将其分解为有意义的标记（如关键字、标识符、符号等）。
-
编译引擎：根据Jack语法规则，接收分词器产生的标记流，并生成结构化的XML输出，反映程序的语法层次。
-
Jack分析器：作为主程序，负责处理文件输入/输出，并协调分词器与编译引擎的工作。
在下一单元，我们将实际动手，使用Java或Python等编程语言来构建这个分析器。
053：项目10 - 构建语法分析器 🛠️
在本节课中，我们将动手实践，开始开发我们一直讨论的语法分析器。
概述
我们正在开发一个Jack编译器，本模块的重点是编译器的语法分析器部分。我们面临的挑战是将此模块与系统的其余部分分开进行单元测试。为此，在项目10中，我们决定让语法分析器生成XML代码。通过查看此XML代码，无论是通过肉眼分析还是使用其他技术，我们都能判断语法分析器是否真正理解了源代码。这就是我们需要开发的程序。
项目要求
我们将在Jack语言的背景下进行开发。要求是开发一个语法分析器，能够翻译项目10目录中提供的所有Jack程序。对于每个这样的Jack文件，分析器应生成一个单独的XML输出文件，反映该Jack文件的语法结构，并且此XML文件应与我们提供的对比文件完全相同。
以下是验证输出的方法：
-
测试程序和对比文件位于您计算机的项目目录中。
-
您可以使用我们提供的名为
TextComparer的实用程序，将您的输出与我们的对比文件进行比较。TextComparer是一个比较两个文本文件的工具，它会忽略空白字符的差异。 -
另一种检查XML输出是否合理的方法是将其加载到浏览器（如Chrome或Firefox）或能够处理编程语言的文本编辑器中。这些工具可以帮您查看生成的XML结构，并判断其是否组织良好。
您需要选择一种编程语言来创建语法分析器，本课程目前接受Java和Python。此外，建议您查阅教材，其中有一整章专门介绍语法分析，您可以找到一些有用的信息。
实现计划
首先，我们将开发一个分词器，这是一个定义明确且相对简单的任务。然后，我们将继续开发编译引擎。我们使用“编译引擎”这个术语来描述一个使用我们之前开发的分词器服务的语法分析器。
我们将分两个阶段开发这个编译引擎：首先构建一个相对简单的基础程序，然后将其扩展为一个功能完整的语法分析器。
开发分词器
让我们从分词器开始。我们以一些源代码开始，最终希望得到类似右侧的XML输出。
现在，我们在这里右侧看到的XML示例与之前单元中看到的略有不同。以下是区别：
-
我们决定用名为
<tokens>和</tokens>的开始和结束标签包装整个XML文件。这样做是因为，如果您要将此文件加载到浏览器中以获得美观的结构化视图，浏览器期望看到一个定义良好、有开始和结束标签的XML文件。 -
您还会注意到，字符串常量（如源代码中的单词“negative”）在XML中显示时没有双引号。这是正确的处理方式。您的语法分析器不应输出双引号，而应原样输出字符串常量。
-
最后，您会注意到某些特殊字符（如
<、>、"、&和%）以特殊方式处理。由于它们在HTML中有特殊含义，为了避免浏览器解析错误，我们使用替代字符集（例如用<代表<）。使用此约定后，当您将文件加载到浏览器中时，就能正确看到这些字符。
那么，如何构建这个分词器呢？我们建议您遵循单元48中描述的API。请记住，本模块中的所有内容（分词器和语法分析器）本质上都是文本处理挑战。因此，您可以自由使用编程语言提供的所有字符串处理和正则表达式功能。
开发语法分析器
上一节我们介绍了分词器，本节中我们来看看如何开发语法分析器（或称整体Jack分析器）。这里有一个Jack代码示例，我们需要将其分析或翻译成右侧所示的XML。
我们如何做到这一点呢？我们在这个模块中已经讨论过，但基本上我们建议您从编写一个基础编译引擎开始，它能处理除表达式之外的所有内容。因为表达式处理起来有些棘手，所以我们倾向于单独处理它们。之后，我们再添加对表达式的处理。为了支持这种分阶段开发策略，我们将提供测试文件，使您能够分别对每个步骤进行单元测试。
以下是您的语法分析器在项目10中应处理的测试文件示例。我将突出显示此Jack文件中的表达式。如您所见，每个程序都包含许多表达式。
我们将为您提供此文件的两个版本：第一个是完整测试版本。但我们还提供了另一个版本，称为无表达式版本。在此版本中，我们将每个表达式替换为此方法作用域内的一个变量名。例如，我们不写 y + size < 254，而只写 x。这里x有意义，因为它恰好是此类中的一个字段，因此可以被所有方法全局识别。同样，我们不写 size = size + 2 这个复杂表达式，而是替换为 size = size。
我们的任务是创建这些文件，您无需关心我们是如何做到的。但结果是，这个文件比原始文件更简单，因为它没有复杂的表达式。因此，它适合测试一个能处理除表达式之外所有内容的语法分析器。这就是这些文件的目的。
基本上，当您查看这些程序的无表达式版本时，您会注意到它们在语义上没有意义，甚至有些奇怪。但从语法上讲，它们是完全有效的，因此它们达到了测试目的。我们很高兴地使用它们来测试语法分析器的基础版本。一旦您的语法分析器可以处理这些无表达式文件，您就可以继续完成也能处理表达式的完整版本。
处理表达式
这就是构建语法分析器的总体计划。现在，我想在本单元结束时谈谈如何处理表达式。
回顾Jack语法，在语法分析方面有问题的部分是这里突出显示的term规则。问题是，当当前标记是一个变量名（或某个标识符）时，它可能是一个像x这样的变量名，也可能是一个像x[18]这样的数组条目，或者是一个像x.doSomething()这样的子程序调用。解决我们处于哪种可能性的唯一方法是向前查看下一个标记。我们必须保存当前标记，然后向前查看下一个标记。一旦我们掌握了这两个标记，我们就拥有了决定如何处理它以及从中生成何种XML所需的所有信息。
好的，这是您在开发完整版语法分析器时必须注意的一个细节。
那么，子程序调用呢？看起来子程序调用在语法中是一个单独的规则，确实如此。但由于各种原因，我们决定子程序调用不由单独的编译方法处理，而是作为处理term的一部分来处理子程序调用规则的右侧逻辑。当您开发语法分析器时，您会发现这个建议会使代码更容易编写。因此，不会有compileSubroutineCall方法，子程序调用逻辑将作为处理term的一部分来处理。
总结
本节课中我们一起学习了构建Jack编译器语法分析器的路线图。我们正在开发一个Jack编译器，在本模块中我们开发了编译器的语法分析器。在下一个模块中，我们将开发一个代码生成器，两者结合将实现Jack语言编译器的完整功能。
这就是我们讨论如何处理项目10的单元，接下来是模块4的总结展望单元。
054：视角与展望
在本单元中，我们将回顾第一部分（语法分析与解析）的内容，并回答一些常见问题，为进入下一模块的代码生成部分做好准备。
概述
在本节课中，我们将探讨编译器构建中关于错误处理、技术通用性以及自动化工具使用的几个关键视角。我们将了解为何在本课程中做出某些设计选择，并展望这些技术在其他领域的应用。
错误处理与诊断
上一节我们介绍了语法分析的核心流程。本节中，我们来看看一个现实问题：错误处理。
在真实的编译器中，除了翻译程序，发现并报告错误同样重要。然而，在我们的Jack编译器中，我们决定完全回避错误诊断。我们做了一个简化的假设：需要编译的源代码是无错误的。
如果我们要移除这个简化假设，该如何处理？在某些情况下，捕获错误是简单的。例如，根据Jack语法，let关键字后必须跟一个标识符（如 let x = ...）。当解析器处理到let这个token时，它应预期下一个token是标识符。如果下一个token不是标识符，就可以生成错误信息并终止编译。
然而，通常编译器会更友好。它们不会在发现第一个错误时就立即停止，而是会尝试“控制”当前错误造成的损害，并继续捕获和报告代码中可能存在的其他错误。同时，一个优秀的编译器会尽力精确定位错误在源代码中的确切位置（这个位置可能与编译器检测到错误的位置不同）。
因此，错误处理是一门复杂的艺术，需要精密的诊断方法和复杂的代码，这些内容在本课程中均未涉及。此外，如果我们希望处理错误，就必须保留原始源代码，以便用各种错误信息和警告信息来标注它。这些细节在开发一个功能完整的编译器时非常重要。但在本课程中，我们决定构建一个最小化的编译器，并将错误诊断视为一个可以随时添加到基础编译器中的可选功能。
技术的通用性
接下来，我们探讨一下在本模块中学到的技术是否适用于其他编程语言。
解析器不仅对解析程序有用，对解析任何基于语法的文本也很有用，这在许多应用程序员的职业生涯中很常见。从生物信息学到电子邮件再到金融服务，有大量应用需要处理、分析和呈现结构化文本。我们在本模块中学到的技术可以直接应用于这些场景。
具体来说，在整个模块中，我们涵盖并开发了语法分析的两个最重要元素：词法分析和语法解析。因此，在这方面，你现在对进行语法分析的核心要点有了扎实的实践理解。
然而，与我们熟悉的Java、C++等工业级编程语言相比，我们处理的Jack语言被刻意设计得非常简单。它既没有运算符优先级，也没有继承等许多复杂特性。这种有限的设计显然是故意的，因为我们的目标是能够使用简单而优雅的解析算法来开发一个Jack编译器。
我们讨论的解析算法是自顶向下的。它尽可能少地读取token，并试图尽早确定正在解析的是哪种语言结构。采用这种自顶向下贪婪策略的解析器非常适合语法简单的语言。
当编译器开发者需要解析语法更复杂的语言时，他们通常会使用自底向上的解析，这与我们的方法有很大不同。这种策略自底向上开始，首先构建解析树的终端叶子节点，并将判断当前处理的是哪种语言结构的决定推迟到解析过程的后期阶段。这样，它们可以同时考虑多种处理可能性。但为了实现这一点，这些算法必须使用回溯，导致解析逻辑比我们在本模块中使用的简单自顶向下解析更难开发。
本课程高度聚焦，形式语言和编译中的许多主题都超出了其范围。如果你对编译和计算语言学感兴趣，那么现在我们已经为你打下了坚实的基础，你可以考虑选修编译课程或购买相关书籍进行深入学习。
为何不使用自动化工具？
以下是关于为何在本课程中手动构建词法分析器和解析器，而非使用自动化工具的说明。
Lex和Yacc是两个来自Unix世界的软件工具，如今已有许多不同名称和风格的版本，并用多种编程语言实现。
-
Lex代表“词法分析器生成器”，指能够自动生成词法分析代码的工具。 -
Yacc代表“又一个编译器编译器”，指能够自动生成语法解析代码的工具。
它们通常一起使用。这些工具的出现是因为许多优秀的程序员都“懒惰”（褒义），他们寻求自动化一切可以自动化的东西。你可能已经注意到，我们在整个模块中概述的解析逻辑（作为开发解析器的“配方”）是高度结构化的。我们建议为Jack语法中的每个产生式规则，在语法分析器中开发一个对应的解析方法，所有这些方法共同构成了分析器。
事实证明，这种开发策略如此结构化，以至于确实可以推广到其他语法并实现自动化。换句话说，如果你有一个定义良好的语言（或某种文件格式）的语法，并且可以用某种约定的机器可读格式来指定它，那么你确实可以编写一个程序，将该语法规范作为输入，并自动生成用C、Java等语言编写的语法分析器。当然，你可能需要进入生成的代码中进行各种修改，但大部分逻辑都可以由Lex和Yacc这类工具自动生成。
那么，回到问题本身：为什么我们坚持要从零开始开发词法分析器和解析器？事实上，我们本可以使用这些自动化工具让事情变得更简单。答案在于本课程的精神——“从第一性原理出发构建”。使用像Lex和Yacc这样的黑盒工具违背了这种精神，因此我们决定不使用它们。
总结
本节课中我们一起学习了编译器构建第一部分的收尾视角。我们探讨了错误处理的重要性与复杂性，了解了自顶向下解析技术的适用场景与局限，并明白了本课程选择手动实现而非依赖自动化工具（如Lex和Yacc）的教学初衷。这为我们进入下一个模块——代码生成——做好了准备。
055：代码生成概述 🧠
在本节课中，我们将要学习编译器的代码生成组件。我们将探讨如何将高级语言程序转换为虚拟机代码，并理解这一过程背后的核心原理。
课程概述
大多数高级程序员倾向于将编译器视为理所当然的工具。他们编写程序，将编译器应用于源代码，然后观察代码如何被翻译成机器语言。他们看不到实际的过程，只看到结果。实际上，他们甚至看不到结果，他们只是执行它，然后继续调试源代码。
这种无知的幸福状态是可以接受的。然而，将程序从高级语言翻译成机器代码无异于一种魔法。如果你不想理解这种魔法，那么你将错失两个重要的好处。首先，你将无法欣赏编写编译器时所涉及的算法和技术的美丽与智慧。其次，你将失去成为一个更称职的高级程序员的机会，因为在编写编译器的过程中，你将获得许多非常重要的能力，这些能力远远超出了为高级语言编写编译器的狭隘范畴。
编译器整体路线图
我们的目标是编写一个编译器，将Jack语言的程序翻译成机器语言。在本课程中，我们决定编写一个两层编译器，就像Java和C#的编译器一样。因此，我们不是直接翻译成机器代码，而是先将Jack翻译成VM代码，然后通过一个VM翻译器进一步翻译成机器语言。
好消息是，VM翻译器已经在之前的两个模块中完成了。所以现在，我们“只需要”编写一个将高级语言翻译成VM代码的编译器。
我们决定将这个编译器的构建分为两个定义明确的模块：语法分析器和代码生成器。语法分析器是我们在之前的模块中已经开发的部分。为了测试它，我们决定让语法分析器输出XML代码而不是VM代码。这个练习的目的是验证分析器能够理解源代码，理解命令的语法结构，并能通过生成可读的XML代码来展示这种理解。
在本项目中，XML代码不再相关。因为在本模块中，我们将专注于代码生成器，它将翻译成VM代码。因此，我们将专注于分析器和代码生成器模块。我们将重写分析器中负责生成代码的某些部分，并编写更多的代码生成能力。最终结果将是一个能够从Jack程序一直翻译到VM代码的编译器。
因此，我们的目标是开发一个全功能的编译器，或者更准确地说，是将我们之前编写的编译器扩展为一个全功能的编译器。我们将把之前拥有的编译引擎从生成被动的XML代码，转变为生成可执行的VM代码。这就是我们的目标，也是我们将要采取的方法。
编译过程的简化观察
当我们谈论程序编译时，我们指的是一个高级的、面向对象的语言——Jack语言。以下是一个你之前见过的代码段示例，它旨在操作二维空间中的一些点。如果你编译并执行这段代码，你最终会在屏幕上看到一些漂亮的结果。正如我们之前讨论的，为了使这段代码正常工作，它必须与另一个提供点功能的类文件（即Point类文件）进行交互。
当你着手开发像编译器这样复杂的东西时，尽可能地简化问题总是有帮助的。因此，我将提出一些简化的观察。
第一个观察是：每个类文件都是单独编译的。
每个Jack类文件，就像每个Java类文件一样，都是一个独立且自包含的编译单元。因此，编译多类程序的整体任务被简化为一次编译一个类的更有限的任务。
第二个观察是：类内部的编译可以进一步分解。
以下是一个Point类的示例。这里列出了一些类级别的声明语句，然后是Point类的所有方法或子程序。由于空间有限，我没有列出所有子程序的代码，只列出了它们的签名，除了一个名为distance的子程序，我展示了其完整代码。
类由两个主要模块组成。首先，我们有一些定义类和一些类级别变量的前导代码。然后，我们有零个或多个子程序代码声明。在这个类中，这里是类级别的代码，这里是一个特定子程序的代码示例。
因此，简化的假设是：编译可以再次被视为两个独立的过程。首先编译我们在顶部看到的类级别代码，然后一次编译一个子程序。在很大程度上，这两个编译任务是相对独立和自包含的。因此，为一个多类程序编写编译器这一整体且艰巨的任务，再次被简化为一次编译一个子程序。
因此，事情再次被局部化，我们将采用一种非常模块化的策略，并且像往常一样，我们将一步一步地进行。
编译子程序面临的挑战
当你编译子程序时，你会看到变量、表达式、if、while等语句，你还可以看到对象，显然，你也会看到数组。因此，我们将要处理的编译挑战就是屏幕上看到的这些内容。这些挑战也构成了本模块后续单元的内容目录，每个单元将依次处理其中一个挑战。
处理这些挑战的任务是：使用VM命令生成能够捕捉变量、表达式等语义的VM代码。这不是一项简单的任务，因为当今的高级语言（包括Jack）非常复杂。它们提供了所有这些花哨的控制结构、对象和数组。然而，目标语言——VM语言——却非常简单和有限。它只有push、pop命令和少数其他命令，仅此而已。
因此，我们面临着弥合高级语言和VM代码之间差距的挑战。我们必须以某种方式，使用非常有限的VM语言来表达你在这里看到的非常丰富的语义。但正如你将看到的，我们将以一种令人惊讶的优雅且相对简单的方式来完成它。
本模块的学习收获
在结束本模块之前，我想列出你将从中获得的一些经验教训。
首先，你将学习编程语言的工作原理。
你将学习如何实现一个简单的过程式语言，如C。因为你将知道如何处理变量、表达式、控制流。你还将学习如何在低级层面处理数组和对象。通过这样做，你将再次对行业工具有非常深入的理解。
其次，你将学习一些通用的技术，这些技术可以应用于许多其他问题和应用。
你将加强对解析的理解（这是我们在上一个模块中广泛讨论的内容），你将理解递归编译是如何工作的，你将学习如何生成代码，如何创建和使用符号表，并且你将开始学习如何巧妙地管理内存（这将在我们讨论本课程最后一个模块的操作系统时再次涉及）。
所有这些好处都将在当前模块中出现。
总结
在本节课中，我们一起学习了编译器代码生成组件的概述。我们探讨了编译器的整体路线图，理解了将高级Jack语言编译为VM代码的两层架构。我们通过将编译任务分解为独立的类编译和子程序编译来简化问题。我们还明确了在编译子程序时将面临的核心挑战：即用简单有限的VM语言去表达复杂的高级语言语义，如变量、表达式、控制流、对象和数组。最后，我们展望了学习本模块将带来的收获，包括深入理解编程语言的工作原理和掌握一系列通用的软件工程技术。
接下来的单元，我们将从处理变量开始，逐一攻克这些挑战。
056：处理变量 🧩
在本节课中，我们将学习编译器如何识别和处理高级语言中的变量。我们将重点介绍符号表的概念及其在代码生成过程中的关键作用。
概述
编译器在将高级语言代码（如Jack语言）转换为虚拟机（VM）代码时，必须能够识别和处理程序中出现的所有变量。这包括确定每个变量的类型、种类（如字段、静态、局部、参数）和作用域。为了实现这一点，编译器使用一种称为“符号表”的数据结构来存储和管理所有变量的信息。
上一节我们介绍了编译器的整体架构，本节中我们来看看如何处理变量这一核心任务。
变量与代码生成
让我们从一个高级语言表达式开始。例如，表达式 sum + x * rate 包含了三个变量：sum、x 和 rate。
代码生成器的任务是将这个表达式翻译成VM指令流。一个可能的翻译结果如下：
push sum
push x
push rate
multiply
add
这些指令会计算表达式的值，并将结果置于栈顶。然而，VM语言本身没有“sum”、“x”、“rate”这样的符号变量，它只有像 local、argument、this、that 这样的虚拟内存段。
因此，为了完成翻译，编译器必须知道每个符号变量对应哪个虚拟内存段及其索引。这需要关于每个变量的详细信息。
变量的属性
在Jack语言中，每个变量都有四个关键属性：
-
名称：一个标识符。
-
类型：可以是三种基本类型（
int、char、boolean）之一，也可以是程序中定义的任何类名。 -
种类：指明变量在程序中的角色，有四种可能：
field（字段）、static（静态）、local（局部）、argument（参数）。 -
作用域：变量被识别的代码区域。在Jack中只有两种作用域：类级（在整个类中有效）和子程序级（仅在当前子程序中有效）。
为了管理这些信息，编译器使用符号表。
符号表示例
考虑以下Jack代码片段：
class Point {
field int x, y; // 类级变量：字段
static int pointCount; // 类级变量：静态
method int distance(Point other) { // 子程序
var int dx, dy; // 子程序级变量：局部
let dx = x - other.getX();
...
}
}
以下是管理这些变量所需的符号表。
类级符号表（Point类）：
| 名称 | 类型 | 种类 | 编号 |
| :— | :— | :— | :— |
| x | int | field | 0 |
| y | int | field | 1 |
| pointCount | int | static | 0 |
子程序级符号表（distance方法）：
| 名称 | 类型 | 种类 | 编号 |
| :— | :— | :— | :— |
| this | Point | argument | 0 |
| other | Point | argument | 1 |
| dx | int | local | 0 |
| dy | int | local | 1 |
请注意，对于方法（method），符号表的第一个条目总是隐式的 this 参数，它代表当前对象，类型是所属的类名（此处为Point），并且总是作为argument 0传递。
符号表的管理与使用
编译器在分析源代码时，会创建和维护这些符号表。
当遇到变量声明时（如 field int x; 或 var int dx;），编译器会：
-
提取变量的名称、类型和种类。
-
根据变量的种类，将其信息添加到相应的符号表中（类级或子程序级）。
-
不生成任何VM代码，仅更新符号表。
当在表达式或语句中使用变量时（如 x - other.getX()），编译器需要生成访问该变量的VM代码（例如 push this 0）。为此，它执行变量查找：
-
首先在当前子程序的符号表中查找变量名。
-
如果未找到，则在类级符号表中查找。
-
如果仍未找到，则报错（变量未定义）。
例如，在表达式 dx = x - other.getX() 中：
-
dx是局部变量，会在子程序符号表中立即找到。 -
x是字段变量，不会在子程序符号表中找到，但会在类级符号表中找到。
扩展到更复杂的语言特性
我们讨论的符号表机制可以轻松扩展到处理更复杂的语言特性。
更多的变量类型和种类：例如，Java有8种基本数据类型。我们的符号表只需在“类型”列中容纳这些类型即可，机制不变。
嵌套作用域：像Java这样的语言允许在代码块（由花括号 {} 定义）内创建新的作用域。这可以通过符号表链表来处理。
-
链表头部是当前最内层作用域的符号表。
-
查找变量时，从链表头部开始，依次在每个符号表中查找，直到找到或遍历完整个链表（最后是类级符号表）。
-
这种结构自然地实现了“内层作用域遮蔽外层作用域同名变量”的规则。
虽然在Jack语言中只有两级作用域，无需链表，但了解这种通用机制对理解编译器设计很有帮助。
总结
本节课中我们一起学习了编译器处理变量的核心机制。我们了解到，通过构建和维护类级与子程序级的符号表，编译器可以记录每个变量的名称、类型、种类和编号。在生成代码时，通过查找这些符号表，编译器能将高级语言中的符号变量准确映射到虚拟机语言的虚拟内存段指令上。这种基于符号表的方法，是连接高级语言抽象与底层虚拟机执行的关键桥梁。
掌握了变量的处理方法后，我们就可以继续前进，探讨编译器如何分析和翻译更复杂的程序结构，例如表达式和语句。
057：处理表达式 🧮
在本节课中，我们将详细探讨编译器如何处理表达式。我们将学习如何将高级编程语言中的表达式（使用中缀表示法）系统地转换为虚拟机（VM）的栈机器代码（使用后缀表示法）。
从语法到代码生成
上一单元我们讨论了变量的处理。这些变量通常出现在表达式的上下文中。当时我们简要提及了将这些表达式转换为虚拟机代码的过程。在本单元中，我们将深入探讨这一转换的细节。
首先，让我们回顾一下Jack语言中定义表达式的语法子集。根据课程配套书籍中的语法定义，一个表达式可以是一个项，或者一个项后跟一个运算符和另一个项。
例如：
-
5 是一个整数常量，根据语法，它是一个项，因此也是一个表达式。
-
x 是一个变量名，同样是一个项，因此也是一个表达式。
-
x + 5 符合“项 + 运算符 + 项”的模式，因此也是一个合法的表达式。
我们可以构造出无限多、高度复杂的表达式。作为编译器编写者，我们面临的问题是：如何系统地将这些多样化的表达式（从简单的 5 或 x 到复杂的组合）映射到虚拟机指令上？
表达式表示法：中缀、前缀与后缀
要理解转换过程，我们需要引入解析树的概念。以简单表达式 A * B + C 为例，其解析树描述了表达式的语义结构。
我们通常将表达式写成 A * B + C 的形式，这种表示法称为中缀表示法，因为运算符位于两个操作数之间。这种表示法对人类来说很直观，因为我们在小学就被这样教导。
然而，这种表示法并非唯一。我们也可以使用前缀表示法（例如 + * A B C），将运算符放在操作数之前。它也被称为函数式表示法，因为函数调用就是这种形式（函数名在前，参数在后）。
更重要的是，我们还有后缀表示法（例如 A B * C +），它先列出操作数，然后列出要应用的运算符。后缀表示法与我们的栈机器语言密切相关，因为虚拟机语言本身就是后缀形式的。例如，要计算 A + B，我们执行 push A, push B, add。
我们的源语言（如Jack、Java、Python）使用中缀表示法，而目标虚拟机语言使用后缀表示法。因此，编译器的核心任务之一就是将中缀表达式转换为后缀表达式。
转换策略：通过解析树生成代码
一种直观的转换方法是：
-
从源代码（中缀）生成解析树。
-
按照特定顺序（如深度优先遍历）访问解析树的每个节点。
-
在访问过程中，生成对应的虚拟机代码。
例如，对于表达式 x + 2 * y，其解析树根节点是 +，左子树是 x，右子树是 *（其左子树是 2，右子树是 y）。深度优先遍历会依次访问 x、2、y、*、+，从而生成代码：push x, push 2, push y, call Math.multiply, add。
然而，为整个程序构建完整的解析树可能非常庞大和低效。幸运的是，存在一种替代方法，可以在不显式构建整个解析树的情况下，动态生成代码。
递归代码生成算法
我们将使用一个优雅的递归算法 codeWrite 来动态生成代码。该算法接收一个表达式并生成对应的虚拟机代码。其核心逻辑如下：
以下是该算法的伪代码描述：
function codeWrite(expression):
if expression is a number (e.g., 5):
output "push constant 5"
else if expression is a variable (e.g., x):
// 根据符号表确定变量段
output "push [segment] [index]"
else if expression is of form "expr1 op expr2" (e.g., x + y):
codeWrite(expr1)
codeWrite(expr2)
output VM command for `op` (e.g., "add")
else if expression is of form "op expr" (unary, e.g., -z):
codeWrite(expr)
output VM command for unary `op` (e.g., "neg")
else if expression is a function call (e.g., f(2, y, -z)):
codeWrite(argument1) // e.g., 2
codeWrite(argument2) // e.g., y
codeWrite(argument3) // e.g., -z
output "call f [argumentCount]"
这个算法不仅捕获了输入表达式的语义，还确保了在运行时，表达式的计算结果会被放置在栈顶。
从语法分析到代码生成
在之前的项目中，我们编写的是语法分析器，它接收类似 let x = a + b - c; 的源代码，并输出描述其结构的XML标签。例如，它会将表达式扁平化地标记为 <term>a</term><symbol>+</symbol><term>b</term><symbol>-</symbol><term>c</term>。
在当前项目中，我们不再生成XML。相反，我们利用语法分析器识别出的结构，直接调用类似 codeWrite 的算法来生成可执行的虚拟机代码。虽然编译器程序的整体API和结构仍然适用，但生成XML的部分需要被替换为生成虚拟机指令的逻辑。
运算符优先级与括号
现在，让我们关注一个重要的细节：运算符优先级。考虑表达式 a + b * c。根据我们上面的递归算法（严格从左到右处理），可能会生成先计算 a + b，再与 c 相乘的代码。然而，在标准数学中，乘法 (*) 的优先级高于加法 (+)，因此正确的结果应该是先计算 b * c，再与 a 相加。
这里有一个关键点：Jack语言规范本身没有定义运算符优先级。这意味着，对于没有括号的表达式 a + b * c，编译器生成上述两种代码版本中的任何一种在语言层面都是“正确”的。运算符优先级的处理方式成为了编译器实现的一部分，由编译器作者决定。
那么，如何让程序员表达他们想要的运算顺序呢？答案是通过括号。括号是Jack语言的一部分，编译器必须尊重括号所指定的优先级。对于表达式 a + (b * c)，编译器必须生成先计算 b * c 的代码。我们的 codeWrite 算法在处理括号时，会自然地优先处理括号内的子表达式，从而生成符合数学直觉的正确代码。
本节课中，我们一起学习了表达式处理的完整流程。我们了解了中缀、前缀和后缀表示法的区别，以及它们与栈机器的关系。我们掌握了一个强大的递归算法，能够将任何复杂度的中缀表达式动态转换为正确的虚拟机后缀代码。最后，我们讨论了Jack语言中运算符优先级的特殊性，并明确了括号在控制运算顺序中的关键作用。这些知识为我们接下来处理程序的控制流结构打下了坚实的基础。
058：处理控制流 🚦
在本节课中，我们将要学习如何将高级语言中的控制流语句（如 if 和 while）翻译成虚拟机语言。这是编译器构建过程中的一个核心挑战。
概述
控制流语句决定了程序的执行路径。在 Jack 语言中，主要有五种语句：let、while、if、return 和 do。其中，while 和 if 语句的翻译最具挑战性，因为它们涉及条件判断和代码跳转。我们将重点探讨如何利用虚拟机语言中的三个分支命令——label、goto 和 if-goto——来实现这些控制流结构。
处理 if 语句
上一节我们介绍了控制流翻译的总体挑战，本节中我们来看看如何具体处理 if 语句。
if 语句在 Jack 语言中的通用结构如下：
if (expression) {
// statements 1
} else {
// statements 2
}
为了生成代码，我们首先在概念上将其转换为一个流程图。关键步骤是将条件表达式的结果取反。这样，代码生成会变得更简单、更紧凑。
以下是生成虚拟机代码的步骤：
-
生成计算表达式值的代码，结果被推入栈顶。
-
使用
if-goto命令：如果栈顶值（表达式结果）为true（非零），则跳转到标签L1。 -
使用
goto命令：无条件跳转到标签L2。 -
在代码流中插入标签
L1，后面跟随else分支的语句代码。 -
在代码流中插入标签
L2，后面跟随if分支结束后的代码。
编译器会自动生成这些唯一的标签（如 L1、L2），确保整个翻译过程是确定性的。
处理 while 语句
理解了 if 语句的翻译后，我们再来看看 while 循环的处理。它在某种程度上比 if 更简单。
while 语句的通用结构是：
while (expression) {
// statements
}
我们同样可以为其构建一个流程图：首先对表达式求值并取反，如果结果为 true，则跳出循环；如果为 false，则进入循环体执行语句，执行完毕后跳回开头重新评估表达式。
生成的虚拟机代码如下：
-
插入一个标签，例如
L1，作为循环的入口点。 -
生成计算表达式值的代码。
-
对结果取反，使用
if-goto L2：如果结果为true，则跳转到L2（循环结束）。 -
生成循环体内语句的代码。
-
使用
goto L1跳回循环开始处，重新评估条件。 -
插入标签
L2，标记循环结束后的位置。
同样，所有标签都由编译器自动生成和管理。
处理复杂情况
我们已经掌握了单个 if 和 while 语句的翻译。然而，实际程序要复杂得多，我们需要考虑两个额外的细节。
1. 生成唯一标签
一个程序通常包含多个控制流语句。编译器必须确保为每个语句生成的标签是全局唯一的，避免跳转目标冲突。这可以通过使用递增的计数器（如 L1， L2， L3…）或结合作用域信息来轻松实现。
2. 支持嵌套结构
控制流语句可以相互嵌套，例如 while 循环内部包含 if 语句，if 语句内部又包含另一个 while 循环，形成“望远镜”式的代码结构。
幸运的是，我们之前设计的编译器采用了高度递归的编译策略。这意味着编译一个语句时，如果其内部包含其他语句，编译器会自然地递归调用自身来处理它们。因此，嵌套结构的支持是内置的，无需额外处理。
能力总结与反思
到目前为止，我们已经掌握了编译一个简单过程式语言所需的核心技术：
-
处理变量：在模块的第一个单元中已介绍。
-
处理表达式：通过代码生成器算法实现。
-
处理控制流：即本节课所学内容。
综合这些能力，我们已经可以为类似 C 语言子集的简单语言编写一个功能完整的编译器。这是一个值得骄傲的成就。
然而，我们也需要认识到以下几点：
-
我们开发的编译器只翻译到虚拟机语言这一中间层，而非直接到机器语言。这缩短了编译器需要跨越的“距离”。
-
编译过程之所以如此优雅和易于管理，很大程度上得益于我们之前建立的虚拟机抽象层。编译器编写者只需生成
push、pop、label、goto等虚拟机命令，而无需关心它们底层是如何实现的，因为这些已在之前的项目和模块中完成。
这充分体现了模块化软件工程的巨大优势：通过分层和抽象，复杂系统的构建变得可控、清晰且高效。
总结
本节课中我们一起学习了如何将高级语言中的 if 和 while 控制流语句翻译成虚拟机代码。我们掌握了其通用的代码生成模式，并讨论了如何处理多语句和嵌套语句的复杂情况。至此，我们已具备了构建一个简单编译器所需的主要技术组件。在下一单元，我们将进入一个更有趣的领域：学习如何处理面向对象代码中对象的创建与操作。
059：底层实现 🖥️
在本节课中，我们将学习编译器如何生成用于处理对象的代码。在深入讨论代码本身之前，我们先了解一些使用虚拟机命令进行数据处理的底层细节。
概述
上一节我们介绍了高级编程与底层实现之间的鸿沟。本节中，我们来看看如何利用虚拟机架构来支持对象和数组数据的表示与访问。
从高级抽象到底层实现
当你编写高级面向对象程序时，可以奢侈地思考各种抽象概念，例如二维点对象。这些对象在像Jack或Java这类对程序员友好的语言中实现，允许你像数学家一样思考这些点及其代数运算。
然而，如果被迫使用中间虚拟机语言编写相同代码，你将无法享受对象和方法的便利。相反，你将面对一个简化的虚拟机世界观，它只包含八个虚拟内存段。所有高级操作都必须通过这些虚拟内存段以及push、pop等虚拟机命令来完成。
最后，如果被迫使用机器语言完成所有工作，限制会更多。对象和数组的概念将完全失去意义，你将直接操作RAM。
幸运的是，我们有编译器来自动处理所有这些麻烦，生成必要的底层和中间代码。编译器的目的就是弥合这些鸿沟，让我们能够专注于高级编程，而由编译器负责在更简单、更原始的语言中表达相同语义的所有细节。
在本课程中，我们已经处理过虚拟机翻译器。你在项目7和8中编写了虚拟机翻译器，因此现在我们可以只专注于编译阶段。
虚拟机代码基础
考虑到这一点，我们必须编写虚拟机代码，或者更准确地说，我们必须编写一个能生成虚拟机代码的编译器。
让我提醒你，在虚拟机程序中，如果我们想操作这八个内存段，必须使用push和pop命令，并且必须指定操作哪个段以及段内的哪个条目。例如：
push local 3
pop static 2
最终，我们在虚拟机级别所做的一切都将简化为对RAM的操作。虚拟机实现通过一种特定的方式看待RAM来处理这种映射。
首先，RAM的前五个字被用作非常重要的指针，它们保存着：
-
栈指针的当前值
-
局部段的基础地址
-
参数段的基础地址
-
this指针 -
that指针
所有这些段都属于当前正在运行的虚拟机函数。此外，虚拟机实现还会在RAM上分配一个特定区域来保存全局栈。这个栈不仅保存当前运行函数的运行栈，还保存调用链上等待当前函数终止的所有函数的运行栈和内存段。
支持局部变量和参数变量
以下是关于这种架构如何支持局部变量和参数变量概念的说明。
局部变量和参数变量存储在栈上，并由虚拟机实现管理。就虚拟机代码而言，我们可以分别使用local和argument段来访问它们。虚拟机实现通过LCL和ARG这两个指针在栈上记录这些段的位置。例如，虚拟机实现将局部段放在栈的某个区域，并将该段的基础地址记录在LCL指针中，对参数段也做同样处理。
表示对象和数组数据
接下来，我们看看如何使用相同的架构来表示对象和数组数据。
这里的情况类似但稍微复杂一些。首先，我们使用RAM上一个完全不同的区域，称为堆。在堆上，我们记录当前程序要操作的所有对象和数组的数据。
在一个面向对象的应用程序中，你可能拥有许多对象和数组来实现计算机游戏、金融应用或其他任何程序。你可能需要同时管理数十、数百、数千甚至数百万个对象。
因此，与局部段和参数段（每个只有一个）不同，我们可能在堆上有许多对象。在使用this段访问对象之前，我们必须以某种方式告诉系统“this”指的是哪个对象。
this和that位置的实现首先通过使用this和that指针来处理，就像我们对局部变量和参数所做的那样。然而，在使用this和that这两个段之前，我们必须先使用pointer段来告诉系统我们希望将this和that指向RAM上的哪个位置。
你可能会问，为什么我们必须以这种方式使用pointer段？这是由架构设计决定的，我们需要提供一种机制来将this和that锚定到代码需要操作的特定对象和数组上，为此我们使用了这个虚拟的pointer段。
一个具体示例
我敢打赌，我刚才说的一些话听起来有点晦涩难懂。我认为下面的例子将澄清一切。
假设我们希望访问RAM地址8000、8001、8002等处的字，因为它们代表一个特定的对象或数组，或者存储了特定对象或数组的数据。我们该怎么做呢？
我想向你展示实现它所需的命令序列。对于每个命令，我将讨论命令本身以及虚拟机实现对该命令的处理。
首先，我们必须将this段锚定到所需的地址（8000）。我们通过以下命令实现：
push constant 8000
pop pointer 0
响应这两个命令，虚拟机实现会将this指针设置为8000，从而得到我们想要的效果。顺便说一句，如果你完成了项目7和8，你应该不会对此感到惊讶，因为你实际上已经实现了这些虚拟机命令的具体实现。
一旦你将this指针设置为特定地址，this段就可以被使用，就好像它镜像或锚定在RAM的8000地址上一样。
因此，从现在开始，给定我们有了这个所需的映射，我可以愉快地使用像push this 0这样的命令。push this 0会做什么？它会获取当前位于RAM[8000]的值，并将其压入栈中。而pop this 0则会从栈中取出一个值，并将其放入RAM[8000]。
我们使用this段来做到这一点。我们可以对this的任何其他索引做完全相同的事情，例如this 1、this 2、this 3、this i。为了访问第i个字，我们将8000和i相加，并利用这里的抽象来精确指向RAM中我们想要的字。
请注意，虚拟机程序并不知道所有这些段在RAM上的具体位置。它只使用this段，而虚拟机实现在后台处理所有其他细节。
访问RAM的具体步骤
这里有一个具体的例子。假设你想将RAM[8000]设置为17。我们该怎么做？
以下是实现步骤：
-
锚定指针：首先，我们需要将
this指针指向地址8000。push constant 8000 pop pointer 0 -
设置值：然后，我们将值17压入栈，并弹出到
this段的第0个位置。push constant 17 pop this 0这将在虚拟的
this段中放入数字17，实际上它会将其放入RAM位置8000。
我刚才在这里展示的技术是使用虚拟机命令访问RAM中特定位置的通用方法。这就是我们处理对象数据的方式，也是我们以非常类似的方式处理数组数据的方法（我们将在课程后面讨论）。
总结
本节课中，我们一起学习了虚拟机层面处理对象和数组数据的底层机制。
-
对象数据通过虚拟机命令使用
this段访问。 -
数组数据通过虚拟机命令使用
that段访问。 -
在这两种情况下，我们都需要先编写一些虚拟机代码，将
this和that（或其中之一）锚定到RAM中的所需位置。我们使用虚拟的pointer段来实现这一点，它只有两个条目（0和1），0用于正确设置this段，1用于设置that段。
有了这些关于使用虚拟机命令进行底层数据处理的背景知识，我们现在具备了继续讨论如何编写处理对象构造的虚拟机代码所需的基础。
060：构造 🏗️
在本节课中，我们将学习如何编写虚拟机（VM）代码来处理对象的构造过程。我们将从调用者的视角和构造函数本身的视角，分别探讨如何生成相应的VM指令。
概述
对象构造是一个两阶段的过程，涉及编译时和运行时。编译时，编译器处理变量声明并更新符号表。运行时，构造函数被调用，在堆上分配内存并初始化对象。我们将学习如何为这两个阶段生成正确的VM代码。
从调用者视角编译对象构造
上一节我们介绍了如何访问堆上的特定区域。本节中，我们来看看如何从调用者的角度编译创建对象的代码。
当高级语言（如Java）中声明一个对象变量时，例如 var point P1;，编译器不会生成任何VM指令。它只会在当前子程序的符号表中记录这个变量，并将其在栈上对应的位置初始化为0。
当调用构造函数时，例如 P1 = Point.new(2, 3);，编译器需要生成调用代码。这个过程与调用普通子程序类似。
以下是处理此类调用的步骤：
-
将构造函数的参数（例如2和3）压入栈。
-
使用
call Point.new指令调用构造函数。 -
构造函数执行完毕后，会将其新创建对象的基地址作为返回值留在栈顶。
-
调用者代码使用
pop指令将这个地址存入之前为P1变量分配的位置（例如pop local 0）。
这样，P1 变量就指向了堆上新创建的对象。
从构造函数视角编译对象构造
现在，我们知道了如何生成调用构造函数的代码。接下来，我们探讨如何编译构造函数本身的VM代码。
构造函数的主要任务有两个：
-
在堆上为新对象分配内存空间。
-
初始化新对象的字段。
为了访问和操作对象的字段，我们需要使用 this 虚拟段。在构造函数开始执行时，this 段尚未指向有效的对象内存。
以下是编译一个构造函数（例如 constructor Point new(int x, int y)）的步骤：
-
分配内存：编译器首先查询类的符号表，确定对象需要多少字（word）的内存（例如，
Point类需要2个字存储x和y）。然后，它生成代码调用操作系统的Memory.alloc函数来申请一块连续的空闲内存。- 代码示例：
push constant 2后跟call Memory.alloc 1。alloc函数会将分配的内存块的基地址返回到栈顶。
- 代码示例：
-
设置
this指针：将alloc返回的基地址弹出到pointer 0。这样，this段就被锚定到了新创建的对象内存起始处。- 公式/代码：
pop pointer 0
- 公式/代码：
-
初始化字段：现在可以通过
this段来访问对象字段。将传入的参数（如x和y）赋值给对象的对应字段。- 代码示例：
push argument 0然后pop this 0（设置x）；push argument 1然后pop this 1（设置y）。
- 代码示例：
-
返回对象引用：根据语言规范，构造函数必须返回新对象的引用。由于
pointer 0正持有这个基地址，只需将其压入栈并返回即可。- 代码示例：
push pointer 0后跟return。
- 代码示例：
完成这些步骤后，控制权返回给调用者，调用者如前所述，将返回的地址存入目标变量。
总结
本节课中我们一起学习了对象构造的完整编译过程。
-
从调用者视角，构造被编译为：压入参数、调用构造函数、接收返回的对象地址并存储。
-
从构造函数视角，构造被编译为：使用
Memory.alloc分配内存、用返回地址设置this指针、初始化对象字段、最后返回this指针的值。
理解这个两阶段的协作过程（调用者准备、构造函数执行并返回结果）是处理面向对象编程中对象生命周期的关键。掌握了对象构造的编译方法后，我们就可以继续学习如何操作已构造好的对象。
061：操作
在本节课中，我们将学习如何编译面向对象代码中的方法调用和方法本身。我们将看到，编译器如何将高级的、面向对象的语法（如 p1.distance(p2)）转换为底层的、过程式的虚拟机指令。
概述
上一节我们介绍了对象的构造，本节中我们来看看如何操作对象。对象操作主要涉及两方面：首先，我们需要知道如何编译调用方法的客户端代码；其次，我们需要讨论如何编译方法本身的代码。
方法调用的编译
当我们在高级语言中调用一个对象的方法时，例如 p1.distance(p2)，其语法遵循面向对象哲学：先指定要操作的对象，再指定方法名，最后提供参数。然而，底层的虚拟机语言并不理解对象。因此，编译器的核心挑战是将这种面向对象的表达方式转换为过程式的表达方式。
以下是通用的转换技术：
-
将方法调用所操作的对象作为第一个隐式参数压入栈。
-
将方法调用中显式提供的所有参数压入栈。
-
调用对应的方法。
以 p1.distance(p2) 为例，其编译后的核心逻辑是：
push p1 // 将对象 p1（即其基地址）作为第一个参数
push p2 // 将显式参数 p2 作为第二个参数
call Point.distance // 调用方法
这里“推送对象”实际上是指推送该对象在内存中的基地址，该地址存储在对应的变量（如 p1）中。
方法本身的编译
现在，让我们将注意力转向方法本身的编译，以 Point 类中的 distance 方法为例。方法被设计为操作当前对象（在大多数语言中用 this 关键字表示）。为了访问当前对象的字段（如 x, y），我们需要正确地设置 this 指针。
以下是编译一个方法（如 distance）的关键步骤：
-
建立符号表：编译方法声明和局部变量声明时，不生成实际代码，而是创建子程序级的符号表，记录
this（作为参数0）和所有参数、局部变量。 -
锚定 this 指针：生成代码，将传入的当前对象的地址（即参数0）设置到
pointer 0，从而让this段指向正确的内存位置。push argument 0 pop pointer 0 -
编译方法体：根据符号表，使用
this 0,this 1等访问对象字段，使用argument 1,local 0等访问参数和局部变量，并生成对应的运算指令。 -
返回值处理：方法结束时，必须通过
return命令返回一个值。对于有返回值的方法，返回值应位于栈顶。
处理 Void 方法
Void 方法（不返回值的方法）的编译与普通方法类似，但有一个重要区别：根据虚拟机规范，所有被调用的子程序都必须返回一个值。
因此，编译 void 方法时：
-
在方法结尾，我们需要推送一个虚拟值（例如
push constant 0），然后执行return。// 在 void 方法（如 print）的结尾 push constant 0 // 推送一个虚拟返回值 return -
在调用方，编译器必须生成额外的指令来清理这个无用的返回值，以保持栈的整洁。
call Point.print // 调用 void 方法 pop temp 0 // 丢弃无用的返回值
这是一个约定：void 方法返回一个虚拟值，而调用方负责将其从栈中弹出。
总结
本节课中我们一起学习了对象操作的核心编译技术。我们了解到，编译器通过将对象作为隐式首参数传递，将面向对象的方法调用桥接到了过程式的底层。在编译方法时，关键步骤是锚定 this 指针以访问对象字段。此外，无论是普通方法还是 void 方法，都必须遵守底层的返回值约定。掌握了这些，你就理解了计算机在幕后如何处理对象，为我们接下来学习数组的处理打下了基础。
062：处理数组 🧩
在本单元中，我们将学习编译器如何为数组的声明和操作生成代码。我们将从数组的构造开始，然后深入探讨如何访问和操作数组元素。
数组构造 🏗️
上一节我们介绍了对象处理，本节中我们来看看数组的构造。首先，我们回顾一下RAM的布局。
假设高级Jack程序员写下 var Array arr; 来声明一个名为 arr 的数组。编译器对此的响应非常直接。
以下是编译器处理此声明和后续构造的步骤：
-
处理声明语句：
var Array arr;这条语句本身不生成任何代码。编译器唯一要做的是更新符号表，添加一行记录，表明有一个名为arr、类型为Array的变量（例如，存储在局部变量0的位置）。 -
处理构造语句：当程序员通过
let arr = Array.new(n);构造数组时，编译器将其视为一次普通的子程序调用。我们已经知道如何为方法调用生成代码（例如，压入参数n，然后调用Array.new）。因此，这里没有新的代码生成逻辑。操作系统（后续课程会讲解）会与编译器协作，在堆中分配足够空间，并将该内存块的基地址存入变量arr（即局部变量0）中。
数组操作基础：this 与 that 指针 🧭
在深入数组操作之前，我们需要回顾VM架构中的两个关键虚拟段：this 和 that。
this 和 that 是两个特殊的指针段，它们允许我们动态地指向RAM中的任意地址，从而间接操作内存。它们的基地址分别存储在RAM位置3 (THIS) 和 4 (THAT) 中。
为了将 this 段锚定到特定地址（例如8058），我们需要使用 pointer 虚拟段。pointer 段只有两个条目：0代表 this，1代表 that。
操作步骤如下：
-
将目标地址（如8058）压入栈。
-
执行
pop pointer 0。VM实现会将此地址存入THIS指针，从而将this段对齐到地址8058。 -
此后，操作
this段（如push this 0）实际上就是在操作地址8058处的内存。
对 that 段（使用 pop pointer 1）的操作逻辑完全相同。在VM翻译器的实现约定中，我们通常用 this 来访问当前对象的字段，用 that 来访问当前数组的元素。
访问数组元素 🔍
现在，我们运用 that 指针来学习如何访问数组元素。假设数组 arr 的基地址已存储在局部变量0中，我们想将数字17存入 arr[2]（即第三个元素）。
生成VM代码的思路如下：
-
计算目标地址：将数组基地址（
arr）和索引（2）压栈，然后相加。结果就是arr[2]在RAM中的物理地址。 -
对齐
that段：将上一步计算出的地址通过pop pointer 1存入THAT指针。这样，that段就被对齐到了目标元素的位置。 -
赋值：将值17压栈，然后执行
pop that 0。这会将17存入that段的第0个位置，也就是我们想要设置的arr[2]。
对应的VM代码序列是：
push local 0 // 压入数组基地址 (arr)
push constant 2 // 压入索引 2
add // 计算 arr + 2 的地址
pop pointer 1 // 将该地址存入 THAT 指针，对齐 that 段
push constant 17// 压入要存储的值
pop that 0 // 将值存入 that 0，即 arr[2]
这里有两个重要观察：
-
我们总是操作
that 0，而不像对象字段那样使用this 0,this 1等。因为对于数组，每次访问不同索引时，我们都会重新对齐that段。 -
这段VM代码完全在虚拟的、符号化的层面运行，它不知道数组具体在RAM的哪个位置。所有物理地址的计算和映射都由底层的VM翻译器处理。这使得代码安全且与具体硬件平台无关，是实现可移植性的关键。
处理通用数组赋值语句 🛠️
上一节我们看了一个简单的例子，本节中我们来看看如何处理更通用的数组赋值语句：arr[expression1] = expression2。一个直接的生成策略可能如下：
-
计算
arr + expression1的地址并存入pointer 1。 -
计算
expression2的值。 -
将结果值弹出到
that 0。
然而，这种方法存在缺陷。考虑语句 a[i] = b[j]。如果按上述步骤：
-
计算
a+i地址并存入pointer 1。 -
计算
b+j地址。但计算b+j本身可能涉及复杂的表达式，其中可能包含对pointer 1的写入操作，这会覆盖第一步中存储的a[i]的地址，导致错误。
因此，我们需要一个更健壮的方案。以下是解决 a[i] = b[j] 的正确VM代码生成步骤：
-
计算左值地址并暂存：计算
a + i的地址，但先不存入pointer 1，而是留在栈顶。 -
计算右值：计算
b + j的地址，然后通过pop pointer 1对齐that段到b[j]。接着，使用push that 0和pop temp 0将b[j]的值存入临时变量。 -
取回左值地址并赋值：此时，栈顶仍保留着
a[i]的地址。将其通过pop pointer 1对齐that段到a[i]。最后，将临时变量中的值 (temp 0) 压栈并pop that 0，完成赋值。
这个模式可以推广到通用的 arr[exp1] = exp2 语句。以下是代码生成模板：
// 1. 计算左值地址 (arr + exp1) 并留在栈顶
push arr // 压入数组基地址
[生成计算 exp1 的代码] // 结果在栈顶
add // 栈顶现在是 arr[exp1] 的地址
// 2. 计算右值 (exp2) 并存入临时变量
[生成计算 exp2 的代码] // 结果在栈顶
pop pointer 1 // 将对齐 that 段到 exp2 结果指向的地址？(这里需要修正)
push that 0 // 取出该地址的值
pop temp 0 // 存入临时变量
// 3. 为左值地址对齐 that 段并赋值
pop pointer 1 // 将栈顶的 (arr+exp1) 地址存入 THAT 指针
push temp 0 // 压入右值
pop that 0 // 赋值给 arr[exp1]
重要修正：上述模板步骤2中，exp2 可能本身就是一个数组访问（如 b[j]），因此它计算出的就是一个地址。我们不应该直接 pop pointer 1 然后 push that 0，因为 exp2 可能就是一个简单值。正确的通用步骤是：
-
计算左地址（
arr+exp1），结果留在栈顶。 -
计算右表达式（
exp2）的值，结果压栈。 -
将右值弹出到临时变量（如
temp 0）。 -
将左地址弹出到
pointer 1以对齐that段。 -
将临时变量中的右值压栈，并弹出到
that 0。
这样，无论 exp2 是简单值、变量、还是另一个数组访问，都能正确处理。
总结 📚
本节课中我们一起学习了编译器如何处理数组。
-
我们了解到数组的声明只更新符号表，而构造则是通过普通的
new方法调用实现。 -
我们回顾了
this和that指针的机制，它们是间接操作内存的关键。 -
我们深入探讨了如何通过计算基地址加偏移、并使用
that指针来访问和赋值数组元素。 -
最后，我们分析并解决了在通用数组赋值语句
arr[exp1] = exp2中可能出现的地址覆盖问题，引入了使用临时变量的健壮代码生成模式。
掌握这些知识后，我们的编译器就具备了处理复杂数据结构——数组的能力。下一单元，我们将改变主题，讨论虚拟机标准映射的相关内容。
063：虚拟机上的标准映射 🗺️
在本单元中，我们将讨论一组约定。建议J语言编译器的开发者遵循这些约定。我们将这组约定统称为“虚拟机上的标准映射”。
概述
首先，让我们回顾一下整体架构。我们正在开发一个编译器，这个编译器是两层的。首先，我们将代码从Jack高级语言编译到虚拟机代码，然后再将虚拟机代码编译到目标平台。第二部分已在模块1和2中完成，而本模块及前一个模块则负责填补Jack语言与虚拟机之间的鸿沟。因此，出于实际目的，我们可以忽略虚拟机代码以下的所有细节，专注于将Jack程序翻译成虚拟机代码。
现在思考一下，当你编写Jack、Java或C++程序时，你会创建各种实体，例如类、函数、构造函数、方法等。然而，当你需要将这些实体翻译到虚拟机层面时，结果看起来会完全不同。在虚拟机层面，我们不知道什么是对象，也不知道什么是构造函数。我们只有栈和虚拟内存段，必须设法将每一个高级构造映射到虚拟机的现实上。如何实现这一点，我们已在本模块中讨论过。现在，我想总结并整合所有从高级语言映射到虚拟机层面时必须遵循的规则。我们通过一份称为“虚拟机平台标准映射”的文档或标准集来实现这一点。
顺便提一下，如果你想为其他语言（如Java、C++等）创建编译器，那么对于每一种语言和编译器，都需要一份不同的标准映射文档，因为每种语言都有不同的构造，尽管许多地方非常相似。在本课程中，我们专注于Jack语言，因此我们将讨论如何将Jack映射到虚拟机。
文件与子程序映射约定 📁
一个Jack程序由一个或多个类组成，每个类有唯一的名称。每一个类文件都将被翻译成一个具有相同文件名的虚拟机文件。在此过程中，源代码中的每一个子程序都将被翻译成虚拟机层面的一个函数。
因此，每个子程序对应一个函数，每个文件对应一个虚拟机文件。
请注意，一个拥有k个参数的Jack构造函数或函数，将被编译成一个同样操作k个参数的虚拟机函数。在示例中，我们看到new是一个构造函数，在Jack层面有一个参数，在虚拟机层面也将有一个参数。同样的情况也适用于函数buzz。
那么方法呢？方法的情况稍微复杂一些。一个拥有k个参数的Jack方法，将被编译成一个操作k+1个参数的虚拟机函数。在这个例子中，bar方法在Jack层面只有一个参数x，但在虚拟机层面将有两个参数。我们稍后会详细阐述这一点，实际上我们在本模块早期讨论对象操作时已经提到过。
观察图表，你会发现一个有趣的现象：子程序的类型（无论是构造函数、方法还是函数）在翻译过程中“丢失”了。因为在到达虚拟机层面时，所有内容都将被映射为函数。因此，我们必须通过某些约定来捕获构造函数、函数和方法的语义，例如刚才讨论的“方法比源代码多一个参数”的规则。关于这一点，我们后面还有更多要说的。
变量映射 🧮
在Jack语言中，我们有四种变量：局部变量、参数变量、静态变量和字段变量。每一种都有特定的处理方式。
-
局部变量：某个Jack子程序的局部变量被映射到虚拟内存段
local。例如，如果x和y是你的子程序中声明的头两个局部变量，那么x将被映射到local 0，y将被映射到local 1。后续的变量将依次映射到local 2、local 3等。 -
参数变量：处理方式完全相同。第一个参数映射到
argument 0，第二个映射到argument 1，依此类推。 -
静态变量：被映射到与当前编译文件关联的虚拟内存段
static。映射方式类似：第一个静态变量映射到static 0，第二个映射到static 1，依此类推。 -
字段变量：当前对象的字段变量处理如下。首先，我们必须假设
pointer 0已经指向了这个对象（当前子程序生成的代码会完成这件事）。如果已经完成，那么这个对象的第i个字段在虚拟机层面就映射到this i。例如，如果x是一个属性或字段，它将映射到this 0；如果y也是一个属性，它将映射到this 1，依此类推。
数组处理 📊
对于数组，我们提出以下约定。如果你试图访问任何数组条目arr[i]，你应该这样做：
-
首先，将
pointer 1设置为该条目的地址，即arr + i。 -
完成这个初始“锚定”后，你就可以通过访问
that 0来简单地访问该条目。
无论i是18还是312，你总是将pointer 1指向它，然后访问that 0。我们发现这是在编译器中处理数组最简单的方法。
编译子程序的约定 🔧
在Jack中，我们有三种子程序：方法、构造函数和函数。让我们分别讨论每一种。
编译方法
编译Jack方法时，编译器必须确保生成的代码首先将this虚拟内存段的基地址设置为argument 0。这是因为我们有一个非常重要的约定：方法的调用者会在调用该方法之前，将方法要操作的对象地址作为第一个参数压入栈。因此，当方法开始运行时，它需要操作当前对象。我们通过将this设置为argument 0的内容来实现这个抽象。一旦完成，我们就可以如前所述，将this 0、this 1、this 2等作为当前对象字段的占位符来引用，这非常方便且合理。
编译构造函数
编译构造函数时，我们首先必须在内存中为要创建的对象分配空间。完成之后，我们将这个新内存块的基地址设置为this段。通过这样做，我们再次建立了对该对象的访问，然后就可以使用this 0、this 1、this 2等来执行构造函数可能想做的任何事情。例如，构造函数通常喜欢将对象字段设置为各种初始值，现在它们可以做到了，因为我们已经建立了对新构造对象的访问。
在返回之前，请记住，构造函数的虚拟机代码还必须记得将新构造对象的基地址返回给调用者。考虑到这一点，我不确定我们是否必须在标准映射中特别说明这一点，因为在Jack层面，我们已经要求构造函数必须总是返回this。由于在Jack层面有这个要求，编译器会自动生成处理return this的代码，因此我们也不必在这里提及。不过，在这里提及这个重要约定也无妨。
编译无返回值函数/方法
无返回值函数和方法在Jack层面不返回值。然而，在虚拟机层面，它们必须返回一个值，因为这是虚拟机函数的要求。既然必须返回点什么，我们决定，如果遵循我们的标准映射，我们要求返回constant 0。顺便提一下，无返回值子程序的调用者必须记住它调用的是一个无返回值子程序，因此当子程序返回时，它要做的第一件事就是丢弃栈顶元素（即包含constant 0的那个值）。我们接下来会讨论如何处理子程序调用。
处理子程序调用的约定 📞
当我们编译一个典型的子程序调用（如subroutineName(arg1, arg2, ...)）时，调用者必须将参数压入栈，然后调用子程序。即执行push arg1、push arg2等，然后call subName。
如果这个子程序是一个方法，那么调用必须记住，它要做的第一件事是压入一个对方法要操作的对象的引用，然后才继续压入arg1、arg2等，并调用该方法。你看，一切是如何连接起来的：一旦你这样做了，从被调用方法的角度看，当前对象的地址就成为了我们之前讨论的argument 0的值。
至于调用无返回值子程序，它在Jack中不返回值，但在虚拟机层面会返回一个我们约定为constant 0的虚拟值。因此，在子程序返回后，子程序调用的编译代码必须弹出并忽略这个返回值。
处理常量 🔢
Jack中有三个常量：null、false和true。以下是它们的处理方式：
-
null和false映射到constant 0。 -
true映射到constant 1。
对于 -1，我们可以简单地生成先压入1再执行neg命令的代码，这将有效地将-1置于栈顶。
类与子程序 🏗️
基本的Jack操作系统被实现为一组八个虚拟机类，名称如Math.vm、Memory.vm等。我们将在课程的下一个（也是最后一个）模块6中详细讨论并实现这些类。所有操作系统类文件必须与编译器生成的虚拟机文件位于同一目录中。因此，在目录层面，你的应用程序文件和操作系统文件没有区别，它们都被视为一个大的虚拟机文件集合。因此，你的代码中的任何虚拟机函数都可以调用这些操作系统类中的任何虚拟机函数。
特殊操作系统服务 ⚙️
显然，如果你编写Jack编译器，必须记住以下几点：
-
乘法命令：必须通过调用
Math.multiply来处理。 -
除法命令：必须生成调用
Math.divide的代码。 -
字符串常量：使用构造函数
String.new和所需字符串的长度来创建。 -
字符串赋值：例如
x = "NAND"，这个由四个字符组成的字符串，通过四次调用String.appendChar来处理。编译器必须再次提供这种抽象。 -
对象构造：需要在RAM中为新对象分配空间。因此，在构造函数的某个地方，我们必须调用
Memory.alloc。所需的大小将根据我们要创建的对象中的字段数量推导出来。因为在Jack中一切都是16位的，所以字段数量与容纳此对象所需的RAM字数或RAM位置数量之间存在一一对应的关系。 -
对象回收：使用操作系统函数
Memory.deAlloc来处理。
以上就是Jack编译器开发者在编写针对我们虚拟机的编译器时，需要牢记在心的所有内容。
总结
在本单元中，我们一起学习了Jack语言到虚拟机的“标准映射”。我们详细探讨了如何将Jack程序中的文件、子程序（方法、构造函数、函数）、各类变量（局部、参数、静态、字段）、数组以及常量映射到虚拟机层面的对应表示。我们还了解了编译不同类型子程序时必须遵循的特定约定，以及如何处理子程序调用和利用操作系统提供的特殊服务。这些约定是构建一个正确、高效的Jack编译器的基石。在下一个单元，我们将讨论如何实际构建这个编译器，以及我们推荐遵循的API结构。
064：编译器完整实现建议方案 🛠️
在本单元中，我们将讨论如何实际构建编译器。我们将基于之前单元中介绍的标准VM映射约定，逐步讲解编译器的整体架构和实现模块。
概述
在之前的项目10中，我们编写了一个生成XML代码的语法分析器。现在，我们需要将这个软件改造为一个生成VM代码的程序，即我们的Jack编译器。我们将分步进行，并基于五个独立的模块来构建编译器的软件架构。
编译器整体架构
以下是编译器的整体架构和路线图。编译器将包含五个主要模块：Jack编译器（主程序）、Jack分词器、符号表、VM写入器和编译引擎。本单元我们将重点讨论符号表和VM写入器。
Jack编译器类
Jack编译器是驱动整个编译过程的主程序。它的用户级功能如下：如果输入是一个.jack文件，编译器将生成一个同名的.vm文件；如果输入是一个目录名，编译器将为该目录中的每个.jack文件生成一个对应的.vm文件。
对于每个源.jack文件，编译器会创建一个Jack分词器对象来处理输入，并创建一个输出的.vm文件。然后，编译器使用符号表、编译引擎和VM写入器来生成VM代码，并将其写入输出文件。
Jack分词器
Jack分词器模块在项目10中已经开发完成，我们可以直接使用，无需为完整规模的编译器进行修改。
符号表
符号表是一个新模块，用于跟踪程序中的各种符号或变量。在Jack语言中，主要有类级别的变量（字段和静态变量）和子程序级别的变量（参数和局部变量）。
符号表示例
考虑以下Point类的示例：
class Point {
static int pointCount;
field int x, y;
method int distance(Point other) {
var int dx, dy;
// ... 方法体
}
}
-
类级别符号表：跟踪
x、y（字段）和pointCount（静态变量）。这些变量在整个类中可见。 -
子程序级别符号表：跟踪
other（参数）和dx、dy（局部变量）。这些变量仅在distance方法内可见。
编译器最多只需要两个符号表：一个类级别符号表和一个子程序级别符号表。每当开始编译一个新类时，类级别符号表被初始化；每当开始编译当前类中的一个新子程序时，子程序级别符号表被重置。
符号表API
符号表类（例如用Java实现）应提供以下方法：
-
构造函数：
SymbolTable()- 创建一个新的空符号表。 -
开始子程序：
startSubroutine()- 重置子程序级别符号表，开始一个新的子程序作用域。 -
定义符号：
define(String name, String type, String kind)- 向当前作用域的符号表添加一个新符号。kind可以是STATIC、FIELD、ARG或VAR。 -
变量计数：
varCount(String kind)- 返回当前作用域中已定义的指定kind的变量数量。 -
查询方法：
-
kindOf(String name)- 返回指定名称符号的kind。 -
typeOf(String name)- 返回指定名称符号的type。 -
indexOf(String name)- 返回指定名称符号在其作用域和种类内的索引号（从0开始）。
-
实现建议
符号表抽象结构可以使用经典的数据结构哈希表来实现。我们可以使用一个哈希表表示类作用域，另一个哈希表表示子程序作用域。开始编译新的子程序时，后一个哈希表被清空重置。
一个重要提示：在编译无错误的Jack代码时，任何在子程序符号表和类符号表中都找不到的符号，必定代表一个子程序名或类名。这个提示在编写编译器时非常有用。
VM写入器
VM写入器的任务是生成VM代码并将其写入输出的.vm文件。
VM写入器API
VM写入器类应提供以下方法：
-
构造函数：
VMWriter(String outputFile)- 创建一个新的输出文件/准备写入。 -
写入Push命令：
writePush(String segment, int index)- 生成一条push segment indexVM命令。 -
写入Pop命令：
writePop(String segment, int index)- 生成一条pop segment indexVM命令。 -
写入算术命令：
writeArithmetic(String command)- 生成一条算术/逻辑VM命令，如add、sub、eq等。 -
写入标签：
writeLabel(String label)- 生成一条label labelVM命令。 -
写入Goto命令：
writeGoto(String label)- 生成一条goto labelVM命令。 -
写入If-Goto命令：
writeIf(String label)- 生成一条if-goto labelVM命令。 -
写入Call命令：
writeCall(String name, int nArgs)- 生成一条call name nArgsVM命令。 -
写入Function命令：
writeFunction(String name, int nLocals)- 生成一条function name nLocalsVM命令。 -
写入Return命令：
writeReturn()- 生成一条returnVM命令。 -
关闭：
close()- 关闭输出文件。
这个模块相对简单，但从软件工程角度看很重要，因为它封装了所有与生成编译器输出相关的活动。
编译引擎
编译引擎从Jack分词器获取输入，并利用VM写入器将输出写入文件。它被组织为一系列compileXxx()例程，其中Xxx是Jack语言中的一个语法元素（例如compileClass()、compileSubroutine()、compileWhile()等，大约有15个）。
这些例程之间的约定是：每个compileXxx()例程应该从输入中读取Xxx构造，将输入恰好推进到Xxx之后，并发出实现Xxx语义的VM代码。如果该元素是表达式的一部分，那么发出的VM代码应计算其值并将其置于VM栈顶。
编译引擎的API与项目10中编写语法分析器时使用的API完全相同。然而，在本项目中，我们需要将这个生成XML代码的API，改造为生成可执行VM代码的API。
总结
在本单元中，我们一起学习了完整Jack编译器的建议实现方案。我们回顾了编译器的整体架构，并详细介绍了其核心模块：Jack编译器（主驱动）、Jack分词器（已就绪）、符号表（用于管理变量作用域和属性）、VM写入器（用于生成VM代码）以及编译引擎（负责语法分析和代码生成的核心逻辑）。下一单元（项目11概述）将提供逐步指南，教你如何实际执行和测试从生成XML代码到生成可执行VM代码的转变。
065：构建编译器
在本项目中，我们将完成编译器的构建。我们将把项目 10 中构建的语法分析器扩展和转变为一个功能完整的编译器。
概述
在项目 10 中，我们构建了一个语法分析器。在本项目中，我们将分两个独立的阶段，将这个语法分析器转变为一个完整的编译器。首先，我们将为其添加符号表处理能力，以理解源代码中标识符的语义。其次，我们将在此基础上实现代码生成功能，最终输出可执行的 VM 代码。
符号表处理
上一节我们介绍了项目的整体目标，本节中我们来看看第一阶段：符号表处理。
目前，语法分析器将所有标识符（如变量名、子程序名）统一标记为 identifier。为了更精确地理解源代码，我们需要分析每个标识符的语义角色。
我们将扩展语法分析器，使其在 XML 输出中包含以下信息：
-
标识符类别：是
var（局部变量）、argument、static、field、class还是subroutine。 -
索引编号：如果标识符属于
var、argument、static或field类别，还需输出其在该类别中的序号（例如，argument 0、argument 1）。 -
定义或使用：标识该标识符是在声明中被定义（如在
var语句中），还是在表达式等上下文中被使用。
以下是实现此功能的方法：
首先，你需要根据之前单元中给出的 API 规范，用 Java 或 Python 等语言实现符号表。
接着，为了测试符号表，我们建议你扩展项目 10 中已构建的语法分析器，为其添加上文所述的标识符处理能力。你可以设计自己的 XML 标签格式来输出这些信息，并通过运行项目 10 的测试程序来验证其正确性。这部分测试仅供你自己验证，无需提交。
代码生成
在成功为语法分析器添加符号表功能后，源代码的语法和符号语义都已被充分理解。接下来，我们将进入编译的最后阶段：代码生成。
我们将通过一系列测试程序来分阶段开发和测试你的编译器。以下是测试流程：
-
使用你正在开发的编译器编译包含测试程序的目录。
-
检查编译器生成的 VM 代码。如果发现问题，返回修改编译器。
-
将生成的 VM 文件目录加载到 VM 模拟器中并执行。
-
检查运行结果是否符合预期。如果不符合，则修复编译器。
需要特别注意的是，我们提供的测试程序本身是完美无误的。因此，任何错误都意味着是你的编译器存在缺陷，需要你来修复。
以下是六个测试程序的说明，请按顺序完成：
测试程序 1：Seven
此程序测试编译器处理简单算术表达式、do 语句和 return 语句的能力。程序计算 1 + 2 * 3。成功编译运行后，屏幕左上角应显示数字 7。
生成的 VM 代码中可能包含类似 pop temp 0 和 push constant 0 的指令。前者用于在 do 语句上下文调用方法后，丢弃其返回值。后者用于在 void 方法返回时，按约定推送一个返回值（此处为 0）到栈上。
测试程序 2：ConvertToBin
此程序测试编译器处理表达式（不含数组和方法调用）以及 if、while、do、let、return 这五种语句的能力。程序将十进制数转换为二进制表示。
测试时，输入值（如 171）需预先放入 RAM[8000]，程序运行后，转换得到的 16 位二进制结果将存入 RAM[8001] 至 RAM[8016]。
测试技巧：
-
使用 VM 模拟器的望远镜图标快速定位 RAM 地址。
-
程序运行后会修改 RAM，因此重新运行前无需（也不应）重置代码。
-
在非“无动画”模式下才能修改 RAM 值。
-
程序执行完毕后，需点击“停止”按钮才能查看 RAM 的最终状态。
测试程序 3：Square（Square Dance）
此程序测试编译器处理构造函数、方法以及包含方法调用的表达式的能力。该目录包含 Square.jack、SquareGame.jack 和 Main.jack 文件。
测试程序 4：Average
此程序测试编译器处理数组和字符串的能力。它是一个单文件程序，计算一组数字的平均值。
测试程序 5：Pong
这是一个完整的面向对象交互式游戏，用于测试编译器处理完整面向对象应用的能力，包括对象和静态变量的处理。目录包含 Ball.jack、Bat.jack、PongGame.jack 和 Main.jack 文件。成功编译后，可在 VM 模拟器中运行游戏，可能需要调整执行速度滑块以便操作。
测试程序 6：ComplexArrays
此程序测试编译器处理包含复杂索引表达式的数组操作的能力。程序运行后，会输出“期望结果”和“实际结果”，两者一致则表明编译正确。
总结
本节课中，我们一起学习了如何分阶段完成编译器的构建。我们首先通过实现符号表来增强语法分析器的语义分析能力，然后按照特定顺序，通过六个逐步复杂的测试程序来开发和验证代码生成功能。最终，你将拥有一个能够将 Jack 高级语言编译成可执行 VM 代码的完整编译器。
066：视角 🧠
在本节课中，我们将探讨代码生成单元的一些常见问题，包括Jack语言的简化特性、将其扩展为更复杂语言的挑战，以及编译器优化的概念。
Jack语言的简化特性
上一节我们介绍了代码生成的基本原理，本节中我们来看看Jack语言为何相对简单。Jack语言的设计包含了几项关键简化，这使得为其编写编译器的工作量大大减少。
以下是Jack语言的主要简化之处：
-
缺乏类型系统：所有数据值都是16位，任何类型的值都可以赋值给任何其他类型的变量。这允许编译器几乎完全避开处理类型问题带来的麻烦。
-
不支持继承：所有方法调用都可以在编译时静态处理。而在支持继承的语言（如Java）中，编译器必须在运行时解析方法调用，这被称为动态绑定或后期绑定。
-
没有公共字段：从类外部访问字段的唯一方式是通过程序员必须编写的访问器方法。
所有这些简化使得为Jack语言进行代码生成，比工业级语言的编译器要简单得多。
扩展Jack语言的挑战
了解了Jack语言的简化之处后，本节我们来看看将其扩展为更复杂语言（如Java或Python）的难度。一些扩展需要大量的代码生成工作，而另一些则相对直接。
以下是扩展Jack语言可能涉及的方面：
-
需要大量工作的扩展：支持继承、多态和动态绑定需要大量的编译工作。
-
相对直接的扩展：
-
添加
for循环和switch等控制结构。 -
在现有三种类型之外添加更多数据类型。
-
允许将字符常量直接赋值给
char类型变量（目前Jack程序员必须使用字符串函数，这很繁琐）。
-
总的来说，扩展一门语言需要两项独立的活动：
-
语言设计者必须谨慎地扩展语言的语法。
-
编译器编写者必须扩展语法分析器和代码生成器以适应这些变化。
好消息是，大多数这些扩展是彼此独立的，可以通过对现有语法分析器和代码生成器进行相对局部和简单的修改来实现。
编译器优化的意义
在讨论了语言扩展之后，我们转向另一个核心话题：编译器优化。编译器本身的效率并不重要，重要的是它能生成高效且优化的低级代码。
例如，考虑Java中的高级语句 x++。
-
一个简单的编译器可能将其翻译成
push x,push 1,add,pop x这样的虚拟机命令，最终可能产生约50行机器码。 -
一个优化的编译器则会识别出这是一个简单的变量递增操作，并直接将其翻译成两条机器指令：
@X后跟M=M+1（在Hack平台上）。
生成尽可能紧凑、使用最少时钟周期和硬件资源的代码，是代码生成和编译器一个非常吸引人的特性。我们在本模块开发的虚拟机翻译器并未进行此类优化。
尽管如此，我们开发的代码生成器虽然未经优化，但仍然代表了一项复杂且实质性的工程成就。完成它的开发后，你应该为自己的成就感到自豪——你刚刚完成了一个面向对象的、类Java语言的编译器。
总结
本节课中我们一起学习了：
-
Jack语言通过缺乏类型系统、不支持继承和没有公共字段等特性实现了简化。
-
将Jack扩展为更复杂的语言，有些方面（如支持继承）挑战巨大，而有些方面（如添加新控制结构）则相对直接。
-
编译器优化的核心目标是生成高效的低级代码，而非优化编译器自身，这是我们未来可以探索的方向。
本模块（模块5）到此结束。在下一个模块中，我们将使用Jack语言开发一个操作系统。
067：操作系统概述 🖥️
在本节课中，我们将要学习操作系统的核心概念、其必要性以及我们将在本模块中构建的Jack操作系统的蓝图。
课程概述
欢迎来到模块6，这是Nand2Tetris第二部分的最后一个核心模块。我们将讨论关于操作系统的众多不同方面。这个模块让我想起在印度餐厅享用的一顿丰盛晚餐，我们将品尝到许多色彩和风味各异的小菜，相信你会非常享受。
回顾我们的课程全景图，我们现在正处于操作系统模块的位置。没有操作系统在后台提供支持，就无法编写高级程序。操作系统的目标是弥合高级编程与程序赖以执行的底层硬件之间的诸多鸿沟。弥合这些鸿沟并描述这个操作系统，正是本模块的全部内容。
为什么需要操作系统？
世界上存在许多操作系统，这里展示了一些广为人知的系统图标。此外，还有一个不那么知名但我们将在本模块中开发的操作系统——Jack操作系统。
那么，为什么我们首先需要操作系统呢？请看这段用Jack语言编写的高级代码。你会发现，这段代码中多次调用了本类中不存在的方法。这些方法很可能存在于其他类中，例如Keyboard、Output、Math。这些类实际上属于Jack语言附带的标准类库。
这不是我们发明的。每一种现代高级语言都配备了一个支持它的标准库，Java、C#、Python、C++ 等都是如此。因此，当你开发一种高级语言时，该语言的用户会期望获得一个支持它的标准库。
操作系统的视角
从高级程序员的角度来思考操作系统，可以将其视为属于某个标准库的一组类。高级程序员期望获得各种数学计算功能的实现，例如平方根。他们期望获得数据结构方面的支持，如字符串、栈、数组等。
程序员期望能够以高级、抽象和便捷的方式与输入设备（如键盘、鼠标，甚至麦克风）进行交互。同样，程序员也期望能够使用一些便捷的API和接口在屏幕上输出文本或图形。因此，作为操作系统的开发者，我们有义务支持所有这些必要的抽象。
系统服务
此外，操作系统还应提供各种面向系统的服务，这些服务可能比我们刚才讨论的更偏向底层。
-
内存管理：我们必须能够管理主机内存（这里指的是RAM）。否则，当高级程序员想要创建新对象和新数组时，我们将无法帮助编译器完成。
-
存储管理：如果我们有海量存储设备（如硬盘、闪存等），我们也必须管理这些存储。为此，我们还需要一些文件系统抽象，至少需要支持文件，最好还能支持文件夹和子文件夹等。这些都是人们通常认为理所当然的东西，但显然是需要有人去实现的抽象。
-
设备驱动：我们需要开发各种驱动程序，这些程序用于在高级程序和低级外围设备（包括键盘、屏幕、鼠标以及绘图仪、打印机等各种你想连接到计算机的设备）之间进行协调。显然，你需要能够与这台计算机对话，因此必须有人实现诸如命令行界面和窗口系统等功能。
-
多任务处理：如今，很多人都希望同时做很多事情，例如写邮件、聊天、写博客、发评论、发布各种消息。为了做到这一点，我们需要为计算机配备多任务处理能力，使其能够同时运行多个程序。
-
网络与安全：如今没有人是一座孤岛，我们期望计算机能够通过网络与世界上的其他计算机交互。为此，我们必须有软件来协调和控制这些通信。一旦有了通信，我们还必须考虑安全性。
因此，我们必须支持所有这些服务，而承担这一重任的“某人”就是操作系统。由此可见，编写操作系统是一项庞大的工程。
Jack操作系统蓝图
在本课程中，我们不会开发一个功能齐全的操作系统，但会开发一个足够有趣且具有挑战性的系统。它将首先包括你在左侧看到的所有内容，即所有语言扩展。我们还将开发系统服务中的内存管理部分，并在一定程度上开发一些I/O设备驱动程序。其他所有内容将作为可选项目留待未来工作，作为我们Nand2Tetris课程的后续。
以下是我们的Jack操作系统的全貌，它由八个类组成，让我简要介绍一下每一个：
-
Math类：提供各种数学运算。Java的Math类有大约60或70个数学函数（尽管许多函数是重载的，所以实际数量更少）。我们提供这个选择，显然如果需要可以添加更多。
-
Memory类：这个类很经典，因为它包含任何操作系统中都存在的一些基本操作：
peek、poke、alloc、deAlloc。这些词现在可能没有意义，但很快你就会明白它们的重要性。 -
Screen类：提供一个允许你在屏幕上绘制图形的类，可以画线、圆、一些多边形。我们将广泛使用它，实际上我们在之前的一些项目中已经使用过了。
-
Output类：我们将广泛使用另一个类
Output，以便在屏幕上输出文本。 -
Keyboard类：通过这个类，我们可以与使用键盘的用户进行交互。
-
String类：字符串处理类，与Java的String类和C#中使用的类非常相似。我们将开发所有这些功能。
-
Array类：这在Jack中有些独特，因为在Jack中，数组不像在其他一些语言中是语言的原始部分。相反，我们决定使用操作系统来实现数组。通过这样做，数组变得与对象非常相似。实际上，Java和C#中也是如此，但我们没有时间深入探讨。这对高级程序员是隐藏的。
-
Sys类：包含一些有用的服务。
这就是我们的操作系统。要知道，有些人就是以开发操作系统为生的。
理论与实践
这些人基本上分为两类。首先是理论家，他们是算法和数据结构的专家。他们根据我们这里提到的需求，设计出各种巧妙的算法和数据结构，旨在高效地实现这些需求。然后是另一类人，他们将这些伟大的想法付诸实践，用C++、C等语言编写程序来实现这些数据结构和算法。
在本课程中，我们将同时采用这两种视角。在本模块的后续单元中，每个单元都将以一些理论讨论开始，探讨在算法和数据结构方面需要什么。然后，单元的后半部分将实际使用Jack语言实现这些想法。因此，Jack操作系统是用Jack语言编写的，就像Unix操作系统是用C语言编写的一样。我们还需要一些引导能力，这也将是本模块的一部分。
本模块的收获
本模块有许多值得学习的要点，这里只列出了其中几个。我们将深入学习应用计算机科学中这些超级重要的兴趣领域，并且将从高层次和低层次两个角度去学习。在本模块结束时，你将对这些内容有深入骨髓的理解。
我们将如何做到这一点呢？这个模块是一个绝佳的机会，让我和Noam可以向你们介绍一些用于管理资源、在屏幕上绘制图形等的优美算法。为了实现这些算法，我们还将向你们介绍巧妙编程的艺术，并给你们一些关于如何控制围绕软件的宿主平台的想法。当然，我们还将提供大量关于如何使用我们可用的所有工具来实际构建它的实现技巧。这就是我们的计划。
关于效率的说明
在结束本单元之前，我想简单谈谈效率问题。到目前为止，在本课程中，我们允许自己在效率方面有些“马虎”。我们不太担心效率，只希望事情能运行起来，不在乎它们是快是慢。但当涉及到开发操作系统时，效率至关重要。因为我们开发的算法将服务于在这些算法之上所做的一切。如果某个服务运行得不够快，那么所有运行在该服务之上的应用程序都会变得迟缓。反之，如果你能在底层优化某些东西，那么所有使用它的人都会视你为大英雄。因此，在操作系统层面，我们不能再对效率问题一无所知，我们必须非常聪明地设计程序的运行方式。这就是我们从下一个单元开始将要学习的内容。
课程总结
本节课中我们一起学习了操作系统的核心作用，它作为高级程序与底层硬件之间的桥梁，提供了必要的抽象和服务。我们概述了Jack操作系统的八个核心组件，并理解了开发操作系统需要兼顾算法理论与工程实践。最后，我们认识到在操作系统开发中，效率是至关重要的考量因素。
068：效率问题 ⚙️
在本单元中，我们将探讨操作系统设计中的一个核心议题：效率。我们将以乘法运算为例，分析不同算法的效率差异，并理解为何在底层系统软件中，高效的实现至关重要。
概述 📋
正如上一单元所述，我们决定以效率问题的讨论来开启操作系统模块。效率之所以重要，是因为操作系统中的基础服务（例如数学运算）将被无数应用程序乃至操作系统自身的其他部分频繁调用。因此，位于软件层次结构底层的服务，其效率越高，对上层服务的支持就越稳固。以乘法、除法、平方根等运算为例，它们必须足够高效。
乘法运算的客户端视角 👁️
在Jack编程中，你可以通过 x * y 这样的语法进行乘法运算。编译器足够智能，能够理解星号（*）代表调用底层操作系统 Math 类中的 multiply 方法，并自动将 419 * 5003 转换为 Math.multiply(419, 5003)。因此，无论使用哪种语法，最终都需要 Math 类来提供乘法功能。
算法一：重复加法
以下是第一种可能的乘法实现方案，它基于“重复加法”的思想：将 x 累加 y 次。
注意：从本单元开始，为了专注于算法本身而非语法细节，我们将使用类似Python的缩进来表示代码块，而不再使用Jack语言的花括号和分号。
def multiply(x, y):
sum = 0
while y > 0:
sum = sum + x
y = y - 1
return sum
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
2
0- 0
已为社区贡献38条内容
所有评论(0)