Posts

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 在之前的阶段中，我们编写了词法分析和语法分析程序，实现了源代码到抽象语法树的转换，这意味着我们就此得到了结构化的语法信息；另外我们还定义了符号表，从而能够将某一处的语义存储并关联到程序的其他部分；最后我们还定义了中间代码的数据结构，让我们能够方便地构建并输出中间代码。而在这些之后，我们需要一个阶段将这些内容全部连接起来，这就是语义分析阶段。 根据语言的不同，语义分析阶段的目标也可能很不相同。例如 C 的语义分析阶段肯定与 SQL 的语义分析差别巨大。不过总体来说，语义分析阶段的思路还是类似的，那就是遍历语法树、维护符号表并构建中间代码（或者类似的翻译操作）。 一、遍历语法树 树的遍历各位同学当然不陌生。但是怎么样遍历才更好却依旧是一个值得思考的问题。假设我们现在用 Node 类表示树的节点： struct Node { int val; std::vector<Node*> children; } 那么我们很容易想到两种遍历的方式。第一种便是在 Node 中增加一个方法 visit。 struct Node { int val; std::vector<Node> children; void visit() { // do something, like `std::cout << val << std::endl;` for (auto child : children) { child.visit(); } } }; 而第二种方式则是将 Node 作为参数。为了避免使用全局变量，我们需要创建一个新的类 Visitor。 struct Visitor { void visit(Node &node) { // do something, like `std::cout << val << std::endl;` for (auto child : children) { visit(child); } } }; 那么就这两种方法来说，哪种更加适合抽象语法树的遍历呢？答案是第二种使用 Visitor 的方法。因为语义分析的关键是跨节点的语义信息传递。采取第一种方法时，信息被隔离在了每一个节点之中，想要传播只能作为 visit 函数的参数和返回值，沿着节点的遍历顺序进行传递。而对于第二种方法，类中所有方法都共享一个类作用域，这意味着信息不仅能沿着遍历顺序传递，还能跨越语法树的分支传播到需要的地方，而不需要经过层层调用。这种功能十分重要，因为实现上下文关系的关键，符号，就是跨越语法树分支存在的。...

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 在语法分析部分，我们将单词序列转化为结构化的抽象语法树。然而抽象语法树依旧无法表达完整的程序语义。因为抽象语法树的定义基于上下文无关文法，而无法反映程序执行时的上下文环境。因此为了记录程序中的上下文相关信息，为后续语义分析阶段提供建议，我们需要定义新的数据结构以维护上下文信息。在程序设计语言中，最为关键的上下文信息即符号信息，因此本章节我们着重讨论符号表。 一、符号表 符号表是编译过程中的一个重要结构，主要用于记录各个符号的标识以及相应的信息，例如名称、作用域、类型、大小、维度、存储地址、行数等各项信息。其目的是在编译过程中遇到对应符号时即可快速查询到相关信息。接下来我们也将提供符号表的实现思路以供参考。要注意，符号表的设计与使用将贯穿后续的全部实验流程，请同学们三思而后行！ 二、符号表的创建 在不区分作用域的情况下，符号表仅由需记录符号与符号信息的简单映射。但如果语言支持嵌套作用域，那么我们就需要表示各作用域符号表间的嵌套关系。在这种情况下，对于一张符号表来说，通常具有如图的结构：一个指向外层作用域符号表的指针 pre，表主体（符号名与对应信息），若干指向内层作用域符号表的指针 next。此外，在编译的过程中，有一个指向当前作用域符号表的指针 cur。 符号表的生成主要有以下几个操作： 初始时，创建一个全局变量符号表，也是最外层作用域符号表，cur 指向该符号表。 编译时，遇到变量声明语句，解析出需要的信息（一般包括类型、维度、大小等），填入 cur 指向的符号表。 编译时，进入新的作用域（block），生成新的符号表，设置 cur 指向的符号表的 next 指针指向新符号表，新符号表的 pre 设置为 cur，然后将 cur 指向新符号表，后续会在新符号表上填入信息。 编译时，离开作用域（block），通过 cur 指向的符号表的 pre 指针回溯至外层符号表，并对应修改 cur 指针。 不难发现，这样生成的符号表具有树状结构。当然，由于两个无嵌套关系的作用域中的符号并无任何联系，所以我们也可以按栈式结构来组织符号表，即进入新的作用域，就压入新的符号表，离开作用域时，弹出当前符号表。 在 tolangc 中，我们定义了一个栈式符号表。符号表类 SymbolTable 对应某一作用域的符号表。每一个符号表拥有一个 _father 字段，指向更外层作用域的符号表。另有 _symbols 字段存储当前作用域的符号。以符号名称为键，以符号信息（这里为 Symbol 类对象）作为值。 class SymbolTable : public std::enable_shared_from_this<SymbolTable> { // ... private: std::unordered_map<std::string, std::shared_ptr<Symbol>> _symbols; std::shared_ptr<SymbolTable> _father; }; 当进入新的作用域时，我们调用 push_scope 函数，创建新的符号表，并将该符号表的 _father 字段设置为当前符号表。...

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 在词法分析阶段，我们将输入的源程序解析为一个个单词；而在语法分析部分，我们将依照文法对单词序列进行进一步的分析，从而构建结构化的抽象语法树。 一、语法分析的作用 进行语法分析的必要性在于，句子是线性结构，不包含相应的语法结构信息。因此直接对线性的句子进行处理非常困难。而语法树的层次化结构能够表现语法结构以及语法成分之间的关系，且方便利用递归等方法来进行处理。 例如，对于上表达式 a + (3 + b) * 2 对于人来说，可以很容易地确定表达式的运算顺序。但是，从计算机角度而言，要编写一个程序仅仅根据这个线性字符串来确定运算的顺序是比较困难的，尤其是当表达式更为复杂的时候。如果我们建立了语法树，则可以很轻松地利用递归等方法来进行计算。 实际上，我们人类确定表达式运算顺序的方法，或许也在一定程度上与语法分析所采用的方法类似。这一点将在下一章节中说明。 还举上面的表达式为例。我们给定文法，并给出表达式在该文法上的语法树 LVal: Ident PrimaryExp: '(' Exp ')' | LVal | Number UnaryExp: PrimaryExp | Ident '(' [FuncRParams] ')' | UnaryOp UnaryExp UnaryOp: '+' | '-' | '!' MulExp: UnaryExp | MulExp ('*' | '/' | '%') UnaryExp AddExp: MulExp | AddExp ('+' | '-') MulExp Exp: AddExp 在上面的例子中，我们要求表达式 Exp 的值（图中序号1），那么我们只需要求出 AddExp（序号2）和 MulExp（序号3）的值并将它们相加即可。要求 MulExp（序号3）的值，我们只需要求出 MulExp（序号4）和 UnaryExp（序号5）的值并将它们相乘即可。同样地，要求 MulExp（序号4）的值，我们只需要求出 AddExp（序号6）和 MulExp（序号7）的值并将它们相乘即可。对于每种语法成分的处理，如 AddExp 和 MulExp 的计算求值，我们都可以采用递归的方法很方便地实现，而且语法树的层次结构自然保证了计算顺序的正确性。...

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 在词法分析阶段，我们将字符序列解析为单词序列，其中每一个单词都是一个最小的语法单元。词法分析的分析结果是非结构化的序列，无法表达程序的复杂语法结构。因此我们还需进行语义分析，用给定的上下文无关文法识别单词序列。而语义分析的最终结果，就是抽象语法树。 一、语法树的表示方法 文法反映了句子中不同结构之间的组成关系。例如下面的文法： 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 ('<' | '>' | '<=' | '>=' | '==' | '!...