基于C++实现编译器【100012866】

# 一、Compiler 设计文档 # 二、程序结构 图中粗箭头代表调用关系，细箭头代表信息传递。  # 三、类/函数功能 以下，只写比较重要的类，只写 public 函数。由于 LexicalAnalyzer 已经差不多写得很完善了，所以这里给出其函数的详细接口。以下，由于类太多，具体的接口设计现在不一定能够做得很完善，故只写函数名。以后会对这个设计加以适当的更改。 ## 3.1 class LexicalAnalyzer - 词法分析器类。完成从文件中读取符号并分类的功能。 - 把语法分析器类等作为友元，以向其暴露符号类型 symbolType、获取到的符号 token、以及这个符号的行号 lineNumber。 - 因为用到全局变量，所以须用单例模式。 ### 3.1.1 static LexicalAnalyzer & initialLexicalAnalyzer(ifstream &) 由于使用单例模式，这个函数充当构造函数。如果多次调用这个函数，只返回同一个对象的引用。 ### 3.1.2 void nextSymbol() 获取下一个符号，保存这个符号的类型及行号，如有必要，需要保存这个符号本身（比如标识符等）。 ### 3.1.3 void nextChar() 获取下一个“字符”，指字符常量中单引号中间的部分。目前的设计是： - 跳过空白符； - 如果遇到非法字符，则将这个符号保存下来，并将类型置为“非法”； - 如果遇到多个字符，只读一个，保存下来，并将类型置为“字符”。 以上设计有可能在不断的完善中更改。 ### 3.1.4 void nextString() 获取下一个字符串，指字符串常量中双引号中间的部分。目前的设计是： - 允许有空串； - 如果读到非法字符，则将非法字符之前的部分保存，将类型置为“字符串”； 以上设计中的第二条，有可能会在实现中不断完善，可能会有更改。 ## 3.2 class GrammarAnalyzer 语法分析器。按照文法，使用递归下降子程序法，将词法分析读到的一个一个单词与文法匹配，并调用相应的语义处理函数。如果有错误，则调用错误处理函数。 目前尚未想到有必要用单例模式，因为暂不涉及全局变量。 ### 3.2.1 grammerAnalyze() 这是对 main 函数提供的接口，也是编译过程前半程的入口。由此，进行语法分析、语义分析、错误处理、中间代码生成等过程。 ### 3.2.2 （各大语法成分的解析函数） 这里函数太多，不逐一展开赘述。使用递归下降子程序法，每一个语法成分都有一个独立的处理函数，它们会调用词法分析程序、语义分析程序，如果出错，会调用错误处理程序。思路与教材相似，但是我的设计是，错误信息的输出由错误处理程序执行，这样程序的结构更加清晰。 ## 3.3 abstract class SemanticAnalyzer 语义分析器。与语法分析器配合，递归调用相应的函数，完成与语义相关的分析工作并生成结构化的四元式代码。与符号表、错误处理、四元式等类都有交互。 在设计上，语义分析器相当于给语法分析器提供的一个函数库，所以要用单例模式。在代码逻辑中，语义分析器负责符号表、四元式类的初始化工作。所以这里把语义分析器定义为抽象类、并把所有对外提供的接口声明为 static 较为合理。 ### 3.3.1 （各个语义动作函数） 这个要具休情况具体分析，在实现时再完善这一部分的设计。即使现在开再大的脑洞，还是不可能做到把需要用到的东西都想到，而且过于抽象，容易出错，还不如实现时具体考虑。 ## 3.4 class SymbolTableManager - 符号表管理器。符号表全程只有一个，这里用作全局变量以提高效率，所以这里必须使用单例模式。 - 对外提供建表、查表、填表、删表等操作。由于查表函数会返回表项的指针，所以不需要再提供填表函数。 - 符号表使用 hash_map，里面的值为表项的指针。 ### 3.4.1 static SymbolTableManager & initialSymbolTableManager() 单例模式中对外提供的“构造函数”，多次调用只返回同一个引用。完成符号表数据结构的构建。 ### 3.4.2 addTable() 当编译器分析到一个里层的分程序时，要在符号表中相应的加一层。这个函数完成的就是这个操作。 ### 3.4.3 lookupTable() 查符号表，参数为标识符，若有，返回表项的指针；若没有，返回 NULL。 ### 3.4.4 deleteTable() 当里层的分程序编译过程完成时，符号表相应的那一层也要释放。 ## 3.5 class Quadruples 四元式列表。保存结构化的四元式，作为语义分析器、代码优化器、目标代码生成器三个类相互之间传递四元式代码的媒介。 关于四元式列表具体的数据结构以及它对外提供哪些接口，及至是否把某些函数用宏实现，都没有想出太完美的答案。如果用数组，那么优化之后的代码有可能比原来的代码短，这好办，但是如果比原来的代码长，这就不好办了。还有，如果用链表，定位的效率太低！也许还有更好的解决办法目前还没有想到。下面只给出目前想到的一些，而且没有考虑函数到底是宏函数还是普通函数。 ### 3.5.1 get() 给四元式标号，返回四元式结构的指针。 ### 3.5.2 put() 给标号以及四元式结构的指针，返回标号。 ### 3.5.3 output() 把当前所有的四元式输出到文件。参数为文件名。 ## 3.6 class CodeOptimizer 代码优化器。这是一个大类，管理流图、DAG 图、定义-使用链、冲突图等数据结构，还要在这个过程中保存活跃变量分析、到达定义分析等数据流分析的结果数据结构等。要把全局寄存器分配的结果放在全局寄存器表中以备目标代码生成器使用。 执行代码优化的过程，包括建立流图、消除局部公共子表达式、数据流分析、建立定义-使用链并建网、建立冲突图、全局寄存器分配等工作。 这里需要强调的是，我是设计中，EBP 不需要参与存储管理，而作为全局寄存器使用。 ### 3.6.1 codeOptimize() 这是代码优化器对外提供的入口，由这个函数调用其他优化算法并管理相应的数据结构，以完成代码优化过程。 ## 3.7 class TargetCodeGenerator 目标代码生成器。以四元式、全局变量分配表作为输入，把 x86 汇编代码输出到文件中。此间，用到临时寄存器池等工具类。 ### 3.7.1 Generate() 生成 x86 汇编代码并输出到文件中。这个过程中会调用几个别的函数以完成这个操作。在生成代码的过程中，会用到全局变量分配表和临时寄存器池等类作为支持。 ## 3.8 class GlobalRegisterTable 全局寄存器分配表，即代码优化的输出之一。把全局寄存器的分配情况封装起来，供代码优化器添加和目标代码生成器查询用。 这部分的数据结构同样没有想好，所以下面只是简述。 ### 3.8.1 addRegister() 向表中加入一条寄存器分配结果。 ### 3.8.2 getRegister() 从表中查询局部变量是否有全局寄存器，如果有，则返回寄存器名；没有，返回一个表示“没有”。 ## 3.9 class RegisterPool 临时寄存器池。给临时变量以及没有得到全局寄存器的变量分配和管理临时寄存器。这里的算法貌似没有最优的，因为没有人能预测未来，知道后面哪个变量用得多。只能随用随分。 寄存器堆只有一个，一定会用到 static 变量，所以这个类必须要用单例模式。 ### 3.9.1 static RegisterPool & initialRegisterPool() 因为用到单例模式，这个是逻辑上的“构造器”。多次调用只会返回�