编译原理 |
您所在的位置：网站首页 › 编译器概述 › 编译原理 |
编译原理
|
Jason Compiler编译器概述
基本功能
实现将C语言自己SysY分别转换成两种中间表示Eeyore和Tigger，以及最终的Risc-V指令。 使用如下命令生成Eeyore中间表示： ./main -S -e test.sy -o test.S使用如下命令生成Tigger中间表示： ./main -S -t tigger.sy -o test.S使用如下命令生成Risc-V指令 ./main -S test.sy -o test.S Jason Compiler 的特点 使用了通用工具Lex和Bison进行词法分析和语法分析，产生相应的C++代码，建立抽象语法树 详细地记录了函数定义时变量的类型信息，可以进行一定的类型检查 使用了一种扩展性很强的内部数据结构存储指令。可以在其基础之上直接产生Eeyore、Tigger以及Risc-V代码 本编译器参考了助教提供的First-Step编译器，使用了其中提供的第三方库xstl来处理Block中变量的重名问题，以及分支语句的跳转位置。 编译器设计 概要设计 主要模块组成所有的模块都被包括在driver之中，其中有负责词法分析和语法分析的yyparser，以及负责根据yyparser产生的抽象语法树（AST）产生中间表示，以及根据中间表示产生目标代码的IRGen。 主要数据结构 抽象语法树的基类BaseAST以及根据SysY语法定义的各种派生类 在IRGen中保存了当前分析指向的函数定义指针_now_func，保存用户定义函数名和函数定义指针映射的_funcs，保存库函数函数名和函数定义指针映射的_lib_funcs，保存当前环境中变量名和变量指针映射的_vars，保存当前环境中跳转标签和标签变量指针映射的_loop_labels，保存当前环境中变量名和变量属性信息映射的_symbol_table，保存函数名和函数变量属性信息映射的_func_table，保存变量名和常量指针映射的_const_vars 在每一个函数定义类中保存了这个函数的函数名，函数返回类型，函数使用的栈空间的偏移量，以及函数包含的变量声明指令序列_decl_insts以及函数包含的其他指令序列_insts 编译器设计架构图
本编译器完全由Driver类进行驱动。Driver类中包括如下成员： 记录本次编译错误数量的变量result Bison语法分析产生的根节点root 用于产生中间表示，以及根据中间表示产生目标代码的IRGen类实例irgen 它包括了以下成员函数 scan_begin打开目标文件，设置flex的debug等级 scan_end关闭目标文件 parse实例化一个yyparser，使用其parse方法进行词法分析和语法分析，构建抽象语法树 compile对语法分析产生的抽象语法树调用GenerateIR方法，将中间表示保存在irgen之中。 Dump_Eeyore调用irgen的Dump_Eeyore方法产生Eeyore中间表示 Dump_Tigger调用irgen的Dump_Tigger方法产生Tigger中间表示 Dump_RISC_V调用irgen的Dump_RISC_V方法产生RISC_V目标代码 抽象语法树设计抽象语法树的节点类继承自基类BaseAST，BaseAST中包括了以下虚函数 Eval对AST节点进行求值，用于常量定义之中对初值的计算，以及使用常量进行赋值时，对常量进行计算。由于可能没有返回值，返回类型为std::optional。由于并非所有的AST都需要重载这个方法，因此该方法没有声明为纯虚函数，而是使用在未被重载时调用抛出运行时异常的方式，并且输出错误提示信息。 GenerateIR方法对AST节点产生中间表示，加入到当前节点所在的函数定义的指令列表_decl_insts以及_insts之中，并且返回一个指向该指令中被赋值对象的指针ValPtr(由于某些AST产生中间表示时可能需要子节点的被赋值对象)。和Eval一样，并非所有AST节点均需要重载此方法，因此在未重载时调用此方法扔出运行时异常并且返回错误提示信息。BaseAST中还包括一些帮助判断派生类类型的私有成员变量。这些私有成员变量会在生成代码时进行动态指针转换时用到，比如 _is_decl判断AST是否是一个声明AST类（包括常量声明和变量声明） _is_array判断AST是否是一个数组声明AST（包括了常量和变量数组的初值即{initval,initval,{initval,initval}}这样的东西，以及函数的形参定义中int a[][5]这样的东西）这个地方这样处理的原因是，常量和变量声明中数组和变量使用了不同的AST，使用_is_array来判断定义的初始化值是一个单一的值还是一串数组。 _is_val_array判断AST是不是一个数组AST。数组AST指向的是类似于T1[T2]或者T1[5]的东西。事后考虑，这里的成员变量应该设计成一个枚举类，然后在初始化所有AST的时候一并初始化这个枚举类，这样可以支持所有不同的类型判断。 符号表设计本编译器包括两种不同的符号表Entry，分别是用于记录一般变量定义的SymbolTableEntry，以及用于记录函数定义时形参定义的FuncTableEntry. 设计两个不同的Entry类型是考虑到数组定义存在差别以及未来潜在可能的定义扩展，尽管他们现在十分类似。 目前SymbolTableEntry包括以下内容： 符号类型_symbol_type 是否为常量符号 _is_const 是否为数组指针 _is_pointer 符号占据的存储空间_symbol_size 数组指针的维度 _dim 保存数组指针每一位大小的向量 _shapeFuncTableEntry相较于SymbolTableEntry少了对是否是常数变量的判断 函数定义中的指令列表以及指令列表中的指令类型设计前文说到，在函数定义类中包括了声明指令列表_decl_insts以及其他指令_insts用于保存中间表示。他们均为一个向量，其中元素的类型为InstBase，即指令类型的基类。此基类中包括了三个纯虚成员函数，分别是Dump_Eeyore,Dump_Tigger以及Dump_RISC_V即要求每个派生指令类型必须显式重载这些方法，以及一个成员变量_inst_type用于记录派生类的指令类型，便于进行类型转换。 在基类之上一共派生了11类指令类型，分别为 DeclareVarInst，对非数组变量的声明指令，其中保存了指向声明变量的指针_val DeclareArrInst，对数组变量的声明指令，其中保存了指向声明变量的指针_val，以及变量占据内存空间的大小_symbol_size AssignInst，赋值指令，其中保存了指向等号左边变量的指针_dest，以及指向等号右边变量的指针_val。注意这里指针指向的可能是常数，或者变量，或者数组引用比如T1[T2] BranchInst，分支指令，保存了一个布尔值_bnez，是否是不等于0跳转，一个指向条件变量的指针_cond，以及一个指向标签变量的指针_label。标签变量是一个临时变量。标签变量和临时变量都是变量类的派生类。 JumpInst，无条件跳转指令。保存了一个指向标签变量的指针_label LabelInst，标签指令。保存了一个指向标签变量的指针_label FuncCallInst，有返回值的函数调用指令，保存了一个指向保存返回值的临时变量的指针_dest，一个指向调用被调用函数函数定义的指针_func，以及一个保存了指向调用实参变量的指针的列表_args VoidFuncCallInst，无返回值的函数调用指令.保存了一个一个指向调用被调用函数函数定义的指针_func，以及一个保存了指向调用实参变量的指针的列表_args ReturnInst，返回指令。保存了一个指向返回值变量的指针_val BinaryInst，二元运算指令。保存了一个指向返回值变量的指针_dest，一个指向运算符左边变量的指针_lhs，一个指向运算符右边变量的指针_rhs以及一个运算符_op UnaryInst，一元运算指令。保存了一个指向返回值变量的指针_dest，一个指向运算符右边变量的指针_opr以及一个运算符_op 变量类型设计前文提到IRGen中有变量名和变量指针的映射_vars以及跳转标签和标签变量指针的映射_loop_labels以及在指令类型中保存了变量指针，在此说明变量类型的设计。 变量类型基类为ValueBase，包括以下成员函数 Dump_Eeyore，向ostream中输出符合Eeyore语法规定的变量 Dump_Tigger，向ostream中输出符合Tigger语法规定的变量 Dump_Tigger_Read，从栈中对应位置读出变量，放置到规定的寄存器中 Dump_Tigger_Write，将规定寄存器中的变量保存到栈中的对应位置 Dump_Tigger_Offset，产生变量在栈中的相对便宜。由于并非所有函数都需要重载这个函数，因此如果未被重载抛出运行时异常 Dump_RISC_V，Dump_RISC_V_Read，Dump_RISC_V_Write，Dump_RISC_V_offset和tigger类似，不再赘述同时它还包括以下成员变量 _is_global，该变量指向的是一个全局变量 _is_array，该变量指向的是一个数组引用 _is_int，该变量指向的是一个整数 _is_arg_ref，该变量指向的是一个对函数形参的变量引用。实际上2，3，4应当和指令类型中一样被合成一个变量在初始化时进行记录 在此基类之上一共派生了6类变量类型，分别为： SlotVal，临时变量，其中记录了当前临时变量在栈上的偏移量_offset，以及该临时变量为改函数定义中第几个临时变量_id。 VarSlotVal, SysY输入中定义的变量，其中记录了当前变量是否是数组地址的判断_is_addr，当前变量在栈上的偏移量_offset，以及该变量为全局第几个变量_id. ArgRefVal，引用函数形参的变量，其中保存了该变量为函数的第几个形参_id ArrayRefVal，数组引用的变量，其中保存了两个变量，分别指向数组的基地址和偏移量。比如该数组引用变量会产生T1[T2]，其中基地址指向T1代表的变量，偏移量指向T2代表的变量 LabelVal，标签变量，其中保存了该变量为全局第几个标签_id IntVal，整数变量，其中保存了该变量的值_val 错误处理本编译器的特点之一在于能够进行类型繁多的错误处理。 词法分析错误处理词法部分的错误处理依赖于lex。词法分析的部分主要实现的错误处理有两个，分别如下 在将不同进制的数从字符串转换成整数时，如果发生越界或者其他错误，则扔出yy::parser::syntax_error，提示行号以及integer out of range加上yytext。实际上syntax_error是对于runtime_error的重载，输出错误信息并停止词法分析 在遇到不在词法规则中的词素时，扔出syntax_error报告行号以及invalid character:加上yy_text，并且停止词法分析 语法分析错误处理语法部分的错误处理依赖于Yacc。语法分析的部分实现的错误处理是在遇到不完整的语法规则的进行错误提示，输出Yacc遇到的语法错误，以及语法错误所在的位置，并且停止往后的语法分析。在实践中我重载了yy:parser::error函数，让其输出行号位置以及错误提示信息。下面是两个示例 前面说到在中间代码生成的时候，每一个AST中都有一个GenerateIR方法，返回一个指向变量的指针。因此我实现了一个LogError函数。这一函数向标准错误输出错误信息，增加错误数量，并且返回一个空指针。返回空指针的目的是让中间代码生成能够继续下去，直到无法继续时输出所有错误信息，并且返回遇到的错误数量 ValPtr IRGen::LogError(std::string_view message){ std::cerr return LogError("Argument Count Mismatch"); }其实这里本来有实参的符号表，有形参的符号表，是可以进行更多的类型检查的。但是由于实现的限制，对于FuncCallAST而言，它拿到的参数是一个ASTBase的列表，这个ASTBase实际上指向的可能是任何能够返回一个变量即ValPtr的派生类。尽管有了所有形参的类型和大小，但是在这个设计中对实参做类型检查需要很多的动态类型转换，做起来十分复杂和困难。 在引用任何一个变量的时候都会查当前环境，有没有这个变量的符号表表项，以及有没有这个变量名映射的变量指针。同样在函数调用之前都需要去查看函数表，看是否有这个函数对应的函数表表项。 auto it = _funcs.find(ast.name()); if (it == _funcs.end()){ it = _lib_funcs.find(ast.name()); if(it == _lib_funcs.end()) return |
这个示例是a[10][10];缺少了右中括号，变成了a[10][10; 
这个示例是main函数最后的大括号缺失了。【本文地址】