申优论文 北航本科编译原理大作业.doc

How to Design a C Object oriented Compiler 罗杨 37230118 Abstract This system is a C object oriented compiler using a extended C0 grammar as the input language It can generate the assembly code according to the Intel 386 instructions set You can use the Masm32v10 software to assemble and link the source code to get your 32 bit applications 摘要摘要 本系统实现了一个以扩充 C0 文法为输入语言的采用 C 及面向对象思想设计的编译 器 可以生成符合 386 指令集规范的汇编代码 用 Masm32v10 汇编可生成 32 位应用程序 本系统考虑到不同版本的 Masm 的功能和使用方法的差异 以及用户手工键入汇编 连接 命令多有不便 本系统自带了汇编器 Ml exe 和连接器 link exe 正文正文 由于是目标是 Windows 平台下 32 位应用程序 有些文法中的功能如输入和输出无法 再像 16 位汇编时调用 DOS 中断解决 因此对于这些问题我使用 Microsoft 提供的类似高级 语言的设计方法 调用 DLL 函数来解决 其实 32 位汇编语言在函数调用方面已与高级 语言相差无异 可以调用系统 API C RunTime 甚至是用户 DLL 中的函数 本系统是一遍扫描编译程序 采用面向对象的方法进行构建 各个主要部分均抽象成 类 主要的类有 分析器类 Parser 符号表管理器类 SymbolTableMgr 四元式管理器类 QuadrupleMgr 代码生成器类 CodeGenerator 错误处理器类 ErrorHandler 全局数据流分 析器类 GDAOptimizer 全局寄存器分配器类 GRDOptimizer 局部公共子表达式删除器类 CSDOptimizer 以上属于具有明显功能划分和界限区别的 高级类 他们的对象在全局 main 函数中分别构造和删除 系统中还有其它一些既具有数据结构意义又具有功能操作的 中级类 它们一般是 高级类 或 中级类 的成员 如基本块集合管理器 BBSetMgr 由全 局数据流分析器类 GDAOptimizer 构建 并为其它多个优化器类共享 还有一些相对意义 上的 低级类 它们具有复杂的数据结构 却几乎没有功能操作 通常由 中级类 或 高级 类 得数组成员进行管理 如项类 Item 四元式类 Quadruple 其中项类 Item 代表符号表中 的每一项 四元式类 Quadruple 顾名思义代表一个四元式 并且四元式的三个操作数是指 向项 Item 的指针 由于这些 低级类 对象通常代表基本数据 数量众多而又经常在各个高 级对象之间传递 为了减少时间空间的开销 本系统对所有的类均采用指针构造 这样需 要传递的就不是对象而只是一个指针了 有效地提高了程序的运行效率 本系统的一个特点是词法分析和语法分析结合 其功能集成在词法与语法分析类 Parser 里 虽然本系统整体式面向对象的 但由于词法分析和语法分析本身的特性 Parser 类却具有明显的面向过程的特征 各个代表文法子程序的层次关系 中间不断嵌入的词法 程序和语义程序 动作符号子程序 这样的体系几乎体现不出面向对象抽象封装的优势 因此我在这部分虽然代码写的很快 调试却花了比写还要长的时间 这的确说明了我前期 的程序框架没有设计好 没有一个好的结构的程序 代码量不大时并不会体现出它的缺陷 但是随着规模的扩大 功能的复杂化 程序最后会达到难以维护的程度 因此我觉得在词 法与语法分析方面能构造出一个简便适用的面向对象的模型非常必要 另外在语法分析方面 考虑到题目中的 C0 文法并无左递归问题 只有回溯问题 根 据课本 为了消除回溯可以用改写文法或是预读字符的方法 当时课堂上老师着重讲了改 写文法的方法 预读字符的方法只是介绍了一下 但是我考虑到若改写成等价文法 使规 则右部多个候选式首符号集不相交的话 虽然语法分析变得简单了 但改写后的规则中的 符号含义变得不明确 本来是语义连贯的动作符号语义子程序 可能因为文法的改写被分 到不同的语法递归子程序中 参数传递复杂而繁琐 而且模糊了语义编写时容易出错 反 而给语义分析带来更大的麻烦 因此我采用预读字符的方法处理回溯问题 由于在预读字 符时只是进行语法分析 并没有语义处理 因此不会出现课本上所说的 相关的语义分析工 作在回溯时也要推倒重来 的情况 不难验证 这两种方法在运行速度上并无本质差别 我认为本系统一个比较突出的亮点是中间代码 四元式的操作数均为指向符号表某 一项的指针 也就是说中间代码其实是四元式表加上符号表 这样做不仅节省空间 而且 由于符号表存储了几乎所有的数据结构信息 在代码生成或优化中都非常方便调用 显然 若这样的话 符号表在生成目标代码前是不能释放的 因此没有采用课本上介绍的栈式符 号表 显而易见 进行语义分析时进入和退出过程的动作与堆栈很像 因此本系统的符号表也采 用了一个指针 pCurrentTable 来表示当前栈顶符号表 因此需要一个对象来管理当前栈顶符 号表 pCurrentTable 再者 考虑到不同模块 过程或函数定义 的在变量作用域上具有独 立性 即模块外的语句不可访问模块内变量 因此本系统实现了多符号表架构 前面提到 本系统的 高级类 之一是符号表管理器类 SymbolTableMgr 就是用 SymbolTableMgr 来管 理符号表 SymbolTable 存储方式考虑到符号表之间的严格的层次关系并没有采用符号表 数组这样的线性存储方式 而是采用的类似于链式存储的形式 在这里指针发挥了很大的 作用 按照前面所说 符号表 SymbolTable 以数组形式拥有项 Item 这里项 Item 设置了一 个 pChildTable 指针 表示子符号表 这个 Item 实际上就代表函数 过程 定义里的函数 过程 头 它拥有这个函数 过程 所对应的符号表 然后符号表管理器类 SymbolTableMgr 模拟了堆栈的操作 压栈和出栈 即对当前栈顶符号表 pCurrentTable 进行变更 为了方便出栈 为每个符号表 SymbolTable 设置了父项 Item 同时又为每个 Item 设置了父符号表 SymbolTable 这样本系统实现的符号表体系实际上类似一个双向链 表 对于单个的符号表 课本上提到 其实编译系统分析过程中很多时间花费在查表建表上 并且提出了多种符号表组织形式 如无序符号表 有序符号表 散列符号表等等 无序符 号表插入操作简单 但查表费时 有序符号表 查表可以用很快的折半查找法 但插入时 需要同时移动很多元素 很费时 散列符号表又过于复杂 包括 HASH 函数的选取等 因 此我借鉴本学期 数据库系统概论 里介绍到的一种方法来解决插入和查找的时间复杂度问 题 这就是索引 为每一个符号表建立一个 Int 类型的索引数组 数组内容即为原表项 Item 数组下标 这样在插入时 数据插入原表项 Item 数组末端 更新索引 查找时直接查 找索引即可 因此插入和查找的时间复杂度都很低 在中间代码方面 由于考虑到为使涉及四则运算的代码更易实现 选定了符号表项 Item 作为四元式的操作数 但是也存在一些问题 有些操作数如符号串 标签 局部常量 并不是符号表的内容 并且有着自己特殊的操作 如标签的命名等等 由于不能存储在符 号表中 因此把它们按类分别建立项 Item 的数组 由四元式管理器 QuadrupleMgr 拥有 并且这些 Item 的 kind 属性各不相同 这样就可以实现不同的语义动作 如全局变量显式 生成声明语句 实参分配压栈后的地址 局部变量分配运行栈中的地址 全局常量采用类 似 C 中宏定义的使用方式 局部常量直接常量替换等等 最后虽然各个操作数的意义大 不相同 但至少逻辑格式是统一的 并且通过它的 type 可以很好地区分不同类型的操作数 基于以上的优点 这部分的代码完成速度很快 而且质量也有保障 文法中的条件转移语句中有 6 种关系操作 即 但它们的运算 方式其实与普通的四则运算还是很像的 都有两个源操作数和一个目标操作数 其实在 C 语言语义下文法按照这样设计的 根据两个源操作数大小关系决定目标操作数为零还是非 零 因此我的中间代码所使用的指令就有类似的操作 即根据两个源操作数大小关系决定 目标操作数为零还是为一 这样就关系运算就没有必要和跳转指令绑在一起了 也算是一 种对文法的扩展吧 当然只是语义上的 语法分析部分如果不符文法还是会报错的 这里 要提到的是由于 X86 指令集并没有判断大小并赋值的语句 因此上面提到的这些中间代码 的指令生成汇编代码时实际上还是采用的判断跳转指令 虽然本质上并没有避开跳转指令 但是这就实现了中间代码对汇编代码的一层抽象 还有浮点数处理也是本系统着重实现的功能之一 虽然文法中的三种数据结构 char int float 实际需要的大小并不一致 虽然 int 有 16 位和 32 位之分 但 VC6 生成的 汇编的 int 类型是 32 位的 而 float 也是 32 位 虽然 char 是 8 位大小的 为了方便处理考 虑 本系统生成的汇编中 char 按照 32 位处理 由于文法并不存在数组这样的数据结构 可知这样的设定不会造成明显的空间浪费 并且 事实上由于 CPU 内部执行机制的原因 统一大小的数据块通过寄存器和内存间的赋值往往比大小不一的数据块的赋值要快 这就 是为什么有时候 VC6 生成的汇编代码中的赋值经常取齐为字或双字的原因 虽然 char 类 型在运算时可以直接按照 int 类型来处理 毕竟存储格式本质是一样的 而浮点数就不同 了 IEEE 定义的单精度浮点类型 float 的存储格式与 int 完全不同 因此在涉及混合类型运 算时必须进行格式转换 可喜的是 386 汇编指令集提供了浮点运算和转换的指令 由专 门的 CPU 浮点数运算单元来处理 因此 针对汇编指令集的情况 构建了两条中间代码指 令来完成 float 转 int 和 int 转 float 的运算 因此在遇到混合类型的四则运算时 char 和 int 之间是不需要处理的 若遇到 float 类型操作数 则它的临操作数若不是 float 类型也需要 格式转换成 float 即对表达式内的表示范围较窄的类型进行隐式提升 若赋值式的左右操 作数类型不一致时 右操作数会强制格式转换成左操作数类型赋值 浮点数需要在生成的汇编代码里能够运算和类型转换 这主要数针对浮点数变量而言 的 若存在浮点数常量的话 此常量必须在编译时就得到正确的值 因此本系统在数据转 换器类 DTS 中的 ToFloat 函数实现了把 string 类型的实数转换为其对应的 string 类型的 32 位浮点数格式 如 string 1 234 转化为 string 3F9DF3B6h 同时 ToFloat 函数的输入的实 数过大 超出了 float 的表示范围 还能够向错误处理器类 ErrorHandler 提交错误 另外 为了使程序有一定的可读性 项 Item 的 kind 属性 type 属性以及四元式 Quadruple 的操作 符 opr 属性取值都采用宏定义给出一个有意义的名字 也就是说这些属性的取值实际上为 int 为了在控制台输出这些属性对应的 string 在 DTS 类还实现了 Convert 方法 由于 DTS 类本身更类似一个函数库 而不是一个类库 因此采用静态 static 方式提供方法 这 样既方便了其他类直接调用 又具有类易于管理的特点 最后是优化部分 在生成中间代码时 由于考虑到汇编语言四则运算指令的种种限制 如两操作数不能同时为变量 不能同时为寄存器间接寻址等因素 因此生成的四则运算相 关的中间代码的目的操作数全都为新分配的临时变量 在运行栈中 然后再将此临时变量 赋值给原高级语言中要赋值的变量 这样做虽然比较安全 但势必会产生很多冗余代码 因此必须进行一定的优化 本系统实现了局部公共子表达式删除优化 对应类 CSDOptimizer 全局寄存器分配优化 对应类 GRDOptimizer 等 其中全局寄存器分配 优化采用了图着色算法 并使用全局数据流分析 对应类 GDAOptimizer 的活跃变量分析 来构建冲突图 由于局部公共子表达式删除优化 CSDOptimizer 需要在基本块内进行 全局 寄存器分配优化 GRDOptimizer 也需要函数块 过程块 的信息以及各基本块的冲突图信 息 因此全局数据流分析 GDAOptimizer 需要最先执行 GDAOptimize 负责构造 BBSetMgr 基本块集管理器类的一个数组 顾名思义 BBSetMgr 代表一个基本块集 即一个函数 过程 同时 BBSetMgr 基本块集管理器类又负责构造 BasicBlock 基本块类的一个数组 BasicBlock 代表一个基本块 BasicBlock 的划分及相应 in 和 out 集的生成又其父类 BBSetMgr 负责 这样 全局数据流分析 GDAOptimizer 的工作就完成了 下面是全局寄存器分配优化 GRDOptimizer 这一步的优化时跨越基本块 在函数 过 程 范围内的 因此需要上一步 GDAOptimizer 生成的 BBSetMgr 数组 又这个数组构建 了冲突图表类 ConflictTable 的数组 一个冲突图表类 ConflictTable 是一个二维表 行和列 相同 都为项 Item 当表格中值为 1 表示行与列有冲突 生成冲突图后实现图着色算法 为局部变量和参数变量分配全局寄存器 优化后的结果会直接反映到四元式管理器类 QuadrupleMgr 中的四元式数组 最后是局部公共子表达式删除优化 CSDOptimizer 它是在基本块下完成的 因此需要 GDAOptimizer 生成的 BBSetMgr 数组 此公共子表达式删除是针对中间代码中的四则运算 赋值和取反操作进行 遇到其他如函数 过程 调用和关系运算不会进行此优化 因为函 数 过程 调用和关系运算都是通过跳转来实现的 这样也不会属于一个基本块 CSDOptimizer 每完成一个基本块的优化 都会把结果反映到四元式管理器类 Quadr