编译原理实验七：LL(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）或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 *，则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(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)/求产生式的select集,s1是产生式左部，s2是产生式右部五：出错分析1:select集计算不出，关键在于能产生空的非终结符没有求出来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 noend;/存放文法中的非终结符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.right=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)/可以间接推出空的非终结符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)/提取产生式中的非终结符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()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.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<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()-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=#)