编译原理之LL(1)GFG

课程设计报告课程：编译原理课程设计学号：姓名：班级：教师：时间：2015.05.20-2015.07.02计算机学院图4 输入LL(1)文法并测试图7 测试非LL(1)文法附录：程序代码#include<stdlib.h>#include<stdio.h>#include<string.h>/*******************************************/int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/ char start; /*开始符号*/char termin[50]; /*终结符号*/char non_ter[50]; /*非终结符号*/char v[50]; /*所有符号*/char left[50]; /*左部*/char right[50][50]; /*右部*/char first[50][50],follow[50][50]; /*各产生式右部的FIRST和左部的FOLLOW集合*/ char first1[50][50]; /*所有单个符号的FIRST集合*/char select[50][50]; /*各单个产生式的SELECT集合*/char f[50],F[50]; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty[20]; /*记录可直接推出^的符号*/char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/ int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M[20][20]; /*分析表*/char choose; /*用户输入时使用*/char empt[20]; /*求_emp()时使用*/char fo[20]; /*求FOLLOW集合时使用*//*******************************************判断一个字符是否在指定字符串中********************************************/int in(char c,char *p){int i;if(strlen(p)==0) return(0);for(i=0;;i++){if(p[i]==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,k,m=0,n=3;char ch,temp[20];ch=c(); /*得到一个不是非终结符的符号*/k=strlen(non_ter);non_ter[k]=ch;non_ter[k+1]='\0';for(j=0;j<=strlen(point)-1;j++){if(point[n]==point[0]){ /*如果'|'后的首符号和左部相同*/ for(j=n+1;j<=strlen(point)-1;j++){while(point[j]!='|'&&point[j]!='\0') temp[m++]=point[j++];left[count]=ch;memcpy(right[count],temp,m);/*从temp所指向的内存单元顺序取m个字节复制到右部*/right[count][m]=ch;right[count][m+1]='\0';m=0;count++;if(point[j]=='|'){n=j+1;break;}}}else{ /*如果'|'后的首符号和左部不同*/left[count]=ch;right[count][0]='^';right[count][1]='\0';count++;for(j=n;j<=strlen(point)-1;j++){if(point[j]!='|') temp[m++]=point[j];else{left[count]=point[0];memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';printf(" count=%d ",count);m=0;count++;}}left[count]=point[0];memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';count++;m=0;}}}/******************************************* 分解不含有左递归的产生式********************************************/ void non_re(char *point){int m=0,j;char temp[20];for(j=3;j<=strlen(point)-1;j++){if(point[j]!='|') temp[m++]=point[j];else{left[count]=point[0];memcpy(right[count],temp,m);right[count][m]='\0';m=0;count++;}}left[count]=point[0];memcpy(right[count],temp,m);right[count][m]='\0';count++;m=0;}/******************************************* 读入一个文法********************************************/char grammer(char *t,char *n,char *left,char right[50][50]){char vn[50],vt[50];char s;char p[50][50];int i,j,k;printf("请输入文法的非终结符号串：");scanf("%s",vn);//getchar(); /*取出缓冲区剩余的回车键，不要也可*/ i=strlen(vn);memcpy(n,vn,i);n[i]='\0';printf("\n请输入文法的终结符号串：");scanf("%s",vt);getchar();i=strlen(vt);memcpy(t,vt,i);t[i]='\0';printf("\n请输入文法的开始符号：");scanf("%c",&s);//getchar();printf("\n请输入文法产生式的条数：");scanf("%d",&i);//getchar();for(j=1;j<=i;j++){printf("\n请输入文法的第%d条（共%d条）产生式：",j,i);scanf("%s",p[j-1]);getchar();}for(j=0;j<=i-1;j++)if(p[j][1]!='-'||p[j][2]!='>'){printf("\nInput error!\n");validity=0;return('\0');} /*检测输入错误*/for(k=0;k<=i-1;k++){ /*分解输入的各产生式*/if(p[k][3]==p[k][0]) recur(p[k]);else non_re(p[k]);}return(s);}/*******************************************将单个符号或符号串并入另一符号串********************************************/void merge(char *d,char *s,int type){/*d是目标串s是源串，type＝1，源串中的'^'并入目串；type＝2，源串中的'^'不并入目串*/ int i,j;for(i=0;i<=strlen(s)-1;i++){if(type==2&&s[i]=='^');else{for(j=0;;j++){if(j<strlen(d)&&s[i]==d[j]) break;if(j==strlen(d)){d[j]=s[i];d[j+1]='\0';break;}}}}}/*******************************************求所有能直接推出‘^’的符号********************************************/void emp(char c){ /*即求所有由'^'推出的符号*/char temp[10];int i;for(i=0;i<=count-1;i++){if(right[i][0]==c&&strlen(right[i])==1){temp[0]=left[i];temp[1]='\0';merge(empty,temp,1);emp(left[i]);}}/*******************************************求某一符号能否推出‘^’********************************************/int _emp(char c){ /*若能推出，返回1；否则，返回0*/ int i,j,k,result=1,mark=0;char temp[20];temp[0]=c;temp[1]='\0';merge(empt,temp,1);if(in(c,empty)==1) return(1);for(i=0;;i++){if(i==count) return(0);if(left[i]==c) /*找一个左部为c的产生式*/{j=strlen(right[i]); /*j为右部的长度*/if(j==1&&in(right[i][0],empty)==1) return(1);else if(j==1&&in(right[i][0],termin)==1) return(0);else{for(k=0;k<=j-1;k++)if(in(right[i][k],empt)==1) mark=1;if(mark==1) continue;else{for(k=0;k<=j-1;k++){result*=_emp(right[i][k]);temp[0]=right[i][k];temp[1]='\0';merge(empt,temp,1);}}}if(result==0&&i<count) continue;else if(result==1&&i<count) return(1);}}}/*******************************************判断读入的文法是否正确********************************************/int judge(){int i,j;for(i=0;i<=count-1;i++){if(in(left[i],non_ter)==0){ /*若左部不在非终结符中，报错*/printf("\nLeft error!");validity=0;return(0);}for(j=0;j<=strlen(right[i])-1;j++){if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^'){ /*若右部某一符号不在非终结符、终结符中且不为'^'，报错*/printf("\nRight error!");validity=0;return(0);}}}return(1);}/*******************************************求单个符号的FIRST集********************************************/void first2(int i){ /*i为符号在所有输入符号中的序号*/char c,ch='^',temp[20];int j,k,m;c=v[i];emp(ch);if(in(c,termin)==1) /*若为终结符*/{first1[i][0]=c;first1[i][1]='\0';}else if(in(c,non_ter)==1) /*若为非终结符*/{for(j=0;j<=count-1;j++){if(left[j]==c){if(in(right[j][0],termin)==1||right[j][0]=='^'){temp[0]=right[j][0];temp[1]='\0';merge(first1[i],temp,1);}else if(in(right[j][0],non_ter)==1){if(right[j][0]==c) continue;for(k=0;;k++)if(v[k]==right[j][0]) break;if(f[k]=='0'){first2(k);f[k]='1';}merge(first1[i],first1[k],2);for(k=0;k<=strlen(right[j])-1;k++){empt[0]='\0';if(_emp(right[j][k])==1&&k<strlen(right[j])-1){for(m=0;;m++)if(v[m]==right[j][k+1]) break;if(f[m]=='0'){first2(m);f[m]='1';}merge(first1[i],first1[m],2);}else if(_emp(right[j][k])==1&&k==strlen(right[j])-1){temp[0]='^';temp[1]='\0';merge(first1[i],temp,1);}else break;}}}}}f[i]='1';}/*******************************************求各产生式右部的FIRST集********************************************/ void FIRST(int i,char *p){int length;int j,k,m;char temp[20];length=strlen(p);if(length==1) /*如果右部为单个符号*/{if(p[0]=='^'){if(i>=0){first[i][0]='^';first[i][1]='\0';}else{TEMP[0]='^';TEMP[1]='\0';}}else{for(j=0;;j++)if(v[j]==p[0]) break;if(i>=0){memcpy(first[i],first1[j],strlen(first1[j]));first[i][strlen(first1[j])]='\0';}else{memcpy(TEMP,first1[j],strlen(first1[j]));TEMP[strlen(first1[j])]='\0';}}}else /*如果右部为符号串*/{for(j=0;;j++)if(v[j]==p[0]) break;if(i>=0) merge(first[i],first1[j],2);else merge(TEMP,first1[j],2);for(k=0;k<=length-1;k++){empt[0]='\0';if(_emp(p[k])==1&&k<length-1){for(m=0;;m++)if(v[m]==right[i][k+1]) break;if(i>=0) merge(first[i],first1[m],2);else merge(TEMP,first1[m],2);}else if(_emp(p[k])==1&&k==length-1){temp[0]='^';temp[1]='\0';if(i>=0) merge(first[i],temp,1);else merge(TEMP,temp,1);}else if(_emp(p[k])==0) break;}}}/******************************************* 求各产生式左部的FOLLOW集********************************************/ void FOLLOW(int i){int j,k,m,n,result=1;char c,temp[20];c=non_ter[i]; /*c为待求的非终结符*/temp[0]=c;temp[1]='\0';merge(fo,temp,1);if(c==start){ /*若为开始符号*/temp[0]='#';temp[1]='\0';merge(follow[i],temp,1);}for(j=0;j<=count-1;j++){if(in(c,right[j])==1) /*找一个右部含有c的产生式*/{for(k=0;;k++)if(right[j][k]==c) break; /*k为c在该产生式右部的序号*/for(m=0;;m++)if(v[m]==left[j]) break; /*m为产生式左部非终结符在所有符号中的序号*/ if(k==strlen(right[j])-1){ /*如果c在产生式右部的最后*/if(in(v[m],fo)==1){merge(follow[i],follow[m],1);continue;}if(F[m]=='0'){FOLLOW(m);F[m]='1';}merge(follow[i],follow[m],1);}else{ /*如果c不在产生式右部的最后*/for(n=k+1;n<=strlen(right[j])-1;n++){empt[0]='\0';result*=_emp(right[j][n]);}if(result==1){ /*如果右部c后面的符号串能推出^*/if(in(v[m],fo)==1){ /*避免循环递归*/merge(follow[i],follow[m],1);continue;}if(F[m]=='0'){FOLLOW(m);F[m]='1';}merge(follow[i],follow[m],1);}for(n=k+1;n<=strlen(right[j])-1;n++) temp[n-k-1]=right[j][n];temp[strlen(right[j])-k-1]='\0';FIRST(-1,temp);merge(follow[i],TEMP,2);}}}F[i]='1';}/*******************************************判断读入文法是否为一个LL(1)文法********************************************/int ll1(){int i,j,length,result=1;char temp[50];for(j=0;j<=49;j++){ /*初始化*/ first[j][0]='\0';follow[j][0]='\0';first1[j][0]='\0';select[j][0]='\0';TEMP[j]='\0';temp[j]='\0';f[j]='0';F[j]='0';}for(j=0;j<=strlen(v)-1;j++) first2(j); /*求单个符号的FIRST集合*/ printf("\nfirst1:");for(j=0;j<=strlen(v)-1;j++) printf("%c:%s ",v[j],first1[j]);printf("\nempty:%s",empty);printf("\n_emp:");for(j=0;j<=strlen(v)-1;j++) printf("%d ",_emp(v[j]));for(i=0;i<=count-1;i++) FIRST(i,right[i]); /*求FIRST集*/for(j=0;j<=strlen(non_ter)-1;j++){ /*求FOLLOW集*/ if(fo[j]==0){fo[0]='\0';FOLLOW(j);}}printf("\nfirst:");for(i=0;i<=count-1;i++) printf("%s ",first[i]);printf("\nfollow:");for(i=0;i<=strlen(non_ter)-1;i++) printf("%s ",follow[i]);for(i=0;i<=count-1;i++){ /*求每一产生式的SELECT集合*/ memcpy(select[i],first[i],strlen(first[i]));select[i][strlen(first[i])]='\0';for(j=0;j<=strlen(right[i])-1;j++)result*=_emp(right[i][j]);if(strlen(right[i])==1&&right[i][0]=='^')result=1;if(result==1){for(j=0;;j++)if(v[j]==left[i]) break;merge(select[i],follow[j],1);}}printf("\nselect:");for(i=0;i<=count-1;i++)printf("%s ",select[i]);memcpy(temp,select[0],strlen(select[0]));temp[strlen(select[0])]='\0';for(i=1;i<=count-1;i++){ /*判断输入文法是否为LL(1)文法*/ length=strlen(temp);if(left[i]==left[i-1]){merge(temp,select[i],1);if(strlen(temp)<length+strlen(select[i])) return(0);}else{temp[0]='\0';memcpy(temp,select[i],strlen(select[i]));temp[strlen(select[i])]='\0';}}return(1);}/*******************************************构造分析表M********************************************/void MM(){int i,j,k,m;for(i=0;i<=19;i++)for(j=0;j<=19;j++) M[i][j]=-1;i=strlen(termin);termin[i]='#'; /*将#加入终结符数组*/termin[i+1]='\0';for(i=0;i<=count-1;i++){for(m=0;;m++)if(non_ter[m]==left[i]) break; /*m为产生式左部非终结符的序号*/ for(j=0;j<=strlen(select[i])-1;j++){if(in(select[i][j],termin)==1){for(k=0;;k++)if(termin[k]==select[i][j]) break; /*k为产生式右部终结符的序号*/ M[m][k]=i;}}}}/*******************************************总控算法********************************************/void syntax(){int i,j,k,m,n,p,q;char ch,S[50],str[50];printf("\n请输入该文法的句型：");scanf("%s",str);getchar();i=strlen(str);str[i]='#';str[i+1]='\0';S[0]='#';S[1]=start;S[2]='\0';j=0;ch=str[j];while(1){if(in(S[strlen(S)-1],termin)==1){if(S[strlen(S)-1]!=ch){printf("\n该符号串不是文法的句型！");return;}else if(S[strlen(S)-1]=='#'){printf("\n该符号串是文法的句型.");return;}else{S[strlen(S)-1]='\0';j++;ch=str[j];}}else{for(i=0;;i++)if(non_ter[i]==S[strlen(S)-1]) break;for(k=0;;k++){if(termin[k]==ch) break;if(k==strlen(termin)){printf("\n词法错误！");return;}}if(M[i][k]==-1){printf("\n语法错误！");return;}else{m=M[i][k];if(right[m][0]=='^') S[strlen(S)-1]='\0';else{p=strlen(S)-1;q=p;for(n=strlen(right[m])-1;n>=0;n--) S[p++]=right[m][n];S[q+strlen(right[m])]='\0';}}}printf("S:%s str:",S);for(p=j;p<=strlen(str)-1;p++) printf("%c",str[p]);printf(" \n");}}/*******************************************一个用户调用函数********************************************/void menu(){syntax();printf("\n是否继续？(y or n):");scanf("%c",&choose);getchar();while(choose=='y') menu();}/*******************************************主函数********************************************/void main(){int i,j;start=grammer(termin,non_ter,left,right); /*读入一个文法*/printf("count=%d",count);printf("\nstart:%c",start);strcpy(v,non_ter);strcat(v,termin);printf("\nv:%s",v);printf("\nnon_ter:%s",non_ter);printf("\ntermin:%s",termin);printf("\nright:");for(i=0;i<=count-1;i++) printf("%s ",right[i]);printf("\nleft:");for(i=0;i<=count-1;i++) printf("%c ",left[i]);if(validity==1) validity=judge();printf("\nvalidity=%d",validity);if(validity==1){ll=ll1();printf("\nll=%d",ll);if(ll==0) printf("\n该文法不是一个LL(1)文法！");else{MM();printf("\n");for(i=0;i<=19;i++)for(j=0;j<=19;j++)if(M[i][j]>=0)printf("M[%d][%d]=%d ",i,j,M[i][j]);menu();}}}。

南开大学计算机科学与技术学院课程设计报告（2010 ~2011 学年度第一学期）课程名称编译原理设计题目LL(1)分析姓名学号专业班级地点教师1.需求分析语法分析是编译过程的核心部分。

它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

语法分析器在编译程序中的地位如图1所示：图1 语法分析器在编译程序中的地位语言的语法结构是用上下文无关文法描述的。

因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。

这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。

对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。

或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。

自顶向下分析法就是语法分析办法中的一类。

顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。

这种方法是带“回溯”的。

自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。

或者说，为输入串寻找一个最左推导。

这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。

实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。

每个这种子程序可作为一个布尔过程。

一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。

对于给定的分析文法对象，构造它的预测分析程序；并任意给一算术表达式进行分析测试，本预测分析程序能够使用分析表和栈联合控制实现LL(1)分析，本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。

文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用递归下降语法分析法分析LL(1)方法的基本递归流程，以及用C++语言来编程实现分析器。

【编译原理】语法分析LL（1）分析法的FIRST和FOLLOW集 近来复习编译原理，语法分析中的⾃上⽽下LL(1)分析法，需要构造求出⼀个⽂法的FIRST和FOLLOW集，然后构造分析表，利⽤分析表+⼀个栈来做⾃上⽽下的语法分析（递归下降/预测分析），可是这个FIRST集合FOLLOW集看得我头⼤。

教课书上的规则如下，⽤我理解的语⾔描述的：任意符号α的FIRST集求法：1. α为终结符，则把它⾃⾝加⼊FIRSRT(α)2. α为⾮终结符，则：（1）若存在产⽣式α->a...，则把a加⼊FIRST(α),其中a可以为ε（2）若存在⼀串⾮终结符Y1,Y2, ..., Yk-1，且它们的FIRST集都含空串，且有产⽣式α->Y1Y2...Yk...，那么把FIRST(Yk)-{ε}加⼊FIRST(α)。

如果k-1抵达产⽣式末尾，那么把ε加⼊FIRST(α) 注意（2）要连续进⾏，通俗地描述就是：沿途的Yi都能推出空串，则把这⼀路遇到的Yi的FIRST集都加进来，直到遇到第⼀个不能推出空串的Yk为⽌。

重复1,2步骤直⾄每个FIRST集都不再增⼤为⽌。

任意⾮终结符A的FOLLOW集求法：1. A为开始符号，则把#加⼊FOLLOW(A)2. 对于产⽣式A-->αBβ： （1）把FIRST(β)-{ε}加到FOLLOW(B) （2）若β为ε或者ε属于FIRST(β)，则把FOLLOW(A)加到FOLLOW(B)重复1,2步骤直⾄每个FOLLOW集都不再增⼤为⽌。

⽼师和同学能很敏锐地求出来，⽽我只能按照规则，像程序⼀样⼀条条执⾏。

于是我把这个过程写成了程序，如下：数据元素的定义：1const int MAX_N = 20;//产⽣式体的最⼤长度2const char nullStr = '$';//空串的字⾯值3 typedef int Type;//符号类型45const Type NON = -1;//⾮法类型6const Type T = 0;//终结符7const Type N = 1;//⾮终结符8const Type NUL = 2;//空串910struct Production//产⽣式11 {12char head;13char* body;14 Production(){}15 Production(char h, char b[]){16 head = h;17 body = (char*)malloc(strlen(b)*sizeof(char));18 strcpy(body, b);19 }20bool operator<(const Production& p)const{//内部const则外部也为const21if(head == p.head) return body[0] < p.body[0];//注意此处只适⽤于LL(1)⽂法，即同⼀VN各候选的⾸符不能有相同的，否则这⾥的⼩于符号还要向前多看⼏个字符，就不是LL(1)⽂法了22return head < p.head;23 }24void print() const{//要加const25 printf("%c -- > %s\n", head, body);26 }27 };2829//以下⼏个集合可以再封装为⼀个⼤结构体--⽂法30set<Production> P;//产⽣式集31set<char> VN, VT;//⾮终结符号集，终结符号集32char S;//开始符号33 map<char, set<char> > FIRST;//FIRST集34 map<char, set<char> > FOLLOW;//FOLLOW集3536set<char>::iterator first;//全局共享的迭代器，其实觉得应该⽤局部变量37set<char>::iterator follow;38set<char>::iterator vn;39set<char>::iterator vt;40set<Production>::iterator p;4142 Type get_type(char alpha){//判读符号类型43if(alpha == '$') return NUL;//空串44else if(VT.find(alpha) != VT.end()) return T;//终结符45else if(VN.find(alpha) != VN.end()) return N;//⾮终结符46else return NON;//⾮法字符47 }主函数的流程很简单，从⽂件读⼊指定格式的⽂法，然后依次求⽂法的FIRST集、FOLLOW集1int main()2 {3 FREAD("grammar2.txt");//从⽂件读取⽂法4int numN = 0;5int numT = 0;6char c = '';7 S = getchar();//开始符号8 printf("%c", S);9 VN.insert(S);10 numN++;11while((c=getchar()) != '\n'){//读⼊⾮终结符12 printf("%c", c);13 VN.insert(c);14 numN++;15 }16 pn();17while((c=getchar()) != '\n'){//读⼊终结符18 printf("%c", c);19 VT.insert(c);20 numT++;21 }22 pn();23 REP(numN){//读⼊产⽣式24 c = getchar();25int n; RINT(n);26while(n--){27char body[MAX_N];28 scanf("%s", body);29 printf("%c --> %s\n", c, body);30 P.insert(Production(c, body));31 }32 getchar();33 }3435 get_first();//⽣成FIRST集36for(vn = VN.begin(); vn != VN.end(); vn++){//打印⾮终结符的FIRST集37 printf("FIRST(%c) = { ", *vn);38for(first = FIRST[*vn].begin(); first != FIRST[*vn].end(); first++){39 printf("%c, ", *first);40 }41 printf("}\n");42 }4344 get_follow();//⽣成⾮终结符的FOLLOW集45for(vn = VN.begin(); vn != VN.end(); vn++){//打印⾮终结符的FOLLOW集46 printf("FOLLOW(%c) = { ", *vn);47for(follow = FOLLOW[*vn].begin(); follow != FOLLOW[*vn].end(); follow++){48 printf("%c, ", *follow);49 }50 printf("}\n");51 }52return0;53 }主函数其中⽂法⽂件的数据格式为（按照平时做题的输⼊格式设计的）：第⼀⾏：所有⾮终结符，⽆空格，第⼀个为开始符号；第⼆⾏：所有终结符，⽆空格；剩余⾏：每⾏描述了⼀个⾮终结符的所有产⽣式，第⼀个字符为产⽣式头（⾮终结符），后跟⼀个整数位候选式的个数n，之后是n个以空格分隔的字符串为产⽣式体。

编译原理实验报告LL(1)分析法课程编译原理实验名称实验二 LL(1)分析法实验目的1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．掌握LL(1)驱动程序的构造方法。

一.实验内容及要求根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG（2）G->+TG（3）G->ε（4）T->FS（5）S->*FS（6）S->ε（7）F->(E)（8）F->i程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。

输出过程如下：步骤分析栈剩余输入串所用产生式1 E i+i*i# E->TG... ... ... ...二.实验过程及结果代码如下：#include#include "edge.h"using namespace std;edge::edge(){cin>>left>>right;rlen=right.length();if(NODE.find(left)>NODE.length()) NODE+=left;}string edge::getlf(){return left;}string edge::getrg(){return right;}string edge::getfirst(){return first;}string edge::getfollow(){return follow;}string edge::getselect(){return select;}string edge::getro(){string str;str+=right[0];return str;}int edge::getrlen(){return right.length();}void edge::newfirst(string w){int i;for(i=0;iif(first.find(w[i])>first.length())first+=w[i];}void edge::newfollow(string w){int i;for(i=0;iif(follow.find(w[i])>follow.length()&&w[i]!='@')follow+=w[i];}void edge::newselect(string w){int i;for(i=0;iif(select.find(w[i])>select.length()&&w[i]!='@') select+=w[i];}void edge::delfirst(){int i=first.find('@');first.erase(i,1);}int SUM;string NODE,ENODE;//计算firstvoid first(edge ni,edge *n,int x){int i,j;for(j=0;j{if(ni.getlf()==n[j].getlf()){if(NODE.find(n[j].getro()){for(i=0;iif(n[i].getlf()==n[j].getro())first(n[i],n,x);}elsen[x].newfirst(n[j].getro());}}}//计算followvoid follow(edge ni,edge *n,int x){int i,j,k,s;string str;for(i=0;i{s=NODE.find(ni.getrg()[i]);if(s-1) //是非终结符if(ifor(j=0;jif(n[j].getlf().find(ni.getrg()[i])==0) {if(NODE.find(ni.getrg()[i+1]){for(k=0;kif(n[k].getlf().find(ni.getrg()[i+1])==0) {n[j].newfollow(n[k].getfirst());if(n[k].getfirst().find("@")n[j].newfollow(ni.getfollow());}}else{str.erase();str+=ni.getrg()[i+1];n[j].newfollow(str);}}}}//计算selectvoid select(edge &ni,edge *n){int i,j;if(ENODE.find(ni.getro()){ni.newselect(ni.getro());if(ni.getro()=="@")ni.newselect(ni.getfollow());}elsefor(i=0;i{for(j=0;jif(ni.getrg()[i]==n[j].getlf()[0]){ni.newselect(n[j].getfirst());if(n[j].getfirst().find('@')>n[j].getfirst().length()) return;}}}//输出集合void out(string p){int i;if(p.length()==0)return;coutfor(i=0;i{cout}cout}//连续输出符号void outfu(int a,string c){int i;for(i=0;icout}//输出预测分析表void outgraph(edge *n,string (*yc)[50]) {int i,j,k;bool flag;for(i=0;i{if(ENODE[i]!='@'){outfu(10," ");cout}}outfu(10," ");coutint x;for(i=0;i{outfu(4," ");coutoutfu(5," ");for(k=0;k{flag=1;for(j=0;j{if(NODE[i]==n[j].getlf()[0]){x=n[j].getselect().find(ENODE[k]); if(x-1){cout"yc[i][k]=n[j].getrg();outfu(9-n[j].getrlen()," ");flag=0;}x=n[j].getselect().find('#');if(k==ENODE.length()-1&&x-1) {cout"yc[i][j]=n[j].getrg();}}}if(flag&&ENODE[k]!='@')outfu(11," ");}cout}}//分析符号串int pipei(string &chuan,string &fenxi,string (*yc)[50],int &b){char ch,a;int x,i,j,k; b++; cout9) outfu(8," "); else outfu(9," "); cout-1) { if(ch==a) { fenxi.erase(fenxi.length()-1,1); chuan.erase(0,1); coutfenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b)) return 1;elsereturn 0;}else{i=NODE.find(ch);if(a=='#'){x=ENODE.find('@');if(x-1) j=ENODE.length()-1; elsej=ENODE.length();}elsej=ENODE.find(a);if(yc[i][j].length()){cout"-1;k--) if(yc[i][j][k]!='@')fenxi+=yc[i][j][k];if(pipei(chuan,fenxi,yc,b)) return 1; elsereturn 0;}elsereturn 0;}}}void main(){edge *n;string str,(*yc)[50];int i,j,k;bool flag=0;cin>>SUM; coutNODE.length()&&ENODE.find(str[j])>ENODE.length())ENODE+=str[j]; } //计算first集合 for(i=0;in[j].getfirst().length()){ n[i].delfirst(); break; } } } } }for(k=0;koutfu(SUM," "); cout>chuan; fchuan=chuan; fenxi="#"; fenxi+=NODE[0]; i=0; coutoutfu(7," ");coutoutfu(10," ");coutoutfu(8," ");coutif(pipei(chuan,fenxi,yc,i))coutelsecout}截屏如下：三.实验中的问题及心得这次实验让我更加熟悉了LL（1）的工作流程以及LL(1)分析表的构造方法。

实验七：LL(1)文法的判断一：要求输入：任意的上下文无关文法。

输出：判断是否为LL（1）文法二：实验目的1．掌握LL(1)的判断，掌握求first和follow集合的算法2．熟悉运用C/C++语言对求first和follow集合进行实现三：实验原理设α＝x1x2…xn，FIRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，则xi∈FIRST（α）；（2）若xi∈VN；①若εFIRST（xi），则FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或i>n为止。

当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。

这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。

下面我们给出文法的FOLLOW集的定义。

设文法G[S]＝（VN，VT，P，S），则FOLLOW（A）＝{a | S …Aa …，a∈VT}。

若S …A，#∈FOLLOW（A）。

由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。

FOLLOW集可按下列方法求得：（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST （y），其中x，y∈V *，则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 first[max];//存放非终结符的first集string follow[max];//存放非终结符的follow集string select[max];//存放产生式的select集void apart(Chomsky *p,int i) //分开产生式左右部，i代表产生式的编号{int j;for(j=0;j<strings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);//从0开始的j长度的子串，即0~j-1p[i].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 (p[i].right[0]="#"&&p[i].right.length()==1)//直接推出空的{empty=empty+p[i].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(p[i].left)>=0)//若此非终结符已经存在直接推出空那里，在此无需重复计算{}else{for(j=0;j<(int)p[i].right.length();j++){if(is_empty(p).find(p[i].right.[j])<0){}}if(j==(int)p[i].right.length())//如果右部所有符号都在直接推出空那里，则此左部也可以推出空{s1=s1+p[i].left[0];}}}}*/void search(Chomsky *p,int n)//提取产生式中的非终结符{int i,j;for(i=0;i<n;i++){if(!(noend.find(p[i].left[0])>=0&&noend.find(p[i].left[0])<noend.length()))noend=noend+p[i].left;for(j=0;j<p[i].right.length();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z'){if(noend.find(p[i].right[j])>=0&&noend.find(p[i].right[j])<noend.length()) break;elsenoend=noend+p[i].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==p[i].left[0]){if('a'<=p[i].right[0]&&'z'>=p[i].right[0])first[mm]=first[mm]+p[i].right.substr(0,1);if(p[i].right[0]=='#')first[mm]=first[mm]+p[i].right.substr(0,1);if('A'<=p[i].right[0]&&'Z'>=p[i].right[0]){for(j=0;j<p[i].right.length();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z')flag++;}if(flag==j)//产生式的右部均为非终结符{flag=0;for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++)if(p[i].right[j]==p[x].left[0]&&p[x].right[0]=='#'){flag++;break;}}if(flag==j)//产生式右部的全部非终结符均能推出空{for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++){if(p[i].right[j]==noend[x])break;}y=x;if(first[y]=="")First(p,n,p[i].right[j],x);f=first[y];for(x=0;x<f.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}first[mm]=first[mm]+"#";}else{for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++){if(p[i].right[j]==noend[x])break;}y=x;if(first[y]=="")First(p,n,p[i].right[j],x);f=first[y];for(x=0;x<f.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+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<p[i].right.length();j++){if(noend[m]==p[i].right[j]){if(j<p[i].right.length()-1&&'a'<=p[i].right[j+1]&&p[i].right[j+1]<='z') follow[m]=follow[m]+p[i].right.substr(j+1,1);if(j<p[i].right.length()-1&&'A'<=p[i].right[j+1]&&p[i].right[j+1]<='Z') {for(y=0;y<noend.length();y++){if(noend[y]==p[i].right[j+1])break;}fo=first[y];for(x=0;x<first[y].length();x++){if(0<=first[y].find('#')&&first[y].find('#')<first[y].length())fo=first[y].substr(0,first[m].find('#'))+first[y].substr(first[y].find('#')+1);}follow[m]=follow[m]+fo;for(x=0;x<n;x++){if(p[i].right[j+1]==p[x].left[0]&&p[x].right[0]=='#')break;}if(x!=n)//非终结符后面的部分可以推出空{for(y=0;y<n;y++){if(p[i].left[0]==noend[y])break;}k=y;if(follow[k]=="")Follow(p,n,y);follow[m]=follow[m]+follow[k];}}if(j==p[i].right.length()-1){for(y=0;y<n;y++){if(p[i].left[0]==noend[y])break;}k=y;if(follow[k]=="")Follow(p,n,y);follow[m]=follow[m]+follow[k];}}}}}string erase(string s)//去First集及follow集中的重复字符{int i,j;for(i=0;i<s.length();i++){for(j=0;j<s.length();j++){if(i!=j&&s[i]==s[j])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<<"->"<<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=new Chomsky[n]; // 初始化产生式数组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(first[m]=="")First(p,n,noend[m],m);}cout<<"该文法非终结符的first集："<<endl;for(i=0;i<noend.length();i++){first[i]=erase(first[i]);cout<<noend[i]<<":"<<first[i]<<endl;}for(m=0;m<noend.length();m++){if(noend[m]==f)follow[m]=follow[m]+"#";if(follow[m]=="")Follow(p,n,m);}cout<<"该文法非终结符的follow集："<<endl;for(i=0;i<noend.length();i++){follow[i]=erase(follow[i]);cout<<noend[i]<<":"<<follow[i]<<endl;}cout<<"该文法的各产生式的select集："<<endl;for(i=0;i<n;i++){select[i]=erase(select[i]);cout<<p[i].left<<"->"<<p[i].right<<":"<<select[i]<<endl; }system("pause");}11 / 11。

/* LL(1)文法<古城童话>$为空字; 输入0，表示结束测试案例：案例1.(编译原理P76的LL(1)文法,E'改成了A,T'改成了B);E->TA A->+TA|$ T->FB B->*FB|$ F->(E)|i 0案例2. （First和Follow有非空交集）S->Ab A->a|B|$ B->b|$ 0*/#include <iostream>#include <string>using namespace std;const int MAX=100;int FirstNum=0,FollowNum=0; // First集合Follow集的数目string SaveStr[MAX]; //预存输入的字符串string TerStr="#"; //保存终结字符串int FlagError1=0; //左递归错误标志struct Assemble{int FlagLast,FlagFirst; //首尾标志int Position ; //字符串的位置char Data;Assemble *Next;};Assemble *First[MAX]; //定义Fist集Assemble *Follow[MAX]; //定义Follow集int IsNonterminal(char Cur) //判断是否为非终结符{if(Cur<='Z'&&Cur>='A')return 1;return 0;}int IsTerminal(char Cur) //判断是否为终结符{if(IsNonterminal(Cur)||Cur=='|')return 0;return 1 ;}int Exist(Assemble* L,char Cur,int Flag) //L的集合里面是否有Cur字符{ //Flag为1表示First，为0表示Followif(!L) return 0;Assemble *P;for(P=L->Next;P;P=P->Next)if(P->Data==Cur)return Flag ? P->Position:1 ;return 0;}int IsEmptyStr(char Cur) //字符串里面是否有${for(int i=0;i<FirstNum;i++)if(SaveStr[i][0]==Cur){ if(SaveStr[i].find('$')==-1)return 0;return 1;}}void HideSame(Assemble* &L) //消除相同的字符{Assemble *P,*Pa;for(P=L->Next;P->Next;P=P->Next)for(Pa=P->Next;Pa;Pa=Pa->Next)if(P->Data==Pa->Data) Pa->Data=3;}Assemble* FindAddFirst(char Cur) //查找要添加的First集{for(int i=FirstNum-1;i>=0;i--)if(First[i]->Data==Cur) return First[i];return NULL;}Assemble* FindAddFollow(char Cur) //查找要添加的Follow集{for(int i=0;i<FollowNum;i++)if(Follow[i]->Data==Cur) return Follow[i];return NULL;}void CreatFirst(Assemble* &L,string Str) //创建Firs集{Assemble *P=L,*Pa;int FlagLeft=0,Pos=3,j,i;L->FlagLast=0;for(i=3;Str[i];i++){int FlagGo=1,FlagLa=1;char Ch=L->Data;if(Ch==Str[3]||Str[i-1]=='|'&&Str[i]==Ch) FlagError1=1; //含有左递归while(i<Str.length()&&Str[i]!='|'){if(IsNonterminal(Str[i]))FlagGo=(IsEmptyStr(Str[i])? 1:0);Pa=new Assemble;Pa->Data=Str[i];Pa->Position=Pos;P->Next=Pa;P=Pa;if(!FlagGo||IsTerminal(Str[i])){ FlagLa=0; break; }i++;}if(!FlagLa)while(Str[i]&&Str[i]!='|')i++;else { L->FlagLast=1; }Pos=i+1;}P->Next=NULL;}void CreatFollow(string Str) //创建Follow集{int i,j,Num;for(i=3;Str[i];i++){Num=-1;if(IsNonterminal(Str[i])){ for(j=0;j<FollowNum;j++)if(Follow[j]->Data==Str[i]){ Num=j; break; }if(Num<0){Follow[FollowNum]= new Assemble;Follow[FollowNum]->Data=Str[i];Follow[FollowNum]->Next=NULL;Num=FollowNum++;}int FlagGo=0,FlagLa=0;Assemble *Pa,*Pb,*P=Follow[Num];for(j=i+1;Str[j]&&Str[j]!='|';j++){Pa=new Assemble;Pa->FlagLast=0;for(;P->Next;P=P->Next);FlagGo=Exist(FindAddFirst(Str[j]),'$',1)? 1:0;Pa->Data=Str[j];P->Next=Pa;Pa->Next=NULL;if(!FlagGo){ FlagLa=1; break; } //是否继续添加}if(!FlagLa) //非终结符位于末尾{for(;P->Next;P=P->Next);Pb=new Assemble;Pb->FlagLast=1;Pb->Data=Str[0];Pb->Next=P->Next;P->Next=Pb;}}}}void InitFollow(int Num) //初始化Follow集{for(int i=0;i<Num;i++){if(!i){Follow[FollowNum]=new Assemble;Follow[FollowNum]->Data=SaveStr[0][0];Follow[FollowNum]->Next=new Assemble;Follow[FollowNum]->Next->Data='#';Follow[FollowNum++]->Next->Next=NULL;}CreatFollow(SaveStr[i]);}}//增添Follow集,Num=1,增添First集，Num=0,增添Follow集void AddFollow(Assemble* &L, Assemble* Head,int Num){Assemble *Pa,*Pb,*Pc;for(Pc=Head->Next;Pc;Pc=Pc->Next){ for(Pa=L->Next;Pa;Pa=Pa->Next)if(Pa->Data==Pc->Data)break;if(!Pa){if(Pc->Data=='$'&&Num) continue;Pb=new Assemble;Pb->Data=Pc->Data;Pb->Next=L->Next;L->Next=Pb;}}}void GetFollow(Assemble* &L) //得到Follow集{Assemble *P,*Head;for(P=L->Next;P;P=P->Next)if(IsNonterminal(P->Data)){if(P->FlagLast) //位于末尾,增添Follow集{Head=FindAddFollow(P->Data);AddFollow(L,Head,0);}else //不位于末尾,增添First集{Head=FindAddFirst(P->Data);AddFollow(L,Head,1);}}}int GetFirst(Assemble* &L) //得到First集{Assemble *P,*Pa,*Pb,*Pc,*Head;for(P=L->Next;P;P=P->Next)if(IsNonterminal(P->Data)){Head=FindAddFirst(P->Data);if(!Head)return 0;for(Pc=Head->Next;Pc;Pc=Pc->Next)if(Pc->Data=='$'&&!L->FlagLast)continue;Pb=new Assemble;Pb->Data=Pc->Data;Pb->Position=P->Position;Pb->Next=L->Next;L->Next=Pb;}}}void KeepTerStr(string Str) //保存终结符{for(int i=3;Str[i];i++)if(IsTerminal(Str[i])&&Str[i]!='$'){if(TerStr.find(Str[i])==-1)TerStr+=Str[i];}}void ShowLL1(Assemble *L,int num)//输出LL(1)文法{Assemble *P=L,*Head;int i,npos;string Str=SaveStr[num];cout<<First[num]->Data<<"\t";for(i=0;TerStr[i];i++){if(npos=Exist(L,TerStr[i],1)){cout<<First[num]->Data<<"->";if(npos==1)npos=3;while(Str[npos]!='|'&&npos<Str.length()){cout<<Str[npos];npos++;}}else if(Exist(L,'$',0)){Head=FindAddFollow(First[num]->Data);if(Exist(Head,TerStr[i],0))cout<<First[num]->Data<<"->"<<"$";cout<<"____";}else cout<<"____";cout<<"\t ";}cout<<"\n\n";}int IsError2()//测试是否有左因子{string AddStr,Str;for(int i=0;i<FirstNum;i++){AddStr="";Str=SaveStr[i];for(int j=0;Str[j];j++)if(j==3||Str[j-1]=='|'){if(AddStr.find(Str[j])!=-1) return 1;AddStr+=Str[j];}}return 0;}Assemble* IsError3(char &Ch) //测试First和Follow是否有非交集{Assemble *P,*Pa,*Head;for(int i=0;i<FirstNum;i++){for(P=First[i]->Next;P;P=P->Next){Head=FindAddFollow(First[i]->Data);if(P->Data!='$'&&IsTerminal(P->Data)&&P->Data!=3)for(Pa=Head->Next;Pa;Pa=Pa->Next)if(Pa->Data==P->Data){ Ch=First[i]->Data; return P; }}}return NULL;}int ShowForm() //显示LL(1)文法的终结符{Assemble *P;char Cur;if(FlagError1){ cout<<"\n文法中含有左递归...!\n"; return 1; }if(IsError2()){ cout<<"\n文法中含有左因子...!\n"; return 1; }if(P=IsError3(Cur)){ printf("\n文法中First(%c)和Follow(%c)有非空交集%c...!\n",Cur,Cur,P->Data);return 1;}cout<<"\nLL(1)分析表:\n\n";for(int i=0;TerStr[i];i++)cout<<"\t "<<TerStr[i];cout<<endl;for(int i=0;i<FirstNum;i++)ShowLL1(First[i],i);}void GetFistrFollow(int Num){int i,j;FirstNum=Num;for(i=0;i<Num;i++){First[i]=new Assemble;First[i]->Data=SaveStr[i][0];CreatFirst(First[i],SaveStr[i]); //创建First集}for(j=0,i=FirstNum-1;i>=0;i--,j++) //得到First集{GetFirst(First[i]);GetFirst(First[j]);}InitFollow(Num); //初始化Follow集for(i=0;i<FollowNum;i++)GetFollow(Follow[i]); //得到Follow集}int main(){int i,j,Num=0;cout<<"请输入文法产生式(以输入0结束):\n";while(cin>>SaveStr[Num]&&SaveStr[Num][0]!='0') {KeepTerStr(SaveStr[Num]);Num++;}GetFistrFollow(Num); //获得First集合Follw集ShowForm(); //输出LL(1)文法表system("pause");}。

语法分析LL(1)设计报告——LCC1 问题描述设计一个由正规文法生成First集和Follow集并能输出测试字符串的预测分析过程。

(算法参见教材)【基本要求】模拟算法的基本功能是：（1）输入一个文法G；（2）消除左循环；（3）输出FIRST集；（4）输出FOLLOW集；（5）输出SELECT集合；（6）输出预测分析表；（7）输出预测分析过程。

2 详细设计2.1 数据结构2.1.1 终结符号： vector<CString>2.1.2 非终结符号： vector<CString>2.1.3 文法： vector<CString> 每条文法定义为一个CString2.1.4 First集合： vector<LEFT_GATHER> LEFT_GATHER{（非终结符），（vector）}2.1.5 Follow集合： vector<LEFT_GATHER> LEFT_GATHER{（非终结符），（vector）}2.1.6 Select集合： vector<LEFT_GATHER> LEFT_GATHER{（文法），（vector）}2.1.7 LEFT_GATHERtypedef struct LEFT_GATHER{CString start;vector<CString> end_gather;}LEFT_GATHER;2.2 算法思想2.2.1 判断文法合法性：满足条件：（1）左部以非终结符开始，并且只有一个（2）右部必须有非终结符，并且只能用零个或多个终结符和非终结符组成不合法情况（1）形如A->A（2）形如A->（已包括）2.2.2 消除左递归：1、消除直接左递归原文法: E --> E a1 | E a2 | ... | E an | b1 | b2 | ... | bn消除后: E --> b1 E' | b2 E' | ... | bn E'E'--> a1 E' | a2 E' | ... | an E' | epsilon2、消除间接左递归a) 把所有非终结符号按一定序列排序为E1, E2, ... En；b) for i=1 to n do /*依次处理每个非终结符号*/for j=1 to i-1 do /*处理第1个到i-1个*/若Ei --> Ej r则改为Ei --> S1 r | S2 r | ... | Sk r其中Ej --> S1 | S2 | ... | Skc) 对Ei消除直接左递归。

2016.11.30LL(1)文法的判断及转换目录一、实验名称 (2)二、实验目的 (2)三、实验原理 (2)1、First集定义 (2)2、Follow集定义 (2)3、Select集定义 (3)4、含左递归文法 (3)四、实验思路 (3)1、求非终结符是否能导出空 (3)2、求First集算法 (3)3、求Follow集算法 (3)4、求Select集算法 (4)五、实验小结 (4)六、附件 (4)1、源代码 (4)2、运行结果截图 (10)一、实验名称LL(1)文法的判断及转换二、实验目的输入：任意一个文法输出：(1)是否为LL(1)文法(2)若是，给出每条产生式的select集(3)若不是，看看是否含有左公共因子或者含有左递归，并用相应的方法将非LL(1)文法变成LL(1)文法，并输出新文法中每条产生式的select集。

三、实验原理1、First集定义令X为一个文法符号（终止符或非终止符）或ε，则集合First（X）有终止符组成，此外可能还有ε，它的定义如下：1.若X是终止符或ε，则First（X）={X}。

2.若X是非终结符，则对于每个产生式X—>X1X2…Xn，First（X）包含了First （X1）-{ε}。

若对于某个i<n，所有的集合First（X1），...，First（Xi）都包含了ε，则First（X）也包括了First（Xi+1）- {ε}。

若所有集合First（X1），...，First （Xn）都包括了ε，则First（X）也包括了ε。

2、Follow集定义给出一个非终结符A，那么集合Follow（A）则是由终结符组成，此外可能还含有#（#是题目约定的字符串结束符）。

集合Follow（A）的定义如下：1. 若A是开始符号，则#在Follow（A）中。

2. 若存在产生式B—>αAγ，则First（γ）- {ε}在Follow（A）中。

3. 若存在产生式B—>αAγ，且ε在First（γ）中，则Follow（A）包括Follow （B）。