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

课 程 设 计 报 告设计题目：一个简单文法编译器的设计与实现班 级：计算机1302组长学号：组长姓名：指导教师：设计时间：2015年12月1设计分工摘 要现代计算机的程序很多都是用高级语言编写的，而这些高级语言计算机是无法识别的，因此需要将它们转变成计算机能识别的语言，此时就需要借助到编译程序。编译程序是一种翻译程序，它特指把某种高级语言（如c、java、pascal）翻译成具体计算机上的低级程序设计语言。编译程序是计算机系统软件最主要的组成部分之，也是用户最直接关系的工具之一。一个编译程序的可以划分为前端和后端。前端包括词法分析、语法分析、语义分析与中间代码生成三个阶段，后端包括优化、目标代码生成两个阶段，另外还有符号表的管理和错误处理贯穿整个过程。一个编译程序，既可以一个阶段一个阶段地对源程序进行分析，也可以前端只对源程序进行一遍分析，后端也只进行一遍分析。本课设实现了对c语言中的一部分功能的编译，包括算术逻辑表达式、if语句、while语句以及一维数组等。前端对源程序扫描一遍实现词法分析、语法分析、语义分析与中间代码生成三个阶段，后端进行目标代码生成，整个过程穿插符号表管理和错误处理。关键词：编译程序，前端，后端目 录摘要.i1 概述 .12 课程设计任务及要求 .2 2.1 设计任务 .2 2.2 设计要求.23 算法与数据结构.3 3.1 算法的总体思想（流程）.3 3.2 词法分析识别器模块.4 3.2.1 功能.4 3.2.2 数据结构.5 3.2.3 算法.9 3.3 语法分析模块.11 3.3.1 功能.113.3.2 数据结构.12 3.3.3 算法.16 3.4 语义分析和中间代码生成模块.30 3.4.1 功能.303.4.2 数据结构.31 3.4.3 算法.33 3.5 符号表模块.41 3.5.1 功能.413.5.2 数据结构.41 3.5.3 算法.43 3.6 目标代码生成模块.43 3.6.1 功能.433.6.2 数据结构.44 3.6.3 算法.454 程序设计与实现.474.1 程序流程图.47 4.2 程序说明.47 4.3 实验结果.505 结论.616 参考文献.627 收获、体会和建议.62631 概述在计算机上执行一个高级语言程序一般要分为两步；第一步，把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。编译程序就是将高级语言程序翻译成机器语言程序或汇编语言程序的工具。工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成。前端包含词法分析、语法分析、语义分析和中间代码生成三个阶段，后端包含优化、目标代码生成两个阶段。词法分析的任务是对构成源程序的字符串进行分解和扫描，识别出一个个token序列，并标上类别码以区分关键字、标识符、常数、变量、数组界符等。词法分析器用自动机实现，每读入一个字符，就进行状态转移，当转移到终止状态的时候一个token就识别出来了。此外，词法分析还要进行常数处理、关键字和标识符的区分操作。语法分析在词法分析的基础上，根据语言的语法规则，确定整个输入串在语法上是否是正确的。分析方法有递归下降子程序分析法、ll(1)分析法、lr(0)分析法、简单优先分析法等。在语义分析和中间代码生成这一过程中，对语法分析所识别的各类语法范畴，要分析其含义，并以四元式的形式产生中间代码。优化的任务在于对中间代码进行加工变换以产生出更为高效的目标代码，主要进行常数合并、公共子表达式节省、删除无用赋值、循环优化等操作。目标代码生成的任务是把中间代码变换成特定机器上的低级语言代码，这一步需要考虑硬件系统结构、机器指令以及寄存器个数等情况，将一中间代码程序段翻译成汇编语言或机器语言目标代码。此外，在这五个阶段当中，符号表的管理、错误处理要穿插在当中进行。本次课设将前端的三个阶段整合到一起，通过对输入的源程序扫描一遍的方式实现，入口为语法分析，使用递归下降子程序分析法。将词法分析器作为语法分析的子程序，当语法分析需要用到token时，调用词法分析器识别出一个token串，同时在语法分析的过程中插入语义动作，每识别完一定的token串就能生成四元式。在后端则直接根据四元式生成目标代码。符号表用于存储变量以及检查是否有重定义、未定义的变量。在错误处理中，一旦发现错误，就进行输出并立即停止编译过程。2 课程设计任务及要求2.1 设计任务定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、if语句、while语句等）；扫描器设计实现；语法分析器设计实现；中间代码设计；中间代码生成器设计实现；目标代码生成。2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。3 算法与数据结构3.1 算法的总体思想（流程）对给定的一段源程序，先进行前端分析。前端包括词法分析、语法分析、语义分析和中间代码生成三个阶段，这三个阶段通过对输入的源程序扫描一遍的方式即可实现，词法分析器作为语法分析的子程序，当语法分析需要用到token时，调用词法分析器识别出一个token串，同时在语法分析的过程中插入语义动作，在进行语法分析的同时也能生成四元式。然后将生成的四元式交给后端进行目标代码生成。此外，符号表用来记录源程序中出现的变量，如果在分析的过程中出现错误，则进行错误处理，将哪一行出现的哪种错误输出。具体流程图如下：源程序前端（词法分析、语法分析、语义分析和中间代码生成）后端（目标代码生成）中间代码目标代码符号表管理错误处理3.2 词法分析模块3.2.1 功能识别器：词法分析器中识别器的具体功能为识别单词的有限自动机。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列4种。（1）关键字：由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。（2）标识符：标示各种名字，如变量名，数组名，函数名等。 （3）常数：程序中出现用来运算的数值，即以自身形态面对用户和系统。（4）界符：单字符界符：+,*,/,！,%等。双字符界符：=,=,19,23,24,=,25,&,26,|,27,!,28,+,29,30,*,31,/,32,%,33,35,36,;,37,(,38,),39,40,41,42,43数组,44;/界符表还有对常数的处理和数组的单独处理（编号和属性的区分）。3.2.3 算法：数组处理：先查找字符找到数组的左括号，将其赋值为“0”，然后再找到右括号，将数组标号的值计算出来。+dd-ddddd.e+|-整数小数e指数e常数处理：词法分析的算法流程图：开始结束调用识别器关键字/标识符算术常数结束符#查kt表查到查填it表查填ct表常数处理c.token查pt表p.tokeni.tokenk.tokenyn查到ere:非法界符ynyynnny3.3 语法分析模块3.3.1 功能语法分析是编译的第二阶段，其任务是识别和处理比单词更大的语法单位，如：程序设计语言中的表达式、各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。另一方面语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位也是非常重要。语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。 按照语法分析树的建立方法，可以粗略的把语法分析方法分成两类，一类是自上而下的分析方法，另一类是自下而上的分析方法。在本次的课程设计中我们组使用的是自上而下的分析方法中的递归下降分析法，用这种分析法的好处是，直观易懂，便于表示做递归和因子提取，对文法的要求比较低，可以通过文法变换的方法将其转换为递归下降的方式。通过递归下降的方法将文法翻译成语法制导的形式，将接收到的token串进行扫描分析。本次试验我们其中一大亮点就是编译前端在语法分析的基础上进行一遍扫描，完成词法分析，语法分析，符号表填充以及中间代码的生成。这样要求在语法分析时每次接收一个token串(结构体)，这样在进行语法分析的时候将符号表语义动作和四元式生成的语义动作嵌入到其中便可以达到目的。同时我们本次实验一个很大的亮点就是我们对数组进行了识别以及各种运算操作，支持数组声明，赋值，数组元素的计算等等。同时在语法中出现的错误会报告出来，并终止程序的运行。例如缺少分号，大括号，小括号等等。3.3.2 数据结构在词法分析中已经定义的token结构体typedef struct tokenchar s20;int code;extramessage extra;token;/token结构体对于语法分析过程而言，其处理的数据是来自于token序列，是词法分析的产物。语法分析的任务就是识别和处理比单词更大的语法单位，比如：程序设计语言中的表达式、各种说明和语句乃至全部程序。主要是通过子程序的递归调用完成语法分析，没有过多的结构体。以下是我们本次实验的文法：it标识符：00ct字符：01st字符串：02ct常数：03kt关键字：void 04,char 05,short 06,int 07,long long 08,float 09,double 10,bool 11,if 12,else 13,while 14,do 15,for 16,main 17,return 18pt界符：= 19, 23, 24,= 25,& 26,| 27,! 28,+ 29,- 30,* 31,/ 32,% 33, 35, 36,; 37,( 38,) 39, 40, 41, 42, 431 语言的文法产生式集合程序定义 ( ) /只有主函数语句定义 | | | | ； ， | | = | = | = = ； | = ； | = ； if（） | if（） else while () 逻辑语句定义 | | & | 1 | 2 | 算术表达式定义 0 | 1 | | 2 | ( ) | 类型定义 int | double | char | 单词集定义 | | e | | . 字符集定义 a|b|c|z|a|b|c|z 0|1|2|3|4|5|6|7|8|9 其中：0 +或- 1 *或/或% 2 单目运算符 1 =或!= 2 =或或=或= geq(=)出 口nnext(w)expression geq()=next(w)expression geq(=)next(w)expression geq()nnnnexpression 表达式入 口next(w)tt+ geq(+)出 口-next(w)t geq(-)nnt 算数项入 口next(w)yy* geq(*)出 口n/next(w)y geq(/)%next(w)y geq(%)nnn入 口next(w)f+ geq(+) fn-next(w)f geq(-)!next(w)f geq(!) 出 口y 算数因子nnn入 口push(i)identifier or const出口（next(w)logicstatement)next(w)nnnerror1error2f 算数单元3.4 语义分析和中间代码生成模块3.4.1 功能中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。中间代码设置的目的是便于编译的后期处理（如优化和目标生成）。在我看来，中间代码即四元式的生成其实是为后期的一个准备过程，这样做的好处是：便于进行与机器无关的代码优化工作；使编译程序改变目标机更容易；使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。下面我来介绍一下四元式生成的过程：首先我们要先定义一个语义栈 semi,在语法分析扫描的过程中，我们要将接收的终结符压入栈中（push(i) 压栈函数(把当前 i 压入语义栈)），这样每当读到一个语义动作的时候我们就可以执行语义动作（geq（i），将栈顶和次栈顶元素弹出，生成四元式。不同的语句的四元式结构不同，在此我将四元式进行分类：（1） 双目运算符（2） 单目运算符（3） 赋值运算符（4） 条件语句（5） 循环语句（6） 数组 在四元式生成过程中要注意栈顶与次栈顶的出栈顺序，分清主操作数和次操作数，我认为合适插入语义动作以及语义动作的调用也要选择恰当时机。3.4.2 数据结构定义语义栈，链式栈typedef struct tokenstack tokennode *base; tokennode *top; sqstack;定义四元式域结构体 struct fourfactor token factor; bool active; ;定义四元式结构体链表 typedef struct fouritem char operators20; fourfactor factor3; struct fouritem *next; fouritem;/四元式结构体链表在中间代码生成过程中，考虑到四元式的数量不确定，我们通过结构体链表作为主要的数据结构来存储生成的四元式，同时套用结构体来对四元式的4个域进行分定义：token类型和bool类型。bool类型为了后期的目标代码生成做准备。定义的链式栈也是担心空间不够用。同时我们组对临时变量的处理也是恰到好处：token token1; token1.s0=t; tot+; int now=tot; int len; for(len=1;now;len+) token1.slen=now%10+0; now=now/10; for(int i=1;i=,=,= geq(=)出 口nnext(w)expression geq()=next(w)expression geq(=)next(w)expression geq(b) while(a+d=b+e&d/e=a)c=b%3;a=+c;c=-b;elsea=c/d;if(!a)b=a;while(a b) a=c/d-x;elsea=