编译原理实验七：LL(1)文法的判断

1、实验七：LL(1)文法的判断 一：要求输入：任意的上下文无关文法。输出：判断是否为LL（1）文法二：实验目的1掌握LL(1)的判断，掌握求first和follow集合的算法2熟悉运用C/C+语言对求first和follow集合进行实现 三：实验原理设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1）若xiVT，则xiFIRST（）；（2）若xiVN； 若 FIRST（xi），则FIRST（xi）FIRST（）； 若FIRST（xi），则FIRST（xi）FIRST（）；（3）ii+1，重复（1）、（2），直到xiVT，（i2，3，n）或xiVN且若 FIRST（xi）

2、或i>n为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则 FOLLOW（A）a | S Aa ，aVT。若S A，#FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1）对于文法GS的开始符号S，有#FOLLOW（S）；（2）若文法GS中有形如BxAy的规则，其中x，yV

3、*，则FIRST（y）FOLLOW（A）；（3）若文法GS中有形如BxA的规则，或形如BxAy的规则且FIRST（y），其中x，yV *，则FOLLOW（B）FOLLOW（A）；四：数据结构与算法typedef struct Chomsky /定义一个产生式结构体 string left; /定义产生式的左部 string right; /定义产生式的右部Chomsky;void apart(Chomsky *p,int i) /分开产生式左右部，i代表产生式的编号string is_empty(Chomsky *p)/判断某非终结符能否直接推出空，空用#代替string isempty(Ch

4、omsky *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)/求产生式的select集,s1是产生式左部，s2是产生式右部五：出错分析1:select集计算不出，关键在于能

5、产生空的非终结符没有求出来2:单个符号的first集与一串符号的first集区别3:实验最后没能输出select集，没能判断出来是否是LL(1)文法 六：实验结果与分析七：源代码#include<iostream>#include<string>using namespace std;#define max 100typedef struct Chomsky /定义一个产生式结构体 string left; /定义产生式的左部 string right; /定义产生式的右部Chomsky;int n;/产生式总数string strings;/存储产生式string n

6、oend;/存放文法中的非终结符string empty;/存放可以推出空的非终结符string firstmax;/存放非终结符的first集string followmax;/存放非终结符的follow集string selectmax;/存放产生式的select集void apart(Chomsky *p,int i) /分开产生式左右部，i代表产生式的编号int j; for(j=0;j<strings.length();j+)if(stringsj='-')pi.left=strings.substr(0,j);/从0开始的j长度的子串，即0j-1pi.righ

7、t=strings.substr(j+1,strings.length()-j);/从j+1开始的后面子串/*string is_empty(Chomsky *p)/判断某非终结符能否直接推出空，空用#代替/如果可以，返回1/不可以，返回0int i;string s;for(i=0;i<n;i+)if (pi.right0="#"&&pi.right.length()=1)/直接推出空的empty=empty+pi.left;s=empty;return s;/s存放能直接推出空的非终结符string isempty(Chomsky *p)/可以间接

8、推出空的非终结符int i,j;string s1;for(i=0;i<n;i+)if(is_empty(p).find(pi.left)>=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)/提取产生式中的非终结符

9、int i,j;for(i=0;i<n;i+)if(!(noend.find(pi.left0)>=0&&noend.find(pi.left0)<noend.length()noend=noend+pi.left;for(j=0;j<pi.right.length();j+)if('A'<=pi.rightj&&pi.rightj<='Z')if(noend.find(pi.rightj)>=0&&noend.find(pi.rightj)<noend.length

10、()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,x,y;int flag=0;for(i=0;i<n;i+)if(m=pi.left0)if('a'<=pi.right0&&'z'>=pi.right0) firstmm=firstmm+pi.right.substr(0,1);if(pi

11、.right0='#') firstmm=firstmm+pi.right.substr(0,1);if('A'<=pi.right0&&'Z'>=pi.right0)for(j=0;j<pi.right.length();j+)if('A'<=pi.rightj&&pi.rightj<='Z')flag+;if(flag=j)/产生式的右部均为非终结符flag=0;for(j=0;j<pi.right.length();j+)for(x=0;x&

12、lt;n;x+)if(pi.rightj=px.left0&&px.right0='#')flag+;break;if(flag=j)/产生式右部的全部非终结符均能推出空for(j=0;j<pi.right.length();j+)for(x=0;x<n;x+)if(pi.rightj=noendx)break;y=x;if(firsty="")First(p,n,pi.rightj,x); f=firsty;for(x=0;x<f.length();x+)if(fx='#')if(x=f.length()-

13、1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f; firstmm=firstmm+"#"elsefor(j=0;j<pi.right.length();j+)for(x=0;x<n;x+)if(pi.rightj=noendx)break;y=x;if(firsty="")First(p,n,pi.rightj,x);f=firsty;for(x=0;x<f.length();x+)if(fx='#')if(x=f.lengt

14、h()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f;void Follow(Chomsky *p,int n,int m)/求文法的follow集int i,j,x,y,k;string fo;for(i=0;i<n;i+)for(j=0;j<pi.right.length();j+)if(noendm=pi.rightj)if(j<pi.right.length()-1&&'a'<=pi.rightj+1&&pi.righ

15、tj+1<='z') followm=followm+pi.right.substr(j+1,1); if(j<pi.right.length()-1&&'A'<=pi.rightj+1&&pi.rightj+1<='Z')for(y=0;y<noend.length();y+)if(noendy=pi.rightj+1)break;fo=firsty;for(x=0;x<firsty.length();x+)if(0<=firsty.find('#')&a

16、mp;&firsty.find('#')<firsty.length()fo=firsty.substr(0,firstm.find('#')+firsty.substr(firsty.find('#')+1); followm=followm+fo; for(x=0;x<n;x+)if(pi.rightj+1=px.left0&&px.right0='#')break; if(x!=n)/非终结符后面的部分可以推出空for(y=0;y<n;y+)if(pi.left0=noendy)br

17、eak; k=y; if(followk="")Follow(p,n,y); followm=followm+followk; if(j=pi.right.length()-1) for(y=0;y<n;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;i<s.length();i+)for(j=0

18、;j<s.length();j+)if(i!=j&&si=sj)s=s.substr(0,j)+s.substr(j+1);return s;/*void select(string s1,string s2)/求产生式的select集,s1是产生式左部，s2是产生式右部if()/即s2可以推出空#cout<<s1<<"->"<<s2<<"="<<first(s2)<<endl;else/即s2不可以推出空#cout<<s1<<&q

19、uot;->"<<s2<<"="<<first(s2)-"#"+<<follow(s1)<<endl;*/void main()cout<<".编译原理实验七：LL(1)文法的判断."<<endl;int i,j,m;char f;/存放文法开始符号cout<<"请输入文法产生式个数N以及各产生式（空用#代替，链接左右部的为-）："<<endl;cin>>n;Chomsky *p=

20、new Chomskyn; / 初始化产生式数组 for(i=0;i<n;i+)strings.erase();/清除cin>>strings; apart(p,i); cout<<"请输入该文法的开始符号："<<endl;cin>>f;search(p,n);/提取产生式中的非终结符/empty=is_empty(p)+isempty(p);/可以推出空的所有非终结符for(m=0;m<noend.length();m+)if(firstm="")First(p,n,noendm,m);cout<<"