编译原理课程设计报告-简单文法的编译器的设计与实现.docx

《编译原理课程设计报告-简单文法的编译器的设计与实现.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计报告-简单文法的编译器的设计与实现.docx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课 程 设 计 报 告设计题目：简单文法的编译器的设计与实现班级：计算机1206组长学号：*组长姓名：指导教师：设计时间：2014年12月11摘 要编译原理是计算机科学与技术专业一门重要的专业课, 它具有很 强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作 原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教 学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展 到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机 科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的 成果与精华。本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务

2、中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力， 进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端目 录摘要31. 概述62. 课程设计任务及要求82.1 设计任务82.2 设计要求93. 算法及数据结构103.1 算法的总体思想103.2 词法分析器模块113.2.1 功能113.2.2 数据结构113.2.3 算法123.3 语法分析器模块133.3.1 功能133.3.2 数据结构133.3.3 算法143.4 中间代码产生器模块243.4.1 功能243.4.2 数据结构243.4.3 算法253.5 优化器模块273.5.1 功能273.5.2 数

3、据结构273.5.3 算法283.6 目标代码生成器模块303.6.1 功能303.6.2 数据结构303.6.3 算法314. 程序设计与实现324.1 程序流程图324.2 程序说明334.3 实验结果355. 结论426. 参考文献437. 收获、体会和建议441 概述在计算机上执行一个高级语言程序一般要分为两步；第一步，用一 个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器 语言程序求得计算结果。在学习编译原理课程过程中，逐渐掌握各 章节构造编译程序的基本理论，并能独立完成词法分析器、语法分析器 和语义分析器实验，在基本实验完成的基础上，逐步完成课程设计。针 对自己的理解

4、和学习，实现一个小编译器括符号表的构造。编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分 析、语义分析和中间代码产生、优化、目标代码生成。第一阶段，词法分析。词法分析的任务是：输入源程序，对构成源 程序的字符串进行分解和扫描，识别出一个个的单词或符号。我们设计 了符号表，包括名字栏和信息栏，其中名字栏作为关键字，根据给定的 名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其 加入到符号表中，否则返回指向该名字的指针，从符号表中删除给定名 字的表项，并且设计了词法分析器，具体实现为设计各单词的状态转换 图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调 用的子程

5、序。词法分析器具备预处理功能。将不翻译的注释等符号先滤 掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理 子程序；，能够拼出语言中的各个单词，将拼出的标识符填入符号表， 返 回识别单词或符号的种别码和 属性值。第二阶段，语法分析。在词法分析的基础上，根据语言的语法规则， 把单词符号串分解成各类语法单位。通过语法分析，确定整个输入串是 否构成语法上正确的“程序”。我们实现了语法分析器，能够使用预测分析法、递归下降分析法、算符优先分析法、SLR分析法实现对表达式、各 种说明语句、控制语句进行语法分析。第三阶段，语义分析和中间代码产生。对语法分析所识别的各类语 法范畴，分析其含义，并进

6、行初步翻译（产生中间代码）。这一阶段包括 两个方面的工作。首先，对每种语法范畴进行静态语义检查。如果语义 正确，则依循语言的语义规则进行中间代码的翻译。第四阶段，优化。优化的任务在于对前段产生的中间代码进行加工 变换，以期在最后阶段能产生出更为高效的目标代码。例如公共子表达 式的提取、循环优化、删除无用代码。第五阶段，目标代码生成，把中间代码变换成特定机器上的低级语 言代码，有赖于硬件系统结构和机器指令含义来实现最后的翻译。在能 完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标 代码。通过对编译器的设计实现，一方面再次熟悉了c语言的编程方法及 思想，另一方面加深了而对所学编译知识

7、的掌握和理解，也深刻的理解 了编译器的思想和实现方法；从词法分析到语法分析，再到语义分析， 整个独立而又紧密联系的环节，紧紧相扣，整体的实现理解的更加透彻。 不过由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢 复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译 器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的 系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。2 课程设计任务及要求2.1 设计任务任务内容：定义一个简单程序设计语言文法（包括变量说明语句、 算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While 语句等）；扫描器

8、设计实现；语法分析器设计实现；中间代码设计； 中间代码生成器设计实现；中间代码优化；生成目标代码。分析完任务内容，我们制定出一套满足老师要求的语句的文法结构， 具体内容如下（其中“？”代表空产生式）：程序-void main （）函数体函数体-变量声明语句 函数体|赋值语句 函数体|if（表达式）函 数体else函数体函数体|while（表达式）函数体 函数体|?变量声明语句-类型 标识符 变量声明语句_1 ;类型-int |char |bool变量声明语句_1-,标识符 变量声明语句_1 |=表达式 变量声明语 句_1|?赋值语句-标识符=表达式;表达式-算数表达式 逻辑表达式逻辑表达式-

9、=算数表达式|T E1E1-+ T E1|- T E1|?T-F T1T1-* F T1|/ F T1|?F-标识符常数|(E)这个文法满足老师的要求，但是也存在一些不足，比如变量类型中没 有处理实数，数组和结构体以及if语句和while语句后必须有大括弧匹 配。2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小 组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要 求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反 映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲

10、解运行结果，说明系统的特色和创新 之处，并回答指导教师的提问；3 算法及数据结构3.1 算法的总体思想词法分析器又称为扫描器，它的任务就是对输入的源程序进行词法分析输出 单词符号供语法分析使用，语法分析器简称分析器，对单词符号串进行语法分析， 根据语法规则进行推导，识别出各类语法单位，最终判断输入串是否构成语法上正 确的“程序”。语义分析与中间代码产生器，按照语义规则对语法分析器推导出的 语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器就是对中间代 码进行优化处理。目标代码生成器，把中间代码翻译成目标程序。符号表用来登记 源程序中出现的变量及其属性。另外，如果源程序有错误，编译发现

11、错误，把有关 错误信息报告给用户，即出错处理。流程图如下：符号表目标代码3.2 词法分析器模块3.2.1 功能词法分析器功能室输入源程序，输出单词符号。单词符号是一个 程序语言的基本语法符号。程序语言的单词符号一般可分为下列5种。（1）关键字 是由程序语言定义的具有固定亿的标识符。有时称 这些标识符为保留字或基本字。（2）标识符 用来标示各种名字，如变量名，数组名，函数名等。（3）常数 程序中出现用来运算的数值（4）运算符我们所定义的文法包括+，-，*，/算术运算符，还有and，or，not，=，=，=逻辑运算符。（5）界符 程序中用来分割的符号。3.2.2 数据结构一个程序语言的关键字，运算

12、符和界符都是确定的，一般只有几 十个或上百个。而对于标识符或常数的使用都不加限制。词法分析器所 输出的单词符号常常表示为二元式结构：（单词种别，单词符号的属性 值）；相应的数据结构处理为如下表示：关键字kchar Definition=, ,（,） , + ,界符表pchar *ID1000;int IdNum=0;/标识符表iint Cons1000;int ConsNumber=0;/算数常量表类码ctypedef struct TokenTypechar code;int value;TokenType;/单词符号的二元式结构3.2.3 算法3.3.3 算法3.3 语法分析器模块3.3.

13、1 功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词 符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法 分析器在编译程序中的地位也是非常重要。语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工 作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。按照语法分析树的建立方法，可以粗略的把语法分析方法分成两类， 一类是自上而下的分析方法，另一类是自下而上的分析方法。在本次的 课程设计中使用的是自上而下的分析方法中的递归下降分析法，用这种 分析法的好处是，直观易懂，便于表示做递归和因子提取。自上而下的分析方法的主旨就是，对任何输入串，试图用一切可能的 办

14、法。从文法开始符号出发，自上而下的为输入串建立一棵语法树。或 者说，为输入串寻找一个最左推导。这种方法本质上就是一种试探过程， 是反复使用不同产生式谋求匹配输入串的过程。3.3.2 数据结构对于语法分析过程而言，其处理的数据是来自于Token序列，是词法 分析的产物。语法分析的任务就是识别和处理比单词更大的语法单位， 比如：程序设计语言中的表达式、各种说明和语句乃至全部程序。所以 这个部分不需要构造新的数据结构，其数据结构是沿用上一部分的数据 结构，在这里就不再列举了，具体数据结构请参见词法分析部分。13主控程序：voidmain()A（w）子程序入口errorerrorNEXT(w)出口DN

15、EXT(w)NEXT(w)NEXT(w)NEXT(w)NEXT(w)B(w)errorerrorerrorerrorB（w）子程序：15error出口生成四元式NEXT(w)19ENDWHILE()为插入的语义动作。ENDWHILE( )B(w)出口C（w）子程序：#D（w）子程序：21IE（）errorNEXT(w)其中IE（）为if else结构的出口标志233.4 中间代码产生器模块3.4.1 功能中间代码是高级程序语言中，各种语法成分的语义结构表示；它介 于源语言和目标语言之间。虽然源程序可以直接翻译为目标语言代码，但是许多编译程序却采 用了独立于机器的复杂性介于源语言和机器语言之间的

16、中间语言。这样 做的好处是：便于进行与机器无关的代码优化工作；使编译程序改变目 标机更容易；使编译程序的结构在逻辑上更为简单明确，以中间语言为 界面，编译前端和后端的接口更清晰。中间代码的形式有多种，但是在本实验中采用的是四元式形式。3.4.2 数据结构typedef struct QUATchar *operational;/操作符char *figure1;/操作数1char *figure2;/操作数2char *result;/结果QUAT;四元式的存储结构QUAT Quat1000;/四元式结构体数组3.4.3算法25( 开始 I 初始化 NEXET (w)error n#y结果输出

17、I 结束 j入口T+nn+-yyNEXT (w)NEXT(w)TTGEQ(+)GEQ(-) I出口 )3.5 优化器模块3.5.1 功能优化处理是指产生更高效的目标代码所做的工作。他可以分为在中 间代码级上的优化和在目标代码上的优化。在本次课设中，采用的是在 中间代码级上的优化。这类优化不依赖于具体的计算机。另外，在优化 的基本块中，为了简单处理，没有划分基本块，就是把整个程序看做一 个基本块，然后就是处理一个基本块内的优化。由优化编译程序提供的 对代码的各种变换必须遵循一定的原则。（1）等价原则。经过优化后不改变程序的运行结果。（2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储

18、 空间较小。（3）合算原则。应尽可能以较低的代价取得较好的优化效果。3.5.2 数据结构typedef struct DAGint n_num;/结点的编号char *operational;/操作符char *M;/主标记char *AdditionalMAX;/附加标记int additionalnum;/附加标记个数int next1;/下一个int next2;/下一个DAG;273.5.3 算法开始DAG置空；依次读取 一四元式A=B C； 分别定义 B,C 结点 （若定义过，则免）ni四元式的个数出口以上为优化器的第一个模块，构造基本块内优化的DAG；出口之后是另外一个模块。#有两

19、个假设：临时变量的作用域是基本块内非临时变量的作用域也可以是基本块内。293.6 目标代码生成器模块3.6.1 功能编译模型的最后一个阶段是代码生成。它以源程序的中间代码作 为输入，并产生等价的目标程序作为输出。代码生成器的输入包括中间 代码和符号表的信息。代码生成是把语义分析后或优化后的中间代码换 成目标代码。目标代码一般都有三种形式。（1） 能够立即执行的机器语言代码，所有地址均已定位。（2） 待装配的机器语言模块。当需要执行时，由连接装入程序把它们 和某些运行程序连接起来，转换成能执行的机器语言代码。（3） 汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语 言代码。代码生成主要考

20、虑两个问题：一是如何使生成的目标代码较短； 另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的 次数。这两个问题都直接影响目标代码的执行速度。再次说明一下，本次课设没有涉及基本块的划分。3.6.2 数据结构typedef struct CODEchar *op;/汇编操作指令char *op1;/第一操作数char *op2;/第二操作数CODE;CODE Code1000;目标代码结构体数组char *R=NULL;/寄存器，里面放的是变量的名，就是一个描述表 另外还有一个常用栈的描述。3.6.3 算法314 程序设计与实现4.1程序流程图程序的总体流程图如下：各个模块的程序具体

21、流程图参考第3节。4.2 程序说明main()： 调用子模块的功能InitStack(S);初始化一个栈结构cifa_main();调用词法分析功能yufa_main();调用语法分析功能output_yuyi();输出四元式序列词法分析：cifa_main(): 词法分析可以生成Token序列及静态符号表并输出IsLetter():判断字符是否为字母IsDigit():判断字符是否为数字IsKey():判断是否为关键字IsDefinition():判断是否为界符InsertID():向符号表中添加标示符(可判断符号表之前是否已存在此标示 符)InsertConst():向符号表中添加数字(可

22、判断符号表之前是否已存在此数 字)语法分析,及中间代码生成：递归下降子程序：判断文法是否正确，并输出自上而下的推导过程 输出错误情况插入语义动作并生成未优化的四元式储存原始的四元式编译后端(四元式的优化)： DAG_Main():四元式优化的主函数 QuatBelongToNumber():判断四元式中操作数是不是为常数 Replace():替换冗余的四元式 DeleteQuat():删除冗余的四元式 Geq():计算并优化四元式编译后端(目标代码生成)：TargetCode():生成目标代码 InitSEMStack():初始化信息栈 ActiveInfo():生成活跃信息表 Collect

23、AndEdit():生成汇编代码 output_code():输出目标代码394.3 实验结果采用如下一段C语言程序进行验证，包含了课设要求的基本语句。 这是一段正确的程序，就是符合我们定义的文法。用它来进行程序的验 证，各模块输出结果如下所示。在这里先说明一下，若待验证的程序没 有错误，那么语法分析就检测不出错误，为了能检测到错误，展示语法 分析的功能，就认为的制造出错误，具体见下面语法分析输出模块。 void main()int a,b,c,x;if(ab)x=(a+b)*c;else x=5-a*b;while(c=x)a=c+5*(3+2);b=a+x;（1）词法分析器模块输出结果如下

24、所示：它的输出结果形式第一列代表 所属类型，第二列为对应的单词。我们的程序也可以识别出字符常量和 字符串常量。因为优化那部分没有涉及到这两种常量，所以就没有向大 家展示出来。(2)语法分析模块输出的结果如下：因为用来验证的程序没有错误，所以需要人为的添加错误。程序能识 别的错误有：能够识别出未定义标识符能够检测出标识符的重定义 能够检测出括弧的匹配与否if和while的判断条件不能为空能够 识别出关键字的拼写正确与否表达式的正确与否。给出检测程序如下： void main()int a,b,x;char a;/a重定义if()/if判断条件为空x=(a+b)*c;else x=5-a*b;wh

25、ile(a=b)a=c+5*(3+2);b=a+x;d=a+b;/d没定义在语句中判断条件不能为空!（3）中间代码产生器模块输出的结果如下： 用四元式序列来表示。I四元式序？卜阿作符.阑乍数1，操作数2,结果 工0：(,日,b, t0)Ll=(if, t0, 一 _)匕2二t+ j 己，h, ti)匕3：(*s tl s c , t2 )L4：( = , t2 5 _,x)L5：(else 5L6：(*?日，h, t3)L7：(-5 5 j t3,t4)产8：(=,七4, 一,K)L9：(endif? _，_， _)L10： (while, _， _， _) Lll：(=,心，Xj t5)L1

26、2：(do,七5， _， _)L13=(+j 3, 2, t6)L14：(*j 5, t6, t7)五5：( + j c 5 t?j t8 )卜16 ( = jt8,a)L17：(+,a, x, t?)L18：(=jt?,b)19二(EndlJhiIe, 一 一 _)(4)优化器模块输出结果如下:L5：(*?已,b, t3)L6：(-, 5 ? t3 ? x)L7：(endifj_)L8：(while,一_)L9：(=, c,X,t5 )卜10：(do, t5,_)Lll：(+, c, 25 j a)L12：(+, a, xs b)L13：(enduile, _, _#（5）目标代码生成模块输

27、出结果如下：45因为生成目标代码需要获取相关变量的活跃度信息，所以先展示一下符号表的内容。符号表如下： 7K- M-里-口类型活跃度：0aintyyyyy1bintyyyy2cintyyy3Xintyyyy4t5y5t3ny6tlny7tny目标代码：LDR,a1GTHj2FJE,103STK,t04LDR.日5ADDILb6STK,ti7LDK,tl8MULRj- c9JMP一1610ST儿乂11LDR.m12MULR,b13ST儿启14LD儿515SUBR.t316STRj-X17LDEj-C18GERj- X19FJB.2729STRj-t521LDRj-C22ADDR.Z523ST儿己

28、24LD儿己25ADDRPX56JMF（6）可视化界面如下图所示：各模块要输出的内容在上面已经被标出。5 结论我们所设计的C语言编译系统可以根据自己所定义的文法成功的进 行词法分析，生成相应的Token序列，另外，通过测试，也可以成功地 生成静态符号表，并能对静态符号表随时进行查看。我们所设计的C语 言编译系统也可以成功地对文档中的内容采用 LL1 分析法进行语法分 析。通过测试，可以检查出所有的错误，并提示出错，但只能输出部分 与错误有关的信息，而不能输出全部错误信息。总体来说还算成功。另 外，在进行语法分析的同时，我们通过插入语义动作可以同时生成四元 式。通过测试，我们可以成功的生成所需的

29、四元式。我们也对四元式的 优化进行了测试，我们可以成功地对原始的四元式进行部分的优化，但 不能优化至最简，而是只能对两个操作数皆为常数，及四元式重复冗余 这两种情况进行优化。我们也可以成功地生成活跃信息表，并通过活跃 信息表生成相应的机器代码。通过测试，我们所生成的机器代码是准确 无误的。因此，整体来说，我们所设计的C语言编译系统是成功的。但我们 也有遗憾，我们所设计的符号表，单独是可以运行的，并没有建立相应 的活动记录。6 参考文献1、陈火旺.程序设计语言编译原理（第3版）. 北京：国防工业 出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D. Ul

30、lman 著.李建中， 姜守旭译.编译原理.北京：机械工业出版社.2003.3、美 Kenneth C.Louden著.冯博琴等译.编译原理及实践.北京： 机械工业出版社.2002.4、金成植著.编译程序构造原理和实现技术. 北京：高等教育 出版社. 2002.7 收获、体会和建议经过了为期2周的课程设计，让一开始都不知道编译器是何物的我 们成功蜕变，在完成基本任务的基础上又进一步实现了编译器后端。依 稀记得刚刚接触课程题目时，都不知道该如何下手，虽然同时也在进行 编译理论课，但当真正要将理论变为实践时，着手起来并没有想象中的 那么容易。万事开头难，这句话一点都不错。刚开始听到别的同学说定义一

31、个 自己的文法，我的第一反应是怎么可能呢？在与组员的交流中，最终我 们组确定了一套类似于C语言的文法。定义属于自己的C语言文法之后， 发现自己对编译的理解又深了一层。整个过程下来收获还是颇多。当定义了属于自己的文法之后，接下来的任务就显得非常明了。虽 然之后还遇到了很多技术性问题，比如之前我们对VC的对话框和单文档 实现比较熟悉，多文档很少涉及，又比如在难度较大的语法语义分析中 总是出问题等等。但是这些问题都不会阻挡我们课程设计的进行，因为 我们不仅有强大的团队，出现问题还可以即时向老师寻求帮助，而且还 有各种网络途径和图书馆资源，在此非常感谢他们提供的各种帮助。当然我们也遇到了一些目前还没有

32、解决的问题，比如说在进行float 类型的数据操作时，汇编会出现溢出错误，所以即使在语义语法上都没 有问题，我们也没有采用这种类型。另外，对函数的操作和数组的定义 都没有去涉及。符号表的功能也不是很完善，基本上还是处于一种比较 不完美的状态。本次课程设计让大家都学到了很多。首先，VC不再是仅仅给我们提 供了编程环境，它还有许多我们以前上机课乃至实习时不曾了解的功能，我们以后也将会继续探索其更多的功能。其次，对于编译程序的理解， 我们不再停留在对词法、语法语义分析等理论知识的了解，还掌握了编 译程序的具体实现。虽然我们的设计是在别人完成的基础上学习的，但 是这并不妨碍我们对知识和技能的掌握，我相信只有积累到足够多的知 识与经验，才能更好地实现创新。最后，在团队合作以及遇到问题后的 分析处理能力也得到了很大的提高。