编译原理课设

编译原理实验报告学院：计算机学院班级：10011005组员：马莹2010302484张春萍2010302485张远芳2010302486日期：2013.11.15成绩说明本课程的主要任务是编写一个小型类Pascal语言的编译器。该编译器应当能够将输入的源程序文本翻译为相应的四元式，并输出符号表。实验要求如下：（1）课程概况课时30学时，要求已经学习了编译原理课程，并掌握了一定的C语言程序设计能力。（2）实验环境词法分析器采用flex；语法分析器采用bison；软件开发建议使用VisualC++6.0。（3）应当具有的基本编译处理功能应当具备的基本处理能力：能够处理整型、实型两种类型的变量定义；能够处理程序结构的定义；能够识别算术、关系和逻辑表达式；能够识别常量定义；能够识别顺序、赋值、循环、选择、复合语句等基本的语句类型；翻译结果（可以考虑将结果保存到文本文件中）：能够将输入的文本输出为四元式序列；能够输出符号表；以上为实验的基本内容。在实验过程中，可根据自己的时间和能力进行适当的扩展。（3）考核方法实验完成后，对实验程序进行验收，并于2009年1月8日之前提交实验报告（电子版）。电子版文件命名要求为：班号-姓名-学号.doci目录目录1实验情况概述...........................................22主要功能...............................................22.1基本功能：........................................22.2扩展功能：........................................43软件总体结构...........................................54详细设计............................................64.1数据结构..........................................64.2主要的算法和辅助函数..............................75实验总结...............................................95.1调试和bug修改总结................................95.2测试和结果........................................95.3实验小结.........................................1221实验情况概述目的是通过工具Flex和Bison，对一段符合自定义的类Pascal语法规范(简称为MiniPascal)的程序段进行词法分析和带语义的文法分析，最终输出该程序段的符号表和四元式序列。遵守MiniPascal语法规则，按照LEX规定格式，手工编写词法分析说明文件(称为LEX源文件，后缀名为.l)。然后使用Flex工具将该文件转换为C语言文件。按照YSP(YaccSpecification)规定格式，手工编写文法处理说明文件(称为LEX源文件，后缀名为.y)。然后使用Bison工具将该文件转化为C语言文件。2主要功能2.1基本功能：本实验实现了将测试程序翻译为四元式格式的功能，本实验的四元式的存储结构如下：structQUATERLIST{charop[OPSIZE];chararg1[ARGSIZE],arg2[ARGSIZE];charresult[ARGSIZE];intresultType;//存在变量表中还是四元式的result(临时变量)中}QuaterList[MAXMEMBER];相应的修改操作如下：//生成运算符四元式voidGEN_Expr(char*op,structexpr*arg1,structexpr*arg2,structexpr*result);3//生成跳转四元式voidGEN_Jump(char*op,structexpr*arg1,structexpr*arg2,intt);其中各个参数的定义详情见代码：ast_yacc.c。表1定义了操作符及其解释，如下：表1操作符说明操作符含义四元式举例简略宏J无条件跳转到指定四元式位置(j，，，2)无条件跳到第2个四元式j800ASSIGN将一个表达式的值赋给一个变量(:=，2，-1，i)进行赋值i:=2:=801JUMP_LOW当两操作数符合“小于”关系时，跳转到指定四元式位置(j，m，n，3)当mn时，跳转到第3条四元式，否则顺序执行j804JUMP_HIGH当两操作数符合“大于”关系时，跳转到指定四元式位置(j，m，n，3)当mn时，跳转到第3条四元式，否则顺序执行j805JUMP_EQUAL当两操作数符合“等于”关系时，跳转到指定四元式位置(j=，m，n，3)当m=n时，跳转到第3条四元式，否则顺序执行j=806JUMP_LE当两操作数符合“小于等于”关系时，跳转到指定四元式位置(j=，m，n，3)当m=n时，跳转到第3条四元式，否则顺序执行j=807JUMP_GE当两操作数符合“大于等(j=，m，n，3)j=8084于”关系时，跳转到指定四元式位置当m=n时，跳转到第3条四元式，否则顺序执行JUMP_NE当两操作数符合“不等于”关系时，跳转到指定四元式位置(j，m，n，3)当mn时，跳转到第3条四元式，否则顺序执行j809STOP停机指令(STOP，-1，-1，-1)停机STOP1000表2阐述了其他可能使用到的指令以及四元式：表2其他指令及四元式操作符含义四元式举例+加法运算(+，a，b，c)即c:=a+b—减法运算(-，a，b，c)即c:=a+b*乘法运算(*，a，b，c)即c:=a+b/除法运算(/，a，b，c)即c:=a+b2.2扩展功能：变量类型的改动：1)struct_BExpr，struct_WBD数据类型新增加了成员，用以配合新该进的算法。2)四元式存储类型的改动，将记录参数的整型变量换为字符数组，在规约过程中直接生成四元式。3)例子程序中的BoolExpr类型规约有误，会出现语法错误，故将原有规则BoolExpr：BoolExprAnd|BoolExprOr修改为BoolExpr：BoolExprAndBoolExpr|BoolExprOrBoolExpr。但存在优先级结合的问题，故改进后的语法还有一个缺陷：除非利用’(’、’)’，否则不能实现结合顺序的改变。54)赋值表达式的优先级结合顺序有问题，故将原有的Expr规约规则改为：Expr:Expr'+'Term|Expr'-'Term|TermTerm:Term'*'Factor|Term'/'Factor|FactorFactor:'('Expr')'|Variable|Const另外，在实现四元式转换的基础上，在赋值语句中检测类型匹配的错误，并在识别语句时在相应的回写位置提出警告。3软件总体结构主要文件列表如表3所示：表3主要文件列表文件名作用AstCP.slnVC++6.0项目入口文件Bison.exe文法分析工具BisonFLEX.exe词法分析工具Flexast_lex.l词法分析说明文件ast_yacc.y文法分析说明文件ast_lex.c词法分析说明文件转化后的.C文件ast_yacc.c文法分析说明文件转化后的.C文件test_cp.txt等测试程序文件文法定义.txt文法定义文本文件主要的程序模块为词法分析工具flex翻译.l文件，调用yylex()接口，经过Bison转换.y文件后，yyparse()提供外界调用的接口。Yylex()与yyparse()通过extern定义的全局变量传递信息。64详细设计4.1数据结构1)四元式的存储结构如下：#defineMAXMEMBER100structQUATERLIST{charop[OPSIZE];chararg1[ARGSIZE],arg2[ARGSIZE];charresult[ARGSIZE];intresultType;//存在变量表中还是四元式的result(临时变量)中}QuaterList[MAXMEMBER];相应的修改操作如下：//生成运算符四元式voidGEN_Expr(char*op,structexpr*arg1,structexpr*arg2,structexpr*result);//生成跳转四元式voidGEN_Jump(char*op,structexpr*arg1,structexpr*arg2,intt);其中各个参数的定义详情见代码：ast_yacc.c。符号表结构VarList(使用VarCount标记当前符号表中行数)：structVARLIST{charname[20];//变量名inttype;//变量类型union{intIv;doubleRv;}Value;//变量值}VarList[MAXMEMBER];2)文法符号类型联合体：7unionYYSTYPE{#line81ast_yacc.y/*yacc.c:355*/intIv;intCH;intNO;struct{intTC,FC,TQ,FQ;}_BExpr;//真假的跳转目的，真假的跳转语句在四元式的存储处struct{intQUAD,CH,FQ;}_WBD;//判断语句的第一条，跳出到哪个四元式，(不合条件的)跳转语句的位置//struct{inttype,place;/*union{intIv;floatRv;}Value;*/}_Expr;//struct{inttype,place;intival;floatrval}_Expr;structexpr*_Expr;char_Rop[5];intFirst;charstr[20];structnode*ast_node;#line221ast_yacc.c/*yacc.c:355*/};4.2主要的算法和辅助函数辅助函数及其主要作用如下：1)voidprintTree(structnode*result);向控制台输出树的内容。2)structexpr*new_expr(intetype);初始化structexpr类型的变量，包括分配存储空间。3)voidAddVarList(structnode*head);8将定义的变量存到变量表内。4)intEntry(char*name,inttype);以name为变量名查表、填符。5)intEnter(char*name,inttype);以name为变量名登记新的一项,返回登记项序号。6)intLookUp(char*name,inttype);以name为变量名、type为类型查表，返回登记项序号：-1:查无此名；-2:变量重复定义。7)intLookUpName(char*name);以name为变量名查表，返回登记项序号-1：查无此名。8)voidtranslate_arg(structexpr*e,char*str);将expr翻译为四元式中的参数。9)voidGEN_Expr(char*op,structexpr*arg1,structexpr*arg2,structexpr*result);生成运算符四元式。10)voidGEN_Jump(char*op,structexpr*arg1,structexpr*arg2,intt);生成跳转四元式。11)voidBackPatch(intquaterNo,intt);用四元式序号t回填以第quaterNo个四元式为表头的链。12)voidExchangeInt(int*f,int*b);交换两个int变量的值。13)voidMerge(intno1,intno2);no1、no2两条链合并为一条链，将no1接在no2的链尾。14)voidOutputPara