《预测分析表的构造毕业设计论文word格式》由会员分享，可在线阅读，更多相关《预测分析表的构造毕业设计论文word格式（36页珍藏版）》请在金锄头文库上搜索。
1、沈阳航空工业学院课 程 设 计 报 告课程设计名称：软件综合课程设计课程设计题目：预测分析表的构造院（系）：计算机学院专 业：计算机科学与技术班 级： 6401101学 号： 姓 名： 指导教师： 黄正文沈阳航空工业学院课程设计报告 目 录第一章 总体设计方案21.1 设计内容及要求21.2设计原理及思路21.2.1LL(1)文法的判定21.2.2 FIRST集和FOLLOW集的构造31.2.3 预测分析表的生成41.2.4 系统的模块结构51.3 实现工具与环境6第二章详细设计72.1 数据结构设计72.1.1全局变量72.1.2 预测分析表的设计82.2 函数的设计及说明92.3 关键算法
2、流程11第三章 调试分析153.1 系统调试中遇到的问题及解决方案153.2 系统运行结果16参考文献19附 录（关键部分程序清单）20 11 沈阳航空工业学院课程设计报告 第一章 总体设计方案1.1 设计内容及要求设计内容 为所输入的文法构造预测分析表。设计要求（1）设计功能性界面和数据性界面。为简单起见，文法符号暂用单字符表示。（2）本题目的功能包括文法输入、预测分析表生成、输出预测分析表。（3）以表格形式输出预测分析表。说明 本题目不进行文法的等价变换，在构造预测分析表的过程中应检查是否是LL（1）文法，若是则生成预测分析表（LL（1）分析表）。1.2 设计原理及思路 在自上而下的分析法
3、中，主要是研究LL(1)分析法。预测分析表是LL（1）语法分析程序的三个组成部分之一。它的解决步骤是，首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法的每个非终结符的FIRST集合和FOLLOW集合，然后根据FIRST集合和FOLLOW集合构造LL（1）分析表。1.2.1 LL(1)文法的判定文法不含左递归是LL(1)文法的前提条件。考查文法GE：EE+T | T TT*F | FF( E ) | i | x | y我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左
4、递归，这里我们通过引入新非终结符的方法来消除左递归，使它满足要求，即：对形如UUx|y的产生式（其中x,yV+ ，y不以U开头），引入一个新的非终结符U后，可以等价地改写成为：UyUUx U|显然改写后，U和U都不是含左递归的非终结符。因此文法GE按上述方法消去左递归后可等价地写成：ETP P+TP | TFQ Q*FQ | F( E ) | i | x | y当输入文法后，系统应该自动判定文法是否含有左递归，一个完善的系统还应能够将含有左递归的文法分解为不含左递归的文法。为简单起见，本系统只对检测到的含有左递归的文法给出不是LL(1)文法的提示。判定LL(1)文法的另外两个条件将在后续求FI
5、RST集和FOLLOW集的过程中进行检测。对不符合条件的文法同样给出提示信息。1.2.2 FIRST集和FOLLOW集的构造 在构造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)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，
6、对于任何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)加至FOLLOW(B)中。连续使用上面的规则，直至每个FOLLOW集合不再
7、增大为止。 根据以上描述的算法，可以构造文法GE的FIRST和FOLLOW集合如下： FIRST(E) = ( , i，x，y FOLLOW(E) = ) , # FIRST(P) = + , FOLLOW(P) = ) , # FIRST(T) = ( , i，x，y FOLLOW(T) = + , ) , # FIRST(Q) = * , FOLLOW(Q) = + , ) , # FIRST(F) = ( , i，x，y FOLLOW(F) = * , + , ) , # 在构造完每个非终结符的FIRST和FOLLOW集合后，系统检测输入的文法是否满足LL(1)文法的后两个条件。对不符合
8、条件的文法，则直接给出提示信息，不予以构造预测分析表。1.2.3 预测分析表的生成现在来构造GE的LL（1）预测分析表。预测分析表MA, a是如下形式的一个矩阵。A为非终结符，a是终结符或#。矩阵元素 MA, a中存放着一条关于A的产生式，指出当A面临输入符号a时所应采用的规则。MA, a也可能存放一条“出错标志”，指出当A根本不该面临输入符号a。文法GE的LL(1) 预测分析表如表1.1所示：表1.1 文法GE的LL(1)预测分析表i +x y * ( ) # EETPERRORETPETPERRORETPERRORERROR PERRORE+TPERRORERRORERRORERRORPP
9、 TTFQERRORTFQTFQERRORTFQERRORERROR QERRORQERRORERRORQ*FQERRORQQ FFiERRORFxFyERRORF（E）ERRORERROR其中，E、P 、T、Q、F为文法GE的非终结符，i、+、x、y、*、(、)，为方法GE的终结符。值得注意的是，“”不管有没有产生式，我们在构造分析表时都不能省去。1.2.4 系统的模块结构系统的主要功能分为文法输入、预测分析表的生成和预测分析表的输出三个部分。文法输入时，包括输入文法的终结符号、非终结符号、开始符号、文法的条数以及各条文法，文法可以以缩略形式（形如UUx|y）输入；预测分析表的生成包括检查文
10、法是否是LL（1）文法、对以缩略形式输入的文法进行分解、构造文法每个非终结符的FIRST和FOLLOW集合以及预测分析表数据结构的建立；预测分析表的输出主要包括设计美观的界面将预测分析表以表格的形式输出。系统模块结构示意图如图1.1所示。文法 文法输入文法 预测分析表生成文法 预测分析表生成系统构造非终结符的first集构造终结符的follow集文法 预测分析表输出图1.1 系统模块结构示意图构造预测分析表1.3 实现工具与环境 （1）编程工具： Microsoft Visual C+ 6.0中文版；（2）操作系统： Microsoft Windows XP Professional Serv
11、ice Pack 2 （3）机器 Personal computer 第二章 详细设计2.1 数据结构设计数据结构设计的合理性直接关系着系统功能的实现方便与否。本系统的数据结构包含两部分，第一部分是全局变量，第二部分是预测分表。2.1.1全局变量int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin50; /*终结符号*/char non_ter50; /*非终结符号*/char v50; /*所有符号*/char left50; /*文法左部*/char right5050;
12、 /*文法右部*/char first5050,follow5050; /*各产生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有单个符号的FIRST集合*/char select5050; /*各单个产生式的SELECT集合*/char f50,F50; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty20; /*记录可直接推出的符号*/char TEMP50; /*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M2020; /*分析表*/int choose1; /*用户输入时使用*/char empt20; /*求_emp()时使用*/char fo20; /*求FOLLOW集合时使用*/2.1.2 预测分析表的设计 预测分析表的机内表示可采用二维数组数据结构。鉴于规则长短不一，一种简便的方法是分析表元素（即规则）用规则序号来代替。分析表的两维分别为非终结符号与终结符号，同样宜于用序号来代替符号，也即，用整数值作为分析表的下标值。概括之，分析表元素MUT将对应于：MU的序号T的序号=规则序号当规则序号为0
