编译原理课程设计报告-预测分析程序的设计.

1、课程设计任务书课程设计任务书学生姓名：学生姓名： 专业班级：专业班级： 指导教师：指导教师： 工作单位：工作单位： 题题 目目: : 预测分析程序的设计预测分析程序的设计初始条件：初始条件：程序设计语言:主要使用 C 语言的开发工具，或者采用 LEX、YACC 等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务要求完成的主要任务: : （包括课程设计工作量及其技术要求，说明书撰写等具体要求）1. 明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决

2、具体问题的方法。严格要求自己，要独立思考，按时、独立按时、独立完成课程设计任务。2. 课设任务：对教材 P94 中的上下文无关文法，实现它的预测分析程序，给出符号串 i+i*i 的分析过程。 （参考教材 P9396）3. 主要功能：对于这个给的 LL（1）文法，假设所有非终结符号 P 的 FIRST 集合和FOLLOW 集合都是已知的，构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对输入串进行分析，并给出了栈的变化过程。4. 进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。5. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字

3、数不少于 0.3 万字。包含内容：课程设计的题目。 目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计） ，数据结构与模块说明（功能与流程图） 、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。 参考文献。 附录：软件清单（或者附盘） 。时间安排：时间安排：消化资料、系统调查、形式描述1 天系统分析、总体设计、实施计划3 天撰写课程设计报告书1 天指导教师签名：指导教师签名： 20102010 年年 6 6 月月 1111 日日编译原理编译原理课程设计说明书课程设计说明书3系主任（

4、或责任教师）签名：系主任（或责任教师）签名： 20102010 年年 6 6 月月 1111 日日 目目 录录1 1引言引言 .4 42 2需求分析需求分析 .5 52.1 问题的提出 .52.2 问题的解决 .52.3 解决步骤 .53 3总体设计总体设计 .6 63.1 概要设计 .63.1.1 设计原理 .63.1.2 构造 LL（1）分析表 .73.2 详细设计 .103.2.1 程序流程图 .103.2.2 设计要求 .123.2.3 设计原理 .123.2.3.1 FIRST(X)(XVNVT)的构造.123.2.3.2 函数 getFIRST() (=X1X2X3Xn)的构造 .

5、123.2.3.3 FOLLOW(A) (AVN)的构造 .133.2.3.4 分析表 M【A,a】的构造 .133.2.3.5 匹配过程的实现.13编译原理编译原理课程设计说明书课程设计说明书43.3 程序设计 .143.3.1 总体方案设计 .143.3.2 各模块的实现 .144 4开发工具的选择开发工具的选择 .23235 5程序测试程序测试 .23236 6有关技术的讨论有关技术的讨论 .25257 7收获与体会收获与体会 .26268 8参考文献参考文献 .2626编译原理编译原理课程设计说明书课程设计说明书51 1 引言引言一个编译程序在对某个源程序完成了词法分析工作之后，就进入

6、了语法分析阶段，分析检查源程序是否语法上正确的程序，并生成相应的内部中间表供下一阶段使用。程序设计语言是一般形式语言的特例，程序语法正确性的检查时语法句子的识别，语法分析问题也就是句型识别问题。按照识别句子语法树建立的方式，有自顶向下与自底向上两大类分析技术。本课程讨论自顶向下的情况。本次课程设计所做的工作是对已知 FIRST 集合和 FOLLOW 集合的 LL(1)文法构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对输入串进行分析，并给出了栈的变化过程。2 2 需求分析需求分析2.1 问题的提出问题的提出语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础

7、上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。2.2 问题的解决问题的解决其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的编译原理编译原理课程设计说明书课程设计说明书6分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建

8、立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。2.3 解决步骤解决步骤在自上而下的分析法中，主要是研究 LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到 LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的 FIRST 和 FOLLOW 集合，然后根据FIRST 和 FOLLOW 集合构造 LL（1）分析表，最后利用分析表，根据 LL(1)语法分析构造一个分析器。当然本课设只是针对 F

9、IRST 和 FOLLOW 集合都以知的任意输入的 LL（1）文法。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。3 3 总体设计总体设计3.1 概要设计概要设计3.1.1 设计原理设计原理所谓 LL（1）分析法，就是指从左到右扫描输入串（源程序） ，同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现 LL（1）分析的程序又称为 LL（1）分析程序或 LL1（1）分析器。我们知道一个文法要能进行 LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的

10、 FIRST 和 FOLLOW 集合，然后根据 FIRST 和 FOLLOW 集合构造编译原理编译原理课程设计说明书课程设计说明书7LL（1）分析表，最后利用分析表，根据 LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，也是采用了C+语言来编写。 LL（1）预测分析程序的总控程序在任何时候都是按 STACK 栈顶符号 X和当前的输入符号 a 做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（）若 X = a =#，则宣布分析成功，停止分析过程。（）若 X

11、 = a #，则把 X 从 STACK 栈顶弹出，让 a 指向下一个输入符号。（）若 X 是一个非终结符，则查看预测分析表 M。若 MA，a中存放着关于 X 的一个产生式，那么，首先把 X 弹出 STACK 栈顶，然后，把产生式的右部符号串按反序一一弹出 STACK 栈（若右部符号为 ，则不推什么东西进STACK 栈）。若 MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在 LL（1）分析器中，实际上是以 LL（1）分析表代替相应方法来进行分析的。3.1.2 构造构造 LL（1）分析表分析表在构造

12、 LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST 和 FOLLOW 集合，按照下面描述的算法来构造这两个集合。FIRST 集合的构造算法：（1）若 XVT，则 FIRST（X）=X。编译原理编译原理课程设计说明书课程设计说明书8（2）若 XVN，且有产生式 Xa，则把 a 加入到 FIRST(X)中；若X 也是一条产生式，则把 也加到 FIRST(X)中。（3）若 XY是一个产生式且 YVN，则把 FIRST(Y)中的所有非 -元素都加到 FIRST(X)中；若 XY1Y2Yk 是一个产生式，Y1，Yi-1 都是非终结符，而且，对于任何 j，1ji-1，FIRST(Yj)

13、都含有 （即 Y1Yi-1* ），则把 FIRST(Yj)中的所有非 -元素都加到 FIRST(X)中；特别是，若所有的 FIRST(Yj)均含有 ，j=1,2,，k，则把 加到 FIRST(X)中。连续使用上面的规则，直至每个集合 FIRST 不再增大为止。FOLLOW 集合的构造算法：（1）对于文法的开始符号 S，置#于 FOLLOW(S)中；（2）若 AB 是一个产生式，则把 FIRST()| 加至 FOLLOW(B)中；（3）若 AB 是一个产生式，或 AB 是一个产生式而 （即FIRST()），则把 FOLLOW(A)加至 FOLLOW(B)中。连续使用上面的规则，直至每个集合 FO

14、LLOW 不再增大为止。 根据以上描述的算法，可以构造文法 GA的 FIRST 和 FOLLOW 集合如下：非终结符 AFIRST(A)FOLLOW(A)A (，i ), # B +, ), # C (，i +, ), # D * , +, ), # 编译原理编译原理课程设计说明书课程设计说明书9E (，i *, +, ), # 构造预测分析表，设计预测分析表的存储结构（构造算法） 。 i+*()#AACBACBBB+CBBBCCEDCEDDDD*EDDDEEiE(A) 总体的框图：编译原理编译原理课程设计说明书课程设计说明书10 句子分析过程的框图：编译原理编译原理课程设计说明书课程设计说明

15、书113.2 详细设计详细设计3.2.1 程序流程图程序流程图在对程序各个模块分析之前。先给出整个程序的流程图。以便于在分析过程中更好的对各个模块之间的联系进行了解。程序的流程图如下：编译原理编译原理课程设计说明书课程设计说明书12开始输入文法相关信息LL（1）文法构造 FIRST 集构造 FOLLOW 集构造预测分析表输入产生式判断句型Continue=“Y“构造句子的预测分析过程是Y结束编译原理编译原理课程设计说明书课程设计说明书133.2.2 设计要求设计要求1. 实现 FIRST(X) (XVNVT)；2. 根据 FIRST(X) (XVNVT)，实现 getFIRST() (=X1X

16、2X3Xn)；3. 实现 FOLLOW(A) (AVN)；4. 根据 getFIRST()以及 FOLLOW(A)构造 LL(1)分析表 M【A,a】 ；5. 根据分析表 M【A,a】 ，对任一输入字符串进行匹配，判断是否合法，并且显示其匹配过程。3.2.3 设计原理设计原理3.2.3.13.2.3.1FIRST(X)(XFIRST(X)(XVNVNVT)VT)的构造的构造连续使用下面的规则，直至每个集合 FIRST 不再增大为止：(1). 若 XVT，则 FIRST(X)=X;(2). 若 XVN，且有产生式 Xa，则把 a 加入到 FIRST(X)中；若 X$(表示空字符串)也是一条产生式

17、，则把$也加到 FIRST(X)中。(3)若 XY是一个产生式且 YVN，则把 FIRST(Y)中的所有非$元素都加到 FIRST(X)中；若 XY1Y2Yk 是一个产生式，Y1,Yi-1 都是非终结符，而且，对于任何 j,1=j$)，则把FIRST(Yj)中的所有非$元素都加到 FIRST(X)中；特别是，若所有的 FIRST(Yj)均含有$,j=1,2,k,则把$加到 FIRST(X)中。如上可得到 FIRST(X) (XVNVT)。3.2.3.23.2.3.2函数函数 getFIRST(getFIRST() ) ( (=X1X2X3Xn)=X1X2X3Xn)的构造的构造之前已经实现了 F

18、IRST(X) (XVNVT)，现在我们能够对文法 G 的任何符号串=X1X2Xn 构造集合 FIRST(a)。首先，置 FIRST()=FIRST(X1)$;若对任 1=j=i-1,$FIRST(Xj),则把 FIRST(Xi)$加至 FIRST()中；特别是，若所有 FIRST(Xj)均含有编译原理编译原理课程设计说明书课程设计说明书14$,1=jB是一个产生式，则把 FIRST()$加至 FOLLOW(B)中；(3). 若 AB 是一个产生式，或 AB是一个产生式而=$(即$FIRST(),则把 FOLLOW(A)加至 FOLLOW(B)。如上可得到 FOLLOW(A) (AVN)的构造

19、。3.2.3.4 分析表分析表 M【A,a】M【A,a】的构造的构造在对文法 G 的每个终结符 A 及其任意候选 a 都构造出 FIRST(a)(2.2 节的getFIRST(a),和 FOLLOW(A)(2.3 节的 FOLLOW(A)之后,我们现在可以用它们来构造 G 的分析表 M【A,a】 。构造分析表 M 的算法是：(1). 对文法 G 的每个产生式 A执行第 2 步和第 3 步；(2). 对每个终结符 aFIRST(),把 A加至 M【A,a】中；(3). 若$FIRST(),则对任何 aFOLLOW(A)把 A加至 M【A,a】中；(4). 把所有无定义的 M【A,a】标上“出错标

20、志“。如上可得到 M【A,a】 。 3.2.3.5 匹配过程的实现匹配过程的实现对于任何(A,a),总控程序每次都执行下述三种可能的动作之一：(1). 若 X=a=#,则宣布分析成功，停止分析过程。编译原理编译原理课程设计说明书课程设计说明书15(2). 若 X=a!=#,则把 X 从 stack 栈顶逐出，让 a 指向下一个输入符号。(3). 若 X 是一个非终结符，则查看分析表 M。若 M【A,a】中存放着关于 X的一个产生式，那么把 X 逐出 stack 栈顶，然后，把产生式的右部符号串按反序一一推进 stack 栈(若右部符号为$,则意味不推什么东西进栈)。若 M【A,a】中存放着“出

21、错标志“，则中断匹配，显示出错信息。3.3程序设计程序设计3.3.1 总体方案设计总体方案设计(1). Main()调用 input(),读入文法 G 的有关内容：G(VT,VN,S,&);(2). Main()调用 createFIRST(),实现 FIRST(X),(XVTVN);(3). 内部程序中通过调用 getFIRST(string)得到字符串的 FIRST 终结符；(4). Main()调用 createFOLLOW(),实现 FOLLOW(A),(AVN);(5). Main()调用 createTABLE(),创建 LL(1)分析表 M【A,a】 ；(6). Main()调用

22、 match (string)对任一输入的字符串进行匹配，判断其是否合法，并且显示匹配过程；3.3.2 各模块的实现各模块的实现(1). void input()VT,VN 都是以字符存储的，numVT 表示 VT 的数目，numVN 表示 VN 的数目。VT 标号 0numVT-1，VN 标号 numVTnumVT+numVN-1。函数findV(char)和 V(int)分别实现字符索引和索引字符间的转换($用 nunVT+numVN索引)。产生式&以字符串的方式读入，经过 comsume()函数处理。产生式存在TTi的 vector 数组中(numVT=inumVT+numVN，i 为

23、VN 标号)。每个 Ti都是一个 string 的 vector 数组，存储 Vi的所有产生式。input ( )函数代码如下：编译原理编译原理课程设计说明书课程设计说明书16void input() /存储文法G的有关内容 /memset:作用是在一段内存块中填充某个给定的值，它对较大的结构体或数组进行清零操作的一种最快方法 memset(FIRST,0,sizeof(FIRST); /把FIRST【】清零 memset(FOLLOW,0,sizeof(FOLLOW);/把FOLLOW【】清零 char cc; string ss; int top=0; coutplease input t

24、he set of VT(end by 0)cc&cc!=0) Vtop+=cc; numVT=top; coutplease input the set of VN(end by 0)cc&cc!=0) Vtop+=cc; numVN=top-numVT; Vtop=$; coutplease input the start VNStart; coutplease input the chanshengshi(end line by 0)ss&ss0!=0) consume(ss);(2). void createFIRST()用布尔数组 FIRSTij(0=i,j=numVT+numVN)

25、来存储 VTVN 的开始终结字符信息。FIRSTij=1 表示 VjFIRSTVi,否则表示 VjFIRSTVi。先初始化 FIRSTij(0=i,j=numVT+numVN)为 false，然后 while 循环按3.2.2 1 的构造规则进行构造，用 leni(0=inumVT+numVN)来记录上一次循环处理后各个终结符与非终结符 X 的开始终结字符数目(即 FIRST(X)。每次循环结束检测 leni并更新。若检测到任一 0=inumVT+numVN,都有 leni=num(FIRST(i),则说明已构造完毕，跳出 while 循环，函数结束返回。createFIRST( )代码如下：

26、void createFIRST() /存储VT VN的开始终结字符信息 int lenmaxV;编译原理编译原理课程设计说明书课程设计说明书17 memset(len,-1,sizeof(len); int i,j,t,no; for(i=0;inumVT;i+) FIRSTii=1; bool sign=1; while(sign) for(i=numVT;inumVT+numVN;i+) for(j=0;jTTi.size();j+) int pp=findV(TTij0); if(ppnumVT|TTij0=$) FIRSTipp=1; continue; bool sign2; fo

27、r(t=0;tTTij.size();t+) sign2=0; no=findV(TTijt); int iter; for(iter=0;iternumVT;iter+) if(FIRSTnoiter) FIRSTiiter=1; if(FIRSTnonumVT+numVN) sign2=1; if(t=TTij.size()-1) FIRSTinumVT+numVN=1; if(sign2=0) break; sign=0; for(i=numVT;inumVT+numVN;i+) int plen=0; for(j=0;jnumVT;j+) if(FIRSTij) plen+; if(F

28、IRSTinumVT+numVN) plen+; if(leni!=plen) sign=1; leni=plen; 编译原理编译原理课程设计说明书课程设计说明书18 (3). vector getFIRST(string str)对于字符串 str，该函数返回 str 的开始终结符数组。可根据 3.2.2 2 的规则实现，对字符串的字符依次分析，将得到的开始终结字符存储到临时 vector数组 tmp 中，函数结束返回 tmp 数组。vector getFIRST(string str)代码如下：vector getFIRST(string str) /返回str的开始终结符数组 vecto

29、r tmp; if(str.size()=0) return tmp; if(str=$) tmp.push_back($); return tmp; int i,j,no; bool sign; for(i=0;istr.size();i+) sign=0; no=findV(stri); int iter; for(iter=0;iternumVT;iter+) if(FIRSTnoiter) tmp.push_back(Viter); if(FIRSTnonumVT+numVN) sign=1; if(i=str.size()-1) tmp.push_back($); if(!sign)

30、 break; return tmp;(4). void createFOLLOW()用布尔数组 FOLLOWij(numVT=inumVT+numVN,0=jnumVT)来存储 VN 的紧接终结字符信息。FOLLOWij=1 表示 VjFOLLOWVi,否则表示 VjFOLLOWVi。编译原理编译原理课程设计说明书课程设计说明书19先初始化 FOLLOWij(0=i,jnumVT+numVN)为 false,然后先根据 3.2.2 3 的规则进行构造。接着 while 循环(3)规则用 leni(numVT=inumVT+numVN)来记录上一次循环处理后各个非终结符 A 的紧接终结字符数目

31、(即 FOLLOW(X)。每次循环结束检测 leni并更新。若检测到任一 numVT=inumVT+numVN,都有 leni=num(FIRST(i),则说明已构造完毕，跳出 while 循环，函数结束返回。void createFOLLOW()代码如下：void createFOLLOW() /求得文法G中每个终结符的FOLLOW集 int lenmaxV; memset(len,0,sizeof(len); int i,j,t,no; no=findV(Start); FOLLOWnofindV(#)=1; for(i=numVT;inumVT+numVN;i+) for(j=0;jTT

32、i.size();j+) for(t=0;t=numVT&no!=numVT+numVN) int tt; if(tTTij.size()-1) vector tmp=getFIRST(TTij.substr(t+1,TTij.size()-t-1); for(tt=0;tttmp.size();tt+) if(tmptt!=$) FOLLOWnofindV(tmptt)=1; bool sign=1; while(sign) for(i=numVT;inumVT+numVN;i+) for(j=0;jTTi.size();j+)编译原理编译原理课程设计说明书课程设计说明书20 for(t=0

33、;t=numVT&TTijt!=$) int tt; if(tTTij.size()-1) vector tmp=getFIRST(TTij.substr(t+1,TTij.size()-t-1); for(tt=0;tttmp.size();tt+) if(tmptt=$) int iter; for(iter=0;iternumVT;iter+) if(FOLLOWiiter) FOLLOWnoiter=1; break; else int iter; for(iter=0;iternumVT;iter+) if(FOLLOWiiter) FOLLOWnoiter=1; sign=0; f

34、or(i=numVT;inumVT+numVN;i+) int plen=0; for(j=0;jnumVT;j+) if(FOLLOWij) plen+; if(leni!=plen) sign=1; leni=plen; (5). void createTABLE()编译原理编译原理课程设计说明书课程设计说明书21 用字符串数组 Mij来存储栈内符 Vi与输入字符 Vj的匹配产生式，若不匹配，则为空。 按照 3.2.2 4 的规则进行栈顶字符和字符串的字符的依次匹配，匹配处理结束后，函数结束返回。void createTABLE ( )代码如下：void createTABLE() /构建

35、预测分析表 int i,j,t; for(i=numVT;inumVT+numVN;i+) for(j=0;jTTi.size();j+) string tmp=TTij; vector first=getFIRST(tmp); bool sign=0; for(t=0;t+TTij; if(sign) int iter; for(iter=0;iter+TTij; (6). bool match (string str)用栈来实现匹配算法：栈 stack 用来存放文法符号。分析开始时，栈底先存放一个#,然后放入文法编译原理编译原理课程设计说明书课程设计说明书22开始符号。同时，假定输入串之后

36、也总有一个#,标志输入串结束。预测分析程序的总控程序在任何时候都是按 stack 栈顶符号 X 和当前的输入符号 a 行事的。对具体情况根据规则 3.2.2 5 的 3 种处理方式之一进行处理。处理完后，函数结束返回。bool match (string str)代码如下：bool match(string str) /用栈来实现匹配算法 str=str+#; cout步骤t符号栈t输入串t产生式endl; int num=0; char stackmaxV; int top=0; stacktop+=#; stacktop+=Start; coutnumt#Starttstrendl; in

37、t i=0,j; while(istr.size() char A=stacktop-1; if(A!=#&findV(A)=-1) return false; if(stri!=#&findV(stri)=-1) return false; string tmp; if(A=#) if(A=stri) return true; else return false; else if(findV(A)=3;j-) stacktop+=tmpj; else return false; stacktop=0; cout+numtstacktstr.substr(i,str.size()-i)ttmp

38、endl; (7)int main()函数 程序的主要功能均在main（）函数里面实现，首先是输入文法的相关信息，然后是创建FIRST表和FOLLOW表（不输出），再输出预测分析表，最后提示输入句子，判断是否是该文法的句型，程序实现了多次输入：int main() 函数代码如下：int main() /主函数 cout*预测分析程序*endl;input(); createFIRST(); createFOLLOW(); createTABLE(); int i,j;cout*预测分析表*endl;couttit+t*t(t)t#tendl; for(i=numVT;inumVT+numVN;i+) coutVit; for(j=0;j0) coutMijt; else coutERRORt; coutendl; string str;char s;bool bl; do编译原理编译原理课程设计说明书课程设计说明书24 cout*分析输入串*endl; coutplease input the str