编译原理实验报告FIRST集和FOLLOW集

编译原理实验报告姓名：叶玉虎班级：计122班指导老师：王森玉实验日期：2015/5/11实验内容：1.求出每个非终结符的FIRST集合2.求出每个产生式右部的FIRST集合3.求出每个非终结符的Follow集合实验环境：Visual Studio2010实验目的:让同学们掌握FIRST集合和FOLLOW集合的求法实验代码：#include<stdio.h>#include<string.h>#define MAX 50char css[MAX][MAX];//保存所有的产生式int count=0;int cnt=0;struct L{//保存所有的终结符char ch;int flag;//1:能推出ε,0:不能,初值:-1int num;char first[MAX];int s;//first的长度char follow[MAX];int l;//follow的长度}l[MAX];//对输入的格式进行控制,并校验输入是否符合格式int handle(char a[]){int len,i=0,j,k;len=strlen(a);while(a[i]!=10){if(a[i]=='$')return 2;if((' '==a[i])||(9==a[i])){i++;continue;}if((a[i]>='A')&&(a[i]<='Z')){if((a[i+1]!='-')||(a[i+2]!='>')){printf("产生式格式错误\n");return -1;}else{j=i;k=0;while((a[j]!=' ')&&(a[j]!=9)&&(a[j]!='$')&&(a[j]!=10)){if(a[j]=='|'){css[count][k]='\0';count++;if((a[j+1]=='')||(a[j]==9)||(a[j]=='$')||(a[j]==10)){printf("产生式格式错误\n");return 0;}css[count][0]=a[i];css[count][1]=a[i+1];css[count][2]=a[i+2];k=3;j++;continue;}css[count][k]=a[j];k++;j++;}css[count][k]='\0';i=j;count++;}}else{printf("产生式格式错误\n");return -1;}}return 0;}//从键盘获得输入int input(){char a[MAX*MAX];int v;printf("输入产生式,产生式之间以空格回车或Tab键分隔,并以$键结束.\n");printf("用@表示虚拟符号ε,终结符用大写字母表示,其他字符表示非终结符\n");while(1){fgets(a,MAX*MAX,stdin);v=handle(a);if(v==-1)return -1;if(v==2)return 0;}}//求出能推出ε的非终结符void seekEmpty(){int i,j,k,t;int flag=0,flag2=0;int len,c;char a[MAX][MAX],ch;for(i=0;i<count;i++){strcpy(a[i],css[i]);}//求出含有的非终结符的个数,并把各终结符保存起来for(i=0;i<count;i++){for(j=0;j<cnt;j++){if(l[j].ch==a[i][0]){l[j].num++;flag=1;break;}elseflag=0;}if((!cnt)||(!flag)){l[cnt].ch=a[i][0];l[cnt].flag=-1;l[cnt].num=1;l[cnt].s=0;l[cnt].l=0;cnt++;flag=1;continue;}}c=count;while(c){for(i=0;i<c;i++){//如果该终结符推出ε，从a[]中删除所有带有该终结符的产生式if(a[i][3]=='@'){ch=a[i][0];for(j=0;j<c;j++){if(ch==a[j][0]){if(j!=c-1){for(k=j;k<c-1;k++)strcpy(a[k],a[k+1]);c--;j--;}else{c--;j--;}}}for(j=0;j<cnt;j++){if(ch==l[j].ch){l[j].flag=1;break;}}i--;continue;}len=strlen(a[i]);for(j=3;j<len;j++){//当该产生式右边含有非终结符时从a[]中删除该条记录if((a[i][j]<'A')||(a[i][j]>'Z')){flag2=1;break;}}if(flag2){for(k=0;k<cnt;k++){if(a[i][0]==l[k].ch){l[k].num--;if(l[k].num==0)l[k].flag=0;break;}}if(i!=c-1)for(k=i;k<c-1;k++){strcpy(a[k],a[k+1]);}c--;i--;flag2=0;continue;}//如果产生式右边为非终结符看看该终结符能不能推出εfor(j=3;j<len;j++){if((a[i][j]>='A')&&(a[i][j]<='Z')){for(k=0;k<cnt;k++){if(a[i][j]==l[k].ch){if(l[k].flag==0){flag2=1;break;}else if(l[k].flag==1){for(t=j;t<len-1;t++)a[i][t]=a[i][t+1];a[i][len-1]='\0';j--;len--;break;}break;}}if(flag2)break;}}if(a[i][3]=='\0'){ch=a[i][0];for(j=0;j<c;j++){if(ch==a[j][0]){if(j!=c-1){for(k=j;k<c-1;k++)strcpy(a[k],a[k+1]);c--;j--;}else{c--;j--;}}}i--;for(k=0;k<cnt;k++){if(ch==l[k].ch){l[k].flag=1;break;}}}if(flag2){for(k=0;k<cnt;k++){if(a[i][0]==l[k].ch){l[k].num--;if(l[k].num==0)l[k].flag=0;}}if(i!=c-1)for(k=i;k<c-1;k++){strcpy(a[k],a[k+1]);}c--;i--;flag2=0;continue;}}}}//求每个非终结符的First集合void seekFirstVn(){int i,j,k,t,t1,t2,c,item;int len,s,flag=0,flag2=0,fchange;char a[MAX][MAX],ch[MAX];for(i=0;i<count;i++){strcpy(a[i],css[i]);}c=count;while(1){fchange=0;for(i=0;i<c;i++){//右部为ε,将ε并入到左部的First中if(a[i][3]=='@'){/*for(j=0;j<cnt;j++){if(l[j].ch==a[i][0]){for(k=0;k<l[j].s;k++)if(l[j].first[k]==a[i][3]){flag=1;break;}if(!flag){l[j].first[l[j].s]=a[i][3];l[j].s++;l[j].first[l[j].s]='\0';fchange=1;break;}flag=0;}}*///从当前列表a[]中删除if(i!=c-1)for(j=i;j<c-1;j++)strcpy(a[j],a[j+1]);c--;i--;continue;}len=strlen(a[i]);//产生式右边符号为终结符时,将该终结符并入到左部的First集合中for(j=3;j<len;j++){if((a[i][j]<'A')||(a[i][j]>'Z')){for(k=0;k<cnt;k++){if(a[i][0]==l[k].ch){for(t=0;t<l[k].s;t++){if(a[i][j]==l[k].first[t]){flag=1;break;}}if(!flag){l[k].first[l[k].s]=a[i][j];l[k].s++;l[k].first[l[k].s]='\0';fchange=1;}flag=0;break;}}//从a[][]中删除该条产生式if(i!=c-1)for(k=i;k<c-1;k++)strcpy(a[k],a[k+1]);c--;i--;break;}//产生式右边符号为非终结符时else if((a[i][j]>='A')&&(a[i][j]<='Z')){/*将该非终结符的FIRST集合除去ε并入到当前非终结符的FIRST集合中*/for(k=0;k<cnt;k++){if(a[i][j]==l[k].ch){for(t=0;t<cnt;t++){if(a[i][0]==l[t].ch){for(t1=0;t1<l[k].s;t1++){for(t2=0;t2<l[t].s;t2++){if(l[k].first[t1]==l[t].first[t2]){break;}}if((t2==l[t].s)&&(l[k].first[t1])!='@'){fchange=1;l[t].first[l[t].s]=l[k].first[t1];l[t].s++;l[t].first[l[t].s]='\0';}}break;}}break;}}if(l[k].flag)continue;elsebreak;}}}if(!fchange){for(i=0;i<cnt;i++){if(l[i].flag){l[i].first[l[i].s]='@';l[i].s++;l[i].first[l[i].s]='\0';}printf("FIRST(%c): %s\n",l[i].ch,l[i].first);}printf("\n");break;}}}//求产生式右部的First集合void seekFirstRight(){struct Right{char a[MAX];char first[MAX];int s;}r[MAX];int i,j,k,t;int cnt=0,len,len1,flag=0;for(i=0;i<count;i++){for(j=0;j<cnt;j++){if(!strcmp(css[i]+3,r[j].a)){flag=1;break;}}if(flag){flag=0;continue;}strcpy(r[j].a,css[i]+3);r[j].s=0;cnt++;}for(i=0;i<cnt;i++){len=strlen(r[i].a);for(j=0;j<len;j++){//遇到终结符if(r[i].a[j]=='@'){r[i].first[r[i].s]='@';r[i].s++;r[i].first[r[i].s]='\0';break;}else if((r[i].a[j]<'A')||(r[i].a[j]>'Z')){r[i].first[r[i].s]=r[i].a[j];r[i].s++;r[i].first[r[i].s]='\0';break;}else{for(k=0;k<cnt;k++){if(r[i].a[j]==l[k].ch){len1=strlen(l[k].first);for(t=0;t<len1;t++){if(l[k].first[t]!='@'){r[i].first[r[i].s]=l[k].first[t];r[i].s++;r[i].first[r[i].s]='\0';}}break;}}if(l[k].flag){if(j==len-1){r[i].first[r[i].s]='@';r[i].s++;r[i].first[r[i].s]='\0';}continue;}elsebreak;}}}for(i=0;i<cnt;i++){printf("FIRST(%s): %s\n",r[i].a,r[i].first);}printf("\n");}//求每个非终极符的Follow集合void seekFollow(){int i,j,k,t,t1,t2,t3,c=0;int flag=0,len;int fchange;//判断一次循环是否有改动的地方char a[MAX][MAX],ch[MAX];for(i=0;i<count;i++){len=strlen(css[i]);for(j=3;j<len;j++){if((css[i][j]>='A')&&(css[i][j]<='Z')){break;}}if(j!=len){strcpy(a[c],css[i]);c++;}}l[0].follow[l[0].l]='#';l[0].l++;l[0].follow[l[0].l]='\0';while(1){fchange=0;for(i=0;i<c;i++){len=strlen(a[i]);for(j=3;j<len;j++){if((a[i][j]>='A')&&(a[i][j]<='Z')){//判断该非终结符的前一位是否为非终结符,是的话,//将其First集合去ε后并到其前一位非终结符的Follow集合中if((a[i][j-1]>='A')&&(a[i][j-1]<='Z')){for(k=0;k<cnt;k++){if(a[i][j-1]==l[k].ch){for(t=0;t<cnt;t++){if(a[i][j]==l[t].ch){for(t1=0;t1<l[t].s;t1++){if(l[t].first[t1]=='@')continue;for(t2=0;t2<l[k].l;t2++)if(l[t].first[t1]==l[k].follow[t2])break;if(t2==l[k].l){fchange=1;l[k].follow[l[k].l]=l[t].first[t1];l[k].l++;l[k].follow[l[k].l]='\0';}}break;}}break;}}}//如果该非终结符是最后一位,//将该产生式左部非终结符的Follow集合//加入到当前非终结符的Follow集合中.//然后从当前终结符开始向右判断是否为非终结符，是的话,进行相应处理//循环直到当前非终结符推不出ε或当前为终结符时退出if(j==len-1){t3=j;strcpy(ch,a[i]);while(!flag){if((ch[t3]>='A')&&(ch[t3]<='Z')){for(k=0;k<cnt;k++){if(ch[0]==l[k].ch){for(t=0;t<cnt;t++){if(ch[t3]==l[t].ch){for(t1=0;t1<l[k].l;t1++){for(t2=0;t2<l[t].l;t2++)if(l[k].follow[t1]==l[t].follow[t2])break;if(t2!=l[t].l)continue;else{fchange=1;l[t].follow[l[t].l]=l[k].follow[t1];l[t].l++;l[t].follow[l[t].l]='\0';}}if(l[t].flag)ch[t3--]='\0';else{flag=1;t3--;}break;}}break;}}}elsebreak;}flag=0;}}//如果当前位为终结符，判断其前一位是否为非终结符//是的话,将该终结符并到该非终结符的Follow集合中else{if((a[i][j-1]>='A')&&(a[i][j-1]<='Z')){for(k=0;k<cnt;k++){if(a[i][j-1]==l[k].ch){for(t=0;t<l[k].l;t++)if(a[i][j]==l[k].follow[t])break;if(t==l[k].l){fchange=1;l[k].follow[l[k].l]=a[i][j];l[k].l++;l[k].follow[l[k].l]='\0';}}}}}}}if(!fchange){for(i=0;i<cnt;i++)printf("FOLLOW(%c): %s\n",l[i].ch,l[i].follow);break;}}}int main(){int i;if(input()==-1)return -1;seekEmpty();seekFirstVn();seekFirstRight();seekFollow();return 0;}实验演示：因为不知道怎么用电脑输出’ε’符号，我在代码里用’@’来表示‘ε’.以‘$’来结束输入测试数据1：S->MH|aH->LSo|@K->dML|@L->eHfM->K|bLM测试数据2：S->aHH->aMd|dM->Ab|@A->aM|e实验感想：经过这几次的实验，不仅让我们更加深刻的知道了first集合和follow集合的计算步骤和方法，还很好的培养了我们动手能力。

for(i=0;i<s1.size();i++)
{
cout<<s1[i]<<" "<<follow(s1[i])<<endl;
}
return 0;
}
四．实验截图
}
}
}
}
}
return s;
}
//******************************
int main()
{
int i;
string s1,s2;
char b;
cout<<"\t************求First集和Follow集**************"<<endl;
cout<<"请输入产生式的数目：";
}
else
{
rights=p[pos.front()].right;
for(i=0;i<rights.size();i++)
{
if(find(rights[i]))
{
s+=first(rights[i]);
index= s.find_last_of('@');
s=s.erase(index,1);
}
编译原理实验
实验名称：求first集和follow集
姓名：
学号：
教师签字：
成绩：
一．实验目的：
.掌握和了解first集和follow集的求解过程。
二．实验原理：
1.first集的求解：（1）若X∈Vt,则FIRST(X)={X};
(2)若X∈Vn,且有产生式X->a……,a∈Vt，则a∈FIRST(X);

【编译原理】语法分析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个以空格分隔的字符串为产⽣式体。

char left[50];
/* 左部 */
char right[50][50];
/* 右部 */
char first[50][50],follow[50][50];
/* 各产生式右部的 FIRST 和左部的 FOLLOW 集合 */
char first1[50][50];
/* 所有单个符号的 FIRST 集合 */
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)
}
/*******************************************
将单个符号或符号串并入另一符号串 ********************************************/
void merge(char *d,char *s,int type)
{
/*d 是目标符号串， s 是源串， type＝1，源串中的‘ ^ ’一并并入目串；
int count=0;
/* 分解的产生式的个数 */
int number;
/* 所有终结符和非终结符的总数 */
char start;
/* 开始符号 */
char termin[50];
/* 终结符号 */
char non_ter[50];

华东交通大学课程设计（论文）任务书软件学院专业项目管理班级2005－4一、课程设计（论文）题目正规文法的First集合Follow集求解过程动态模拟二、课程设计（论文）工作：自2008年6月23 日起至2008年 6 月27 日止。

三、课程设计（论文）的内容要求：1、基本要求：进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC 6.0 或其它软件编程工具。

为了使学生从课程设计中尽可能取得比较大的收获，对课程设计题目可根据自己的兴趣选题（须经老师审核），或从老师给定题目中选择完成（具体见编译原理课程设计题目要求）。

通过程序实现、总结报告和学习态度综合考评，并结合学生的动手能力，独立分析解决问题的能力和创新精神。

成绩分优、良、中、及格和不及格五等。

2、具体要求设计一个由正规文法生成Fisrt集Follow集的动态过程模拟动态模拟算法的基本功能是：●输入一个正规文法；●输出由文法构造的First集的算法；●输出First集；●输出由文法构造的Follow集的算法；●输出Follow集；学生签名：2008 年 6 月 27 日课程设计（论文）评阅意见评阅人职称副教授2008 年 6 月 27 日目录一、需求分析 (3)二、总体设计 (4)三、详细设计 (9)四、课设小结 (12)五、谢辞 (13)六、参考文献 (14)一、 需求分析问题描述设计一个由正规文法生成First 集和Follow 集并进行简化的算法动态模拟。

(算法参见教材) 【基本要求】动态模拟算法的基本功能是： （1） 输入一个文法G ；（2） 输出由文法G 构造FIRST 集的算法； （3） 输出First 集；（4） 输出由文法G 构造FOLLOW 集的算法； （5） 输出FOLLOW 集。

专题3_LL(1)语法分析设计原理与实现李若森 13281132 计科1301一、理论传授语法分析的设计方法和实现原理；LL(1) 分析表的构造；LL(1)分析过程；LL(1)分析器的构造。

二、目标任务实验项目实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的 LL(1)文法的LL(1)分析程序。

G[E]:E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→(E)|iA→+|-M→*|/设计说明终结符号i为用户定义的简单变量，即标识符的定义。

加减乘除即运算符。

设计要求(1)输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；(2)LL(1)分析程序应能发现输入串出错；(3)设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。

任务分析重点解决LL(1)表的构造和LL(1)分析器的实现。

三、实现过程实现LL(1)分析器a)将#号放在输入串S的尾部b)S中字符顺序入栈c)反复执行c)，任何时候按栈顶Xm和输入ai依据分析表，执行下述三个动作之一。

构造LL(1)分析表构造LL(1)分析表需要得到文法G[E]的FIRST集和FOLLOW集。

构造FIRST(α)构造FOLLOW(A)构造LL(1)分析表算法根据上述算法可得G[E]的LL(1)分析表，如表3-1所示：表3-1 LL(1)分析表主要数据结构pair<int, string>:用pair<int, string>来存储单个二元组。

该对照表由专题1定义。

map<string, int>:存储离散化后的终结符和非终结符。

vector<string>[][]:存储LL(1)分析表函数定义init:void init();功能：初始化LL(1)分析表，关键字及识别码对照表，离散化（非）终结符传入参数：（无）传出参数：（无）返回值：（无）Parse:bool Parse( const vector<PIS> &vec, int &ncol )；功能：进行该行的语法分析传入参数：vec:该行二元式序列传出参数：emsg:出错信息epos:出错标识符首字符所在位置返回值：是否成功解析。

First集合的求法：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。

1. 直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中2. 反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。

Follow集合的求法：Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。

1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。

2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)除ε直接收入到Follow(U)中。

3．反复传送：对形如P－…U的产生式（其中U是非终结符），应把Follow(P)中的全部内容传送到Follow(U)中。

(或 P－…UB且First(B)包含ε，则把First(B)除ε直接收入到Follow(U)中，并把Follow(P)中的全部内容传送到Follow(U)中)例1：判断该文法是不是LL(1)文法，说明理由 S→ABc A→a|ε B→b|ε？First集合求法就是：能由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。

如此题A可以推导出a和ε，所以FIRST（A）=｛a，ε｝；同理FIRST （B）={b,ε};S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=｛a，b，c｝。

Follow集合的求法是：紧跟随其后面的终结符号或＃。

但文法的识别符号包含＃，在求的时候还要考虑到ε。

具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。

}
}
for(set<char>::iterator iter=ter.begin(); iter!=ter.end(); iter++) {
flag = false;
cout<<*iter<<" FIRST集:";
fir.clear();
getFirst(*iter, fir);
for(set<char>::iterator iterF=fir.begin(); iterF!=fir.end(); iterF++) {
vector<string> rightSide; //右部
char Begin;
bool capL(char c) //字母是否大写
{
if(c<='Z' && c>='A')
return true;
return false;
}
bool CapLString(string s) //大写字符串
{
for(int i=0; i<s.size(); i++) {
if(!capL(s[i])) {
return false;
}
}
return true;
}
bool isToEmpty(char ch) //判断终结符能否推出空
{
bool flag;
flag = false;
multimap<char, string>::iterator mIter = sentence.find(ch);
if(s[j]==ch) {//有左递归,跳出循环

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）。

摘要：编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。

由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。

本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。

我们这次课程设计的主要任务是编程实现对给定文法的FIRST 集和FOLLOW集的求解。

通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。

同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。

关键词：编译原理；FIRST集；FOLLOW集目录1 课题综述 (1)1.1 课题来源 (1)1.2 课题意义 (1)1.3 预期目标 (1)1.4 面对的问题 (1)1.5 需解决的关键技术 (1)2 系统分析 (2)2.1 基础知识 (2)2.1.1 FIRST集定义 (2)2.1.2FIRST集求解算法.................................................................... 错误!未定义书签。

2.1.3FOLLOW集的定义 (4)2.1.4 FOLLOW集算法 (4)2.2 解决问题的基本思路 (4)2.3 总体方案 (4)3 系统设计 (5)3.1 算法实现 (5)3.2 流程图 (6)4 代码编写 (10)5 程序调试 (15)6 运行与测试 (15)1 课题综述1.1 课题来源文法：包含若干终结符，非终结符，由终结符与非终结符组成的产生式。

本次课程设计就是对产生式进行左递归分析，待无左递归现象后进行FIRST集与FOLLOW集的求解。

1.2 课题意义由文法产生的若干个句子有可能是合法的或者不合法的，也有可能产生歧义，所以要消除歧义先消除文法左递归，然后根据求得的FIRST集与FOLLOW 集构造分析表，分析给定句子的合法性。

《编译原理》实验报告
专业班级：计101班
学号：109074002
姓名：卞恩会
指导老师：王森玉
实验内容：
1.求出每个非终结符的FIRST集合
2.求出每个产生式右部的FIRST集合
3.求出每个非终结符的Follow集合实验环境：
Visual Studio2010
实验目的:
掌握FIRST集合和FOLLOW集合的求法
测试数据1：
S->aH
H->aMd|d
M->Ab|@
A->aM|e
输出结果：
测试数据2：S->AB
S->bC
A->@
A->b
B->@
B->aD
C->AD
C->b
D->aS
D->c
测试数据3：E->TX
X->+TX|@ T->FY
Y->*FY|@ F->i|(E)
输出结果：
感受：通过上机调试代码让我对书上的单纯的理论的知识有了一个更深的理解同时让我明白了对待一个问题我们应该全面的去理解它，这样才能学到的更多。

程序清单：。

LL(1)语法分析一，实验名称：实现LL分析。

二，实验要求：➢输入任意文法➢消除左递归➢消除左因子➢测试任意输入语句是否合法➢数据结构描述➢算法说明➢输出first集合➢输出follow集合➢输出LL(1)表三．设计原理及算法描述所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。

实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。

一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。

当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。

LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。

对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X = a =‘#’，则宣布分析成功，停止分析过程。

（２）若X = a ‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。

（３）若X是一个非终结符，则查看预测分析表M。

若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK 栈顶，然后，把产生式的右部符号串按反序一一弹出STACK 栈（若右部符号为ε，则不推什么东西进STACK栈）。

若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。

事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。

♨自上而下语法分析 Top-Down Parsing
G1: S → pA |qB A → a | cA B → b | dB 输入串 pca G2: S → Ap | Bq A → a | cA B → b | dB 输入串 cap
FIRST 集
FIRST集 / 开始符号集 / 终结首符集
* a…, a∈VT} FIRST(α) = {a|α * ε, 则规定 ε∈FIRST(α) 若α
G: S→ AB A→aA |ε B→bA |ε
自上而下语法分析面临的问题
G: S → cAd A → a|ab 输入串 cabd

－ 回溯 Backtrack S
c A d
S
c A d a b
a A→ α1 |α2 |…|αn 如何决定用哪个候选式替换A? 不确定分析: 带回溯 (试探) 确定分析 : 不带回溯
练习: 求 First 集
G: S → ABC A → aA |ε B → bB |b C → cC |c First(S) = { a, b }
First(A) = { a, ε }
First(B) = { b}
First(C) = { c}
例: 自上而下语法分析
G5: E → TE' E'→ +TE'|ε T → FT' T'→ *FT'|ε F → (E) | i 输入串 i＋i
Select 集
SELECT集 选择集合
给定上下文无关文法的产生式A→α, * ε， • 若α SELECT(A→α) = FIRST(α) * ε， • 若α SELECT(A→α) = (FIRST(α)－{ε})∪FOLLOW(A)

《LL（1）分析器的构造》实验报告一、实验名称LL(1)分析器的构造二、实验目的设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。

三、实验内容和要求设计并实现一个LL(1)语法分析器，实现对算术文法:G[E]:E->E+T|TT->T*F|FF->(E)|i所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。

实验要求:1、检测左递归，如果有则进行消除；2、求解FIRST集和FOLLOW集；3、构建LL(1)分析表；4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。

四、主要仪器设备硬件：微型计算机。

软件：Code blocks（也可以是其它集成开发环境）。

五、实验过程描述1、程序主要框架程序中编写了以下函数，各个函数实现的作用如下：void input_grammer(string *G);//输入文法Gvoid preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k);//将文法G预处理得到产生式集合P，非终结符、终结符集合U、u，int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GGint* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表void analyse(string **table,string U,string u,int t,string s)；//分析符号串s2、编写的源程序#include<cstdio>#include<cstring>#include<iostream>using namespace std;void input_grammer(string *G)//输入文法G,n个非终结符{int i=0;//计数char ch='y';while(ch=='y'){cin>>G[i++];cout<<"继续输入?(y/n)\n";cin>>ch;}}void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)//将文法G预处理产生式集合P，非终结符、终结符集合U、u，{int i,j,r,temp;//计数char C;//记录规则中（）后的符号int flag;//检测到（）n=t=k=0;for( i=0;i<50;i++) P[i]=" ";//字符串如果不初始化，在使用P[i][j]=a时将不能改变，可以用P[i].append(1,a)U=u=" ";//字符串如果不初始化，无法使用U[i]=a赋值，可以用U.append(1,a)for(n=0;!G[n].empty();n++){ U[n]=G[n][0];}//非终结符集合，n为非终结符个数for(i=0;i<n;i++){for(j=4;j<G[i].length();j++){if(U.find(G[i][j])==string::npos&&u.find(G[i][j])==string::npos) if(G[i][j]!='|'&&G[i][j]!='^')//if(G[i][j]!='('&&G[i][j]!=')'&&G[i][j]!='|'&&G[i][j]!='^')u[t++]=G[i][j];}}//终结符集合，t为终结符个数for(i=0;i<n;i++){flag=0;r=4;for(j=4;j<G[i].length();j++){P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';/* if(G[i][j]=='('){ j++;flag=1;for(temp=j;G[i][temp]!=')';temp++);C=G[i][temp+1];//C记录（）后跟的字符，将C添加到（）中所有字符串后面}if(G[i][j]==')') {j++;flag=0;}*/if(G[i][j]=='|'){//if(flag==1) P[k][r++]=C;k++;j++;P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';r=4;P[k][r++]=G[i][j];}else{P[k][r++]=G[i][j];}}k++;}//获得产生式集合P，k为产生式个数}int eliminate_1(string *G,string *P,string U,string *GG)//消除文法G1中所有直接左递归得到文法G2，要能够消除含有多个左递归的情况）{string arfa,beta;//所有形如A::=Aα|β中的α、β连接起来形成的字符串arfa、betaint i,j,temp,m=0;//计数int flag=0;//flag=1表示文法有左递归int flagg=0;//flagg=1表示某条规则有左递归char C='A';//由于消除左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入for(i=0;i<20&&U[i]!=' ';i++){ flagg=0;arfa=beta="";for(j=0;j<100&&P[j][0]!=' ';j++){if(P[j][0]==U[i]){if(P[j][4]==U[i])//产生式j有左递归{flagg=1;for(temp=5;P[j][temp]!=' ';temp++) arfa.append(1,P[j][temp]);if(P[j+1][4]==U[i]) arfa.append("|");//不止一个产生式含有左递归}else{for(temp=4;P[j][temp]!=' ';temp++) beta.append(1,P[j][temp]);if(P[j+1][0]==U[i]&&P[j+1][4]!=U[i]) beta.append("|");}}}if(flagg==0)//对于不含左递归的文法规则不重写{GG[m]=G[i]; m++;}else{flag=1;//文法存在左递归GG[m].append(1,U[i]);GG[m].append("::=");if(beta.find('|')!=string::npos) GG[m].append("("+beta+")");else GG[m].append(beta);while(U.find(C)!=string::npos){C++;}GG[m].append(1,C);m++;GG[m].append(1,C);GG[m].append("::=");if(arfa.find('|')!=string::npos) GG[m].append("("+arfa+")");else GG[m].append(arfa);GG[m].append(1,C);GG[m].append("|^");m++;C++;}//A::=Aα|β改写成A::=βA‘，A’=αA'|β，}return flag;}int* ifempty(string* P,string U,int k,int n){int* empty=new int [n];//指示非终结符能否推导到空串int i,j,r;for(r=0;r<n;r++) empty[r]=0;//默认所有非终结符都不能推导到空int flag=1;//1表示empty数组有修改int step=100;//假设一条规则最大推导步数为100步while(step--){for(i=0;i<k;i++){r=U.find(P[i][0]);if(P[i][4]=='^') empty[r]=1;//直接推导到空else{for(j=4;P[i][j]!=' ';j++){if(U.find(P[i][j])!=string::npos){if(empty[U.find(P[i][j])]==0) break;}else break;}if(P[i][j]==' ') empty[r]=1;//多步推导到空else flag=0;}}}return empty;}string* FIRST_X(string* P,string U,string u,int* empty,int k,int n) {int i,j,r,s,tmp;string* first=new string[n];char a;int step=100;//最大推导步数while(step--){// cout<<"step"<<100-step<<endl;for(i=0;i<k;i++){//cout<<P[i]<<endl;r=U.find(P[i][0]);if(P[i][4]=='^'&&first[r].find('^')==string::npos) first[r].append(1,'^');//规则右部首符号为空else{for(j=4;P[i][j]!=' ';j++){a=P[i][j];if(u.find(a)!=string::npos&&first[r].find(a)==string::npos)//规则右部首符号是终结符{first[r].append(1,a);break;//添加并结束}if(U.find(P[i][j])!=string::npos)//规则右部首符号是非终结符,形如X：：=Y1Y2...Yk{s=U.find(P[i][j]);//cout<<P[i][j]<<":\n";for(tmp=0;first[s][tmp]!='\0';tmp++){a=first[s][tmp];if(a!='^'&&first[r].find(a)==string::npos)//将FIRST[Y1]中的非空符加入first[r].append(1,a);}}if(!empty[s]) break;//若Y1不能推导到空，结束}if(P[i][j]==' ')if(first[r].find('^')==string::npos)first[r].append(1,'^');//若Y1、Y2...Yk都能推导到空，则加入空符号}}}return first;}string FIRST(string U,string u,string* first,string s)//求符号串s=X1X2...Xn的FIRST集{int i,j,r;char a;string fir;for(i=0;i<s.length();i++){if(s[i]=='^') fir.append(1,'^');if(u.find(s[i])!=string::npos&&fir.find(s[i])==string::npos){ fir.append(1,s[i]);break;}//X1是终结符，添加并结束循环if(U.find(s[i])!=string::npos)//X1是非终结符{r=U.find(s[i]);for(j=0;first[r][j]!='\0';j++){a=first[r][j];if(a!='^'&&fir.find(a)==string::npos)//将FIRST(X1)中的非空符号加入fir.append(1,a);}if(first[r].find('^')==string::npos) break;//若X1不可推导到空，循环停止}if(i==s.length())//若X1-Xk都可推导到空if(fir.find(s[i])==string::npos) //fir中还未加入空符号fir.append(1,'^');}return fir;}string** create_table(string *P,string U,string u,int n,int t,int k,string* first)//构造分析表，P为文法G的产生式构成的集合{int i,j,p,q;string arfa;//记录规则右部string fir,follow;string FOLLOW[5]={")#",")#","+)#","+)#","+*)#"};string **table=new string*[n];for(i=0;i<n;i++) table[i]=new string[t+1];for(i=0;i<n;i++)for(j=0;j<t+1;j++)table[i][j]=" ";//table存储分析表的元素，“ ”表示error for(i=0;i<k;i++){arfa=P[i];arfa.erase(0,4);//删除前4个字符，如：E::=E+T,则arfa="E+T"fir=FIRST(U,u,first,arfa);for(j=0;j<t;j++){p=U.find(P[i][0]);if(fir.find(u[j])!=string::npos){q=j;table[p][q]=P[i];}//对first（）中的每一终结符置相应的规则}if(fir.find('^')!=string::npos){follow=FOLLOW[p];//对规则左部求follow()for(j=0;j<t;j++){if((q=follow.find(u[j]))!=string::npos){q=j;table[p][q]=P[i];}//对follow（）中的每一终结符置相应的规则}table[p][t]=P[i];//对#所在元素置相应规则}}return table;}void analyse(string **table,string U,string u,int t,string s)//分析符号串s {string stack;//分析栈string ss=s;//记录原符号串char x;//栈顶符号char a;//下一个要输入的字符int flag=0;//匹配成功标志int i=0,j=0,step=1;//符号栈计数、输入串计数、步骤数int p,q,r;string temp;for(i=0;!s[i];i++){if(u.find(s[i])==string::npos)//出现非法的符号cout<<s<<"不是该文法的句子\n";return;}s.append(1,'#');stack.append(1,'#');//’#’进入分析栈stack.append(1,U[0]);i++;//文法开始符进入分析栈a=s[0];//cout<<stack<<endl;cout<<"步骤分析栈余留输入串所用产生式\n";while(!flag){// cout<<"步骤分析栈余留输入串所用产生式\n"cout<<step<<" "<<stack<<" "<<s<<" ";x=stack[i];stack.erase(i,1);i--;//取栈顶符号x,并从栈顶退出//cout<<x<<endl;if(u.find(x)!=string::npos)//x是终结符的情况{if(x==a){s.erase(0,1);a=s[0];//栈顶符号与当前输入符号匹配，则输入下一个符号cout<<" \n";//未使用产生式，输出空}else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}if(x=='#'){if(a=='#') {flag=1;cout<<"成功\n";}//栈顶和余留输入串都为#，匹配成功else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}if(U.find(x)!=string::npos)//x是非终结符的情况{p=U.find(x);q=u.find(a);if(a=='#') q=t;temp=table[p][q];cout<<temp<<endl;//输出使用的产生式if(temp[0]!=' ')//分析表中对应项不为error{r=9;while(temp[r]==' ') r--;while(r>3){if(temp[r]!='^'){stack.append(1,temp[r]);//将X::=x1x2...的规则右部各符号压栈i++;}r--;}}else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}step++;}if(flag) cout<<endl<<ss<<"是该文法的句子\n"; }int main(){int i,j;string *G=new string[50];//文法Gstring *P=new string[50];//产生式集合Pstring U,u;//文法G非终结符集合U，终结符集合uint n,t,k;//非终结符、终结符个数,产生式数string *GG=new string[50];//消除左递归后的文法GGstring *PP=new string[50];//文法GG的产生式集合PPstring UU,uu;//文法GG非终结符集合U，终结符集合uint nn,tt,kk;//消除左递归后的非终结符、终结符个数,产生式数string** table;//分析表cout<<" 欢迎使用LL(1)语法分析器!\n\n\n";cout<<"请输入文法（同一左部的规则在同一行输入，例如：E::=E+T|T；用^表示空串）\n"; input_grammer(G);preprocess(G,P,U,u,n,t,k);cout<<"\n该文法有"<<n<<"个非终结符：\n";for(i=0;i<n;i++) cout<<U[i];cout<<endl;cout<<"该文法有"<<t<<"个终结符：\n";for(i=0;i<t;i++) cout<<u[i];cout<<"\n\n 左递归检测与消除\n\n";if(eliminate_1(G,P,U,GG)){preprocess(GG,PP,UU,uu,nn,tt,kk);cout<<"该文法存在左递归！\n\n消除左递归后的文法:\n\n";for(i=0;i<nn;i++) cout<<GG[i]<<endl;cout<<endl;cout<<"新文法有"<<nn<<"个非终结符：\n";for(i=0;i<nn;i++) cout<<UU[i];cout<<endl;cout<<"新文法有"<<tt<<"个终结符：\n";for(i=0;i<tt;i++) cout<<uu[i];cout<<endl;//cout<<"新文法有"<<kk<<"个产生式：\n";//for(i=0;i<kk;i++) cout<<PP[i]<<endl;}else{cout<<"该文法不存在左递归\n";GG=G;PP=P;UU=U;uu=u;nn=n;tt=t;kk=k;}cout<<" 求解FIRST集\n\n";int *empty=ifempty(PP,UU,kk,nn);string* first=FIRST_X(PP,UU,uu,empty,kk,nn);for(i=0;i<nn;i++)cout<<"FIRST("<<UU[i]<<"): "<<first[i]<<endl;cout<<" 求解FOLLOW集\n\n";for(i=0;i<nn;i++)cout<<"FOLLOW("<<UU[i]<<"): "<<FOLLOW[i]<<endl; cout<<"\n\n 构造文法分析表\n\n";table=create_table(PP,UU,uu,nn,tt,kk,first);cout<<" ";for(i=0;i<tt;i++) cout<<" "<<uu[i]<<" ";cout<<"# "<<endl;for( i=0;i<nn;i++){cout<<UU[i]<<" ";for(j=0;j<t+1;j++)cout<<table[i][j];cout<<endl;}cout<<"\n\n 分析符号串\n\n";string s;cout<<"请输入要分析的符号串\n";cin>>s;analyse(table,UU,uu,tt,s);return 0;}3、程序演示结果（1）输入文法（2）消除左递归（3）求解FIRST和FOLLOW集（4）构造分析表（5）分析符号串匹配成功的情况：匹配失败的情况五、思考和体会1、编写的LL(1)语法分析器应该具有智能性，可以由用户输入任意文法，不需要指定终结符个数和非终结符个数。

【编译原理】FIRST集、FOLLOW集算法原理和实现书中⼀些话，不知是翻译的原因。

还是我个⼈理解的原因感觉不是⾮常好理解。

个⼈重新整理了⼀下。

不过相对于消除左递归和提取左公因,FIRST集和FOLLOW集的算法相对来说⽐较简单。

书中的重点给出:FIRST:⼀个⽂法符号的FIRST集就是这个符号能推导出的第⼀个终结符号的集合, 包括空串。

例: A -> abc | def | ε那么FIRST(A) 等于 { a, d, ε }。

FOLLOW：蓝线画的部分很重要。

特别是这句话：请注意，在这个推导的某个阶段，A和a之间可能存在⼀些⽂法符号。

单如果这样，这些符号会推导得到ε并消失。

这句话的意思就是好⽐说： S->ABa B->c | ε 这个⽂法 FOLLOW(A)的值应该是FIRST(B)所有的终结符的集合（不包含ε），但是FIRST(B)是包含ε的，说明B是可空的，既然B是可空的S->ABa 也可以看成 S->Aa。

那么a就可以跟在A的后⾯.所以在这种情况下，FOLLOW(A)的值是包含a的。

换句话说就是。

⼀个⽂法符号A的FOLLOW集合就是它的下⼀个⽂法符号B的FIRST集合。

如果下⼀个⽂法符号B的FIRST集合包含ε，那么我们就要获取下⼀个⽂法符号B的FOLLOW集添加到FOLLOW(A)中代码中的注释已经很详细// 提取First集合func First(cfg []*Production, sym *Symbolic) map[string] *Symbolic {result := make(map[string] *Symbolic)// 规则⼀如果符号是⼀个终结符号，那么他的FIRST集合就是它⾃⾝if sym.SymType() == SYM_TYPE_TERMINAL || sym.SymType() == SYM_TYPE_NIL {result[sym.Sym()] = symreturn result}// 规则⼆如果⼀个符号是⼀个⾮终结符号// (1) A -> XYZ 如果 X 可以推导出nil 那么就去查看Y是否可以推导出nil// 如果 Y 推导不出nil，那么把Y的First集合加⼊到A的First集合// 如果 Y 不能推导出nil，那么继续推导 Z 是否可以推导出nil,依次类推// (2) A -> XYZ 如果XYZ 都可以推导出 nil, 那么说明A这个产⽣式有可能就是nil，这个时候我们就把nil加⼊到FIRST(A)中for _, production := range cfg {if production.header == sym.Sym() {nilCount := 0for _, rightSymbolic := range production.body { // 对于⼀个产⽣式ret := First(cfg, rightSymbolic) // 获取这个产⽣式体的First集合hasNil := falsefor k, v := range ret {if v.SymType() == SYM_TYPE_NIL { // 如果推导出nil, 标识当前产⽣式体的符号可以推导出nilhasNil = true} else {result[k] = v}}if false == hasNil { // 当前符号不能推导出nil, 那么这个产⽣式的FIRST就计算结束了，开始计算下⼀个产⽣式break}// 当前符号可以推导出nil，那么开始推导下⼀个符号nilCount++if nilCount == len(production.body) { // 如果产⽣式体都可以推导出nil，那么这个产⽣式就可以推导出nilresult["@"] = &Symbolic{sym: "@", sym_type: SYM_TYPE_NIL}}}}}return result}// 提取FOLLOW集合func Follow(cfg []*Production, sym string) [] *Symbolic {fmt.Printf("Follow ------> %s\n", sym)result := make([] *Symbolic, 0)// ⼀个⽂法符号的FOLLOW集就是可能出现在这个⽂法符号后⾯的终结符// ⽐如 S->ABaD, 那么FOLLOW(B)的值就是a。

#include<iostream>#include"string.h"#define MAX 100using namespace std;//产生式结构体struct product{int rl;char l,r[20];}p[100];//first 和follow 集struct set{int n;//元素数量char elm[100];}first[MAX],follow[MAX];int table[MAX][MAX];//预测分析表char v[100],t[100];//变量和终结符int n,vnum,tnum;//产生式数量,变量数量和终结符数量//判断是否为终结符inline bool isterminal(char x){if(x>='A'&&x<='Z')return false;return true;}//判断符号x是否从未出现过bool ex(char x){int i;if(isterminal(x)){for(i=1;i<=tnum;i++)if(t[i]==x) return true;return false;}for(i=1;i<=vnum;i++)if(v[i]==x) return true;return false;}//读入文法void load(){int i,j,k;char tmp[25];//printf("输入产生式的数量："); scanf("%d",&n);for(vnum=tnum=0,i=1;i<=n;i++) {scanf("%s",tmp);p[i].l=tmp[0];if(!ex(tmp[0])) v[++vnum]=tmp[0]; for(k=0,j=3;tmp[j];j++){p[i].r[k++]=tmp[j];if(isterminal(tmp[j])){if(!ex(tmp[j]))t[++tnum]=tmp[j];}else if(!ex(tmp[j]))v[++vnum]=tmp[j];}p[i].r[k]=0,p[i].rl=k-1;}t[++tnum]=v[++vnum]='#';}//输出用户输入的文法void show(){int i;for(i=1;i<=n;i++)printf("%c->%s\n",p[i].l,p[i].r);}//把符号x变为对应的编号int cid(char x){int i;if(!isterminal(x)){for(i=1;i<=vnum;i++)if(v[i]==x) return i;}for(i=1;i<=tnum;i++)if(t[i]==x) return i+1000;return -1;}//判断集合st里面是否包含符号idtbool inclu(struct set &st,char idt){int i;for(i=1;i<=st.n;i++)if(st.elm[i]==idt)return true;return false;}//把符号e添加到集合st里面inline void add(struct set &st,char e){st.n++;st.elm[st.n]=e;}//求first集void makefirst(){int i,j,k,idl,idr;bool inc;inc=true;while(inc){inc=false;for(i=1;i<=n;i++) //遍历所有产生式{idl=cid(p[i].l);for(j=0;p[i].r[j];j++){idr=cid(p[i].r[j]);//如果当前为终结符//并且first[idl]中不包含这个终结符就把这个终结符加入first[idl] if(idr>1000){if(!inclu(first[idl],p[i].r[j])){add(first[idl],p[i].r[j]);inc=true;}break;}//否则把该变量的first集里面的元素加入first[idl]else{for(k=1;k<=first[idr].n;k++)if(!inclu(first[idl],first[idr].elm[k])){add(first[idl],first[idr].elm[k]);inc=true;}}//.....if(!inclu(first[idl],'~')) break;}}// 若idl可以转换为空,则‘~’应属于first[idl]if(p[i].r[j]==0&&!inclu(first[idl],'~')){add(first[idl],'~');inc=true;}}}}//输出集合,flag用于表示是first还是followvoid print(struct set *st,int flag){int i,j;char *s;puts("\n");flag==0? s="FIRST":s="FOLLOW";for(i=1;i<=vnum;i++){printf("%s(%c): ",s,v[i]);for(j=1;j<=st[i].n;j++)printf("%c ",st[i].elm[j]);puts("");}}//求follow集void makefollow(){int i,j,k,idl,idr,idf;bool flag,inc=true;add(follow[1],'#');//把结束标志"#"加入起始符的follow集while(inc){inc=false;for(i=1;i<=n;i++)idl=cid(p[i].l);for(flag=true,j=p[i].rl;j>=0;j--){idr=cid(p[i].r[j]);if(idr>1000){flag=false; continue;}if(flag){for(k=1;k<=follow[idl].n;k++){if(!inclu(follow[idr],follow[idl].elm[k])){add(follow[idr],follow[idl].elm[k]);inc=true;}}}if(j<p[i].rl) idf=cid(p[i].r[j+1]);else continue;if(idf>1000){if(!inclu(follow[idr],p[i].r[j+1]))add(follow[idr],p[i].r[j+1]);continue;}for(k=1;k<=first[idf].n;k++){if(!inclu(follow[idr],first[idf].elm[k])&&first[idf].elm[k]!='~') {add(follow[idr],first[idf].elm[k]);inc=true;}}}}}}void maketable(){int i,j,k,idl,idr,idt;char ch;bool flag;memset(table,0,sizeof(table));table[vnum][tnum]=-1;for(i=1;i<=n;i++){idl=cid(p[i].l);for(j=0;j<=p[i].rl;j++){ch=p[i].r[j];idr=cid(ch);if(idr>1000){idr-=1000;if(ch!='~'){if(table[idl][idr]) goto end;table[idl][idr]=i;}else{for(k=1;k<=follow[idl].n;k++){idt=cid(follow[idl].elm[k])-1000;if(table[idl][idt]) goto end;table[idl][idt]=i;}}break;}for(flag=false,k=1;k<=first[idr].n;k++) {idt=cid(first[idr].elm[k])-1000;if(first[idr].elm[k]=='~') flag=true; if(table[idl][idt]) goto end;table[idl][idt]=i;}if(!flag) break;}if(j>p[i].rl){for(k=1;k<=follow[idl].n;k++){idt=cid(follow[idl].elm[k])-1000;if(table[idl][idt]) goto end;table[idl][idt]=i;}}}return;end: printf("It's not a LL(1) language,and if you want to use this program to compile you may get a wrong answer!\n");return;}void compile(char *exp){int i,j,top,idl,idr,t,step[MAX],c=0;char stack[MAX];top=1;t=strlen(exp);stack[0]='#',stack[1]=v[1];exp[t]='#',exp[t+1]=0;for(i=0;;){idl=cid(stack[top]);idr=cid(exp[i])-1000;if(idl>1000) goto fail;t=table[idl][idr];if(t==0) goto fail;step[++c]=t;for(top--,j=p[t].rl;j>=0;j--){if(p[t].r[j]!='~')stack[++top]=p[t].r[j];}while(top>=0&&exp[i]&&stack[top]==exp[i]){if(stack[top]=='#') goto pass;top--,i++;}}pass: printf("Accept!\n");for(i=1;i<=c;i++)printf("%c->%s\n",p[step[i]].l,p[step[i]].r);return;fail: printf("Compile Error!\n");return;}int main(){char exp[MAX];freopen("LL(1).txt","r",stdin); load();show();makefirst();print(first,0);makefollow();print(follow,1);maketable();while(scanf("%s\n",exp)!=EOF) compile(exp);return 0;}。

编译原理实验报告实验名称计算first集合和follow集合实验时间院系计算机科学和技术班级软件工程1班学号姓名输入：任意的上下文无关文法。

输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。

2. 实验原理设文法G[S]＝（V N ，V T ，P ，S ），则首字符集为： FIRST （α）＝{a | α⇒*a β，a ∈V T ，α,β∈V *}。

若α⇒*ε，ε∈FIRST （α）。

由定义可以看出，FIRST （α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。

所以FIRST 集也称为首符号集。

设α＝x 1x 2…x n ，FIRST （α）可按下列方法求得：令FIRST （α）＝Φ，i ＝1；（1） 若x i ∈V T ，则x i ∈FIRST （α）；（2） 若x i ∈V N ；① 若ε∉FIRST （x i ），则FIRST （x i ）∈FIRST （α）；② 若ε∈FIRST （x i ），则FIRST （x i ）－{ε}∈FIRST （α）；（3） i ＝i+1，重复（1）、（2），直到x i ∈V T ，（i ＝2，3，…，n ）或x i∈V N 且若ε∉FIRST （x i ）或i>n 为止。

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

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

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

设文法G[S]＝（V N ，V T ，P ，S ），则FOLLOW （A ）＝{a | S ⇒… Aa …，a ∈V T }。

若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 ）；计算first集合和follow集合4.实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。