编译原理课程设计报告

提供全套毕业论文，各专业都有课程设计报告设计题目：简单文法的编译器的设计与实现班级:计算机1206组长学号：20123966组长姓名：指导教师：设计时间：2014年12月摘要编译原理是计算机科学与技术专业一门重要的专业课，它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端目录摘要.°。。.。。..。....。。.。.。..。。.。。.。.。°..。。。。.。。。°。..。。.。。.。31。^概述.62°课程设计任务及要求・・・。。・・。。.・.・。。・。。。。・。・。。。・.。・・・。・.・8^设计任务。O.O.OO..O..OOO.O.OO.OO.O..000.8o2^设计要求。.O...O.OO..OOOOOOO..OO.OO...OOO..O.OO.OOO9算法及数据结构.。。。.・。。.。。.。.・。。。。.・。。・.。。。.・。。。。・.・。。10算法的总体思想.o.oo..o..o..ooooo.oo.o....oooo..o..10词法分析器模块OO.OOOO.OO..O.OOO..OOOOOO.....O..O.O11功目匕...OOOOOOOOO.O.OO.OOO.O.O...OO...OO.11据结构...。.O..O.OOOO.OO..O....OO.O...OO.OO.O11o2o3^算'^法....OOOO.OOO..O..O.OOOOO.OOOO...OO.12°3^语法分析器模块..。0.00...00000.0.0..0OO.O..O13^功目匕.OO..OOOOOOO..OOO.OOOOOO.OO..OOOOO...O..0.13数据结构.O....O..OOOOOOOO.O.OOOO.OO.OOOO....O.133O3o3法。.OOOOOO.O...O.OOO..OO.O.OO..143.4中间代码产生器模块。...O.O.O.OOO..OOOOOO.O..OO..O.O243O4.1^功目匕.O.OOOOOOO.O...OOOOOO..OOOOOO..OOO.O.O.00.243.4o2据结构.。..OOOO..OO.O.OO..O.OO..O.O..OOOO...O24算^^^a°°•。.ctoooo..。。..。.。..。.。....。。。。..。。..。..253.5优化器模块.....273.5°1^功目匕.。°..O....。°.。°.OOO..°.。.。.。°..。°.。.。.000.273°5°2据结木勾.。00000..O..O.OO...OOOO.OO.O.OOOO.000.273°5.3算.......0.....0......0.000..0...0.....0.0.028O6目标代码生成器模块.•。.O.O.O.OO.OOOO.OO.OO.O.O..O..30功能.000....O.O.000..OO.OO.O30数据结构O303.6O3算^^^A00...OO..O.....O.O.....OO.O....O..000..O.00314o程序设计与实现.O..O.OOO.O..OO..OOO....OOO..OO..O..O..OO324°1程序流程图O..OO.OO..O....O..OOO..O0.0032^£序说^明.OOO.OOOO.O.O...O.O.OOOO..OOOOO..O.O33°3^实马垃结口果°.°..°..°.°.°°°..°..°°.°°...OOOOO355。^结论..°..°.......O.OO...OOO°.OOO..°..°....000000。.....°426O^参考文献。..OOO..OOOOO..O.OO.O.O.OOOO..OOO..O..437.收获、体会和建议・O.・・OO・・・・O・O・O……0.0000....OOO...OO1概述在计算机上执行一个高级语言程序一般要分为两步；第一步，用一个编译程序把高级语言翻译成机器语言程序;第二步，运行所得的机器语言程序求得计算结果。在学习《编译原理》课程过程中，逐渐掌握各章节构造编译程序的基本理论，并能独立完成词法分析器、语法分析器和语义分析器实验，在基本实验完成的基础上，逐步完成课程设计。针对自己的理解和学习，实现一个小编译器括符号表的构造.编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、优化、目标代码生成。第一阶段，词法分析。词法分析的任务是：输入源程序对构成源程序的字符串进行分解和扫描，识别出一个个的单词或符号。我们设计了符号表，包括名字栏和信息栏，其中名字栏作为关键字，根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针，从符号表中删除给定名字的表项，并且设计了词法分析器，具体实现为设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序.词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；，能够拼出语言中的各个单词，将拼出的标识符填入符号表，返回识别单词或符号的种别码和属性值.第二阶段，语法分析。在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。我们实现了语法分析器，能够使用预测分析法、递归下降分析法、算符优先分析法、SLR分析法实现对表达式、各种说明语句、控制语句进行语法分析.第三阶段，语义分析和中间代码产生.对语法分析所识别的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。这一阶段包括两个方面的工作。首先，对每种语法范畴进行静态语义检查.如果语义正确，则依循语言的语义规则进行中间代码的翻译。第四阶段,优化。优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码.例如公共子表达式的提取、循环优化、删除无用代码。第五阶段，目标代码生成，把中间代码变换成特定机器上的低级语言代码，有赖于硬件系统结构和机器指令含义来实现最后的翻译。在能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码。通过对编译器的设计实现，一方面再次熟悉了c语言的编程方法及思想，另一方面加深了而对所学编译知识的掌握和理解，也深刻的理解了编译器的思想和实现方法；从词法分析到语法分析，再到语义分析，整个独立而又紧密联系的环节，紧紧相扣，整体的实现理解的更加透彻。不过由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。2课程设计任务及要求2。1设计任务任务内容：①定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；②扫描器设计实现；③语法分析器设计实现；④中间代码设计;⑤中间代码生成器设计实现；⑥中间代码优化；⑦生成目标代码。分析完任务内容，我们制定出一套满足老师要求的语句的文法结构，具体内容如下（其中“？”代表空产生式）：程序>voidmain（）（函数体｝函数体——〉变量声明语句函数体I赋值语句函数体|if（表达式）｛函数体｝［else｛函数体｝］函数体|while（表达式）｛函数体｝函数体|?变量声明语句>类型标识符变量声明语句_1;类型〉intIcharIbool变量声明语句_1〉，标识符变量声明语句_1I二表达式变量声明语句_1|?赋值语句>标识符二表达式；表达式〉算数表达式逻辑表达式逻辑表达式一-〉〉［=］算数表达式|〈［二］算数表达式I二二算数表达式|and算数表达式|or算数表达式Inot算数表达式I?（此处的□代表可选）算数表达式（这个地方直接写出老师上课讲授的形式）：E--〉TE1E1—->+TE1|-TE1I?T--〉FT1T1-->*FT1|/FT1I?F—>标识符［常数］1(E)这个文法满足老师的要求，但是也存在一些不足，比如变量类型中没有处理实数，数组和结构体以及if语句和while语句后必须有大括弧匹配。2。2设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；符号表3算法及数据结构3.1算法的总体思想符号表词法分析器又称为扫描器，它的任务就是对输入的源程序进行词法分析输出单词符号供语法分析使用，语法分析器简称分析器，对单词符号串进行语法分析，根据语法规则进行推导,识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序"。语义分析与中间代码产生器，按照语义规则对语法分析器推导出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器就是对中间代码进行优化处理.目标代码生成器，把中间代码翻译成目标程序。符号表用来登记源程序中出现的变量及其属性.另外，如果源程序有错误，编译发现错误把有关错误信息报告给用户，即出错处理。流程图如下:出错处理目标代码3。2词法分析器模块3.2.1功能词法分析器功能室输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号.程序语言的单词符号一般可分为下列5种。（1）关键字是由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字.（2）标识符用来标示各种名字，如变量名，数组名，函数名等。（3）常数程序中出现用来运算的数值（4）运算符我们所定义的文法包括+，-，*，/算术运算符，还有and,or，not，＞二,〉，〈，〈二，=二逻辑运算符。（5）界符程序中用来分割的符号。3。2。2数据结构一个程序语言的关键字，运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用都不加限制。词法分析器所输出的单词符号常常表示为二元式结构：（单词种别，单词符号的属性值）；相应的数据结构处理为如下表示：char*KeyWords□={〃main〃,〃bool"，〃int"，"char"，"void"，〃if〃，"else〃，〃while〃}；//关键字kcharDefinition[]={?{?,’}’，’[',’]'，’（’，'）',’+','-','*'，'/','='，'〉'，'〈'，'；'，'，','\''，'\〃'};//界符表pchar*ID[1000];intIdNum=0；〃标识符表iintCons[1000]；intConsNumber=0;//算数常量表类码c

typedefstructTokenType{charcode；intvalue；}TokenType;//单词符号的二元式结构3。2.3算法y查到y算术常数yy界符P.TOKEN查到结束关键字标识符结束符开始nnnnyC.TOKENK.TOKEN查填IT表I.TOKEN调用识别器ny查KT表查PT3。2.3算法y查到y算术常数yy界符P.TOKEN查到结束关键字标识符结束符开始nnnnyC.TOKENK.TOKEN查填IT表I.TOKEN调用识别器ny查KT表查PT表常数处理查填CT表3.3.1功能语法分析是编译过程的核心部分.它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则.语法分析器在编译程序中的地位也是非常重要。语言的语法结构是用上下文无关文法描述的.因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。按照语法分析树的建立方法，可以粗略的把语法分析方法分成两类,一类是自上而下的分析方法，另一类是自下而上的分析方法.在本次的课程设计中使用的是自上而下的分析方法中的递归下降分析法，用这种分析法的好处是，直观易懂，便于表示做递归和因子提取。自上而下的分析方法的主旨就是，对任何输入串，试图用一切可能的办法。从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导.这种方法本质上就是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程.3.3.2数据结构对于语法分析过程而言，其处理的数据是来自于Token序列，是词法分析的产物.语法分析的任务就是识别和处理比单词更大的语法单位，比如:程序设计语言中的表达式、各种说明和语句乃至全部程序.所以这个部分不需要构造新的数据结构，其数据结构是沿用上一部分的数据结构，在这里就不再列举了，具体数据结构请参见词法分析部分.主控程序:#y开始A(w)结束error主控程序:#y开始A(w)结束errornNEXT(w)入口voidmain出口A(w)子程序:NEXT(w)NEXT(w)NEXT(w)NEXT(w)NEXT(w)NEXT(w)errorerrorerrorB(w)errorerror入口voidmain出口A(w)子程序:NEXT(w)NEXT(w)NEXT(w)NEXT(w)NEXT(w)NEXT(w)errorerrorerrorB(w)errorerrorerror

if()Y判断是否符合文法中对if的规定NwhileerrorerrorerrorNYNNYvNEXT(w)YNB(w)NEXT(w)Yif()Y判断是否符合文法中对if的规定NwhileerrorerrorerrorNYNNYvNEXT(w)YNB(w)NEXT(w)YNEXT(w)WHILE()NEXT(w)errorerrorerrorW(w)errorNYNEXT(w)NEXT(w)B(w)DO()NEXT(w)errorENDWHILE()为插入的语义动作。*ENDWHILE()B(w)出口入口Nerror,判断该字符是否为标示符pushC(w)NEXT(w)W（w）入口Nerror,判断该字符是否为标示符pushC(w)NEXT(w)W（w）NEXT(w)生成四元式将其加入符号表丫「NEXT(w)C（w）其中IE()为ifelse结构的出口标志3.4中间代码产生器模块3。4。1功能中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。虽然源程序可以直接翻译为目标语言代码，但是许多编译程序却采用了独立于机器的复杂性介于源语言和机器语言之间的中间语言。这样做的好处是：便于进行与机器无关的代码优化工作；使编译程序改变目标机更容易；使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰.中间代码的形式有多种，但是在本实验中采用的是四元式形式。3。4。2数据结构typedefstructQUAT{char^operational;//操作符char*figure1；//操作数1char大figure2；//操作数2char大result；//结果)QUAT；四元式的存储结构QUATQuat[1000];//四元式结构体数组n(kin/*)出口error2errorln入口入口出口FFFGEQ(*)GEQ(/)PUSH(i)NEXT(w)ENEXT(w)yyyNEXT(w)nynyNEXT(w)3.5优化器模块n(kin/*)出口error2errorln入口入口出口FFFGEQ(*)GEQ(/)PUSH(i)NEXT(w)ENEXT(w)yyyNEXT(w)nynyNEXT(w)3。5.1功能优化处理是指产生更高效的目标代码所做的工作.他可以分为在中间代码级上的优化和在目标代码上的优化。在本次课设中，采用的是在中间代码级上的优化。这类优化不依赖于具体的计算机。另外，在优化的基本块中，为了简单处理，没有划分基本块，就是把整个程序看做一个基本块，然后就是处理一个基本块内的优化。由优化编译程序提供的对代码的各种变换必须遵循一定的原则。（1）等价原则。经过优化后不改变程序的运行结果。（2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小.（3）合算原则。应尽可能以较低的代价取得较好的优化效果。3.5。2数据结构typedefstructDAG{intn_num;〃结点的编号char^operational；〃操作符char大M;//主标记char大Additional[MAX]；//附加标记intadditionalnum；//附加标记个数intnextl;〃下一个intnext2；//下一个}DAG;开始DAG置空;依次读取一四元式A=BaC；分别定义B,C结点（若定义过，则免）出口以上为优化器的第一个模块，构造基本块内优化的DAG；出口之后是另外一个模块。有两个假设：①临时变量的作用域是基本块内②非临时变量的作用域也可以是基本块内。3。6目标代码生成器模块3.6。1功能编译模型的最后一个阶段是代码生成。它以源程序的中间代码作为输入，并产生等价的目标程序作为输出。代码生成器的输入包括中间代码和符号表的信息.代码生成是把语义分析后或优化后的中间代码换成目标代码.目标代码一般都有三种形式。（1）能够立即执行的机器语言代码，所有地址均已定位.（2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。（3）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。代码生成主要考虑两个问题：一是如何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。再次说明一下，本次课设没有涉及基本块的划分。3.6。2数据结构typedefstructCODE（char*op;//汇编操作指令char*op1；//第一操作数char*op2;//第二操作数}CODE;CODECode[1000]；目标代码结构体数组char*R=NULL;//寄存器，里面放的是变量的名，就是一个描述表另外还有一个常用栈的描述。取到了结束基本块出口n开始yyn变量信息生成取下一四元式编写目标指令释放寄存器取下一基本块预处理结束处理取到了结束基本块出口n开始yyn变量信息生成取下一四元式编写目标指令释放寄存器取下一基本块预处理结束处理4程序设计与实现4。1程序流程图程序的总体流程图如下:各个模块的程序具体流程图参考第3节。4.2程序说明main()：调用子模块的功能InitStack(S);初始化一个栈结构cifa_main()；调用词法分析功能yufa_main();调用语法分析功能output_yuyi()；输出四元式序列词法分析：cifa_main():词法分析｛可以生成Token序列及静态符号表并输出｝IsLetter()：判断字符是否为字母IsDigit()：判断字符是否为数字IsKey():判断是否为关键字IsDefinition():判断是否为界符InsertID()：向符号表中添加标示符(可判断符号表之前是否已存在此标示符)InsertConst()：向符号表中添加数字(可判断符号表之前是否已存在此数字)语法分析，及中间代码生成：递归下降子程序：判断文法是否正确，并输出自上而下的推导过程输出错误情况插入语义动作并生成未优化的四元式储存原始的四元式编译后端(四元式的优化)：DAG_Main()：四元式优化的主函数QuatBelongToNumber()：判断四元式中操作数是不是为常数Replace():替换冗余的四元式DeleteQuat():删除冗余的四元式Geq()：计算并优化四元式编译后端(目标代码生成)：TargetCode():生成目标代码InitSEMStack()：初始化信息栈ActiveInfo():生成活跃信息表CollectAndEdit():生成汇编代码output_code():输出目标代码4.3实验结果采用如下一段c语言程序进行验证，包含了课设要求的基本语句。这是一段正确的程序，就是符合我们定义的文法。用它来进行程序的验证，各模块输出结果如下所示。在这里先说明一下，若待验证的程序没有错误，那么语法分析就检测不出错误，为了能检测到错误，展示语法分析的功能，就认为的制造出错误，具体见下面语法分析输出模块。voidmain(){inta，b,c，x；if(a〉b){x=(a+b)大c；}else(x=5-a*b;}while(c>=x)(a=c+5大(3+2);b=a+x;}}词法分析器模块输出结果如下所示：它的输出结果形式第一列代表所属类型，第二列为对应的单词。我们的程序也可以识别出字符常量和字符串常量.因为优化那部分没有涉及到这两种常量，所以就没有向大家展示出来。a-c+5*c3+2>;b=a+X-5>-6a-c+5*c3+2>;b=a+X-5>-6.■名名..名：名：：寿幕蜀嘉暮岌界变界常界界常界常界界变界变界变界界名：：名：.字：名名：名：：字：名：：名：：

变界界变界界天界变界常界变界变界界天界变界界变界界uoidmain<><inta■Fbrc■FXIif列」k-4—!■I.■■■■■■■■■■■■■■■■■■■■■■nr'tx于:名.•名.•名：字.•名：名：：名：：四天天界界界天变界变界变邪变界天界变界变界界变界界celsexauhilecx语法分析模块输出的结果如下：因为用来验证的程序没有错误，所以需要人为的添加错误.程序能识别的错误有：①能够识别出未定义标识符②能够检测出标识符的重定义③能够检测出括孤的匹配与否④if和while的判断条件不能为空⑤能够识别出关键字的拼写正确与否⑥表达式的正确与否.给出检测程序如下：voidmain()(inta，b,x;chara；//a重定义if()(//if判断条件为空x=(a+b)*c；}else(x=5一a*b;}while(a〉=b)(a=c+5*(3+2);b=a+x；d=a+b;//d没定义}}临比函数声明甲款少，语句中判断条件不能为空！■_IIII中间代码产生器模块输出的结果如下:用四元式序列来表示.|四元式序夕I"慎作符撬作数1,操作数矿结果M二(>,b3t0)Ll=(if,t0s一_)t2：(+,a,h,tl)t3：(*?tl,c,t2)M：(=?t2,x)TOC\o"1-5"\h\zL5：(else?_)L6:(*,a,b,t3)L*?5?t3?t4)哗(=?t4,x)p：(endif?_)L10=(while,_)Lil:(>=,c3x3t5)L12：(do,t5,_)L13：(+?3S2,t6)L14：(*?5St6?t7)L15:(+3c,t73t8)L16：(=3t8,_?a)^j17：(+,a,x,t?)L18：(=?一b)L19：(enduhile,_)

(4)优化器模块输出结果如下:•结果TOC\o"1-5"\h\z3：(iF,t0,_)L2:(*,a,h,tl)L3:tl?c?x)L4：(else3_)L5:h,t3)L6=(—?5?t3?x)L7：(endif?_)L8：(while,一_)L9:(>=,c?x?t5)L10=(do?t5?_)Lil:(*,c?25,a)L12:(+?a,x?b)L13:(enduhile?_)(4)优化器模块输出结果如下:(5)目标代码生成模块输出结果如下：因为生成目标代码需要获取相关变量的活跃度信息，所以先展示一下符号表的内容。符号表如下：又里类型活跃度：Qaintyyyyy1bintyyyy2cintyyy3xintyyyy4t5叫5t3叫6tlny7t&ny目标代码：0LDR,a1GTB,b2FJR,103STR,t04LD5的。ILb6STR,ti7LDB,tl8MULRj.c9JMP_,1610STR,x11LD12MULR_b13STK,t314LDK,515SUBR,t316STF,x17LBR,c18GER,x19FJK,2729STR,t521LDR,c22ADDR-2523STR,a24LDH,己25ADDR.xJHP_,16(6)可视化界面如下图所示：各模块要输出的内容在上面已经被标出.5结论我们所设计的c语言编译系统可以根据自己所定义的文法成功的进行词法分析，生成相应的Token序列，另外，通过测试，也可以成功地生成静态符号表，并能对静态符号表随时进行查看。我们所设计的C语言编译系统也可以成功地对文档中的内容采用LL1分析法进行语法分析。通过测试，可以检查出所有的错误，并提示出错，但只能输出部分与错误有关的信息，而不能输出全部错误信息.总体来说还算成功。另外，在进行语法分析的同时，我们通过插入语义动作可以同时生成四元式.通过测试，我们可以成功的生成所需的四元式。我们也对四元式的优化进行了测试，我们可以成功地对原始的四元式进行部分的优化，但