Posts

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 不论是从标准输入中读取还是从文件中解析，我们的源程序总是以字符流的形式存在。例如，对于下面这个简单的源程序： int main() { int var = 8 + 2; if (var != 10) { printf("error!"); } else { printf("correct!"); } return 0; } 尽管从我们的视角来看，源程序是结构化的，包含了顺序、分支、循环等多种结构；同时通过空格、换行等方法，我们还可以将程序中的各个成分清晰地区分开来。但是从编译器的角度看，源程序不带有任何结构，只是由字符组成的序列（字符串）： int main() {\n\tint var = 8+2;\n\tif (var != 10) {\n\t\tprintf(“error!”);\n\t}\n\telse {\n\t\tprintf(“correct!”);\n\t}\n\treturn 0;\n} 这导致了一个问题，虽然字符是构成字符串的基本单元，却每个字符自身却不一定具备特定的含义。这些字符需要组成一个单词才能传达出对于程序来说有意义的信息。因此，实现编译器的第一步就是要把这样的线性字符串分割成一个个单词，便于后续分析。在编译器中，这一阶段被称为词法分析。 一、词法分析作用 词法分析器作为编译器的第一部分，承担的任务就是通过扫描输入的源程序字符串，将其分割成一个个单词。如图所示，经过词法分析器的处理，我们将字符序列转换为单词序列。对于每个单词，我们至少应当记录单词的取值及其类别信息。另外，编译器在词法分析阶段也可能记录单词在源代码中的位置信息，例如源文件路径、行号、列号等等。这些额外信息对于编译器的错误处理十分重要。得当的错误定位能够为代码的编写者提供极大便利。 在源程序中，还有一些字符并不会影响程序的语法语义，如换行符 \n、注释等，这些符号自然也不会被词法分析器解析为单词，但词法分析器也需对这些符号进行适当处理，如忽略跳过、记录行号列号等等。 二、词法分析器的接口 在上一小节中，我们了解了词法分析阶段的主要作用，在本小节中，我们将基于此介绍词法分析器（Lexer）。 首先，词法分析的输出是单词序列，因而我们需要定义单词的数据结构。在 tolangc 中，我们所实现的 Token 类包括三个字段：type、content 和 lineno，分别对应了单词的类型、取值和位置。 struct Token { enum TokenType { #define X(a, b) a, TOKEN_TYPE #undef X } type; std::string content; int lineno; Token() = default; Token(TokenType type, std::string content, int lineno) : type(type), content(content), lineno(lineno) {} }; 对于单词类型，除了文法定义中出现的类型外，我们还额外定义了 TK_EOF 类型。这一类型用于表示我们已经读到了输入字符串的末尾。...

本系列是北航《编译技术》实验教程的前端教程部分，介绍了编译器前端的实现过程。此系列内容由本人编写或参与修改，在此也感谢所有参与教程编写工作的本届和往届助教。对于完整的实验教程，可见 wokron/tolangc。 系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 一、本教程的背景 编译技术实验是计算机科学与技术专业核心专业必修课编译技术的实践环节，旨在帮助学生深入理解编译原理和技术，并掌握实际编译器的设计和实现方法。在本实验中，各位同学需要自行设计、实现一个完整的编译器，该编译器能够实现 SysY 语言（C 语言子集）到中间代码 LLVM、Pcode 或目标代码 MIPS 的编译过程。 亲自实现一个编译器对各位同学理解编译技术有着极大的帮助。然而，作为这门课的初学者，同学们往往难以在一开始就对编译器产生完整全面的认识。在实验中，这一点体现为一些同学在编译器的设计上存在不足，难以运用理论课上的知识实现一个架构清晰、可随实验进度不断扩展的编译器。这导致这种情况的出现：早期的设计隐患在之后的实验中爆发，不得不重构之前的程序逻辑。在浪费时间的同时，无法学到编译器设计的更好方法。 当然，这并不意味着理论课的内容毫无必要，而是理论与实际之间本就有着难以轻易逾越的鸿沟。将理论与实践融会贯通，本就需要付出极大的努力。在往届的实验中，我们也曾提供或推荐一些已有的编译器代码供同学们学习，然而这些代码或过于老旧、或过于复杂，常常难以满足同学们的学习和借鉴需要。 为了能稍稍帮助同学们更好的完成编译实验，实验课教程组决定做出一点自己的贡献。以往的编译实验教程主要关注于讲述实验中可能会用到的相关知识，尽管也有一些辅助理解的例子，但也常常局限于单一章节的内容，不同章节间内容互不相通。这一定程度上妨碍了同学们从中学习编译器的设计方法，并容易造成了理解上的混乱。 因此，我们决定修改原有的编译实验教程，通过示例驱动的方式给同学们提供更有参考价值的教程内容。具体来说，我们会设计一个十分简单的编程语言：tolang。在本教程中，我们将以 tolang 编译器 tolangc 的编写为主线，介绍基本的编译器设计和实现方法，从而为同学们提供一个相对较好的实践样例。 二、tolang 介绍 tolang 这个名字很奇怪，最初起名时的含义是 toy lang，但是也有 too long 的谐音。不过这个语言确实是一个玩具语言，根本没有复杂冗长的语法语义。 （1）文法定义 我们的 tolang 可以由如下的 EBNF 范式确定： CompUnit: {FuncDef} {VarDecl} {Stmt} FuncDef: 'fn' Ident '(' [FuncFParams] ')' '=>' Exp ';' FuncFParams: Ident { ',' Ident } VarDecl: 'var' Ident ';' Stmt: 'get' Ident ';' | 'put' Exp ';' | 'tag' Ident ';' | 'let' Ident '=' Exp ';' | 'if' Cond 'to' Ident ';' | 'to' Ident ';' Exp: AddExp AddExp: MulExp | AddExp ('+' | '-') MulExp MulExp: UnaryExp | MulExp ('*' | '/' | '%') UnaryExp UnaryExp: PrimaryExp | Ident '(' [FuncRParams] ')' | ('+' | '-') UnaryExp PrimaryExp: '(' Exp ')' | Ident | Number FuncRParams: Exp { ',' Exp } Cond: Exp ('<' | '>' | '<=' | '>=' | '==' | '!...

之前使用 Matplotlib 画图的时候发现不能正常显示中文。在解决问题的过程中了解了一下字体显示的一些知识，在这里记录一下。 一、编码与字体 我们知道，为了让字符能够存储在计算机中，我们为每个字符分配对应的数码。这种人为约定称为字符编码。常见的编码包括 ASCII、GBK、Unicode 等等。字符编码是字符的数据表示。 然而，仅有编码依然不能在计算机中显示字符。因为符号是一种图形，若我们不能确定字符所对应的图形的样式，那么我们就无法在屏幕中看到字符。同样的，这种字符到对应图形的约定称为字形，字形的集合即字体。字体是字符的图像表示。 于是，这里我们就有了两种不同的映射关系。一种是字符到字符编码的映射关系，这一关系确定了字符的存储方式；另一种是字符到字体的映射关系，这一关系确定了字符的显示方式。 因此，简单来说，计算机显示字符的过程就是将编码数据转换为字形图像的过程。 二、编码的分裂和统一 然而这一过程并不真的那么简单。原因之一便是从计算机技术早期遗留下来的一系列互不兼容的编码方式。 在互联网还未诞生的时候，各个国家和地区为了在计算机中显示自己的文字，各自开发出自己的字符编码方式，例如简体中文的 GB2312、繁体中文的 Big5、日文的 Shift_JIS 等等。然而在互联网的国际化场景下，不同的编码方式带来了交流上的困难。 所以这时候 Unicode 标准应运而生。Unicode 由统一码联盟推动，旨在使用 Unicode 取代现存的字符编码。该标准整理并编码了世界上大部分的文字系统，使得电脑能以通用划一的字符集来处理和显示文字。 然而 windows 下的默认编码方式还是 gbk。 Unicode 编码空间区间为 $[0, 17 \times 2^{16})$，但目前只使用了其中很少一部分。该编码空间被划分为了 17 个平面，其中 4-13 号均未使用。其他平面的主要内容为： 0 号平面（0x0000-0x​FFFF）称为基本多文种平面，包含了几乎所有现代语言的字符。 1 号平面（0x10000-0x1FFFF）称为多文种补充平面，包括了绝大多数古代文字，现时已不再使用或很少使用的符号等。 2、3 号平面（0x20000-0x​2FFFF、0x30000-0x​3FFFF）称为补充表意文字平面，用于中日韩统一表意文字中未被包含在早期编码标准中的文字。 14 号平面（0xE0000-0xEFFFF）为特别用途补充平面。 15、16 号平面（0xF0000-0x​10FFFF）为私人使用平面。（例如苹果公司的图标字符） Unicode 虽然制定了统一的字符编码方式，但是直接使用 Unicode 编码进行存储的效率并不高。因此需要对 Unicode 进行进一步编码，这就带来了 UTF（Unicode Transformation Format），包括 UTF-32、UTF-16 和 UTF-8。 UTF-32 使用定长的 32 位对 Unicode 进行编码。根据 Unicode 的编码空间我们知道，最多只需要 21 位即可表示所有编码。因此 UTF-32 中的 11 位始终为 0。这使得 UTF-32 的空间效率很低。所以这种编码方式主要用在系统的内部 API 中。...

一、前言 我语言的局限，即是我世界的局限 —— 路德维希·约瑟夫·约翰·维特根斯坦 二、从文法树到语义 经过语法分析阶段的处理，我们将词序列组织成了一棵文法树。而在语义分析阶段，我们的目标就是理解该文法树的含义，并按其含义将该文法树翻译含义等价的另一种语言。 上面的表述十分宽泛。这是因为语义分析阶段不像前两个阶段有着明确的输入输出和确定的算法，根据使用场景的不同采用各自的处理方法。 举个例子，对比 C 语言和 SQL 语言，虽然它们都会采用编译技术进行语句的处理，但是 C 语言的语义分析产物是类似汇编的中间代码；而 SQL 语言的语义分析的结果则是对数据库中数据的处理操作。 因此，语义分析并没有通用的算法，就算同样是编程语言，面向过程、面向对象、函数式等不同的语言类别在语义分析上也有许多不同的处理。所以在本篇文章中，我们只会介绍最为简单和普遍的一种语义分析方法，那就是语法制导翻译。 三、语法制导翻译 （1）属性翻译文法 通过前面的文章，我们知道文法树表达了句子的结构。这种结构从语义上来说有两种含义： 一是指整体由部分组成。这反映了文法树中父节点的含义。例如对于表达式会 $1 + 2$，表达式本身是文法树中的父节点，而 $1$ $+$ 和 $2$ 则是子节点。 二是指部分处于整体之中。这反映了文法树中子节点的含义。 在使用语法制导翻译进行语义分析时，这两种含义我们称为属性。第一种属性由 “父” 传递到 “子”，称之为继承属性；第二种属性由 “子” 传递到 “父”，称之为综合属性。 （2）符号表管理 四、中间代码

一、前言 从这个精神王国的圣餐杯里， 他的无限性给他翻涌起泡沫。 —— 格奥尔格·威廉·弗里德里希·黑格尔《精神现象学》下卷 第八章 绝对知识 二、从正则文法到上下文无关文法 词法分析阶段，我们可以使用正则文法描述词的定义，这是因为词的结构是无嵌套的。也就是说，词只会由例如前缀、后缀以及结构的顺序重复等概念描述，不可能出现需要前后匹配的地方。举个例子，正则文法不能定义形如 $12344321$ 的回文数；或形如 $(()(()))$ 的括号结构。 然而，所有的高级语言却都是嵌套的。通过嵌套，高级语言能够表示更加复杂的结构，实现控制流、子程序、作用域、类等等高级概念。因此，正则文法并不能描述高级语言的语法，我们需要使用 2 型文法，也即上下文无关文法描述高级语言。2 型文法区别于 3 型文法就在于其嵌套性。 举个例子，我们可以将上述括号结构用如下 2 型文法定义： $$ S \rightarrow (S)S | \epsilon $$ 其中规则 $S \rightarrow S(S)$ 中左括号和右括号同时出现，这样就保证了对于一个左括号，必定有一个右括号与其匹配。因而我们说上面的文法具有嵌套性。 而 3 型文法则不同。由于左线性和右线性的约束，3 型文法中不可能出现一条规则中右侧有多个终结符的情况。 不过虽然 2 型文法相较于 3 型文法具有更强的表达能力，但是这也为其解析提供了一定的困难。我们可以选择用前面定义的文法给出 $(()(()))$ 的文法树： 可以看出，相较于 3 型文法的文法树，2 型文法的文法树更像是树：并不是只向一侧增长，而是在任意地方都可能产生子树。因此，2 型文法的推导或归约过程不再能看作状态的转移，我们需要用有穷自动机之外的另一种模型描述，该模型应当具有接受嵌套结构的能力。这就是下推自动机。 三、下推自动机 （1）例子：判断有效括号问题 初学编程的时候各位应该都做过类似的题目，那就是判断有效括号。实际上这是一个编译问题。我们可以使用编译理论的语言将该问题表述为：对于符号集 $\Sigma = \{`(`, `)`, `[`, `]`, `\{`, `\}`\}$，对给定的括号文法 $G$，对于任意 $s \in \Sigma^*$，给出一个算法，判断是否有 $s \in L(G)$（即 $s$ 是否被文法 $G$ 接受）。...

本文是北航《操作系统》课程预习教程的一部分。此版本由本人编写。 2024 年课程实验环境由 GXemul 更换为 QEMU，为了方便同学适应新的实验环境，在预习教程中特地新增《GDB：程序的解剖术》和《QEMU 模拟器介绍》两篇文章。 操作系统是直接运行在计算机硬件之上，向下管理硬件资源，对上为软件提供统一服务的一类程序。在本课程的实验中，为了开发和运行我们的 MOS 操作系统，我们必须具备一套支持操作系统运行的硬件系统，其中包括处理器、内存、外部设备（如磁盘）等多个组成部分。 然而，为每位同学都准备一套硬件设备是不切实际的。相较之下，使用模拟器则是一个更好的选择。模拟器能够模拟计算机硬件的行为和特性，使开发者可以在模拟的环境中运行和测试软件，而无需实际的物理硬件设备。 本实验所采用的模拟器为 QEMU，接下来我们就会对这一模拟器进行介绍。 什么是 QEMU QEMU（Quick Emulator）是一个通用的开源的机器仿真和虚拟化工具，由传奇程序员法布里斯·贝拉（Fabrice Bellard）编写。QEMU 能够提供跨体系结构的硬件模拟，支持 x86、ARM、MIPS、RISC-V 等多种架构。 法布里斯·贝拉 是 QEMU、FFmpeg 等著名项目的创始人。他的工作涉足操作系统（QEMU）、编译器（Tiny C Compiler）、图形学（TinyGL）、通信技术（Amarisoft）、数学（Bellard’s formula）、音视频（FFmpeg）、人工智能（NNCP）等众多领域，并都做出过许多突出的贡献。是一位近乎全才的人物。 QEMU 拥有多种不同的使用方式，而在实验中我们所使用的主要是 QEMU 的系统仿真模式。在此模式中，QEMU 能够模拟处理器的执行过程以及各种硬件设备的行为，从而提供包括处理器、内存和外部设备在内的整机虚拟模型。在此模型之上，我们能够运行一个完整的操作系统，而不需要任何额外硬件的支持。 QEMU 提供了高度定制化的硬件模拟能力，使得搭建指定硬件平台的运行环境十分容易。并且 QEMU 也提供了使用 GDB 进行调试的原生支持，使程序的开发更加便捷。正因如此，QEMU 成为了底层开发领域十分重要的工具。 QEMU 的工作原理 这部分并不是本课程要求掌握的内容。各位可以按兴趣阅读。 在正式谈论 QEMU 的工作原理前，我们需要先了解一下虚拟化（Virtualization）技术。这里的虚拟化特指硬件虚拟化，是指隐藏真实的物理硬件，而由软件模拟出特定的硬件环境，在此环境中运行的操作系统就好像运行在实际的物理机器上一样。在此过程中，通过模拟产生的硬件环境称为虚拟机（Virtual Machine），实现虚拟化的程序称为虚拟机管理程序（Hypervisor）。本质上，虚拟机管理程序是一种中间件。 通过虚拟化技术，我们可以屏蔽底层硬件的差别，从而在单台物理设备上运行许多不同的操作系统环境，充分利用硬件资源。虚拟化产生的硬件环境也很容易在不同设备间迁移，这也利于系统的管理和维护。 根据虚拟化实现方式的不同，虚拟机管理程序分为第一类虚拟机管理程序（Type 1 Hypervisor）和第二类虚拟机管理程序（Type 2 Hypervisor）。 第一类虚拟机管理程序直接运行在硬件之上，如下图 (a) 所示。此时虚拟机管理程序实际上占据了类似操作系统的位置，整个物理机被其分割为多个虚拟机。 而第二类虚拟机管理程序则运行在操作系统之上，是操作系统中的应用程序，如下图 (b) 所示。其中称运行该虚拟机管理程序的操作系统所处的机器为宿主机（Host），而管理程序中的虚拟机则为客户机（Guest）。由于第二类虚拟机管理程序采取了软件模拟处理器、解释执行机器码的方式，所以也被称为模拟器（Simulator）。 第一类虚拟机管理程序主要在企业数据中心或服务器中使用。常见的产品包括 KVM、VMWare ESXi 等等。而第二类虚拟机管理程序则通常在个人计算机上使用，以便能在运行虚拟机的同时执行其他进程。常见的产品包括 VMware Workstation、Oracle VirtualBox 等等，其中也包括 QEMU。 图片来自 Andrew S....