编译原理课程设计(词法语法分析器,follow集)

编译原理课程设计(词法语法分析器,follow集)编译原理课程设计题目 follow集分析课程编译原理姓名陈飞学号 10821380144 学院应用技术学院 2010年 7 月 9日目录目录 I 1系统分析 1 1.1选题要求 1 1.2预期目标 ...

编译原理课程设计题目 follow集分析课程编译原理姓名陈飞学号 10821380144 学院应用技术学院 2010年 7 月 9日目录目录 I 1系统分析 1 1.1选题要求 1 1.2预期目标 1 2系统设计 1 2.1基本设计 1 2.2程序流程图 3 3系统实现 5 3.1上机编程 5 3.2运行结果 8 3.2.1 读入文法 9 3.2.2执行结果 9 4 总结与感想 12 参考文献 13 1系统分析 1.1选题要求求出输入文法的follow集 1.2预期目标设计程序，使输入文法，能输出其follow集 2系统设计 2.1基本设计核心算法：对于文法中的符号X VN ，其FOLLOW(A)集合可反复应用下列规则计算，直到FOLLOW(A)集合不再增大为止。 (1)对于文法开始符号S，因为S S，故#FOLLOW(S)； (2)若A→α?Bβ，其中BVN，α(VT VN)*、β(VT VN)+，则 FIRST(β)-{}FOLLOW(B)； (3)若A→α?B或A→α?Bβ (β? ?)，则 FOLLOW(A) FOLLOW(B)。 FOLLOW集的算法描述如下： void FOLLOW(int i) X为待求的非终结符把当前字符放到一临时数组tempFOLLOW[]中,标识求已求其FOLLOW集.避免循环递归 if X为开始符号 then #∈FOLLOW(X) 对全部的产生式找一个右部含有当前字符X的产生式注：比如求FOLLOW(B)则找A→αX或A→αXβ(β ε)的产生式 if X在产生式右部的最后(形如产生式A→αX) then 查找非终结符A是否已经求过其FOLLOW集.避免循环递归 if 非终结符A已求过其FOLLOW集 then FOLLOW(A)∈FOLLOW(X) 继续查下一条产生式是否含有X else 求A之FOLLOW集，并标识为A已求其FOLLOW集 else if X不在产生式右部的最后(形如A→αBβ) then if右部X后面的符号串β能推出空字ε then 查找β是否已经求过其FOLLOW集.避免循环递归 if 已求过β的FOLLOW集 then FOLLOW(A)∈FOLLOW(B) 结束本次循环 else if β不能推出空字 then 求FIRST(β) 把FIRST(β)中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过： 2.2程序流程图（一）基本模块流程（二）查找字符是否在指定字符串图（二）图（三）（三）不含左地柜的产生式分解（上图右）（四）判定终结符非终结符 3系统实现 3.1源代码 #include #include #include #include #include using namespace std; FILE *inparse;//用于指向输入文件的指针 char inparsefile[300];//接收存储输入文件名 /***************定义产生式的语法集结构*************/ typedef struct { char formula[200]; //产生式 }grammarElement; grammarElement gramOldSet[200];//原始文法的产生式集 grammarElement gramNewSet[200];//消除左递归后文法的产生式集 /*********************变量定义*********************/ int grammarNum=0; //原始的产生式数目 int Pcount=0; //分解的产生式的个数 char startSymbol; //开始符号 char terSymbol[200]; //终结符号 char non_ter[200]; //非终结符号 char allSymbol[400]; //所有符号 char leftStr[200]; //产生式左部(不包括"->") char rightStr[200][200]; //产生式右部(不包括"->") char followSET[100][100]; //各产生式左部的FOLLOW集合 char tempFOLLOW[100]; //求FOLLOW集合时使用 char followed[100]; //记录各符号的FOLLOW是否已求过,0和1 表示其状态 char epsilon[100]; //记录可直接推出@("ε")的符号 char tempEpsilon[100]; //求someDerivateEpsilon()时使用,标识此字符已查找其是否可推出空字 int validity=1; //表示输入文法是否有效 char choice; //用户输入时使用 /************************************************** 查找字符是否在指定字符串中 **************************************************/ bool FindChar(char ch,char *p) { int i; if(strlen(p)==0) return false; for(i=0;i<(int)strlen(p);i++) { //若存在，返回真 if(p[i]==ch) return true; } return false; } /************************************************** （为简化默认不含有左递归）产生式类型A->Bb|c **************************************************/ void nonLeftRecursive(char *point) { //指针point指向当前要分解的产生式A->Bb|c int m=0,j; char temp[20]; for(j=3;j<=(int)strlen(point)-1;j++) { if(point[j]!='|')//产生式形如A->Bb temp[m++]=point[j]; else//产生式形如A->Bb|c,分解为A->Bb和A->c { leftStr[Pcount]=point[0]; memcpy(rightStr[Pcount],temp,m); rightStr[Pcount][m]='\0'; m=0; Pcount++; } } leftStr[Pcount]=point[0]; memcpy(rightStr[Pcount],temp,m); rightStr[Pcount][m]='\0'; Pcount++; m=0; } void lastProduce() { int i; for(i=0;i"字符串 //检查是否是正确的产生式 if(fscanf(inparse,"%c->%s\r\n",&NTtmp,&rightTmp)!=2) { validity=0; //产生式无效 break; //结束循环 } //求开始符号 if(tmpIndex==0) { startSymbol=NTtmp; } gramOldSet[tmpIndex].formula[0]=NTtmp; gramOldSet[tmpIndex].formula[1]='-'; gramOldSet[tmpIndex].formula[2]='>'; strcat(gramOldSet[tmpIndex].formula,rightTmp); strcpy(p[tmpIndex],gramOldSet[tmpIndex].formula); tmpIndex++; for(i=0;i=65&&rightTmp[i]<=90||rightTmp[i]=='|')) { for(j=0;j=65&&rightTmp[i]<=90) { for(k=0;kB,B可推出空) return(1); else if(j==1&&FindChar(rightStr[i][0],terSymbol))//右部长度为1但第一个字符为终结符,返回0(A->a,a为终结符) return(0); else { for(k=0;k<=j-1;k++) if(FindChar(rightStr[i][k],tempEpsilon))//查找临时数组tempEpsilon[].(A->AB) mark=1; if(mark==1)//找到的字符与当前字符相同(A->AB) continue;//结束本次循环 else//(mark等于0) { for(k=0;k<=j-1;k++) { result*=someDerivateEpsilon(rightStr[i][k]);//查找右部符号是否可推出空字,把返回值赋给result temp[0]=rightStr[i][k]; temp[1]='\0'; join(tempEpsilon,temp,true);//把当前符号加入到临时数组tempEpsilon[]里. } } } if(result==0&&i*ε)，则FOLLOW(A)∈FOLLOW(B)。 /**************************************************/ void FOLLOW(int i) { int j,k,m,n,result=1; char X,temp[20]; X=non_ter[i]; //X为待求的非终结符 temp[0]=X; temp[1]='\0'; //把当前字符放到一临时数组tempFOLLOW[]中,标识求已求其FOLLOW集.避免循环递归 join(tempFOLLOW,temp,false); //若为开始符号-----开始符号S，则#∈FOLLOW(S) if(X==startSymbol) { temp[0]='#'; temp[1]='\0'; join(followSET[i],temp,false); //把#号加入到当前字符的FOLLOW集 } //若A→αB或A→αBβ for(j=0;j<=Pcount-1;j++) { if(FindChar(X,rightStr[j])) //找一个右部含有当前字符X的产生式 { //比如求FOLLOW(B)则找A→αB或A→αBβ(β=>*ε)的产生式 for(k=0;;k++) if(rightStr[j][k]==X) break; //k为X在该产生式右部的序号.如B在产生式A→αB中的位置

                    本文档为【编译原理课程设计(词法语法分析器,follow集)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

编译原理课程设计(词法语法分析器,follow集)

你可能还喜欢