编译原理课程实践基于C++实现的一个SysY到RISC-V的编译器项目源码+实践报告

# 编译原理课程实践报告：StupidSysY2RV ## 一、编译器概述 ### 1.1 基本功能 本编译器基本具备如下功能： 1. 将[SysY](https://pku-minic.github.io/online-doc/#/misc-app-ref/sysy-spec)语言编译为[Koopa IR](https://pku-minic.github.io/online-doc/#/misc-app-ref/koopa)形式； 1. 将[SysY](https://pku-minic.github.io/online-doc/#/misc-app-ref/sysy-spec)语言编译为RISC-V代码； 1. 大概率通过自身崩溃检查代码错误的功能； ### 1.2 主要特点 包含了基本要求的功能：表达式编译、常量变量、语句块作用域、if, while语句、函数调用、全局变量、数组。 还有如下等特点：速度慢、容易崩溃……/(ㄒoㄒ)/~~ ## 二、编译器设计 整体设计： 1. 使用词法、语法分析器分析SysY代码文件，构建抽象语法树AST； 2. 调用根节点AST的函数，直接通过AST生成Koopa IR结构的内存形式； 3. 将Koopa IR结构输出为代码，重新读取后，再遍历Koopa IR结构的内存形式，生成RISC-V代码。 ### 2.1 主要模块组成 编译器由4个主要模块组成： 1. 分析模块：```sysy.l```以及```sysy.y```分别进行词法分析和语法分析，构建抽象语法树(AST)； 2. AST模块：```ast```文件夹中的代码。实现AST结构，并使用该结构生成Koopa结构。 3. Builder模块：```builder```文件夹中的代码。读取Koopa结构，生成RISC-V代码。 4. 工具模块：其他文件。包含基本块维护器，循环结构维护器，生成Koopa结构的工具函数等。 ### 2.2 主要数据结构 #### 抽象语法树 抽象语法树节点均继承自```BaseAST```类，该类规定了一些可以实现的功能，方便使用多态调用。比如```build_koopa_values```用于将该节点的语义转化为Koopa结构并返回；```CalcValue```用于计算常量表达式的值。 ```BaseAST``` 中有3个static成员，作为全局信息：用于维护生成IR时需要的符号表```symbol_list```；当前基本块的语句缓存区```block_maintainer```；维护嵌套循环结构的```loop_maintainer``` ```c++ class BaseAST { public: static SymbolList symbol_list; static BlockMaintainer block_maintainer; static LoopMaintainer loop_maintainer; virtual ~BaseAST() = default; virtual std::string to_string() const; virtual void *build_koopa_values() const; virtual int CalcValue() const; virtual void *koopa_leftvalue() const; }; ``` AST节点示例： 赋值语句的AST需要包含左值节点和右值表达式节点。其重写函数```build_koopa_values```中，调用了子节点的函数，以获取他们的Koopa结构，并由此构建自己的Koopa结构（Store语句），再通过全局结构```block_maintainer```将该语句添加进当前基本块。 ```c++ class AssignmentAST : public BaseAST { public: std::unique_ptr<BaseAST> lval; std::unique_ptr<BaseAST> exp; AssignmentAST(std::unique_ptr<BaseAST> &_lval, std::unique_ptr<BaseAST> &_exp); void *build_koopa_values() const override { koopa_raw_value_data *res = new koopa_raw_value_data(); // .. some code to build koopa_raw_value_data block_maintainer.AddInst(res); return res; } }; ``` #### 基本块维护器 在```BlockMaintainer```中，需要存储当前正在构建的函数、基本块、指令缓冲区等Koopa结构信息。由于其为静态成员，任意AST节点都可以调用他来添加基本块、语句等。 当一个基本块完成时，该类的```FinishCurrentBlock```函数负责清楚基本块末尾无法到达的语句，以及添加Jump、Return之类的语句防止基本块出错。 ```c++ class BlockMaintainer { koopa_raw_function_t current_func; std::vector<const void *> current_insts_buf; std::vector<const void *> *basic_block_buf; public: void SetCurrentFunction(koopa_raw_function_t _cur_func); void SetBasicBlockBuf(std::vector<const void *> *_basic_block_buf); void FinishCurrentBlock(); void AddNewBasicBlock(koopa_raw_basic_block_data_t *basic_block); void AddInst(const void *inst); }; ``` #### 循环维护器 嵌套的循环结构会造成大量基本块，出现复杂的跳转结构，为此实现了一个类来维护。 该类使用一个vector来构建一个栈，用于表示嵌套的循环结构。栈中元素存储对应循环的各个基本块信息，方便AST节点构建Koopa时使用。 ```c++ struct KoopaWhile { koopa_raw_basic_block_data_t *while_entry; koopa_raw_basic_block_data_t *while_body; koopa_raw_basic_block_data_t *end_block; }; class LoopMaintainer { std::vector<KoopaWhile> loop_stk; public: void AddLoop(...) { KoopaWhile kw; // ... 构建kw loop_stk.push_back(kw); } KoopaWhile GetLoop() { return loop_stk[loop_stk.size() - 1]; } void PopLoop() { loop_stk.pop_back(); } }; ``` #### RISC-V构建器 (builder) RISC-V构建器中包含一个输出流```output```，通过```build```函数递归遍历Koopa结构，生成的RISC-V代码直接输出到output中。 构建器中包含一个```Env```结构，用于存储Koopa指令到int的映射，代表该指令的计算结果存储在栈上的位置，RISC-V找到该结构并读取。 ```c++ class RISCVBuilder { class Env { int total_size; map<koopa_raw_value_t, int> addr; public: int cur; bool has_call; void NewEnv(int size, bool _has_call); int GetTotalSize(); int GetAddr(koopa_raw_value_t kval); } env; ostream &output; static int calc_func_size(koopa_raw_function_t kfunc, bool &has_call); // ... some functions to calculate memory static int calc_type_size(koopa_raw_type_t ty); void traversal_raw_slice(const koopa_raw_slice_t *rs); // ... some functions for every instructions void gen_riscv_value_return(const koopa_raw_return_t *kret); public: RISCVBuilder(ostream &_out) : output(_out) {} void build(const koopa_raw_program_t *raw); }; ``` ### 2.3 主要设计考虑及算法选择 #### 2.3.1 符号表的设计考虑 符号表类里面定义了一个vector实现的栈，表示作用域的嵌套结构，新建作用域时在栈顶添加元素。 栈中每个元素为一个map，将字符串映射到Koopa结构，表示该作用域的符号表。 当需要查找符号时，从栈顶开始在map中查找，若没有找到，则进入栈中前一个元素继续查找，实现往父作用域的查找。 ```c++ struct LValSymbol { enum SymbolType type; void *number; }; class SymbolList { std::vector<std::map<std::string, LValSymbol>> sym_stk; public: void NewEnv(); void AddSymbol(const std::string &name, LValSymbol koopa_item); LValSymbol GetSymbol(const std::string &name) { LValSymbol res; for (size_t i = sym_stk.size() - 1; i >= 0; i--) if (sym_stk[i].count(name) != 0) { res = sym_stk[i][name]; break; } return res; } void DeleteEnv(); }; ``` #### 2.3.2 寄存器分配策略 寄存器分配采用全部放在栈上的策略，仅在一些运算中途会使用寄存器。 首先Builder进入函数时，计算所有语句以及变量等占用的空间大小，在栈上分配足够的空间。 每个语句确保自己执行的内部寄存器不会冲突，执行完毕将语句的结构存在栈上指定位置，寄存器信息不再保存，可被其他语句复用。 每个语句仅使用t0~t6寄存器，函数参数即返回值使用a0~a7。 #### 2.3.3 其它补充设计考虑 ##### 优化语法分析中的列表 在语法分析器中，针对列表状的语句。=，如```int x0,x1,x2....```任意多个变量。 在yacc中设计为如下形式： ```c VarDecl : BType VarDefList ';'; VarDefList : VarDef | VarDefList ',' VarDef; VarDef : ..... {add_inst(...);} ``` 并在全局开一个vector