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

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

2、、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端45 目 录摘要.3 1. 概述.6 2. 课程设计任务及要求.8 2.1 设计任务.8 2.2 设计要求.9 3. 算法及数据结构.10 3.1算法的总体思想.10 3.2 词法分析器模块.11 3.2.1 功能.11 3.2.2 数据结构.11 3.2.3 算法.12 3.3 语法分析器模块.13 3.3.1功能.13 3.3.2 数据结构.13 3.3.3算法.14 3.4 中间代码产生器模块.24 3.4.1 功能.24 3

3、.4.2 数据结构.24 3.4.3 算法.25 3.5 优化器模块.27 3.5.1 功能.27 3.5.2 数据结构.27 3.5.3 算法.283.6 目标代码生成器模块.30 3.6.1功能.30 3.6.2 数据结构.30 3.6.3 算法.31 4. 程序设计与实现.32 4.1 程序流程图.32 4.2 程序说明.33 4.3 实验结果.355. 结论.426. 参考文献.437. 收获、体会和建议.44 1 概述 在计算机上执行一个高级语言程序一般要分为两步；第一步，用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。在学习编译原理课程过程中

4、，逐渐掌握各章节构造编译程序的基本理论，并能独立完成词法分析器、语法分析器和语义分析器实验，在基本实验完成的基础上，逐步完成课程设计。针对自己的理解和学习，实现一个小编译器括符号表的构造。 编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、优化、目标代码生成。 第一阶段，词法分析。词法分析的任务是：输入源程序，对构成源程序的字符串进行分解和扫描，识别出一个个的单词或符号。我们设计了符号表，包括名字栏和信息栏，其中名字栏作为关键字，根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针，从符号表中删除给

5、定名字的表项，并且设计了词法分析器，具体实现为设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；，能够拼出语言中的各个单词，将拼出的标识符填入符号表，返回识别单词或符号的种别码和属性值。 第二阶段，语法分析。在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。我们实现了语法分析器，能够使用预测分析法、递归下降分析法、算符优先分析法、slr分析法实现对表达式

6、、各种说明语句、控制语句进行语法分析。 第三阶段，语义分析和中间代码产生。对语法分析所识别的各类语法范畴，分析其含义，并进行初步翻译(产生中间代码）。这一阶段包括两个方面的工作。首先，对每种语法范畴进行静态语义检查。如果语义正确，则依循语言的语义规则进行中间代码的翻译。 第四阶段，优化。优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。例如公共子表达式的提取、循环优化、删除无用代码。 第五阶段，目标代码生成，把中间代码变换成特定机器上的低级语言代码，有赖于硬件系统结构和机器指令含义来实现最后的翻译。在能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇

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

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

9、 变量声明语句_1|?赋值语句-标识符=表达式;表达式-算数表达式 逻辑表达式逻辑表达式- =算数表达式|t e1e1-+ t e1|- t e1|?t-f t1t1-* f t1|/ f t1|?f-标识符常数|(e)这个文法满足老师的要求，但是也存在一些不足，比如变量类型中没有处理实数，数组和结构体以及if语句和while语句后必须有大括弧匹配。2.2 设计要求 1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运

10、行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问； 3 算法及数据结构 3.1 算法的总体思想 词法分析器又称为扫描器，它的任务就是对输入的源程序进行词法分析输出单词符号供语法分析使用，语法分析器简称分析器，对单词符号串进行语法分析，根据语法规则进行推导，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析与中间代码产生器，按照语义规则对语法分析器推导出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器就是对中间代码进行优化处理。目标代码生成器，把中间代码翻译成目标程序

11、。符号表用来登记源程序中出现的变量及其属性。另外，如果源程序有错误，编译发现错误，把有关错误信息报告给用户，即出错处理。流程图如下： 出 错 处 理 符 号 表 词法分析器 源程序 语法分析器 单词符号 优化器 语义分析及中间代码产生器 语法单位 目标代码生成器 中间代码 中间代码 目标代码3.2 词法分析器模块 3.2.1 功能 词法分析器功能室输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列5种。 （1）关键字 是由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。 （2）标识符 用来标示各种名字，如变量名，数组名，函数名等

12、。 （3）常数 程序中出现用来运算的数值 （4）运算符 我们所定义的文法包括+，-，*，/算术运算符，还有and，or，not，=，,四元式的个数 n 出口 y 以上为优化器的第一个模块，构造基本块内优化的dag；出口之后是另外一个模块。该结点为带有附加标记的叶结点结构：b|a1，a2.按结点编码顺序，依次读取每一结点信息 入口有两个假设：临时变量的作用域是基本块内非临时变量的作用域也可以是基本块内。 结点为带有附加标记的非叶结点结构： n n a|a1，a2 结束i结点个数 生成a i=a(i=1,2,.)a i为非临时变量 生成四元式a=b c 生成四元式a i = b (i=1,2,.)

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

14、何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。 再次说明一下，本次课设没有涉及基本块的划分。 3.6.2 数据结构 typedef struct codechar *op;/汇编操作指令char *op1;/第一操作数char *op2;/第二操作数code;code code1000;目标代码结构体数组char *r=null;/寄存器，里面放的是变量的名，就是一个描述表另外还有一个常用栈的描述。 开始 3.6.3 算法 释放寄存器 编写目标指令 取下一四元式 变量信息生成 结束 结束处理 取到了 取下一基

15、本块 预处理 n y 基本块出口 y n 4 程序设计与实现4.1程序流程图 错误输出中间代码产生器 目标代码生成器 结束 优化器有错误 语法分析器 词法分析器 开始 程序的总体流程图如下： y n 各个模块的程序具体流程图参考第3节。4.2 程序说明main()： 调用子模块的功能initstack(s);初始化一个栈结构cifa_main();调用词法分析功能yufa_main();调用语法分析功能output_yuyi();输出四元式序列词法分析：cifa_main(): 词法分析可以生成token序列及静态符号表并输出isletter():判断字符是否为字母isdigit():判断字符

16、是否为数字iskey():判断是否为关键字isdefinition():判断是否为界符insertid():向符号表中添加标示符（可判断符号表之前是否已存在此标示符）insertconst():向符号表中添加数字（可判断符号表之前是否已存在此数字）语法分析,及中间代码生成： 递归下降子程序：判断文法是否正确，并输出自上而下的推导过程 输出错误情况 插入语义动作并生成未优化的四元式 储存原始的四元式编译后端（四元式的优化）：dag_main():四元式优化的主函数quatbelongtonumber():判断四元式中操作数是不是为常数replace():替换冗余的四元式deletequat():

17、删除冗余的四元式geq():计算并优化四元式编译后端（目标代码生成）：targetcode():生成目标代码initsemstack():初始化信息栈activeinfo():生成活跃信息表collectandedit():生成汇编代码output_code():输出目标代码 4.3 实验结果 采用如下一段c语言程序进行验证，包含了课设要求的基本语句。这是一段正确的程序，就是符合我们定义的文法。用它来进行程序的验证，各模块输出结果如下所示。在这里先说明一下，若待验证的程序没有错误，那么语法分析就检测不出错误，为了能检测到错误，展示语法分析的功能，就认为的制造出错误，具体见下面语法分析输出模块。

18、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）词法分析器模块输出结果如下所示：它的输出结果形式第一列代表所属类型，第二列为对应的单词。我们的程序也可以识别出字符常量和字符串常量。因为优化那部分没有涉及到这两种常量，所以就没有向大家展示出来。（2） 语法分析模块输出的结果如下： 因为用来验证的程序没有错误，所以需要人为的添加错误。程序能识别的错误有：能够识别出未定义标识符能够检测出标识符的重定义能够检测出括弧的匹配与否if和while的判断条件不能为空能够识别出关键字

19、的拼写正确与否表达式的正确与否。给出检测程序如下：void main() int a,b,x; char a;/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没定义 （3） 中间代码产生器模块输出的结果如下：用四元式序列来表示。（4） 优化器模块输出结果如下：（5） 目标代码生成模块输出结果如下：因为生成目标代码需要获取相关变量的活跃度信息，所以先展示一下符号表的内容。（6） 可视化界面如下图所示：各模块要输出的内容在上面已经被标出。 5 结论 我们所设计的c语言编译系统可以根据自

20、己所定义的文法成功的进行词法分析，生成相应的token序列，另外，通过测试，也可以成功地生成静态符号表，并能对静态符号表随时进行查看。我们所设计的c语言编译系统也可以成功地对文档中的内容采用ll1分析法进行语法分析。通过测试，可以检查出所有的错误，并提示出错，但只能输出部分与错误有关的信息，而不能输出全部错误信息。总体来说还算成功。另外，在进行语法分析的同时，我们通过插入语义动作可以同时生成四元式。通过测试，我们可以成功的生成所需的四元式。我们也对四元式的优化进行了测试，我们可以成功地对原始的四元式进行部分的优化，但不能优化至最简，而是只能对两个操作数皆为常数，及四元式重复冗余这两种情况进行优

21、化。我们也可以成功地生成活跃信息表，并通过活跃信息表生成相应的机器代码。通过测试，我们所生成的机器代码是准确无误的。 因此，整体来说，我们所设计的c语言编译系统是成功的。但我们也有遗憾，我们所设计的符号表，单独是可以运行的，并没有建立相应的活动记录。 6 参考文献1、陈火旺.程序设计语言编译原理（第3版）. 北京：国防工业出版社.2000.2、美 alfred v.aho ravi sethi jeffrey d. ullman著.李建中，姜守旭译.编译原理.北京：机械工业出版社.2003.3、美 kenneth c.louden著.冯博琴等译.编译原理及实践.北京：机械工业出版社.2002.4、金成植著.编译程序构造原理和实现技术. 北京：高等教育出版社. 2002. 7 收获、体会和建议 经过了为期2周的课程设计，让一开始都不知道编译器是何物的我们成功蜕变，在完成基本任务的基础上又进一步实现了编译器后端。依稀记得刚刚接触课程题目时，都不知道该如何下手，