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

《编译原理课程设计报告预测分析程序的设计.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计报告预测分析程序的设计.doc（26页珍藏版）》请在三一办公上搜索。

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

2、现它的预测分析程序，给出符号串i+i*i的分析过程。（参考教材P9396）3. 主要功能：对于这个给的LL（1）文法，假设所有非终结符号P的FIRST集合和FOLLOW集合都是已知的，构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对输入串进行分析，并给出了栈的变化过程。4. 进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。5. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容：课程设计的题目。 目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、

3、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。 参考文献。 附录：软件清单（或者附盘）。时间安排：消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名： 2010年 6月 11日系主任（或责任教师）签名： 2010年 6月 11日 目 录1引言42需求分析52.1问题的提出52.2问题的解决52.3解决步骤53总体设计63.1概要设计63.1.1设计原理63.1.2构造LL（1）分析表73.2详细设计103.2.1程序流程图103.2.2设计要求12

4、3.2.3设计原理123.2.3.1 FIRST(X)(XVNVT)的构造123.2.3.2 函数getFIRST() (=X1X2X3Xn)的构造123.2.3.3 FOLLOW(A) (AVN)的构造133.2.3.4 分析表M【A,a】的构造133.2.3.5 匹配过程的实现133.3程序设计143.3.1总体方案设计143.3.2各模块的实现144开发工具的选择235程序测试236有关技术的讨论257收获与体会268参考文献261 引言一个编译程序在对某个源程序完成了词法分析工作之后，就进入了语法分析阶段，分析检查源程序是否语法上正确的程序，并生成相应的内部中间表供下一阶段使用。程序设

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

6、产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。2.2 问题的解决其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。2.3 解决步骤在自上而下的分析法中，

7、主要是研究LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。当然本课设只是针对FIRST和FOLLOW集合都以知的任意输入的LL（1）文法。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。3 总体设计3.1 概要设计3.1.1 设计原理所谓LL（1）分析法

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

9、分析，也是采用了C+语言来编写。LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（）若X = a =#，则宣布分析成功，停止分析过程。（）若X = a #，则把X从STACK栈顶弹出，让a指向下一个输入符号。（）若X是一个非终结符，则查看预测分析表M。若MA，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。

10、事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。3.1.2 构造LL（1）分析表在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。FIRST集合的构造算法：（1）若XVT，则FIRST（X）=X。（2）若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。（3）若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若

11、XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有（即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)加至FO

12、LLOW(B)中。连续使用上面的规则，直至每个集合FOLLOW不再增大为止。 根据以上描述的算法，可以构造文法GA的FIRST和FOLLOW集合如下：非终结符AFIRST(A)FOLLOW(A)A (，i ), # B +, ), # C (，i +, ), # D * , +, ), # E (，i *, +, ), # 构造预测分析表，设计预测分析表的存储结构（构造算法）。 i+*()#AACBACBBB+CBBBCCEDCEDDDD*EDDDEEiE(A) 总体的框图： 句子分析过程的框图：3.2 详细设计3.2.1 程序流程图在对程序各个模块分析之前。先给出整个程序的流程图。以便于在分

13、析过程中更好的对各个模块之间的联系进行了解。程序的流程图如下：开始输入文法相关信息LL（1）文法构造FIRST集构造FOLLOW集构造预测分析表输入产生式判断句型Continue=“Y“构造句子的预测分析过程是Y结束3.2.2 设计要求1. 实现FIRST(X) (XVNVT)；2. 根据FIRST(X) (XVNVT)，实现getFIRST() (=X1X2X3Xn)；3. 实现FOLLOW(A) (AVN)；4. 根据getFIRST()以及FOLLOW(A)构造LL(1)分析表M【A,a】；5. 根据分析表M【A,a】，对任一输入字符串进行匹配，判断是否合法，并且显示其匹配过程。3.2.

14、3 设计原理3.2.3.1 FIRST(X)(XVNVT)的构造连续使用下面的规则，直至每个集合FIRST不再增大为止：(1). 若XVT，则FIRST(X)=X;(2). 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X$(表示空字符串)也是一条产生式，则把$也加到FIRST(X)中。(3)若XY是一个产生式且YVN，则把FIRST(Y)中的所有非$元素都加到FIRST(X)中；若XY1Y2Yk是一个产生式，Y1,Yi-1都是非终结符，而且，对于任何j,1=j$)，则把FIRST(Yj)中的所有非$元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有$,j=1

15、,2,k,则把$加到FIRST(X)中。如上可得到FIRST(X) (XVNVT)。3.2.3.2 函数getFIRST() (=X1X2X3Xn)的构造之前已经实现了FIRST(X) (XVNVT)，现在我们能够对文法G的任何符号串=X1X2Xn构造集合FIRST(a)。首先，置FIRST()=FIRST(X1)$;若对任1=j=i-1,$FIRST(Xj),则把FIRST(Xi)$加至FIRST()中；特别是，若所有FIRST(Xj)均含有$,1=jB是一个产生式，则把FIRST()$加至FOLLOW(B)中；(3). 若AB是一个产生式，或AB是一个产生式而=$(即$FIRST(),则把

16、FOLLOW(A)加至FOLLOW(B)。如上可得到FOLLOW(A) (AVN)的构造。3.2.3.4 分析表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】标上“出错标

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

18、put(),读入文法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()调用match (string)对任一输入的字符串进行匹配，判断其是否合法，并且显示匹配过程；3.3.2 各模块的实现(1). void input()VT

19、,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为VN标号)。每个Ti都是一个string的vector数组，存储Vi的所有产生式。input ( )函数代码如下：void input() /存储文法G的有关内容 /memset:作用是在一段内存块中填

20、充某个给定的值，它对较大的结构体或数组进行清零操作的一种最快方法 memset(FIRST,0,sizeof(FIRST); /把FIRST【】清零 memset(FOLLOW,0,sizeof(FOLLOW);/把FOLLOW【】清零 char cc; string ss; int top=0; coutplease input the 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; Vt

21、op=$; 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)来存储VTVN的开始终结字符信息。FIRSTij=1表示VjFIRSTVi,否则表示VjFIRSTVi。先初始化FIRSTij(0=i,j=numVT+numVN)为false，然后while循环按3.2.2 1的构造规则进行构造，用leni(0=inumVT+nu

22、mVN)来记录上一次循环处理后各个终结符与非终结符X的开始终结字符数目(即FIRST(X)。每次循环结束检测leni并更新。若检测到任一0=inumVT+numVN,都有leni=num(FIRST(i),则说明已构造完毕，跳出while循环，函数结束返回。createFIRST( )代码如下：void createFIRST() /存储VT VN的开始终结字符信息 int lenmaxV; memset(len,-1,sizeof(len); int i,j,t,no; for(i=0;inumVT;i+) FIRSTii=1; bool sign=1; while(sign) for(i=

23、numVT;inumVT+numVN;i+) for(j=0;jTTi.size();j+) int pp=findV(TTij0); if(ppnumVT|TTij0=$) FIRSTipp=1; continue; bool sign2; for(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) FIRSTin

24、umVT+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(FIRSTinumVT+numVN) plen+; if(leni!=plen) sign=1; leni=plen; (3). vector getFIRST(string str)对于字符串str，该函数返回str的开始终结符数组。可根据3.2.2 2的规则实现，对字符串的字符依次分析，将得到的开始终结字符存储到临时vector数组tmp中，函数结

25、束返回tmp数组。vector getFIRST(string str)代码如下：vector getFIRST(string str) /返回str的开始终结符数组 vector 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_b

26、ack(Viter); if(FIRSTnonumVT+numVN) sign=1; if(i=str.size()-1) tmp.push_back($); if(!sign) break; return tmp;(4). void createFOLLOW()用布尔数组FOLLOWij(numVT=inumVT+numVN,0=jnumVT)来存储VN的紧接终结字符信息。FOLLOWij=1表示VjFOLLOWVi,否则表示VjFOLLOWVi。先初始化FOLLOWij(0=i,jnumVT+numVN)为false,然后先根据3.2.2 3的规则进行构造。接着while循环(3)规则用l

27、eni(numVT=inumVT+numVN)来记录上一次循环处理后各个非终结符A的紧接终结字符数目(即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(#)

28、=1; for(i=numVT;inumVT+numVN;i+) for(j=0;jTTi.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;jTT

29、i.size();j+) for(t=0;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) FOLLO

30、Wnoiter=1; sign=0; for(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() 用字符串数组Mij来存储栈内符Vi与输入字符Vj的匹配产生式，若不匹配，则为空。 按照3.2.2 4的规则进行栈顶字符和字符串的字符的依次匹配，匹配处理结束后，函数结束返回。void createTABLE ( )代码如下：void createTABLE() /构建预测分析表 int

31、 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用来存放文法符号。分析开始时，栈底先存放一个#,然后放入文法开始符号。同时，假定输入串之后也总有一个#,标志输入串结束。预测分析程序的总控程序在任何时候都是按s

32、tack栈顶符号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; int 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)numVT) if(A=stri)