《编译原理实验七：LL(1)文法的判断》由会员分享，可在线阅读，更多相关《编译原理实验七：LL(1)文法的判断（11页珍藏版）》请在金锄头文库上搜索。
1、实验七：实验七：LL(1)LL(1)文法的判断文法的判断一：要求一：要求输入：任意的上下文无关文法。输出：判断是否为 LL1文法二：实验目的二：实验目的1 掌握 LL(1)的判断，掌握求 first 和 follow 集合的算法2 熟悉运用 C/C+语言对求 first 和 follow 集合进行实现三：实验原理三：实验原理设x1x2xn，FIRST可按以下方法求得：令 FIRST，i1；1假设 xiVT，则 xiFIRST ；2假设 xiVN； 假设 FIRSTxi ，则 FIRSTxiFIRST ； 假设FIRSTxi ，则 FIRSTxiFIRST ；3ii+1，重复1 、 2 ，直到
2、xiVT， i2，3，n或 xiVN 且假设 FIRSTxi或 in 为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符 A 之后，才能知道是否选择 A产生式。这些合法地出现在非终结符 A 之后的符号组成的集合被称为 FOLLOW 集合。 下面我们给出文法的 FOLLOW 集的定义。设文法 GSVN，VT，P，S ，则FOLLOWAa | S Aa ，aVT。假设 S A，#FOLLOWA 。由定义可以看出，FOLLOWA是指在文法GS的所有句型中，紧跟在非终结符 A 后的终结符号的集合。FOLLOW 集可按以下方法求得：1对于文法 GS的开始符号 S，有#
3、FOLLOWS ；2假设文法 GS中有形如 BxAy的规则，其中 x，yV *，则 FIRSTyFOLLOWA ；3假设文法 GS中有形如 BxA 的规则，或形如 BxAy 的规则且FIRSTy ，其中 x，yV *，则 FOLLOWBFOLLOWA ；四：数据结构与算法四：数据结构与算法typedef struct Chomsky /定义一个产生式结构体 string left; /定义产生式的左部 string right; /定义产生式的右部Chomsky;void apart(Chomsky *p,int i) /分开产生式左右部，i 代表产生式的编号string is_empty(C
4、homsky *p)/判断某非终结符能否直接推出空，空用#代替string isempty(Chomsky *p)/可以间接推出空的非终结符void search(Chomsky *p,int n)/提取产生式中的非终结符void First(Chomsky *p,int n,char m,int mm)/ 求文法中非终结符的First集void Follow(Chomsky *p,int n,int m)/求文法的 follow 集string erase(string s)/去 First 集及 follow 集中的重复字符void select(string s1,string s2)/
5、求产生式的 select 集,s1 是产生式左部，s2 是产生式右部五：出错分析五：出错分析1:select 集计算不出，关键在于能产生空的非终结符没有求出来2:单个符号的 first 集与一串符号的 first 集区别3:实验最后没能输出 select 集，没能判断出来是否是 LL(1)文法2六：实验结果与分析六：实验结果与分析3七：源代码七：源代码#include#includeusing namespace std;#define max 100typedef struct Chomsky/定义一个产生式结构体string left; /定义产生式的左部string right; /定义
6、产生式的右部Chomsky;int n;/产生式总数string strings;/存储产生式string noend;/存放文法中的非终结符string empty;/存放可以推出空的非终结符string firstmax;/存放非终结符的 first 集string followmax;/存放非终结符的 follow 集string selectmax;/存放产生式的 select 集void apart(Chomsky *p,int i) /分开产生式左右部，i 代表产生式的编号int j;for(j=0;jstrings.length();j+)if(stringsj=-)pi.lef
7、t=strings.substr(0,j);/从 0 开始的 j 长度的子串，即 0j-1pi.right=strings.substr(j+1,strings.length()-j);/从 j+1 开始的后面子串/*string is_empty(Chomsky *p)/判断某非终结符能否直接推出空，空用#代替/如果可以，返回 1/不可以，返回 0int i;string s;for(i=0;in;i+)if (pi.right0=#&pi.right.length()=1)/直接推出空的empty=empty+pi.left;4s=empty;return s;/s 存放能直接推出空的非终
8、结符string isempty(Chomsky *p)/可以间接推出空的非终结符int i,j;string s1;for(i=0;i=0)/假设此非终结符已经存在直接推出空那里， 在此无需重复计算elsefor(j=0;j(int)pi.right.length();j+)if(is_empty(p).find(pi.right.j)0)if(j=(int)pi.right.length()/如果右部所有符号都在直接推出空那里， 则此左部也可以推出空s1=s1+pi.left0;*/void search(Chomsky *p,int n)/提取产生式中的非终结符int i,j;for(i
9、=0;i=0&noend.find(pi.left0)noend.length()noend=noend+pi.left;5for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=0&noend.find(pi.rightj)noend.length()break;elsenoend=noend+pi.right.substr(j,1);void First(Chomsky *p,int n,char m,int mm)/求文法中非终结符的 First 集int length=noend.length();string f;int i,j,
10、x,y;int flag=0;for(i=0;in;i+)if(m=pi.left0)if(a=pi.right0)firstmm=firstmm+pi.right.substr(0,1);if(pi.right0=#)firstmm=firstmm+pi.right.substr(0,1);if(A=pi.right0)for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=Z)flag+;if(flag=j)/产生式的右部均为非终结符flag=0;for(j=0;jpi.right.length();j+)for(x=0;xn;x+)i
11、f(pi.rightj=px.left0&px.right0=#)flag+;break;6if(flag=j)/产生式右部的全部非终结符均能推出空for(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=noendx)break;y=x;if(firsty=)First(p,n,pi.rightj,x);f=firsty;for(x=0;xf.length();x+)if(fx=#)if(x=f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1);firstmm=f
12、irstmm+f;firstmm=firstmm+#;elsefor(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=noendx)break;y=x;if(firsty=)First(p,n,pi.rightj,x);f=firsty;for(x=0;xf.length();x+)if(fx=#)if(x=f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1);7firstmm=firstmm+f;void Follow(Chomsky *p,int n,int
13、m)/求文法的 follow 集int i,j,x,y,k;string fo;for(i=0;in;i+)for(j=0;jpi.right.length();j+)if(noendm=pi.rightj)if(jpi.right.length()-1&a=pi.rightj+1&pi.rightj+1=z)followm=followm+pi.right.substr(j+1,1);if(jpi.right.length()-1&A=pi.rightj+1&pi.rightj+1=Z)for(y=0;ynoend.length();y+)if(noendy=pi.rightj+1)brea
14、k;fo=firsty;for(x=0;xfirsty.length();x+)if(0=firsty.find(#)&firsty.find(#)firsty.length()fo=firsty.substr(0,firstm.find(#)+firsty.substr(firsty.find(#)+1);followm=followm+fo;for(x=0;xn;x+)if(pi.rightj+1=px.left0&px.right0=#)break;if(x!=n)/非终结符后面的部分可以推出空for(y=0;yn;y+)8if(pi.left0=noendy)break;k=y;if(
15、followk=)Follow(p,n,y);followm=followm+followk;if(j=pi.right.length()-1)for(y=0;yn;y+)if(pi.left0=noendy)break;k=y;if(followk=)Follow(p,n,y);followm=followm+followk;string erase(string s)/去 First 集及 follow 集中的重复字符int i,j;for(i=0;is.length();i+)for(j=0;js.length();j+)if(i!=j&si=sj)s=s.substr(0,j)+s.s
16、ubstr(j+1);return s;/*void select(string s1,string s2)/求产生式的 select 集,s1 是产生式左部，s2 是产生式右部if()/即 s2 可以推出空#couts1s2=first(s2)endl;else/即 s2 不可以推出空#9couts1s2=first(s2)-#+follow(s1)endl;*/void main()cout.编译原理实验七：LL(1)文法的判断.endl;int i,j,m;char f;/存放文法开始符号cout请输入文法产生式个数N 以及各产生式空用 #代替，链接左右部的为 - ：n;Chomsky
17、*p=new Chomskyn;/ 初始化产生式数组for(i=0;istrings;apart(p,i);cout请输入该文法的开始符号：f;search(p,n);/提取产生式中的非终结符/empty=is_empty(p)+isempty(p);/可以推出空的所有非终结符for(m=0;mnoend.length();m+)if(firstm=)First(p,n,noendm,m);cout该文法非终结符的 first 集：endl;for(i=0;inoend.length();i+)firsti=erase(firsti);coutnoendi:firstiendl;for(m=0;mnoend.length();m+)if(noendm=f)followm=followm+#;if(followm=)Follow(p,n,m);cout该文法非终结符的 follow 集：endl;for(i=0;inoend.length();i+)followi=erase(followi);10coutnoendi:followiendl;cout该文法的各产生式的 select 集：endl;for(i=0;in;i+)selecti=erase(selecti);coutpi.leftpi.right:selectiendl;system(pause);11
