《编译技术》课程设计文档

1、编译技术课程设计文档学号： _36060511姓名： 张毅 2009 年 3 月 14 日目录需求说明 41 编写目的 42 文法要求 43 参考资料 5详细设计 51程序结构 52函数调用依赖关系 63 词法分析程序设计说明 73.1 程序描述 73.2 目的 83.3 函数 83.4 CO文法单词编号表（编号， 名字）8”94 语法分析程序设计说明 94.1 程序描述 94.2功能94.3函数95 语义分析，四元式程序设计 1O5.1四元式数据结构 1O5.2四元式格式 1O5.3 函数定义 1O5.4 语义动作 11常量声明 11变量声明 11过程声明 11表达式 12赋值语句 12控制

2、语句 12过程调用 136 符号表设计 146.1 程序描述 146.2功能146.3 符号表结构 14全局符号表 14子函数符号表 147 动态运行栈设计 147.1 程序描述 147.2功能157.3 运行栈结构 158 错误处理 158.1程序描述 158.2错误记录结构 158.3函数168.4 错误类型列表 169 优化程序设计 169.1程序描述 169.2 值编码表数据结构 179.3 基本块数据结构 179.4 删除公共表达式 17函数 17值编码算法 189.5 活跃变量分析 18函数 18活跃变量算法 189.6 全局寄存器分配 18函数 18着色算法 19冲突图结构 19

3、9.7 常量传播 19函数 19常量传播算法 20定值表结构 20三操作说明 201运行环境 202操作步骤 20四测试报告（见 CO编译器测试报告） 22五总结感想 22需求说明1 编写目的A. 本设计设计的编写目的：解释设计思路，说明编译器的设计方式。B. 本设计文档的读者：编译器开发人员，编译器使用者。2 文法要求加法运算符:=+ 1 乘法运算符:=* 1 /关系运算符:= |=|=|!= | =字符:=| a | .|z | A | .|Z数字:=0|非零数字非零数字:=1|.|9字符串:=" 合法字符 "/ 字符串中可以出现所有合法的可打印字符集中的字符程序:=常

4、量说明部分变量说明部分子函数定义部分主函数常量说明部分:=con st 常量定义, 常量定义;常量定义:= 标识符=整数整数:=+|非零数字数字|0标识符:= 字符字符|数字声明头部:= int 标识符变量说明部分:= 声明头部,标识符;子函数定义部分:=（声明头部|void 标识符）参数复合语句复合语句:= 常量说明部分变量说明部分语句序列参数:= （'参数表 ）'参数表:=int标识符, int 标识符 | 空主函数:= void main '（' 复合语句表达式:=+| 项加法运算符项项:= 因子 乘法运算符因子 因子:= 标识符| （'表达式 ）

5、 '|整数|子函数调用语句语句:= 条件语句|循环语句| '语句序列 |'子函数调用语句;|赋值语句 ; | 返回语句 ; |读语句 ;|写语句 ;| ;赋值语句:= 标识符=表达式条件语句:=if （'条件）语句else语句条件:= 表达式关系运算符表达式|表达式循环语句:= while （'条件 ） '语句子函数调用语句:= 标识符 （'值参数表 ） '值参数表:=表达式, 表达式| 空语句序列:=语句语句读语句:=scan f '标识符）写语句：:=printf'（字符串 , 表达式 |字符串| 表达式 ）&

6、#39;'返回语句：:=retur n /表达式）'附加说明：（1）返回类型为void的子函数不允许出现在表达式中（2） 子函数的返回类型必须与返回语句匹配，若无返回语句，则子函数必须声明为void类型（3）标识符不区分大小写字母（4）写语句中字符串原样输出3参考资料1. 编译原理（美）Alfred ，Ravi，Jeffrey著 李建中，姜守旭译机械工与出版社2. 编译原理及编译程序构造金茂忠，高仲仪编北京航空航天大学出版社3 32位汇编程序设计穆玲玲编电子工业出版社4 现代编译原理（c语言描述）（美）An drew著 人民邮电出版社1 详细设计1 .程序结构调用2 .函数调用

7、依赖关系丄才亠山前端add"eserveLookupgetToke nlistmain1r*parse Del com monerror仝Main_fu ncISub f unci rcanshufuheookupyujusetCurF uncn sertbiaodashr*Var expdiaoyon 崎Con st expxunhuan *Const deffuzhi *insert table后端Init inColor*remov3词法分析程序设计说明3.1程序描述Token）。词法分析程序的输入是源文件，其目的是将字符串形式的源程序分解为具有独立语法意义的单词符号（ 如：常

8、量，标识符，字符串等。3.2目的1. 找到文法中定义的标识符，识别出关键字;2字符串整数转化为整数。3. 过滤掉程序中的空格、制表符以及换行符；4. 发现单词错误信息。3.3函数返回类型函数名功能intreserveLookup(int， char*,int)r查找是否为保留字voidadd(i nt, int, char*,i nt)将单词添加进链表voidword error(i nt ,char *, int )单词错误处理inttran sf(char *)将字符串整数转为整形voidgetToke nlist(FILE*)生成单词链表3.4 C0文法单词编号表（编号，名字）Numbe

9、rname0.Co nst1.Int2.Void3.Mai n4.If5.Else6.While7.Scanf8.Printf9.Retur n19.字符串20.标识符21.整数22.23.+24.*25./26.(27.)28.29.30.<31.<=8.39.>>=!=4语法分析程序设计说明4.1程序描述语法分析程序是编译过程的核心部分，它是语义分析的基础。4.2功能1. 按照文法，从源程序符号串中识别出各类语法成分;2. 进行语法检查，为语义分析和代码生成做准备。4.3函数采用递归下降分析法。返回类型函数名函数功能voidsu

10、b fu nc();子函数语法检查voidvar exp();变量表达式检查voidcon st exp();常量表达式检查voidmain fu nc();主函数检杳voidparse();语法分析voidfan hui();返回语句匹配voidbiaodashi();表达式匹配intzhica nshubiao(PMea n);值参数表匹配intyuju();语句匹配voidtiaojia n yuju();条件语句匹配voidyujuxulie();语句序列匹配voiddu();读语句匹配voidxie();写语句匹配voidxia ng(PMea n);项匹配voidyi nzi(PM

11、ea n);因子匹配5语义分析，四元式程序设计5.1四元式数据结构typedef struct no de7char opWordMax,操作符char op1WordMax操作数 1char op2WordMax操作数 2char resWordMax 结果int block_num;/所属基本块编号char func_nameWordMax 所属函数名int op1_code; op2编码II为数据流分析做准备int op2_code;op2 编码int res_code;res 编码struct no de7 *n extFOUR,*PFOUR;5.2四元式格式格式涵义MUL OP1 O

12、P2RESRes=op1*op2DIV OP1 OP2RESRes=op1/op2ADD OP1 OP2RESRes=op1+op2MINUSOP1OP2 RESRes=op1-op2i JGABLABELlf(a>b) goto labelJLABLABELIf(a<b) goto labelJEABLABELIf(a=b) goto labelJNE AB_ABELIf(a!=b) goto labelJGE AB_ABELIf(a>=b) goto labelJLE ABLABELIf(a<=b) goto label! GOTO-LABELgoto labelA

13、SSIGNOP1- RESRes=op1PARAOP1- -Op1作为参数传递RETURNOP1- -Op1作为返回值.CALL-OP1调用op1SCANFOP1- -读入数写到op1PRINTFOP1- -输出op1 ,op1为子符串或表达式值PRINTFOP1OP2 -连续输出op1 op2, op1为子符串，op2表达式值5.3函数定义voidmatch(i nt wordtype);匹配单词intlookup(PMea n)查找局部变量intlookup_all(PMea n):查找全局变量intlookup_ki nd(PMea n)查找类型voidin sert(PMea n);插

14、入当前层符号表voidin sert all(PMea n);:插入全局符号表voidsetCurFu nc(PMea n);建立新符号表char*get_temp(void);:得到新临时变量intcheckParaNum(char *fname int coun t);检杳参数5.4语义动作常量声明v常量说明部分：:=const v常量定义 , v常量定义;v常量定义:=v标识符 serName= v整数 setNumber insert serName： v常量定义.name=v标识符 .namesetNumber: v常量定义.number= v整数.number insert动作：以

15、v常量定义.name,v常量定义.number新建符号表项，类型是ITableConst. CONST将新建的符号表项插入到当前过程的符 号表中，若v常量定义.name的名字的标识符已经存在，报错。变量声明v声明头部：:= intv标识符 insert v声明头部.name= v标识符 .namev变量说明部分 :=v声明头部setName1 ,v标识符 setName2insert ； setName1: v变量说明部分 .Name=v声明头部.name setName2： v变量说明部分 .Name=v标识符 .name insert动作：v变量说明部分.Name为名称，ITableCon

16、st.CONST类型新建符号表项，将新建的符号表项插入到当前过程的符号表中，若v变量说明部分.Name的名字的标识符已经存在，报错。过程声明v声明头部:= intv标识符v子函数定义部分=:=(v声明头部 setName1 setCurFunc insert1 | void v标识符 setName2 setCurFunc insert )v参数v复合语句 setName1: v子函数定义部分.Name=声明头部.namesetName2： v子函数定义部分.Namev标识符.namesetCurFunc:以该函数名为标识新建一张符号表，插入到符号表列表中，并且设置全局变量-当前符号表为该新建

17、符号表 insert1动作：v子函数定义部分.Name为名称，ITableConst. PROC类型新建符号表项，将新建的符号表项插入到全局变量的符号表中，若v子函数定义部分.Name的名字的标识符已经存在，报错。insert2 动作：v子函数定义部分.Name为名称，ITableConst. VOID_PROC类型新建符号表项，将新建的符号表项插入到全局变量的符号表中，若v子函数定义部分.Name的名字的标识符已经存在，报错。v参数:='('v参数表')'v参数表 :=int v标识符 setNameinsert ， int v标识符 setNameinser

18、t | 空setName： v参数表 .Name=v 标识符 .name insert动作：v参数表.Name为名称，ITableConst. PARA 类型新建符号表项，将新建的符号表项插入到全局变量的符号表中，若v参数表 .Name的名字的标识符已经存在，报错。v主函数 :=void main setCurFunc insert'('')'v复合语句setCurFunc:以“ main"为标识新建一张符号表，插入到符号表列表中，并且设置全局变量-当前符号表为该新建符号表insert动作：v子函数定义部分.Name为名称，ITableConst. V

19、OID_PROC类型新建符号表项，将新建的符号表项插入到全局变量的 符号表中，若"main”的名字的标识符已经存在，报错。表达式v表达式 :=setFlag v项 1 emit3 （v加法运算符 setOPv项 2 releaseTempIndex allocTempName emit1| 空setAttribute） v加法运算符 setOPv项 2 releaseTempIndex emit2 setFlag :设置标志值 如果token是-'标识设为1，其他为0.setOP: v表达式 .OP=v加法运算符 .OPreleaseTempIndex :若v项1项2申请了临

20、时名字，则临时名字下标全局量减一allocTempName： v表达式 .name =申请的临时名字setAttribute : v表达式 .name=v 1 .name; v表达式 .number= v项 1 .number; v表达式 .type= v项 1 .typeemit1:生成四元式v表达式 .OP, v项1 .name, v项2 .name, v表达式 .name;emit2: 生成四元式v表达式 .OP, v表达式 .name, v项2.name, v表达式 .name;emit3: 如果标志为1，执行动作 allocTempName，生成四元式“ MINUS , v项1 .n

21、ame, null,v表达式 .name;项 :=v 因子 1 （v乘法运算符 setOP v 因子 2 releaseTempIndex allocTempName emit1| 空setAttribute ） v乘法运算符 setOPv 因子 2 releaseTempIndex emit2 setOP: 项 .OP=v乘法运算符 .OPreleaseTempIndex :若v因子1v因子2申请了临时名字，则临时名字下标全局量减一allocTempName： 项 .name =申请的临时名字setAttribute : 项 .name=v因子 1 .name; 项 .number= v因子

22、 1 .number; 项 .type= v因子 1 .typeemit1:生成四元式项 .OP, v 因子 1 .name, v因子 2.name, 项 .name;emit2: 生成四元式项 .OP, 项 .name, v 因子 2 .name, 项 .name;v因子 := v标识符 setName1 lookUpTable |'（'v表达式 setAttribute '）'丨 v整数 setNumber |v子函数调 用语句 setName2setName1: v 因子 .name= v标识符 .name;setName2: v因子 .name= v子函

23、数调用语句 .name;setAttribute : v 因子 .name= v表达式 .name; v 因子 .number= v表达式 .number; v 因子 .type= v表达式 .typesetNumber: v 因子 .number= v整数 .number;lookUpTable:在符号表中查找当前标识符是否存在（不区分大小写），若不存在，报错赋值语句v赋值语句 :=v标识符 lookUpTable =v表达式 releaseTempIndex emit releaseTempIndex :若v表达式申请了临时名字，则临时名字下标全局量减一lookUpTable:在符号表中查

24、找当前标识符是否存在（不区分大小写），若不存在，报错emit :生成四元式 “ASSIGN v标识符 .name,null,v表达式 .name控制语句v条件语句 :=ifsetQuad1 '（'v条件'）'v语句1 backpatch1 merge1 else addQuadsetQuadv语句 2backpatch2merge2setQuad1： v条件语句 .quad仁 nextQuadsetQuad2 v条件语句 .quad2= nextQuadbackpatchl:用v条件语句.quadl填写v条件.trueList中各中间代码跳转语句的标号； bac

25、kpatch2:用v条件语句.quad2填写v条件.falseList中各中间代码跳转语句的标号addQuac将 nextQuad 添加到 v语句 1 . nextList merge1:将v条件 .falseList 和v语句1 . nextList的并集添加到v条件语句.nextList merge2将v语句1. nextList和v语句2 . nextList的并集添加到v条件语句.nextListv条件 :=v表达式1 v关系运算符v表达式 2 makeList emit1 |v表达式 1 makeList emit2makeList : v条件 .trueList=nextQuad;

26、v条件 .falseList=nextQuad+1.emit1:生成四元式“ J ? ”，v表达式 1 .name, v表达式 2 .name, “GOTO ?；“ GOTO”， null ， null, -emit2:生成四元式“JNE', v表达式 1 .name,“0” , “GOTO ?;“ GOTO”， null ， null, -注：goto语句的标号等回填是填写，J ?具体操作有关系运算符决定v循环语句 :=whilesetQuad1 '（'v条件'）'setQuad2语句 backpatch makeList emitsetQuad1：

27、v循环语句 .quad仁 nextQuadsetQuad2 v循环语句 .quad2= nextQuadmakeList : v条件 .trueList=nextQuad;v条件 .falseList=nextQuad+1.backpatch:用v循环语句 .quad1填写v语句.nextList中各中间代码跳转语句的标号；用v循环语句 .quad2填写v条件 .trueList 中各中间代码跳转语句的标号emit:生成四元式 “GOTO, null , null, v循环语句 .quad2v语句 := v条件语句 makeList1 |v循环语句 makeList2 |' 语句序列

28、' '|v子函数调用语句;|v赋值语句;| 返回语句;| v读语句 ；|v写语句 ;| ;makeList1 : v语句.nextList=v条件语句 .nextListmakeList2 : v语句.nextList=v循环语句 .nextListv语句序列 := v语句 1 makeList1 backpatch v语句 2backpatch makeList2 makeList1 : v语句序列.nextList= v语句 1 .nextListmakeList2 : v语句序列.nextList= v语句 2 .nextListbackpatch:用nextQuad填写

29、v语句序列.nextList中各中间代码跳转语句的标号过程调用v子函数调用语句:=v标识符 lookUpTable'（'v值参数表'）'checkParaNumemitlookUpTable:在符号表中查找当前标识符（类型是PROC或VOID_PROC是否存在（不区分大小写），若不存在，报错 checkParaNum: 到符号表中检查参数数目是否正确，若不正确，报错。emit:生成四元式“CALL' , v标识符 .name, null, null;v值参数表 :=v表达式 releaseTempIndex emit ，v表达式 releaseTempI

30、ndex emit |空 releaseTempIndex :若v表达式申请了临时名字，则临时名字下标全局量减一emit:生成四元式 “PARA , v表达式 .name, null, null;v读语句 := scanf '（'v标识符 emit '）'emit:生成四元式 “SCANF , v表达式 .name, null, null;v写语句 := printf '（' 字符串 ,v表达式 emit1 | 字符串emit2 | v表达式 emit 3 '） emit1: 生成四元式 emit2: 生成四元式 emit3: 生成四元式

31、PRINTF , v字符串 .name, v表达式 .name, null;PRINTF , v字符串 .name, null, null;PRINTF , v表达式 .name, null, null;v返回语句 :=return '（'v表达式'）'emit emit: 生成四元式RETURN , v表达式 .name, null, null;6符号表设计6.1程序描述编译器通过符号表来记录名字的作用域以及相应信息，符号表是贯穿整个编译过程的重要数据结构。6.2功能1. 检查语义的正确性；2. 生成四元式代码。6.3符号表结构全局符号表全局常量1O O O

32、O全局常量n全局变量1O O O全局变量n子函数1O O子函数n主函数子函数符号表参数局部常量1O O O O局部常量n局部变量1O O O局部变量ntypedef struct node2/符号表单元结构char nameWordMax; 名称int type;当前项类型编号int number;如果是子函数类型，代表参数个数in t value;如果是常量，代表初值Mea n, *PMea n;Mean tableMax_Table_hangMax_Table_lie;tableO代表全局符号表，table1n代表子函数表7动态运行栈设计7.1程序描述编译器通过运行栈来实现函数调用。7.2

33、功能1为子函数创建新的数据区，同时传参数7.3运行栈结构变量常量参数区2返回地址2子函数2变量常量参数区1返回地址1子函数1变量常量Mai n 函数8错误处理8.1程序描述并在编译结束的时候将错误输出出来。错误处理程序用来记录和处理编译程序编译过程中遇到的词法和语法错误。8.2错误记录结构typedef struct nodeint Lin eshow;行数int Lextype; 类型char SemWordMax; 名称8.3函数voiderror(char *, in t ,i nt )错误处理8.4错误类型列表1.缺少符号；2.无主函数3.非法单词4.符号表空间不足5.缺少结尾6.语法

34、上应为标识符7.函数未定义，8.临时寄存器溢出，9.标识符未定义，10.缺少类型符，11.缺少12.缺少,13.缺少（,14.缺少）,15.标识符重复定义，16.缺"，17.返回值寄存器错误，18.常量未赋值19.赋值式左部非变量，20.赋值式右部类型错误，21.应有=',22.不能是void型,23.标识符类型错误，24.函数调用时参数个数不对25.打印格式错误9优化程序设计9.1程序描述dag图）对公共表达式首先将各个过程的中间代码化为一个个的基本块，接着对每一个基本块采用值编码算法（不是 删除；同时对每一个过程的各个基本块进行活跃变量分析，为以后全局寄存器分配做准备。9

35、.2值编码表数据结构typedef struct node8/ 编码表结构int code;char n ameWordMax;CODE_TABLE;CODE_TABLE code_tableCodeMax; / 编码表9.3基本块数据结构typedef struct no de11int block_ num;FOUR siyua nBlockRowMax;int siyuan_num;四元式数量char func_nameWordMax; 所属函数名 int pre_blockRelateMax; 前继基本块编号 int aft_blockRelateMax;int in VarMax;i

36、n t outVarMax;int useVarMax;int defVarMax;in t liveVarMax;BASE_BLOCK; BASE_BLOCK block_arrayMaxBlock;9.4删除公共表达式函数返回类型函数名功能Voiddel com mon():删除子表达式intin sert table(char*op1)变量常量放入编码表，返回编码号Intassig n( char*res,char op1)编码res=op1,返回op1和res编码intfirst_show(char *)op1是变量，return -1标示首次出现voidempty()基本块入口置表空

37、voidin sert after del()删除公共表达式后放入结果数组intrepeat()检查四兀式在after dal是否重复，右重复，调用 assign值编码算法1在基本块入口置表为空2逐条扫描四元式3遇到变量，常量第一次时，加入编码表4 遇至U a=b, 使 code( a) =code( b)5对四元式进行等价替换，删除多余的四元式9.5活跃变量分析函数返回类型函数名功能voiddef use()计算def, use集合intret code(char *op1)返回编号voidin it i n()初始化in集合voidin out()计算in, out集合活跃变量算法Use集

38、合定义：在该变量的任何定义之前可能引用该变量的变量的集合。Def集合定义：在引用变量之前以明确地对该变量进行赋值的变量的集合。In集合定义：该基本块前继基本块的活跃变量的集合。Out集合定义：紧跟在该基本块后的活跃变量的集合。每个基本块的活跃变量 =OUT(B) 一 DEF(B) USE(B)用一个数组表示以上各个集合，即为变量分配一个编号(数组下标)，例如变量vara的编号为0，若def0=1则表示vara在def这个集合中。9.6全局寄存器分配函数返回类型函数名功能voidalloc all reg()分配全局寄存器voidcolor(i nt)为冲突图着色Voidremov(i nt s

39、)从冲突图移走节点着色算法1生成冲突图2通过反复删掉少于 3条边的节点，我们要么得到一个空图；要么得到一个每个节点有3条边的图。3对于前一种情况，按节点被移走的相反顺序为其着色即可得到一个3色的染色；对于后一种情况，去掉任意一个节点，并不对其分配全局寄存器，然后继续进行着色。4参与全局寄存器分配的变量有：每个过程中的参数和变量。冲突图结构in t con flictVarMaxVarMax; 冲突数组 int remove_orderVarMax; 移走顺序int var_regGLOBAL; II全局寄存器分配状态1 采用冲突数组的方法实现，int con flictVarMaxVarMax

40、; 若 a 与 b 冲突，code (a)=1,code(b)=2则conflict12=1.若不冲突则值为零。2 染色时，移走某节点 a,置 conflict1O .n=2, conflict0 .n1=2;同时把1加入remove_order数组3按移走顺序反向分配全局寄存器，用后 设置var_regcode (a) =reg_num其中reg_num是寄存器编号，从 0-2，分别代表 esi, edi, ebx9.7常量传播函数返回类型函数名功能voidcon st comb in e()常量合并与传播voiddelet(char *s)分配全局寄存器voidcha nge(PFOUR

41、p,i nt nu m,char *s)替换四兀式voidputi n( char *s char *value)将定值放入定值表intkno w(char*s)查询是否是定值Voidget value(char *s,char *value)从定值表得到值常量传播算法基本思想：若四元式分量都是取常数值，则编译程序把值算出来，替换原有运算，删除当前四元式 需要定义一个常数定值表， 元素是二元组（ name， value）。 若有（ y， 5）表示当前 y 取 5.。1 当四元式是赋值式 assign op1 null res 若 op1 已知，把（ res， op1 ）放入表中2若四元式是运算式，且 op1, op2已知，把（res,计算结果）放入表中3当四元式是赋值式 assign op1 null res 若op1未知，把（res, op1）从表中删除4 若四元式是运算式,且 op1 或 op2 在表中,替换四元式定值表结构typedef struct node12/定值表char name20;变量或常量名char value10;定值ConstDef;ConstDef constdefCodeMax;三操作说明1运行环境由源码生成 386 汇编码的运行环境为 windows xp/vista, 运行 386