资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
实验四:LL (1)文法的判别一、 实验名称LL(1)文法的判别二、 实验目的(1)能导出空串的非终结符算法(2)实现首符集,后跟符集和可选集算法(3)输出要指出是否为 LL(1)文法, 三、 实验原理 将数组 X 中对应每一非终结符的标记置初值为未定。 扫描文法中的产生式。(a) 删除所有右部含有终结符的产生式,若这使得以某一非终结符为左部的所有产生式都被删除,则将数组中对应该非终结符的标记值改为否,说明该非终结符不能推出 。(b) 若某一非终结符的某一产生式右部为 ,则将数组中对应该非终结符的标志置为是,并从文法中删除该非终结符的所有产生式。例中对应非终结符 A、B 的标志改为是。 扫描产生式右部的每一符号。(a) 若所扫描到的非终结符号在数组中对应的标志是是,则删去该非终结符,若这使产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改是,并删除该非终结符为左部的所有产生式。(b) 若所扫描到的非终结符号在数组中对应的标志是否,则删去该产生式,若这使产生式左部非终结符的有关产生式都被删去,则把在数组中该非终结符对应的标志改成否。 重复,直到扫描完一遍文法的产生式,数组中非终结符对应的特征再没有改变为止。由中(a) 、(b)得知例中对应非终结符 D 的标志改为否,对应非终结符 A、B 的标志改为是。经过上述中(a)、(b)两步后文法中的产生式只剩下:SAB 和 CAD ,也就是只剩下右部全是非终结符串的产生式。再由中的(a)步扫描到产生式 SAB 时,在数组中 A、B 对应的标志都为是,删去后 S 的右部变为空,所以 S 对应标志置为是。最后由中的(b)扫描到产生式 CAD 时,其中,A 对应的标志为是,D对应的标志是否,删去该产生式后,再无左部为 C 的产生式,所以 C 的对应标志改为否四、 实验小结通过本次实验,熟悉了 LL(1)文法,掌握了 LL(1)文法的判定方法,具体实践了 FIRST 集、FOLLOW 集、SELECT 集的计算,加深了对 LL(1)文法的理解。此外,将理论用于实践,亲身体会到了怎样求 FIRST 集等。如何理解转化的过程是相当重要,以及如何去创建程序去实现这一转化过程。这样的编程对于我来说是相当困难的,这次的程序并非自己编写的。但是我会一步步去理解该程序的每步含义,争取就算自己不会编写代码,但至少做到实现过程、步骤。通过实验进一步理解编译原理这门课程,知道这么可是多么难学,知道和理解了该理论在计算机中是怎样执行的,对该理论在实践中的应用有深刻的理解。在这次课程设计中,我们组就是按照实验指导的思想来完成,加强培养实践动手能力和程序开发能力。五、 附录#include#includeint 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; /*分析表*/char choose; /*用户输入时使用*/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*/判断一个字符是否在指定字符串中char c()char c=A;while(in(c,non_ter)=1)c+;return(c);/得到一个不是非终结符的符号void recur(char *point)/ 分解含有左递归的产生式 /*完整的产生式在point中*/int j,m=0,n=3,k;char temp20,ch;ch=c(); /*得到一个非终结符*/k=strlen(non_ter);non_terk=ch;non_terk+1=0;for(j=0;j) printf(ninput error!);validity=0;return(0);/*检测输入错误*/for(k=0;k=0) firsti0=;firsti1=0; elseTEMP0=;TEMP1=0;else for(j=0;j+)if(vj=p0)break;if(i=0)memcpy(firsti,first1j,strlen(first1j);firstistrlen(first1j)=0;elsememcpy(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);elsemerge(TEMP,first1m,2);else if(_emp(pk)=1&k=length-1)temp0=;temp1=0;if(i=0)merge(firsti,temp,1); elsemerge(TEMP,temp,1);else if(_emp(pk)=0)break;void FOLLOW(int i) /求各产生式左部的FOLLOWint 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=0;n-)Sp+=rightmn;Sq+strlen(rightm)=0;printf(S:%s str:,S);for(p=j;p=0)printf(M%d%d=%d ,i,j,Mij);menu();*/
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号