Tolang

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 项目的规模越大，越难以通过直接观察发现隐藏的代码缺陷。在实验中，各位同学需要实现的是一个万行级别的编译器项目。在这一情景下若不对自己的开发过程进行规范，及时进行项目测试，必然会严重影响代码质量，进而影响各位同学的实验进展。 因此在本附录中，我们将结合 tolangc 项目，提供一个较为简单，但具体可行的项目测试示例，以供同学们参考。 一、单元测试 （1）单元测试的结构 单元测试样例用于对程序中的最小功能模块进行测试，能够验证功能模块内部的正确性。一般来说，一个单元测试对应一个类或一个函数。对于编译器这一架构得到了充分研究的程序类型，一般来说我们可以选择为各个编译阶段设计对应的单元测试。例如在 tolangc 中，我们为 Lexer、Parser、Visitor 等等分别编写了单元测试。 一个单元测试样例是对某一功能进行的一次测试。不同的样例之间应当尽可能相互独立、互不影响。这也意味着单元测试的执行顺序不应当影响测试的结果。 需要注意的是，一些单元测试框架可能会提供设定样例执行顺序的功能，例如在某一样例成功之后执行等等。但是此处的执行顺序实际上反映的是功能模块之间的依赖关系，意为 “由于 A 模块依赖于 B 模块，所以如果 B 模块的测试出错，那么 A 模块的测试便没有意义”，而并不意味着单元测试之间可以相互关联。 由于上述特点，单元测试实际上应当看作一一个不同的可执行程序。但和整个项目所组成的程序不同，单个功能模块往往无法单独运行，且不像程序那样有着明确的输出。这就需要我们为单元测试构建测试所需的环境，并对模块的运行结果进行检验。这组成了单元测试所需要遵循的三个阶段：构造、操作和检验。 CMake 中提供的 “测试” 实际上就是这样的可执行程序。 构造指设定模块的运行环境，例如参数、依赖的对象、数据库中数据等等。构造在每个单元测试中都要进行，绝不能依赖其他单元测试的运行结果。运行环境当中需要重点关注的是可以被所有单元测试访问的单例和全局变量，以及可以实现数据持久化的文件和数据库。如果存在单元测试之间相互影响的风险，则需要在单元测试结束后进行重置操作。 操作指功能模块的运行。当构造完成运行环境之后，我们希望功能模块能够按照预期方式正确运行。 最后，检验指将功能模块的运行结果和预期结果进行比对。一般来说，测试框架会提供一系列用于比较结果的接口。具体的接口则视框架而定。这一部分的关键实际在于如何获取功能模块的运行结果。如果运行结果相对简单，如某个数值、单个数组等等，那么检验过程便相对简单。但如果运行结果的数据结构较为复杂，或运行结果位置分散，那么检验起来便较为困难。这时可以选择定义相应的信息提取函数，例如定义 to_string 函数将复杂数据结构转换为字符串。在 tolangc 中，对于语法树我们便采用了这样的处理方式。 （2）Mock 如果我们发现难以编写某个类或函数的单元测试代码，那可能意味着我们的类或函数需要进行进一步的拆分。难以测试可能是代码中的副作用或具体类之间的耦合导致的。对于类之间的耦合，我们需要遵循依赖倒置原则，用抽象的接口替代具体的实现。 例如，在实现 Lexer 时，我们没有将 ifstream 作为参数，而是将其父类 istream 作为参数。尽管对于 tolangc 来说，源代码总是从文件中读入的。 class Lexer { Lexer(std::istream &in) : _input(in) {} // ... } 这样做将使 Lexer 类更加可测试。若对 Lexer 类进行测试，我们不必创建真正的源文件。因为 istream 存在子类 istringstream。该类创建时需传入一字符串，而当从流中读取时，读到的便是传入的字符串的内容。...

系列导航： 《编译技术教程：前言》 《编译技术教程：词法分析》 《编译技术教程：抽象语法树》 《编译技术教程：语法分析》 《编译技术教程：符号表与类型系统》 《编译技术教程：语义分析》 《编译技术教程：附录 - 项目测试》 在之前的阶段中，我们编写了词法分析和语法分析程序，实现了源代码到抽象语法树的转换，这意味着我们就此得到了结构化的语法信息；另外我们还定义了符号表，从而能够将某一处的语义存储并关联到程序的其他部分；最后我们还定义了中间代码的数据结构，让我们能够方便地构建并输出中间代码。而在这些之后，我们需要一个阶段将这些内容全部连接起来，这就是语义分析阶段。 根据语言的不同，语义分析阶段的目标也可能很不相同。例如 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 类型。这一类型用于表示我们已经读到了输入字符串的末尾。...