编译器设计文档
参考编译器介绍
本次实验预备阶段主要学习参考了经典的Pascal编译器，现进行一定的介绍。
总体结构
课程组提供的Pascal编译器总体结构为词法分析、语法分析、错误处理、语义分析、代码生成和代码优化六个部分。
接口设计
该编译器并未进行模块化设计，而是将各函数放在一个文件下，在调用时设定形参实参进行数据的交互。主要函数如下：
nextch读取下一个字符test检查符号合法性error打印错误信息typ处理类型typedeclaration处理自定义类型
constant处理常量adjustscale处理实数
variabledeclaration处理普通变量procdeclaration处理过程和函数parameterlist处理形参
statement处理各种语句enter登记符号表enterreal登记实常量表enterarray登记数组符号表enterblock登记分程序信息入分程序表
emit生成中间代码
文件组织
该Pascal编译器全部函数均放在一个文件下，抽象化层次化程度低，复杂程度较高。实际上，可以建立库函数文件（或者像面向对象设计一样建立类，分文件调用），以此降低文件组织的耦合程度。
编译器总体设计
总体结构
设计的编译器主要分为前端 Front 、中端 Middle 、后端 Back 三个部分。
其中，前端主要负责词法分析、语法分析部分，有词法分析器 Lexer 、语法分析器 Parser 。中端主要负责语义分析（符号表的构建与管理）与中间代码生成有语义分析器（符号管理器） Manager 、中间代码生成器 Visitor 、代码优化器 Opitimizer 。后端主要负责目标代码生成以及代码优化，有目标代码翻译器 Translator 、代码优化器 Opitimizer 。
整体的结构与流程设计如下所示：
接口设计
前端：
content：未经任何处理的待翻译程序字符串；tokens：经词法分析后获得的单词列表；AST：经语法分析后获得的抽象语法树（Abstract Syntax Tree，下简称语法树）。
中端：
tables：经语义分析后获得的符号表项列表，其中列表第一项即是全局符号表项；MCT：经中间代码生成后获得的中间代码树（Medium Code Tree）。
后端：
OCT：经目标代码翻译后获得的目标代码树（Object Code Tree）；optim：经代码优化后获得的目标代码树。
文件组织
整体文件组织如下：
1 | ├─ Front 前端处理器 |
其中， Front 的文件组织如下：
1 | ├─Lexer 词法分析 |
Middle 的文件组织如下：
1 | ├─Manager 符号管理 |
Back 的文件组织如下：
1 | ├─Optimizer 代码优化 |
CompilerError 的文件组织如下：
1 | CompileError.java 编译错误类 |
IO 的文件组织如下：
1 | Printer.java 输出解析类 |
词法分析设计
源程序读入后作为长字符串存储在编译器中。词法分析部分的主要任务是将源程序字符串转化为单词。
首先应该建立单词类 Token 。在单词中，应当包含该单词种类、所在行、单词内容。因此设计单词类 Token ，其中包含属性 token、lineNum、type，用于存储必要信息。
在词法分析器 Lexer 中，读入源程序字符串，目标是生成单词列表。其中，部分单词是保留词，需要设置为相应类型。为防止无法分别标识符和部分保留词，首先应建立保留词表，以便分析出新单词后正确判断其类型。开始分析后，可以按照以下分类分析字符串：
- 当前字符是数字：那么下一个单词是数字常量。继续读入字符，直至该字符不是数字为止。该段字符串即是下一个单词，该单词的单词内容即是该段字符串，该单词的类型是
INTCON。 - 当前字符是
\"或\'：那么下一个单词是字符串常量或者字符常量。继续读入字符，直至该字符不是对应的"或'为止。应注意，在读入字符时，有可能出现转义字符\"或\'，需要进行特殊判断（当前字符是\时下一个字符是否是"或'），不能作为字符或字符串结束标志。该段字符串即是下一个单词，该单词的单词内容即是该段字符串，该单词的类型是STRCON或CHRCON。 - 当前字符是字母或
_：那么下一个单词是标识符或保留字。继续读入字符，直至该字符不是字母、数字或_。将该段字符串内容和保留词表比对，判断是否是保留词以及是什么类型的保留词。该段字符串即是下一个单词，该单词的单词内容即是该段字符串，该单词的类型是IDENFR或相应的保留词类型。 - 当前字符是
+-*%;,()[]{}：那么下一个单词是保留词。这些字符是保证只能单独出现的保留词，因此直接将该字符与保留词表比对，判断是什么类型的保留词。 - 当前字符是
!=><：那么下一个单词是保留词。这些字符可能组合出现，产生不同于当前字符含义的保留词。继续读入字符，直至该字符不是这些字符。将该段字符串内容和保留词表比对，判断是什么类型保留词。 - 当前字符是
&|：那么下一个单词是保留词。由于该字符可能出现错误，因此单列出来考虑。继续读入字符，若该字符与当前字符不同，词法分析部分出现错误；若相同则与保留词表比对，判断是什么类型保留词。该单词的类型是AND或OR。 - 当前字符是
/：那么接下来可能是保留词/或注释//、/**/。读入下一个字符，若该字符是/或*，那么接下来是注释，若不是，则是保留词/，类型为DIV。如果这两个字符是//，继续读入字符，直至读入\n；如果这两个字符是/*，继续读入字符，直至读入*/。 - 当前字符是
\n：源程序进行了换行，当前行数加一。 - 当前字符是其他字符：跳过即可。
获得单词后，将其存入单词列表 tokens 中，并正确输出结果。
语法分析设计
词法分析部分分析出的单词列表存储在编译器中。语法分析部分的主要任务是按照 SysY 语言文法自顶向下将单词列表转化为语法树。
SysY 语言文法如下：
1 | 编译单元 CompUnit → {Decl} {FuncDef} MainFuncDef |
首先应该建立语法成分接口 Syntax 。后续建立语法树 AST 时所有节点都应该实现 Syntax 接口，以保证统一性。对于每一个语法成分，都应建立一个类，存储它作为语法树节点所有的子节点。
在语法分析器 Parser 中，读入单词列表，目标是生成语法树。按照 SysY 语言文法，自顶向下为每个节点类建立分析函数。同时为了不进行回溯，应在每个分析函数开始部分建立是否为当前语法成分的判断部分（判断首单词是否符合当前推导规则）：
CompUnit：语法树的最顶层节点，代表整个待编译程序。其子节点可能为Decl、FuncDef、MainFuncDef，其中，前两部分可能存在若干次，因此使用for循环进行解析，直至无法解析出Decl或FuncDef。对于第三部分MainFuncDef，直接解析即可。Decl：代表声明部分，分为常量声明ConstDecl和变量声明VarDecl。先假定为常量声明进行解析，若返回值为空，按照变量声明解析即可。FuncDef：代表普通函数（非主函数）声明部分。当需要解析函数时，首先应该判断是否符合函数定义格式以及是否是主函数。对于函数定义，最大的特征标识是函数名标识符Ident后的小括号(，如果成立则可以判定为函数。对于是否是主函数的判定，只需要判定函数名标识符Ident是否是main即可。判定确实为普通函数后，存储该函数的函数类型FuncType、函数名标识符Ident，并对标识符后的函数形参进行解析及存储（存储形参个数、形参名、形参类型等）。之后对函数主体的块Block进行解析即可完成整个函数的解析。MainFuncDef：代表主函数声明部分。其大体流程与普通函数声明部分相似：判断是否符合函数定义格式以及是否是主函数。对于函数定义，最大的特征标识是函数名标识符Ident后的括号(，如果成立则可以判定为函数。对于是否是主函数的判定，只需要判定函数名标识符Ident是否是main即可。需注意，二者都必须进行，否则可能出现被命名为main的变量被判定为主函数而导致的解析错误。判定为主函数后，存储相应函数信息，不需要对函数形参进行解析，直接对函数主体的块Block进行解析即可完成整个主函数的解析。Block：代表由大括号包覆的块。其内部含有若干各块组成BlockItem，因此使用for循环进行解析，直至无法解析出BlockItem（实际上是到达块的后一个大括号}）。最后，将块的后一个大括号}解析即可。ConstDecl：代表常量声明部分。首先应通过当前单词是否是const判断是否是常量定义，若不是常量定义则返回空值。如果是常量定义，则存储之后定义的常量的数据类型BType。由于一句常量声明中可以存在多条常量定义语句，因此使用for循环进行解析，直至无法解析出ConstDef。VarDecl：代表变量声明部分。首先应当判定是否是变量定义：当前单词应该是变量的数据类型BType，且不应该出现BType Ident (的情况。如果是变量定义，则存储之后定义的变量的数据类型BType。由于一句变量声明中可以存在多条变量定义语句，因此使用for循环进行解析，直至无法解析出VarDef。ConstDef：代表常量定义部分。首先需要判断是否是常量定义，由于ConstDef只能从ConstDecl获得，因此只需要通过是否存在定义常量标识符Ident判定是否是定义语句即可。如果是常量定义，则存储当前常量标识符Ident。该标识符所代表常量可能是常量数组，需要通过标识符后是否是中括号[来判断。如果该常量是常量数组，则需要对中括号[后的常量表达式ConstExp进行解析，以获得该数组的元素个数。如果不是常量数组，正常进行后续操作即可。对于常量定义部分，还需要解析为定义常量所赋的初值。对等号=后的常量表达式ConstExp进行解析并存储即可。VarDef：代表变量定义部分。首先需要判断是否是变量定义，由于VarDef只能从VarDecl获得，因此只需要通过是否存在定义变量标识符Ident判定是否是定义语句即可。如果是变量定义，则存储当前变量标识符Ident。该标识符所代表变量可能是变量数组，需要通过标识符后是否是中括号[来判断。如果该变量是变量数组，则需要对中括号[后的变量表达式VarExp进行解析，以获得该数组的元素个数。如果不是变量数组，正常进行后续操作即可。对于变量定义部分，还需要判定是否存在为定义变量赋初值的情况，通过标识符Ident或中括号]后是否存在等号=来判断。如果存在，解析为定义变量所赋的初值。对等号=后的普通表达式Exp进行解析并存储即可。ConstInitVal：代表常量定义时的初值，可能为字符串常量，常量数组元素集合，常量表达式。对于字符串常量，直接存储即可。对于数组元素集合，通过大括号{来判定，如果是则解析后续出现的若干常量表达式即可；对于常量表达式，直接解析即可。InitVal：代表变量定义时的初值，可能为字符串常量，变量数组元素集合，普通表达式。对于字符串常量，直接存储即可。对于数组元素集合，通过大括号{来判定，如果是则解析后续出现的若干普通表达式即可；对于普通表达式，直接解析即可。FuncFParams：代表函数形参声明部分。函数形参声明可能有若干形参，因此使用for循环进行解析，直至无法解析出FuncFParam为止。根据解析出的形参个数，判定是否存在函数形参声明部分。即如果解析出的形参个数为0，则不存在函数形参部分。FuncFParam：代表每个函数形参的定义部分。对于每个函数形参的定义，存储该形参的数据类型BType和形参标识符Ident。部分形参可能是数组（实际上是有着数组形式的指针），识别标识符后的中括号[]，并将类型存储。BlockItem：代表每个块组成。其可能是声明Decl或语句Stmt。先假定为声明进行解析，若返回值为空，按照语句解析即可。Stmt：代表块中可能出现的语句，推导规则比较复杂，大体可以分为三类：赋值型，特殊功能型，块或表达式。对于赋值型，即LVal '=' Exp ';',LVal '=' 'getint''('')'';',LVal '=' 'getchar''('')'';'，需要通过等号=来判定，如果是赋值型，直接存储即可；如果不是赋值型，此时已经对左值表达式LVal进行了解析，需要进行回溯，因此在解析前应保留解析位置，以便后期回溯。对于特殊型，可以直接通过关键词判断类型：'if' '(' Cond ')' Stmt [ 'else' Stmt ]可以通过if判定，并解析if的条件Cond和需要执行的语句Stmt，如果存在else，则额外解析else需要执行的语句Stmt；'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt可以通过for判定，并解析for的条件Cond和两个for语句ForStmt（如果存在的话），以及需要执行的语句Stmt；';'、'break' ';'和'continue' ';'语句中全部是保留词，直接解析即可；'return' [Exp] ';'可以通过return判定，并解析之后可能出现的表达式Exp；'printf''('StringConst {','Exp}')'';'可以通过printf判定，存储保留词和字符串常量，并解析之后可能出现的若干表达式Exp。对于块或表达式，在排除上述所有情况后，直接解析即可，不会再出现需要回溯的情况。ForStmt：代表for语句，只可能出现左值表达式的赋值。因此解析被赋值的左值表达式LVal和待赋值的普通表达式Exp即可。需注意，判定是ForStmt的标识是赋值的等号=，此时已经对左值表达式LVal进行了解析，如果不是ForStmt则需要进行回溯，因此在解析前应保留解析位置，以便后期回溯。Cond：代表各类语句的条件，只能是逻辑表达式，按照文法，只能是逻辑或表达式LOrExp。因此，直接按照逻辑或表达式LOrExp对其解析即可。LOrExp：代表逻辑或表达式，由逻辑或表达式LOrExp、逻辑或符号||、逻辑与表达式LAndExp组成。由于该文法是左递归文法，如果直接解析会出现无限下降的问题。因此，改写文法，先解析逻辑与表达式LAndExp，如果存在逻辑或符号||，则将其种类变换为逻辑或表达式LOrExp，并按照上述方法继续进行。LAndExp：代表逻辑与表达式，由逻辑与表达式LAndExp、逻辑与符号&&、相等性表达式EqExp组成。由于该文法是左递归文法，因此，按照LOrExp中相似的方法进行解析。EqExp：代表相等性表达式，由相等性表达式EqExp、相等性符号==或!=、关系表达式RelExp组成。由于该文法是左递归文法，因此，按照LOrExp中相似的方法进行解析。RelExp：代表关系表达式，由关系表达式RelExp、关系符号>或<或>=或<=、加减表达式AddExp组成。由于该文法是左递归文法，因此，按照LOrExp中相似的方法进行解析。ConstExp：代表常量表达式，只能是加减表达式。因此，直接按照加减表达式AddExp对其解析即可。同时应指出，由文法规定，常量表达式中出现的全部标识符必须是常量。Exp：代表普通表达式，只能是加减表达式。因此，直接按照加减表达式AddExp对其解析即可。AddExp：代表关系表达式，由加减表达式AddExp、加减符号+或-、乘除表达式MulExp组成。由于该文法是左递归文法，因此，按照LOrExp中相似的方法进行解析。MulExp：代表乘除表达式，由乘除表达式MulExp、乘除符号*或/或%、一元表达式UnaryExp组成。由于该文法是左递归文法，因此，按照LOrExp中相似的方法进行解析。UnaryExp：代表一元表达式，可能是带一元符号的一元表达式，基本表达式或函数调用。对于带一元符号的一元表达式，通过医院符号进行判定，若是则解析一元表达式UnaryExp即可。对于函数调用，通过标识符后的小括号(判定，若是函数调用，则对括号内进行函数实参FuncRParams解析。排除函数调用的情况后，一定是基本表达式，对基本表达式PrimaryExp进行解析即可。FuncRParams：代表函数实参。其由若干普通表达式组成，因此使用for循环进行解析，直至无法解析出Exp为止。PrimaryExp：代表基本表达式。可能是int型常量、char型常量、带小括号的普通表达式或左值表达式LVal。对于int型常量、char型常量，按照数据类型直接解析存储即可。对于带小括号的普通表达式，通过小括号(判定，若是则对后续普通表达式解析即可。对于左值表达式LVal，直接解析即可。LVal：代表左值表达式，主要是标识符（普通变量常量标识符，变量常量数组标识符，带偏移的变量常量数组标识符）。对于不带偏移的标识符（即不存在[Exp]），直接当作标识符Ident处理即可。对于带偏移的变量常量数组标识符，在存储标识符的同时也需要对偏移量表达式解析存储。
对于每一种实现 Syntax 的语法节点，其应有属性 syntaxes ，表示其含有的全部子节点。获得语法树 AST 各节点后，将其存入父节点的 syntaxes 中，并设置函数，使其可以正确输出必要信息。
语义分析设计
语法分析部分分析出的语法树 AST 会存储在编译器中。语义分析部分的主要任务是解析出现的标识符（函数标识符，常量标识符，变量标识符），构建符号表，以便后续代码生成时方便查阅。
对于各类符号，在不同域定义的标识使用范围不同：在外层定义的标识可以在内层使用，而在内层定义的标识不可以在外层使用。相同层不同域定义的标识不可以互相使用。因此，需要建立一种双向树结构，每个节点代表每个符号表项，相同层节点代表相同层的符号表项。建立符号表项类 Table ，其属性有符号表项序号 id ，符号表项的父符号表项 father ，符号表项所处的层数 floor ，符号表项内存储的符号 symbols 。这样在查找符号时，从当前表项出发，从底向上逐层遍历，直至获得当前符号：
1 | public Symbol searchDefinition(String symbolName) { |
需要储存的符号有函数，变量，常量，变量数组以及常量数组。每种符号都有其类型和要储存的属性，应该建立类，规定相应属性：
Symbol：总的符号类，其他符号类的父类，存储有各类符号的基本信息。包括符号序号id，符号所在的符号表项table，符号名name， 符号对应的单词token，符号类型type（可能为"intVar"、"charVar"、"intArray"、"charArray"、"intFunc"、"charFunc"、"voidFunc"）。对于每个属性，建立set和get方法，并设置函数，使其可以正确输出必要信息。VarSymbol：变量常量符号类，继承Symbol。除去Symbol中存储的信息，还应额外存储符号数据类型bType，符号是否代表常量con。在创建该类时，应给出全部必要信息。ArraySymbol：变量常量数组符号类，继承Symbol。除去Symbol中存储的信息，还应额外存储符号数据类型bType，符号是否代表常量con，数组维度dim（应指出SysY语言规定数组为一维）。在创建该类时，应给出全部必要信息。FuncSymbol：函数符号类，继承Symbol。除去Symbol中存储的信息，还应额外存储函数数据类型funcType，函数的形参个数paramNum，函数各形参的类型paramTypes（可能为"intVar"、"charVar"、"intArray"、"charArray"）。在创建该类时，应给出全部必要信息。
完成必需类准备后，可以进行符号的解析与符号表的构建。在语义分析器（符号管理器） Manager 中，读入并遍历语法树 AST ，解析各语法成分，获得新出现的符号，存入相应的符号表项。在遍历过程中，由于函数、块等的存在，符号会出现不同的定义与使用域，因此在遍历过程中，需要注意和维护当前符号所在层数，在层数改变时改变当前符号表（层数增加时新建符号表项，层数减少时转移至当前表项的父符号表项，如不存在则报错）。由于层数改变出现较为频繁，因此封装函数 createTable() 和 quitTable() 。
1 | public void createTable() { |
会发生符号表变更的位置是（主）函数定义，带块的 if 和 for ，普通的块。应指出，虽然这几个位置产生表的变化都是因为块，但不可将符号表项的变更放在块的解析中。这是因为函数定义中可能出现形参，需要存入新符号表项中，因此应该具体问题具体分析。对于不带块的 if 和 for ，根据文法，其后只能是 [Exp] ';' ，不能出现新的声明 Decl ，因此不新建符号表。这些符号表项变化主要出现在 MainFuncDef 、 FuncDef 和 Stmt 中。
MainFuncDef：主函数内的符号表变化，不含形参。主要是在主函数的块内，因此在进入块前调用createTable()，完成块的解析并退出块后调用quitTable()。FuncDef：普通函数内的符号表变化，不含形参。主要是在普通函数的形参声明以及块内，因此在函数进行形参声明前调用createTable()，完成块的解析并退出块后调用quitTable()。Stmt：主要是带块的if、for和 普通的块。在这里，可以进行合并，统一在Stmt → Block的过程中进行。在进入块前调用createTable()，完成块的解析并退出块后调用quitTable()。
对于三种符号 FuncSymbol 、 VarSymbol 、 ArraySymbol ，第一种主要在函数定义中出现（ main 函数可以直接获得符号，无需特殊说明），后两种主要在变量常量定义，函数形参解析中出现。
FuncDef：根据解析的语法成分，获得函数标识符并建立FuncSymbol存储在当前符号表项中。ConstDef/VarDef：根据解析的语法成分（标识符和数据类型），建立VarSymbol或ArraySymbol存储在当前符号表项中。FuncFParam：建立符号的方法基本与ConstDef/VarDef相同，建立VarSymbol或ArraySymbol存储在当前符号表项中。
错误处理设计
按照文法设计与实验安排，本次实验中总共有 a 类错误会出现在词法分析部分，i 、 j 、 k 类错误会出现在语法分析部分，其余错误会出现在语义分析部分。同时，为了统一性和复用性，在实验中建立了错误判定器类 Judgement ，判断每类错误时输入必要信息，获得判断结果。同时 Judgement 内含属性 errors ，存储分析过程中抛出的全部错误。现对每种错误进行分析：
a类错误：非法符号&和|，应该将其当做&&与||进行处理，并在记录单词名称的时候正确记录。这个错误主要在词法分析对&|的分析中出现，判断当前字符与下一个字符是否相同即可。由于出现在词法分析部分，为了错误检测的正常运行（以检测出全部错误），按照出现的第一个字符添加或更改字符，将其作为正确单词存入。判断函数输入的必要信息是当前字符、下一个字符以及当前字符所在行数。b类错误：符号名在当前域下重复定义。应指出，变量在同一级域下重定义会判定错误，不同级作用域下，内层会覆盖外层定义。这个错误主要出现在语义分析符号定义阶段。将当前符号放入当前符号表项搜索，判断是否出现相同名字的符号。判断函数输入的必要信息是当前符号以及当前符号表项。c类错误：使用未定义的标识符。使用当前符号表项或其父符号表项中不含有的的符号，主要出现在语义分析的语句和表达式的解析中。将当前符号在当前符号表以及父符号表等递归搜索，判断是否出现相同名字的符号。判断函数输入的必要信息是当前标识符单词以及当前符号表项。d类错误：函数的形参和实参个数不匹配。主要出现在语义分析的函数调用阶段。在函数定义阶段，有对函数的形参进行存储。在调用阶段（UnaryExp的解析阶段），以,作为分隔符解析函数实参，存储实参的个数。比较形参数组的大小和实参个数即可。判断函数输入的必要信息是当前函数的符号以及实参个数。e类错误：函数的形参和实参类型不匹配。主要出现在语义分析的函数调用阶段。在函数定义阶段，有对函数的形参进行存储。在调用阶段（UnaryExp的解析阶段），以,作为分隔符解析函数实参，存储各实参的类型。比较各形参和各实参的类型是否匹配即可。应注意，类型匹配过程中，普通变量常量允许出现数据转换，即intVar和charVar可以认为是匹配的。其余类型必须完全匹配才可。判断函数输入的必要信息是当前函数的符号以及实参类型数组。f类错误：void类型的函数存在不匹配的return语句。void类型函数如果存在返回语句，返回语句后一定不能出现Exp。主要出现在语义分析的语句分析阶段。在语句分析的过程中，如果出现return，应解析其后单词，判断是否出现Exp。判断函数输入的必要信息是当前函数符号，当前return所在行数以及当前return是否存在返回值。g类错误：int或char类型的函数在函数末尾不存在return语句。为简化问题，实验规定，int或char类型的函数在函数末尾必须存在return语句，即使在if-else控制流语句中出现也不能省略。主要出现在语义分析的函数定义阶段。在控制流外，如果出现return语句，则存储该语句所在域层数returnFloor（这表明该变量一定保留的是最后一个return语句所在的层数，该变量初始化为）；如果 returnFloor的值不等于funcFloor + 1（为时证明不存在 return语句，大于funcFloor + 1时证明该return语句在控制流内），则证明其存在该类错误。判断函数输入的必要信息是函数符号，最后一个return语句所在的层数以及函数块}的行号。h类错误：尝试修改常量的值。主要出现在语义分析的语句和表达式的解析中。在构建语法树时，对于标识符，有属性con判断其是否是常量。因此，在赋值时根据该属性判断是否存在错误即可。判断函数输入的必要信息是常量符号以及是否是对该常量赋值。i类错误：缺少必要的;。这个错误主要出现在语法分析部分，在构建语法树的过程中按照正确文法检测相应位置是否存在;即可。由于出现在语法分析部分，为了错误检测的正常运行（以检测出全部错误），添加缺少的;，以保证当前语法成分的正确性。判断函数输入的必要信息是当前字符、上一个字符所在行数。j类错误：缺少必要的)。这个错误主要出现在语法分析部分，在构建语法树的过程中按照正确文法检测相应位置是否存在)即可。由于出现在语法分析部分，为了错误检测的正常运行（以检测出全部错误），添加缺少的)，以保证当前语法成分的正确性。判断函数输入的必要信息是当前字符、上一个字符所在行数。k类错误：缺少必要的]。这个错误主要出现在语法分析部分，在构建语法树的过程中按照正确文法检测相应位置是否存在]即可。由于出现在语法分析部分，为了错误检测的正常运行（以检测出全部错误），添加缺少的]，以保证当前语法成分的正确性。判断函数输入的必要信息是当前字符、上一个字符所在行数。l类错误：printf字符串中格式字符数量与表达式个数不匹配。文法规定printf函数中可以出现格式字符%d/%c，用于输出int或char类型的算式。该类错误即是格式字符%d/%c与要输出的表达式的数量不同。 主要出现在语义分析的语句printf的解析中。在printf语句解析时，使用正则表达式，获得输出字符串中格式字符的匹配数量，并与解析的表达式个数进行比较。判断函数输入的必要信息是输出字符串以及表达式数量。m类错误：在非循环块中使用break和continue语句。主要出现在语义分析的语句break和continue的解析中。要判断当前语句是否位于循环块中，需要动态维护循环层数forFloor。该属性初值为，仅在进入循环时增加，在退出循环时减少。解析 break/continue语句时，只需要判断循环层数forFloor是否大于即可。 判断函数输入的必要信息是 break/continue语句的行号以及循环层数forFloor。
错误处理主要出现在词法分析、语法分析和语义分析部分。为了尽可能全面地检查出全部错误，按照流程，应保证词法分析和语法分析部分遇到错误不仅需要抛出相应错误，还需要进行修正，以便后续流程进行。错误处理完成后，获取 errors 属性，并输出相应信息。同时 errors 也将作为判断是否能进行代码生成的充分条件。
代码生成设计
在获得语法树 AST 后，可以按照树型结构将其转换为目标代码树。直接转化为目标代码难度较大，因此优先转化为中间代码树，在转换为目标代码树。本次实验中选择的目标代码是MIPS，中间代码是LLVMIR。
中间代码生成设计
在中间代码生成器 Visitor 中，读入语法分析中生成的抽象语法树 AST 和语义分析中生成的符号表 tables ，目标是生成中间代码树 MCT 。对于特定的语法成分，可以对应生成相应的中间代码节点 IR 。LLVMIR中的成分与结构如下图所示：
LLVMIR中的成分主要有模块 Module ，对应语法成分中的 CompUnit ；全局值 GlobalValue ，对应语法成分中直接声明的全局变量常量；函数 Function ，对应语法成分中的 FuncDef ；基本块 BasicBlock ，存有需要先后执行的指令（一个基本块中的指令一定是一同执行的）；指令 Instrunction ，LLVMIR的基本指令，也是转化为MIPS指令的中间形式。一些常用的LLVMIR基本指令如下：
| LLVM IR | 使用方法 | 简介 |
|---|---|---|
add |
<result> = add <ty> <op1>, <op2> |
/ |
sub |
<result> = sub <ty> <op1>, <op2> |
/ |
mul |
<result> = mul <ty> <op1>, <op2> |
/ |
sdiv |
<result> = sdiv <ty> <op1>, <op2> |
有符号除法 |
srem |
<result> = srem <type> <op1>, <op2> |
有符号取余 |
icmp |
<result> = icmp <cond> <ty> <op1>, <op2> |
比较指令 |
and |
<result> = and <ty> <op1>, <op2> |
按位与 |
or |
<result> = or <ty> <op1>, <op2> |
按位或 |
call |
<result> = call [ret attrs] <ty> <name>(<...args>) |
函数调用 |
alloca |
<result> = alloca <type> |
分配内存 |
load |
<result> = load <ty>, ptr <pointer> |
读取内存 |
store |
store <ty> <value>, ptr <pointer> |
写内存 |
getelementptr |
<result> = getelementptr <ty>, ptr <ptrval> {, <ty> <idx>}* |
计算目标元素的位置（数组部分会单独详细说明） |
phi |
<result> = phi [fast-math-flags] <ty> [<val0>, <label0>], ... |
/ |
zext..to |
<result> = zext <ty> <value> to <ty2> |
将 ty 的 value 的 type 扩充为 ty2（zero extend） |
trunc..to |
<result> = trunc <ty> <value> to <ty2> |
将 ty 的 value 的 type 缩减为 ty2（truncate） |
br |
br i1 <cond>, label <iftrue>, label <iffalse> br label <dest> |
改变控制流 |
ret |
ret <type> <value>, ret void |
退出当前函数，并返回值 |
想要对中间代码成分进行分析，首先应为各成分建立类型类 ValurTypeIR 。根据代码生成中出现的变量类型，可将其分为两类，基本类型和复合类型。
- 基本变量类型：
IntegerTypeIR：位数据类型，含有属性位数bits，代表数据所占的位数。bits = 32，代表int类型；bits = 8，代表char类型；bits = 1，代表bool类型。VoidTypeIR：void数据类型，仅FunctionIR中会出现。LabelTypeIR：标签类型，代表当前变量的类型为标签。
- 复合变量类型：
ArrayTypeIR：数组类型，含有属性数组元素类型typeIR、数组元素个数elementNum。其中，本实验中规定数组元素类型typeIR仅能为位数据类型IntegerTypeIR，即只存在int/char类型的数组。PointerTypeIR：指针类型，含有属性指针对象类型typeIR。其中，本实验中规定指针所指对象类型为数组类型ArrayTypeIR（当含有为数组申请地址的指令时）和位数据类型IntegerTypeIR（当含有普通地址指令时）。FunctionTypeIR：函数类型，含有属性函数数据类型typeIR、函数形参数据类型paramTypes。
在建立成分类型类后，为各中间代码成分构建类，并对语法树 AST 遍历解析获得中间代码成分。所有的中间代码节点（除顶层模块），均继承于中间代码值类 ValueIR 。该类主要代表各种中间代码索要使用的值，最常用的子类是 FunctionIR （用于函数调用等指令中）、 BasicBlockIR （用于跳转等指令中）等。构建的中间代码成分类如下：
ModuleIR：中间代码中的模块，代表整个程序。由于本次实验中涉及的待编译SysY语言文件都是单文件，因此ModuleIR唯一。其含有属性全局变量声明globalVariables、函数声明functions。在CompUnit解析中获得ModuleIR。GlobalVariableIR：中间代码中的全局变量声明。其含有属性变量名name、初始值initValue、是否是输出字符串isPrint。在Decl中，根据当前变量常量所在层数判断其是否是全局变量常量。FunctionIR：中间代码中的函数（包括主函数）。其含有属性函数名name、函数参数params、函数含有的基本块blocks、函数中变量数量numVar。在FuncDef解析中获得FunctionIR。LLVMIR中变量以序号表示，每个函数中的变量编号均从开始，因此可以内置函数 allocVar，为函数申请新变量。1
2
3
4
5public VariableIR allocVar(ValueTypeIR typeIR) {
VariableIR var = new VariableIR(typeIR, numVar, name);
numVar++;
return var;
}BasicBlockIR：中间代码中的基本块，存储需要一同执行的LLVMIR指令。其含有属性基本块标签label、基本块是否可以添加指令canAddInstr、基本块含有的指令instrs。在Block的解析中获得BasicBlockIR（由于申请到的块在Block外可能需要使用，因此将新BasicBlockIR的申请放在FuncDef或Stmt的解析中）。在if或for这种含有条件Cond解析的语句中，需要注意额外新BasicBlockIR的申请。对于普通的
Cond判断，其结构应该是condBlock-trueBlock-falseBlock。条件判断块condBlock中含有跳转指令br cond, trueLabel, falseLabel。在条件Cond的解析中，需要满足短路求值原则。即对于逻辑与表达式和逻辑或表达式，当左侧表达式可以确定整体表达式值时，不访问右侧表达式。这意味着，当前访问表达式之前的表达式计算结果为真。对于不同形式的表达式，由于短路求值原则，跳转的标签也有所不同。- 对于逻辑或表达式
B1 || B2，B1对应的基本块block1的跳转指令，为真跳转到trueLabel，为假跳转到B2Label；B2对应的基本块block2的跳转指令，为真跳转到trueLabel，为假跳转到falseLabel。 - 对于逻辑与表达式
B1 && B2，B1对应的基本块block1的跳转指令，为真跳转到B2Label，为假跳转到falseLabel；B2对应的基本块block2的跳转指令，为真跳转到trueLabel，为假跳转到falseLabel。 - 对于逻辑与或组合表达式
B1 && B2 || B3，B1对应的基本块block1的跳转指令，为真跳转到B2Label，为假跳转到B3Label；B2对应的基本块block2的跳转指令，为真跳转到trueLabel，为假跳转到B3Label；B3对应的基本块block3的跳转指令，为真跳转到trueLabel，为假跳转到falseLabel。 - 对于逻辑与或组合表达式
B1 || B2 && B3，B1对应的基本块block1的跳转指令，为真跳转到trueLabel，为假跳转到B2Label；B2对应的基本块block2的跳转指令，为真跳转到B3Label，为假跳转到falseLabel；B3对应的基本块block3的跳转指令，为真跳转到trueLabel，为假跳转到falseLabel。
由于在
Cond的解析函数中，无法获得具体的表达式的数量，因此只能在逻辑与或表达式的解析中创建新的基本块。在解析与或表达式时，出现与或符号，证明还存在下一个表达式，则在解析当前表达式之前应该建立新的基本块。解析逻辑或表达式新建的基本块（nextOrBlock，下一个逻辑或表达式块）应当一同传入逻辑与表达式的解析函数中。同时可以观察到，像B1 || B2 && B3这种形式，B2后不存在下一个逻辑或表达式块，为假时跳转到falseLabel。因此，在逻辑或表达式新建基本块时应判断当前是否是最后一个逻辑或表达式，以决定跳转指令的目标。同时，应注意，LLVMIR规定，一个基本块中只能出现一个改变控制流的指令（
br或ret），因此在基本块出现该类指令后将canAddInstr置为false，后续产生的指令不能再添加到该基本块中。- 对于逻辑或表达式
ConstIR：中间代码中的常量。其含有属性常量数值value。ConstArrayIR：中间代码中的数组常量，继承ConstIR。其含有属性数组元素values。ConstStringIR：中间代码中的字符串常量，继承ConstIR。区别于普通的字符串常量（那将在字符数组的初始化中解决），这个字符串常量专指printf中的输出字符串。其含有属性字符串名name、字符串值value、字符串长度length。
VariableIR：中间代码中的变量。其含有属性变量名name、变量编号pos、变量值value、是否是全局变量isGlobal。对于普通变量和全局变量，其所使用的属性不同：全局变量使用变量名、变量值，局部变量使用变量编号、变量值。InstrIR：中间代码中的指令。其含有属性操作符号op。AllocateIR：申请地址的指令，含有属性申请结果result、申请类型type。主要出现在变量常量声明中，为要声明的标识申请足够的存储地址。StoreIR：存储变量的指令，含有属性存储值value、存储地址address。主要出现在赋值语句中，将新值存储在变量对应的地址。LoadIR：加载变量的指令，含有属性加载到的值value、加载地址address。主要出现在对变量的使用语句中，将变量的值从对应地址中取出并参与运算。CallIR：调用函数的指令，含有属性调用函数function、函数返回值result（函数是void型时为空）、函数实参params。主要出现在一元表达式的函数调用中，确定调用函数，将解析的表达式作为实参存入指令，获得返回值。GetElementIR：计算数组元素地址的指令，含有属性元素地址result、数组基地址address、元素索引index。主要出现在数组元素的访问中。BinaryIR：二元有符号计算指令，含有属性左值lValue、右值rValue、结果result。主要出现在加减乘除表达式的解析中，根据计算类型设置指令类型。BTypeTranIR：数据类型转换指令，含有属性转换值value、转换结果result。主要出现在各种数据类型转换的赋值中。IcmpIR：数据比较指令，含有属性左值lValue、右值rValue、结果result。主要出现在关系表达式和相等性表达式。BrIR：跳转指令，含有属性是否存在条件haveCond、跳转块block、跳转条件cond、为真时跳转块trueBlock、为假时跳转块falseBlock。有条件的跳转指令使用跳转条件、为真时跳转块、为假时跳转块；无条件的跳转指令使用跳转块。主要出现在各BasicBlock末尾改变控制流。RetIR：返回指令，含有属性返回结果result（函数是void型时为空）。主要出现在return语句的解析中。
完成全部预备类构建后，即可遍历语法树 AST ，按照上文中所述的解析方式，构建对应的LLVMIR成分，组成中间代码树 MCT 。
目标代码生成设计
在目标代码翻译器 Translator 中，读入生成的中间代码树 MCT ，目标是生成目标代码树 OCT 。目标代码的结构与中间代码相似，顶层模块 ModuleMips 、全局声明 GlobalMips 、函数 FunctionIR 、基本块 BlockMips 、指令 InstrMips 。因此，目标代码生成的主要思路是遍历中间代码树，生成对应的目标代码部分。
对于模块 ModuleIR 、全局声明 GlobalVariableIR 、基本块 BasicBlockIR 的遍历解析，难度较小，基本为直译，因此不过多赘述。主要说明函数 FunctionIR 和指令 InstrIR 的翻译。此次实验中使用到的MIPS指令如下：
| MIPS | 使用方法 | 简介 |
|---|---|---|
La |
La $1, <label> |
从标签加载数值 |
Li |
Li $1, <value> |
从立即数加载数值 |
move |
move $1, $2 |
将寄存器值赋给另一寄存器 |
mfhi |
mfhi $1 |
读 hi 寄存器 |
mflo |
mflo $1 |
读 lo 寄存器 |
addu |
addu $1, $2, $3 |
无符号加 |
addiu |
addiu $1, $2, <value> |
无符号加立即数 |
subu |
subu $1, $2, $3 |
无符号减 |
mult |
mult $1, $2 |
有符号乘 |
div |
div $1, $2 |
有符号除 |
slt |
slt $1, $2, $3 |
有符号小于置1 |
andi |
andi $1, $2, $3 |
与立即数 |
sll |
sll $1, $2, <offset> |
逻辑左移 |
srl |
srl $1, $2, <offset> |
逻辑右移 |
sra |
sra $1, $2, <offset> |
算术右移 |
lw |
lw $1, <offset>($2) |
加载字 |
sw |
sw $1, <offset>($2) |
存储字 |
beq |
beq $1, $2, <label> |
相等时转移 |
bne |
bne $1, $2, <label> |
不等时转移 |
bgez |
bgez $1, <label> |
大于等于0时转移 |
blez |
blez $1, <label> |
小于等于0时转移 |
bgtz |
bgtz $1, <label> |
大于0时转移 |
bltz |
bltz $1, <label> |
小于0时转移 |
j |
j <label> |
跳转 |
jal |
jal <label> |
跳转并链接 |
jr |
jr $1 |
跳转至寄存器 |
syscall |
syscall |
系统调用 |
对于MIPS指令的翻译，最重要的是寄存器的存储和分配系统的建立。建立寄存器类 Register ，其含有属性名称 name 、编号 id 、是否正在使用 use 、寄存器中值 value 。同时建立寄存器表类 RegisterTable ，负责寄存器的管理。对于寄存器的分配，采用的策略是如果有未在使用的寄存器，即分配该寄存器；如果全部寄存器都在使用，则将 $t0 的值压入数据栈中，分配 $t0 。对于该种分配方法，核心是寄存器应该在何时释放。寄存器的释放原则是每次存入寄存器的值只能使用一次，使用后立即释放（出于正确性考虑，再使用寄存器前，应检查该寄存器内数据是否是当前变量），以防止寄存器数量不够用以及控制流改变引发的寄存器冲突问题。寄存器的释放过程在指令中进行。
由于每一个 VariableIR 可能被不止一次使用，因此应该建立中间代码变量符号表，以便后续使用。建立中间代码符号类 SymbolMips ，其含有属性变量名 name 、是否是全局声明 isGlobal 、是否是立即数 isImm 、是否是绝对地址 isAbsolute 、分配的寄存器 register 、数值 value 、存储的相对地址 addrOffset 。对于普通变量或立即数，填写相应属性即可。对于代表地址的变量，则需要要特殊处理。对于存储全局声明标签的变量，需要标记 isAbsolute 为真，后续使用时可能出现相对地址与绝对地址之间的转化。
在完成预备类的构建后，进行 InstrIR 的翻译：
AllocateIR：为变量申请地址，不增加MIPS指令，只改变当前的offset。为变量构建中间代码变量符号，并将当前相对 的偏移量offset赋值给相应属性即可。按照申请的地址大小，增加offset的值（int/char型均按照一个字节存储，变量为数组时按照元素数量改变offset的值）。StoreIR：存储变量，使用sw $1, <offset>($2)即可。应注意判断存储到的指针变量类型：若该变量是相对地址，则使用sw $1, <offset>($sp)；若该变量是绝对地址，则使用sw $1, 0($2)。完成存储后，释放分配给值变量和地址变量的寄存器。LoadIR：加载变量，使用lw $1, <offset>($2)即可。对于待加载的指针变量类型的判定和StoreIR相同。完成加载后，释放分配给地址变量的寄存器。CallIR：调用函数，使用jal <label>跳转到函数位置即可。GetElementIR：计算数组元素地址，elementAddr = baseAddr + index * 4，elementAddr统一使用绝对地址。如果基地址为绝对地址，直接使用sll和addu指令计算即可。如果基地址为相对地址，则需要额外加$sp。完成计算后，释放分配给基地址变量和索引变量的寄存器。BinaryIR：二元有符号计算，使用对应的二元计算指令即可。应注意，为防止计算中的数值溢出，加减指令应使用addu和subu。对于乘除模，使用mult、div指令搭配mfhi、mflo指令即可。完成计算后，释放分配给算式左值右值的寄存器。BTypeTranIR：数据类型转换，由于int/char型均按照一个字节存储，理论上结果变量使用值变量的寄存器即可。但应注意，对于trunc指令，将int型缩减到char型，高24位数据应当舍弃。因此若为trunc指令，则添加andi $1, $2, 0xff。IcmpIR：二元有符号比较，按照比较类型添加指令即可。由于LLVMIR中是先比较得到结果再进行跳转，而MIPS中只有slt一种比较指令，其他类型比较只有直接的跳转指令。因此为了不破坏LLVMIR指令的原子性，需要使用组合的slt指令。将<=/>=转化为!>/!<，==/!=转化为!> && !</> || <，使用slt搭配逻辑运算指令即可实现其他类型的比较。完后比较后，释放分配给比较式左值右值的寄存器。BrIR：各类跳转。对于br label，可直接翻译为j <label>；对于br cond, trueLabel, falseLabel，可翻译为beq cond, 0, <falseLabel>与j <trueLabel>的组合。对于后者，完成比较后，释放分配给条件的寄存器。RetIR：函数返回。对于存在返回值的RetIR指令，首先需要将返回值赋值给$v0及$v1。由于文法中规定，返回值至多为一个值，因此只使用$v0即足够。完成赋值后，jr $ra返回调用前下一条指令即可。
由于MIPS中只存在全局寄存器和数据栈，不存在函数形参和实参的概念，因此 FunctionMips 的处理与 FunctionIR 的处理有所不同。在调用函数时，首先应进行压栈，将目前全部寄存器中的数据压入栈中，并按照压栈的数据数量改变 $sp 的值，防止函数解析时改变寄存器值而造成的错误。将实参解析后存入 $a0 - $a3 寄存器中，如果实参数量超过 $sp 和实参取出并存在栈中。由于可能存在参数数量超过 $a0 对应的参数应当存入 offset = 4 的地址，会造成形参的污染，因此形参的存储应从后向前进行。函数解析中如果出现调用其他函数的情况，重复上述操作即可。行进到 ret 语句时取出 $sp ，并加入 jr $ra 。完成函数解析并返回调用前下一条指令后，将调用前压入栈中的数据从栈中取出（在出栈前可以先释放全部临时寄存器，以防函数遗留数据导致寄存器后期无法使用），并按照压栈的数据数量改变 $sp 的值。
代码优化
中间代码优化
中间代码优化主要有以SSA形式建立中间语言、死代码删除、GVN&GCN建立、常量提取等。由于时间原因，本次实验中编译器未进行中间代码优化。
目标代码优化
目标代码优化主要有指令选择、图着色寄存器分配、乘除法优化、基本块合并和窥孔优化。本次实验中，主要完成了指令选择、无用指令删除、乘除法优化。
指令选择
为了实现更多功能，以及更加方便翻译高级语言，MIPS提供了大量的伪指令使用，例如subi、move、ble 等，能够缩短指令的条数，增加代码的可读性。但实际上，伪指令会被翻译为多条实际指令进行使用。以 subi 为例，一条 subi $1, $2, 1000 的指令，会被MIPS的模拟器Mars翻译为 addi $3, $0, 0x3e8 和 sub $1, $2, $3 两条指令；但是如果直接使用 addi $1, $2, -1000 的指令，不会被翻译为额外指令，可以提高程序执行效率。因此，将全部 subi 指令替换为 addi 指令。程序中涉及到 subi 指令的部分主要是调用函数时 $sp 的改变，将这部分指令替换即可。
在目标代码翻译的过程中，出于保护LLVMIR指令原子性的考虑，将 IcmpIR 翻译为 slt 和逻辑运算指令搭配的形式，如 %res = icmp eq i32 %1, %2 ，翻译为MIPS指令就是 slt $t2, $t1, $t0 、 slt $t1, $t0, $t1 、 or $t2, $t2, $t1 、 xor $t2, $t2, 1 四条指令，最终寄存器 $t2 存储的就是比较结果。由于比较式出现在 Cond 中，其后通常伴随着跳转指令，因此可以对其进行优化。比如说源代码 if(i == 1) {...} ，直接生成LLVMIR指令如下：
1 | %main_var2 = load i32, i32* %main_var1 |
优化前优化后的MIPS指令如下：
1 | # 优化前： |
其他比较类型 != | >= | <= 与上述优化相似。
无用指令删除
在MIPS指令中，每个基本块不强制要求出现改变控制流的跳转指令，如果该块不存在跳转指令，则默认按照顺序执行。由于在目标代码翻译的过程中，对于带条件的 br 指令 br cond, trueLabel, falseLabel ，采取的翻译模式是 beq cond, 0, <falseLabel> 与 j <trueLabel> 的组合，而通常来讲 j <trueLabel> 跳转到的 trueBlock 即是下一个基本块。同时，在中间代码生成的过程中，可能会出现仅含有 br 指令的基本块。这类块在目标代码翻译中会被翻译为 j <label> ，且通常跳转到下一个基本块。在这些情况中，会出现多余的跳转指令。因此可以特判跳转指令，如果跳转到的 <label> 和下一个块的标签相同，则省略这条跳转指令。
乘除法优化
在MIPS指令中，乘除法计算指令 mult 和 div 消耗时间相比 sll 、srl 等移位指令， addu 、subu 等计算指令过大，需要进行一定优化。按照程序设置，在中间代码生成的过程中，当表达式左右两侧都为常量值时，会直接计算出结果。因此在目标代码翻译的过程中，只可能出现两个变量计算或一个变量一个常量值计算。乘除法优化基于一个变量一个常量值计算进行，主要原理是通过判定常量值是否是特定数值，优化乘除计算指令。在优化过程中，我们保证除数为正，当除数为负数时添加 subu $1, $0, $1$ 即可。
乘法优化
- 数值为
：可以直接对结果寄存器赋 值。 - 数值为
的幂数：使用 sll指令，计算该常量对于的幂次，左移相应位数。 - 数值与小于它的最大
的幂数差小于 ：按照实验设定， mult的时间消耗是sll、addu的倍，因此部分乘数可以分解为 sll + n * addu的形式，如数值为10 = 8 + 2，此时将x * 10就可以转变为x << 3 + x + x，时间变短。数值与大于它的最小的幂数差小于 的同理，分解为 sll + n * subu的形式。 - 其他数值：无法进行优化，正常添加指令即可。
除法优化
数值为1：可以直接对结果寄存器赋原值。
数值为2的幂数：使用
sra指令，计算该常量对于2的幂次，右移相应位数。移位计算的结果是除法结果向下取整，如、 。若被除数小于 ，除法结果应当是移位计算结果加1。因此，首先使用 srl $2, $1, 31获得被除数的符号位，并与移位结果相加（若被除数为正，符号位为，除法结果等于移位计算结果；若被除数为负，符号位为 ，除法结果等于移位计算结果加 ）。 其他数值：按照实验设定，
div指令的时间消耗远大于mult的，因此可以借助乘法来优化除法。基本原理是先对原被除数乘一个大数，再右移获得最终结果。这个大数既要保证乘之后可以保证原除法结果，又要保证除法结果已经全部位于hi寄存器中。对于被除数、除数 、大数 ，存在关系： ，其中大数 满足 ，常数 保证该大数满足要求。为简化大数 的取值，设定 。可以得到代码如下： 1
2
3
4
5
6
7
8
9
10
11
12
13
14int l = 1;
int m = (int) (Math.pow(2, 32 + l) / valueAbs);
if (!(Math.pow(2, 32 + l) <= ((long) m) * valueAbs &&
((long) m) * valueAbs <= Math.pow(2, 32 + l) + Math.pow(2, l))) {
m++;
} // 保证m满足条件
SymbolMips rSym = new SymbolMips(m);
symUseReg(rSym);
curBlock.addInstr(new MultMips(lSym.getRegister(), rSym.getRegister()));
curBlock.addInstr(new MfhiMips(resSym.getRegister()));
curBlock.addInstr(new SraMips(resSym.getRegister(), resSym.getRegister(), l));
curBlock.addInstr(new SrlMips(lSym.getRegister(), lSym.getRegister(), 31));
curBlock.addInstr(new AdduMips(resSym.getRegister(), resSym.getRegister(), lSym.getRegister()));
rSym.getRegister().freeReg();
对于乘法优化，左值右值为常量时均可进行；对于除法优化，被除数为常量时不能进行，除数为常量时可以进行。
实验感想
本次实验确实是一次量大难度高的任务，极具挑战性。在实验中，需要按照流程建立一套编译程序，从读入程序字符串出发，直到翻译为机器码，并能够执行获得结果。实验的架构设计是较为明确的，课程组提供的流程十分科学，可以进行模块化开发，词法分析、语法分析、符号表建立、中间代码生成、目标代码翻译，每一个模块相互独立，建立接口实现两两之间的信息交互。本次实验更像是在学完各种课程后的一次实战演练，将之前在计算机组成、操作系统等课中学到的各类知识结合运用起来。实验涉及的知识点很多，字符串解析、层次分析法、有限状态机等。可以使用的设计理念也有很多，如单例模式、工厂模式、观察者模式等。本次实验也是继OO课设后第一次自行设计实现大型项目，十分强调程序的层次化模块化抽象化，不仅锻炼了我的编码能力，还锻炼了我的架构设计思维。在实现编译流程后，还进行了一定的代码优化工作。这些工作向我展示了编译程序的底层优化逻辑，从程序结构和底层机器码的角度出发，既有对于无用部分的删除，也有偏硬方面的优化。美中不足的是，由于各项课程事务繁多，无法再对设计的编译器做进一步优化。整体来说，实验难度很大，从高级语言、LLVMIR到MIPS，结构理念都有很大的不同，每一次转换都是一种挑战，每一个语言下的Bug都曾令我困扰良久。但看着完成的七八千行代码，以及可以成功编译执行的各个代码文件，内心十分有成就感。文档末尾，是对一学期课程的反思与告别。也想感谢理论课老师、两位帮助我颇多的助教和每一位一同进步的同学，使得我能够在这条艰难的路上一直走下去。