Posts

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 在词法分析阶段，我们将字符序列解析为单词序列，其中每一个单词都是一个最小的语法单元。词法分析的分析结果是非结构化的序列，无法表达程序的复杂语法结构。因此我们还需进行语义分析，用给定的上下文无关文法识别单词序列。而语义分析的最终结果，就是抽象语法树。 一、语法树的表示方法 文法反映了句子中不同结构之间的组成关系。例如下面的文法： VarDecl: BType Ident Dims [ '=' InitVals ] 便反映了变量定义由类型、标识符、维度以及可选的初始化值组成。 而对于组成这一概念，十分常见的建模方法便是将整体定义为类，而将各子部分定义为其属性。因此对于上面的文法，可以将其建模为如下形式： struct VarDecl { BType btype; Ident ident; Dims dims; InitVals *init_vals; }; 同理，我们也可以进一步定义 BType、Ident、Dims 以及 InitVals。如此继续下去，我们便可以对文法中的任意符号定义对应的类型，从而实现对源程序的结构化表示。我们所定义的这一系列类型，实际上也就是文法所对应的语法树中的可能节点。 在定义节点的时候，需要注意某一非终结符对应多条规则的情况。例如下面的规则： Stmt: 'if' '(' Cond ')' Stmt [ 'else' Stmt ] | 'while' '(' Cond ')' Stmt 这种情况下我们会发现，if 语句和 while 语句的结构并不相同，然而不管是 if 语句还是 while 语句，它们都是语句。 对是（is-a）关系的一种很容易想到的建模方法便是继承。因此，我们可以用如下方法表示 Stmt 符号对应的两条规则： struct Stmt {}; struct IfStmt : public Stmt {}; struct WhileStmt : public Stmt {}; 然而，继承不仅意味着变量多态，还意味着函数多态，可是在语法树的表示中，我们实际上只是希望用同一个名称指代不同的数据类型，而并不需要同一个函数拥有不同行为。因此，继承在此处似乎太 “重” 了。...

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 不论是从标准输入中读取还是从文件中解析，我们的源程序总是以字符流的形式存在。例如，对于下面这个简单的源程序： 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$ 接受）。...