SysY语言编译器设计文档

2022编译器设计文档

项目源码在此库中，如果觉得对你有所启发的话，请给个star吧！🥰源码库

词法分析设计

编码前的设计

代码结构总体设计

• 构造了一个词法分析器类：Lexer，其功能是完成词法分析，因此这个类封装了完成词法分析所需要的所有方法；同时lexer类还实现了error接口,用来处理词法分析过中可能实现的错误；
• 构造了一个单词信息类：WordInfo，其功能是储存通过词法分析获得的单词的内容，类别码等信息；对于类别码是IntConst的单词，还会存储它的数值。

词法分析的具体实现方案

• 总体实现方法: 词法分析函数每次读入一个字符，然后根据这个字符的值进入不同的分支，并且在该分支之下一定会完成一个单词类别码的分析或注释的处理。
• 实现难点:
  1. 字符串的处理: SysY语言中的字符串一定是被"所包裹的,因此只要识别到字符"就进入字符串处理分支, 一直读取字符直到读到下一个"。这个过程可能出现如下错误: 在读到下一个"之前结束; 读取字符过程中出现非法字符(非法字符的定义详见错误处理); %或\单独出现(文法规定必须是%d和\n);
  2. 双字符符号的识别: 对于!=、>=、<=、==、&&、||这些双字符符号, 在读到对应的前缀进入对应的条件分支时, 需要预读一个字符,假如说可以组成文法定义的双字符, 则将其添加为双字符符号, 否则进行符号回退, 并且只处理前缀。
  3. 注释的处理: 由于字符串通过一个独立的分支处理, 因此字符串中的//、/*、*/不会被识别为注释; 同时一旦确定读取到//或/*,在读到换行符或*/之前不会对注释字符进行任何语法上的分析。因此也同时避免将注释内容误认为语法成分。
  4. 标识符的处理: 只要是以字母和下划线开头, 就进入标识符处理分支, 直到字符既不是字母、数字或者下划线。
  5. 换行: 注意在不同操作系统下的换行符可能有不同的情况,因此需要进行相关处理; 同时后续的错误处理作业中会有要求输出错误片段对应的行号的要求,因此要注意保存行号。

编码后的修改

考虑到词法分析中部分函数可能在其它功能中也需要使用，使代码的结构更加清晰合理，因此新建一个名字为Tools的工具类，而Lexer类只保留最主要的词法分析相关的方法，将字符串判断和处理函数这些与词法分析功能关联不大的方法转移到Tools类中，将其作为一个专门存储通用的静态方法的工具类使用。

语法分析设计

代码结构总体设计

• 构造了一个语法分析类：SyntacticParser，其功能是完成语法分析，因此这个类有着语法分析所需要的大部分静态方法；同时SyntacticParser类还实现了error接口，为错误处理部分预留了接口。
• 新建了一个类ParseInfo，其继承于抽象类WordInfo，用于在语法分析过程中存储非终结符，便于输出。
• 在Tools类中新添了一些语法分析所必须的方法。

语法分析具体实现方案

• 实现方案：本编译器采用的是递归下降分析法（一种自顶向下的分析方法）来实现语法分析。即为每一个非终结符编写一个递归子程序，用于完成该非终结符对应的语法成分的分析与识别任务。
• 实现难点：
  1. 语法匹配：在SysY语言的文法中，有许多非终结符的推导存在多个分支，且它们之间的FIRST集的交不为空。因此为了避免在语法分析过程中发生回溯，我采取的方案是进行预读，直到能够区分该进入哪一个分支，因此在语法分析类SyntacticParser中增加了一个回退读指针(对应类中变量WordlistIndex)的方法，用于把读指针回退到预读前的状态。
  2. 文法改写：原文法中存在左递归文法，而递归向下分析法是没有办法处理左递归文法的，因此我们需要对文法进行改写以消除左递归，并且保证文法改写前后的等价性。

语法树设计

本编译器在使用递归下降分析法进行语法分析的同时建立源程序的语法树。后续的语义分析、中间代码生成都是在语法树的基础上进行的，下面是语法树的类的设计思路：

• 这部分类位于 ./src/front/SyntaxTree 中。
• 首先所有的语法树节点都继承了接口 TreeNode ，实现了获取其子节点序列(实现遍历)和生成中间代码两个方法；同时为文法中每一个非终结符设置了一个类，代表一个节点，实现了接口TreeNode 的方法。
• 除了为文法中的非终结符设计一个节点类，为了实现错误处理的相关功能，我们还增加了ErrorSymbol 节点来保存错误处理所需要的信息。

符号表设计

类的设计

• SymbolTable ：由于SysY语言属于分程序结构语言，需要为每一个分程序建立一个符号表，类变量中的fatherTable指向其外层符号表；symbolList存储的是符号表项；sonTable存储着该层下所有的符号表。
• SymbolItem ：符号表项接口，里面定义了获取符号表项信息的所有方法getName获取变量名；isConst判断是否为常量；getSize获取当前表项变量所占内存大小；setAddr是设置表项变量在内存的地址；getAddr是获取表项变量在内存的地址。
• Func：符号表项的函数项的类，该类可以存储函数名，函数参数个数，函数返回值的种类等信息，同时实现了symbolItem接口中定义的所有方法。
• FuncFormVar ：符号表项中的函数参数项的类。该类存储了编译过程中函数参数所必需的信息：名字name，维数dimension，数组维数参数shape，地址addr等信息。同时实现了symbolItem接口中定义的所有方法。
• Var：符号表项中的变量项的类。该类存储了编译过程中变量所必需的信息：名字 name，是否为常量isConst，变量初始化值initVal，常量初始化值constInitVal，维数dimension，数组维数参数shape，地址addr等信息。

为了处理不同模块下变量出现重名的情况，还添加了loc字段，其内容为块号@块内号，在name后面加上loc字段就可以唯一标识变量名。

错误处理设计

类的设计

为了实现错误处理,我们在front增加了一个继承了Exception类的Error类，用于记录错误种类和所在行，并且改写了toString方法，使其能打印出符合要求的错误信息。

我还在front模块设计了添加了一个ErrorList类，用于存储编译过程中源程序可能存在的错误，并且在其中实现了把错误输出到error.txt的方法。

编译器可处理的错误类型

error类能够处理如下错误:

错误类别码	解释
a	非法符号(报错行号在所在行)
b	同一作用域下名字重定义(所在行)
c	未定义的名字(所在行)
d	函数参数个数不匹配(函数名调用语句的函数名所在的行)
e	函数参数类型不匹配(函数名调用语句的函数名所在的行)
f	无返回值的函数存在不匹配的return语句(return所在行)
g	有返回值的函数缺少return语句(函数结尾’}’所在行)
h	不能改变常量的值(所在行)
i	缺少分号(缺少分号的前一个非终结符所在行)
j	缺少右小括号’)’(缺少右小括号前一个非终结符所在行)
k	缺少右小括号’)’(缺少右小括号前一个非终结符所在行)
l	printf中’%d’数量宇表达式个数不匹配(printf所在行)
m	在非循环模块使用break、continue(break、continue所在行)
n	其他错误

在本编译器中在词法分析、语法分析、生从语法树、构建符号表的过程中就可以完成。只有在源程序没有错误的情况下编译器才会进行中间代码和目标代码的生成。

代码生成设计

中间代码生成

在接口TreeNode中添加方法createMidCode(),再在具体的节点中实现该方法。

本编译器的中间代码采用形如以下的四元式：

(operation, operand1, operand2, result)，依次为运算符，运算数1，运算数2，结果。

本编译器涉及常量声明、变量声明、读语句、写语句、赋值语句、加减乘除模等运算语句、函数定义及调用语句，此部分的operation相关定义如下：

# 基本算数运算
ASSIGN    # 赋值
ADD       # 加
SUB       # 减
MUL       # 乘
DIV       # 除
MOD       # 模
SET       # 逻辑判断
NOT       # 非

# 函数相关部分
FUNC          # 函数定义
END_FUNC      # 函数结束标志
PREPARE_CALL  # 函数调用准备
CALL          # 函数调用
PUSH_PARA     # 函数参数传递
RETURN        # 函数返回语句

# 变量定义部分
VAR_DEF           # 变量定义
CONST_DEF         # 常量定义
FUNC_FORM_VAR_DEF # 函数参数定义

# 数组操作
ARR_SAVE      # 保存数组值到内存
ARR_LOAD      # 读取数组值到寄存器
PUSH_PARA_ARR # 传递数组的地址(数组作为函数参数)

# 跳转操作
JUMP_IF
JUMP
LABEL

# IO
PRINT
GETINT

# 跳转
OP_JUMP_IF "JUMP_IF"
OP_JUMP "JUMP"
OP_LABEL "LABEL"
LVal: 变量名@<depth,block序号>
shape: 初值为-1时说明是函数的参数值(Array)

# 其它
SIGNAL_ARR_ADDR   # 该变量为数组
NEW_BLOCK         # 基本块的开始
EXIT_BLOCK        # 基本块的结束
WHILE_BIND        # 绑定循环判断式和跳转标签
EMPTY             # 空语句
ENTER_WHILE       # 循环的开头
EXIT_WHILE        # 循环的结尾

实现过程

在实现产生四元式的过程中，从语法树的根节点开始调用createMidCode完成一次后序遍历，期间生成中间代码，为了实现代码结构的解耦，语法树中的节点类中添加新的代码时，会传递参数#TEMP，由MidCodeList类负责分配新的临时变量，对于操作数少于四个的指令，传递#NULL占位，同时对于某些需要实现跳转的指令，部分四元式中存在参数#AUTO_LABEL，通过MidCodeList类负责分配新的跳转标签，对于字符串输出，则采用参数#STRCONS进行占位。

Mips代码生成

类构成分析

该部分的代码都位于/src/back文件夹中,下面是相关类的介绍：

• Mips：Mips代码生成的最主要的类，实现了Mips代码生成的大部分逻辑。
  • createMipsCode：Mips类中实现代码生成的主要逻辑，首先查询符号表对所有的数组在.data段进行声明和内存分配，把输出的所有formatString保存到内存里。然后进行.text段代码编写：最后遍历中间代码生成Mips代码。
  • GenArithmetic：生成算数相关的Mips代码的函数。
  • addOneMipsCode：添加一条Mips代码。
  • isConst：判断变量是否为常量。
  • setRegister：为变量分配寄存器。
  • loadValue：从内存读取数据。
  • saveValue：保存数据到内存。
  • isInRegister：判断变量是否分配了寄存器。
  • PrintMipsCode：输出Mips代码。
• Tools：存储Mips代码生成过程中使用的一些方法。

普通变量寻址

以函数为单位合并符号表，对于每一张符号表，确定新的所需空间的大小和每个变量的地址偏移，每次在进入函数前，将栈指针sp向下移动相同的单位，每次读到一个中间代码的变量名时，若发现其不在寄存器中或者需要写入内存，则查相应的函数符号表和全局符号表，获得变量在内存的地址。

数组变量寻址

直接查找.data段的数组名进行寻址。

函数运行栈布局

• funcStackSize：函数中出现的所有局部变量的所需空间；
• StackTBegin：栈中保存t寄存器的偏移量为60；
• StackSBegin：栈中保存s寄存器的偏移量为60；
• LocalAddrInit：局部变量的起始地址。

上述变量的单位均为byte。

函数跳转流程

1. 栈指针sp下移funcStackSize + LocalAddrInit的空间；
2. 使用寄存器$a0 ~ $a3传递前四个参数；
3. 以(sp)为基址，传递多出来的参数；
4. 以funcStackSize + StackSBegin为基址，保存所有储存在寄存器$s中的变量。
5. 使用指令jal跳转。

寄存器分配

在每次进入函数时，按照符号表的顺序为变量分配所有的t寄存器和s寄存器，并建立绑定关系。在翻译四元式时，对于中间代码中的变量，查看其是否被分配了寄存器，若是，则直接返回此寄存器，否则用临时寄存器保存该变量在内存中的值，返回此临时寄存器。

四元式翻译

• 基本运算
  • 将三个操作数中的中间变量转化为变量所在的寄存器(若未分配寄存器则通过lw加载到临时寄存器中)。
  • 将中间代码翻译为对应的mips指令。
  • 结果寄存器若使用的是临时寄存器$t则写回内存。
• IO操作
  • 对于GETINT则直接执行系统调用li $v0, 5 \n syscall，结果赋值给对应变量。
  • 若PRINT的为#STRCONS(字符串)，则先获取位于.data段中对应的地址，再进行系统调用；
  • 若为一个数字，则将该变量存入$a0后执行系统调用。
• 函数调用
  • 在PREPARE_CALL时，修改栈指针sp；
  • 在PUSH_PARA时，将变量的值或者数组的首地址保存到指定的offset(sp)的位置；
  • 在CALL时，先保存所有$s和$t寄存器和$ra寄存器，在通过jal指令跳转到函数中，调用结束后再恢复这些寄存器。
• 跳转
  • 把JUMP_IF指令后的条件翻译为不同的mips指令完成跳转：

    public HashMap<String, String> mipsBOp = new HashMap<>();
    mipsBOp.put("!=", "bne");
    mipsBOp.put("==", "beq");
    mipsBOp.put(">=", "bge");
    mipsBOp.put("<=", "ble");
    mipsBOp.put(">", "bgt");
    mipsBOp.put("<", "blt");