预测分析表的构造毕业设计（论文）word格式.doc

沈阳航空工业学院 课课 程程 设设 计计 报报 告告 课程设计名称：软件综合课程设计软件综合课程设计 课程设计题目：预测分析表的构造预测分析表的构造 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 6401101 学 号： 姓 名： 指导教师： 黄正文 沈阳航空工业学院课程设计报告 i 目目 录录 第一章第一章 总体设计方案总体设计方案.2 1.1 设计内容及要求 2 1.2设计原理及思路2 1.2.1ll(1)文法的判定.2 1.2.2 first 集和 follow 集的构造3 1.2.3 预测分析表的生成4 1.2.4 系统的模块结构5 1.3 实现工具与环境 6 第二章第二章详细设计详细设计7 2.1 数据结构设计 .7 2.1.1 全局变量.7 2.1.2 预测分析表的设计8 2.2 函数的设计及说明 .9 2.3 关键算法流程 .11 第三章第三章 调试分析调试分析.15 3.1 系统调试中遇到的问题及解决方案 .15 3.2 系统运行结果 .16 参考文献参考文献.19 附附 录（关键部分程序清单）录（关键部分程序清单）.20 沈阳航空工业学院课程设计报告 2 第一章第一章 总体设计方案总体设计方案 1.11.1 设计内容及要求设计内容及要求 设计内容设计内容 为所输入的文法构造预测分析表。 设计要求设计要求 （1）设计功能性界面和数据性界面。为简单起见，文法符号暂用单字符表 示。 （2）本题目的功能包括文法输入、预测分析表生成、输出预测分析表。 （3）以表格形式输出预测分析表。 说明说明 本题目不进行文法的等价变换，在构造预测分析表的过程中应检查是否是 ll（1）文法，若是则生成预测分析表（ll（1）分析表） 。 1.21.2设计原理及思路设计原理及思路 在自上而下的分析法中，主要是研究 ll(1)分析法。预测分析表是 ll（1） 语法分析程序的三个组成部分之一。它的解决步骤是，首先接收到用户输入的一 个文法，对文法进行检测和处理，消除左递归，得到 ll(1)文法，这个文法应该 满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法 的每个非终结符的 first 集合和 follow 集合，然后根据 first 集合和 follow 集合构造 ll（1）分析表。 1.2.11.2.1 ll(1)文法的判定文法的判定 文法不含左递归是 ll(1)文法的前提条件。 考查文法 ge： ee+t | t tt*f | f 沈阳航空工业学院课程设计报告 3 f( e ) | i | x | y 我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左递归， 这里我们通过引入新非终结符的方法来消除左递归，使它满足要求，即：对形如 uux|y 的产生式（其中 x,yv+ ，y 不以 u 开头） ，引入一个新的非终结符 u 后，可以等价地改写成为： uyu ux u| 显然改写后，u 和 u都不是含左递归的非终结符。因此文法 ge按上述 方法消去左递归后可等价地写成： etp p+tp | tfq q*fq | f( e ) | i | x | y 当输入文法后，系统应该自动判定文法是否含有左递归，一个完善的系统还 应能够将含有左递归的文法分解为不含左递归的文法。为简单起见，本系统只对 检测到的含有左递归的文法给出不是 ll(1)文法的提示。 判定 ll(1)文法的另外两个条件将在后续求 first 集和 follow 集的过程 中进行检测。对不符合条件的文法同样给出提示信息。 1.2.21.2.2 first 集和集和 follow 集的构造集的构造 在构造 ll(1)预测分析表之前，首先要构造该文法的每个非终结符的 first 集合和 follow 集合，按照下面描述的算法来构造这两个集合。 first 集合的构造算法： （1）若 xvt，则 first（x）=x。 （2）若 xvn，且有产生式 xa，则把 a 加入到 first(x)中；若 沈阳航空工业学院课程设计报告 4 x 也是一条产生式，则把 也加到 first(x)中。 （3）若 xy是一个产生式且 yvn，则把 first(y)中的所有非 -元 素都加到 first(x)中；若 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)加至 follow(b)中。 连续使用上面的规则，直至每个 follow 集合不再增大为止。 根据以上描述的算法，可以构造文法 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)文法的后两个条件。对不符合条件的文法，则直接给出提示信息，不 予以构造预测分析表。 1.2.31.2.3 预测分析表的生成预测分析表的生成 现在来构造 ge的 ll（1）预测分析表。预测分析表 ma, a是如下形式 的一个矩阵。a 为非终结符，a 是终结符或# 。矩阵元素 ma, a中存放着一 沈阳航空工业学院课程设计报告 5 条关于 a 的产生式，指出当 a 面临输入符号 a 时所应采用的规则。ma, a也可 能存放一条“出错标志” ，指出当 a 根本不该面临输入符号 a。文法 ge的 ll(1) 预测分析表如表 1.1 所示： 表表 1.11.1 文法文法 gege的的 ll(1)ll(1)预测分析表预测分析表 i +x y * ( ) # eetperroretpetperroretperrorerror perrore+tperrorerrorerrorerrorpp ttfqerrortfqtfqerrortfqerrorerror qerrorqerrorerrorq*fqerrorqq ffierrorfxfyerror f（e ） errorerror 其中，e、p 、t、q、f 为文法 ge的非终结符，i、+、x、y、*、(、)， 为方法 ge的终结符。值得注意的是， “”不管有没有 产生式，我们在构 造分析表时都不能省去。 1.2.41.2.4 系统的模块结构系统的模块结构 系统的主要功能分为文法输入、预测分析表的生成和预测分析表的输出三个 部分。文法输入时，包括输入文法的终结符号、非终结符号、开始符号、文法的 条数以及各条文法，文法可以以缩略形式（形如 uux|y）输入；预测分析表的 生成包括检查文法是否是 ll（1）文法、对以缩略形式输入的文法进行分解、构 造文法每个非终结符的 first 和 follow 集合以及预测分析表数据结构的建立； 预测分析表的输出主要包括设计美观的界面将预测分析表以表格的形式输出。系 统模块结构示意图如图 1.1 所示。 沈阳航空工业学院课程设计报告 6 文法 文法输入文法 预测分析表生成 文法 预测分析表生成系统 构造非终结符的 first 集 构造终结符的 follow 集 文法 预测分析表输出 图图 1.11.1 系统模块结构示意图系统模块结构示意图 构造预测分析表 1.31.3 实现工具与环境实现工具与环境 （1）编程工具： microsoft visual c+ 6.0 中文版； （2）操作系统： microsoft windows xp professional service pack 2 （3）机器 personal computer 沈阳航空工业学院课程设计报告 7 第二章详细设计 2.1 数据结构设计数据结构设计 数据结构设计的合理性直接关系着系统功能的实现方便与否。本系统的数据 结构包含两部分，第一部分是全局变量，第二部分是预测分表。 2.1.1 全局变量全局变量 int count=0; /*分解的产生式的个数*/ int number; /*所有终结符和非终结符的总数*/ char start; /*开始符号*/ char termin50; /*终结符号*/ char non_ter50; /*非终结符号*/ char v50; /*所有符号*/ char left50; /*文法左部*/ char right5050; /*文法右部*/ char first5050,follow5050; /*各产生式右部的 first 和左部的 follow 集合*/ char first15050; /*所有单个符号的 first 集合*/ char select5050; 沈阳航空工业学院课程设计报告 8 /*各单个产生式的 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 时，表示不存在规则。 为区分文法规则右部的终结符号和非终结符号，可做如下处理： 终结符号用它们在终结符号集中的序号代表，因此，将分别对应于整数值 沈阳航空工业学院课程设计报告 9 1、2、|vt|，而非终结符号则用它们在非终结符号集中的序号加上 100 代表， 即，它们将分别对应于 101、102、100+|vn|。这里假定终结符号个数少于 100，这一般不成问题。不然可让 ui 对应于 200+i，甚至 1000+ i。如果不这样处 理，不论是终结符号还是非终结符号都用一个从 1 开始的自然数代表，即分别对 应与 1、2、n，这时便必须给出符号种类以说明是终结符号还是非终结符号。 2.2 函数的设计及说明函数的设计及说明 （1）int in(char c，char*p)函数： 功能：判断一个字符是否在指定字符串中。 说明：若 char c 在 char*p 指向的字符串中，返回 1；否则，返回 0。 （2）void non_re(char *point)函数： 功能：分解不含有左递归的产生式，即，将形如 p*qa|f 的产生式分 解为 p*qa 和 pf。 说明：完整的产生式在 point 中。 （3）char grammer(char *t,char *n,char *left,char right5050)函数： 功能：读入一个文法。 说明：char *t 指向终结符号的集合； char *n 指向非终结符号的集合； char *left 指向文法产生式的左部； char right5050传递的参数是文法产生式的右部。 （4）void merge(char *d,char *s,int type)函数： 功能：将单个符号或符号串并入另一符号串 说明：d 指向目标符号串，s 指向源串，type1，源串中的 一 并并入目串；type2，源串中的 不并入目串。 （5）void emp(char c)函数： 功能：求所有能直接推出的符号。 说明：char c 为需要判断的符号。 （6）int _emp(char c)函数： 沈阳航空工业学院课程设计报告 10 功能：求某一符号能否推出 。 说明：char c 为需要判断的符号，若能推出 ，返回 1；否则，返 回 0。 （7）int judge( )函数： 功能：判断读入的文法是否正确。 说明：正确，返回 1；否则，报错，返回 0。 （8）void first2(int i)函数： 功能：求单个符号的 first 集。 说明：i 为符号在所有输入符号中的序号。 （9）void first(int i,char *p)函数： 功能：求各产生式右部的 first 集。 说明：i 为分解后的产生式的序号；char *p 指向产生式的右部。 （10）void follow(int i)函数： 功能：求各产生式左部的 follow 集。 说明：i 为分解后的产生式的序号。 （11）int ll1()函数： 功能：判断读入文法是否为一个 ll(1)文法。 说明：是 ll(1)文法，返回 1；否则，报错，返回 0。 （12）void mm()函数： 功能：构造预测分析表 m。 说明：在该函数中，把预测分析表设计成二维数组，构造预测分析表 时，文法用其序号代替。 （13）void menu() 功能：设置用户界面。 说明：该函数将设计一个人机交互界面，从而选择实现各种功能。 （14）void func() 功能：调用各种功能函数。 说明：该函数可以将系统的运行结果显示出来。 沈阳航空工业学院课程设计报告 11 2.3 关键算法流程关键算法流程 （1）总控流程：构造预测分析表主要包括以下几个步骤，首先输入文法， 然后计算各个终结符号和非终结符号的 first 和 follow 集合，然后填分析表， 若填入表中的元素均唯一，则输出预测分析表。流程图如图 2.1 所示。 开始 输入文法 计算 first 集合 计算 follow 集合 填分析表 元素均唯一 不能构造 ll（1） 预测分析表 输出 ll（1） 分析表 结束 y n （2）first 集合计算流程：根据第一章中计算 first 集合的算法，从第一条文法 开始，依次构造各条文法左部非终结符号的 first 集合，该流程的核心是判断各符 号的 first 集合是否包含 。流程图如图 2.2 所示。 图图 2.1 总程序控制流程图总程序控制流程图 沈阳航空工业学院课程设计报告 12 置初值 未加入新元素 i=1 左部=文法i-左部符号序号 右部 p=文法i-定义结点指针 右部长度=文法i-规则右部长度 右部长度0 把右部 p 指向的右部首符号的 first 集合加入规则右部的 first 集合i 把规则右部 first 集合i加入相应 左部的 first 集合，却有加入时置 “加入新元素” i= i +1 i左部符号序号 p！=null p=规则右部 first 集合i j=p-终结符号序号 j=0 q=follow 集合左部符号 q！=null k=p-终结符号序号 分析表左部符号 k！=0 分析表左部符号 k =i q= q-下一集合元素指针 p=p-下一集合元素指针 itp 请输入文法的第 2 条（共 5 条）产生式：p-+tp| 请输入文法的第 3 条（共 5 条）产生式：t-fq 请输入文法的第 4 条（共 5 条）产生式：q-*fq| 请输入文法的第 5 条（共 5 条）产生式：f-(e)|i|x|y * 分解后的产生式共 10 条: * 1. e-tp 2. p-+tp 3. p- 4. t-fq 5. q-*fq 6. q- 7. f-(e) 8. f-i 沈阳航空工业学院课程设计报告 17 9. f-x 10. f-y * *欢迎使用预测分析表生成系统* 1.输入文法 2. 生成预测分析表 3.输出预测分析表 其它键退出 * 2 预测分析表已生成！ *欢迎使用预测分析表生成系统* 1.输入文法 2. 生成预测分析表 3.输出预测分析表 其它键退出 * 3 ll(1)预测分析表如下 - + * ( ) i x y # - e 1 1 1 1 - p 2 3 3 - t 4 4 4 4 - q 6 5 6 6 - f 7 8 9 10 - *欢迎使用预测分析表生成系统* 1.输入文法 2. 生成预测分析表 3.输出预测分析表 其它键退出 沈阳航空工业学院课程设计报告 18 * 5 感谢使用本系统，期待您的下次使用！ press any key to continue 将系统的运行结果和第一章中的分析结果进行比较，可知其运行结果是正确 的。经过多次测试，说明了上述现象的出现不是偶然的，从而验证了系统设计的 正确性。 沈阳航空工业学院课程设计报告 19 参考文献 1 陈火旺，刘春林等. . 编译原理（第三版） m. 北京：国防工业出版社， 2000 2 霍林编译技术课程设计与上机指导m. 重庆：重庆大学出版社，2001 3 胡元义，邓亚玲，谈姝辰. .编译原理教程(第二版)习题解析与上机指导m .西 安：西安电子科技大学出版社，2006 4 王雷，刘志成，周晶. . 编译原理课程设计m . 北京：机械工业出版社，2005 5 alfred v.aho,ravi sethi,jeffrey d.ullman.李建中，姜守旭.编译原理m .北京： 机械工业出版社，2003 6 高仲仪，金茂忠.编译原理及编译程序构造m .北京：北京航空航天大学出版 社，1990 沈阳航空工业学院课程设计报告 20 附 录（关键部分程序清单） #include #include #include int count=0; /*分解的产生式的个数*/ int number; /*所有终结符和非终结符的总数*/ char start; /*开始符号*/ char termin50; /*终结符号*/ char non_ter50; /*非终结符号*/ char v50; /*所有符号*/ char left50; /*左部*/ char right5050; /*右部*/ 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 集合时使用*/ / 判断一个字符是否在指定字符串中 int in(char c,char *p) int i; if(strlen(p)=0) return(0); for(i=0;i+) if(pi=c) return(1); /*若在，返回 1*/ if(i=strlen(p) return(0); /*若不在，返回 0*/ /分解不含有左递归的产生式 void non_re(char *point) 沈阳航空工业学院课程设计报告 21 int m=0,j; char temp20; for(j=3;j) printf(“ninput error!“); validity=0; return(0); /*检测输入错误*/ for(k=0;k=0) firsti0=; firsti1=0; 沈阳航空工业学院课程设计报告 27 else temp0=; temp1=0; else for(j=0;j+) if(vj=p0) break; if(i=0) memcpy(firsti,first1j,strlen(first1j); firstistrlen(first1j)=0; else memcpy(temp,first1j,strlen(first1j); tempstrlen(first1j)=0; else /*如果右部为符号串*/ for(j=0;j+) if(vj=p0) break; if(i=0) merge(firsti,first1j,2); else merge(temp,first1j,2); for(k=0;k=0) merge(firsti,first1m,2); else 沈阳航空工业学院课程设计报告 28 merge(temp,first1m,2); else if(_emp(pk)=1 temp1=0; if(i=0) merge(firsti,temp,1); else merge(temp,temp,1); else if(_emp(pk)=0) break; /求各产生式左部的 follow void follow(int i) int j,k,m,n,result=1; char c,temp20; c=non_teri; /*c 为待求的非终结符*/ temp0=c; temp1=0; merge(fo,temp,1); if(c=start) /*若为开始符号*/ temp0=#; temp1=0; merge(followi,temp,1); for(j=0;j%sn“,i,lefti,righti);