编译原理语法分析器课程设计

语法分析器的设计（说明）重庆理工大学最牛逼的应用技术学院108213801班学者所做，自己人毋抄袭。版权所与，抄袭必纠！！！要求：建立一个针对LL(1)文法编译器的自动生成器。要完成此编译器的生成器需对源文件进行两遍处理：第一遍词法分析，第二遍语法分析。语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，然后建立词法分析器，包括词法分析主程序、扫描器部分、关键字表等。经词法分析后分别计算所输入的文法的每个非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是则输入文法符合LL(1)文法则可以进行分析。语法分析器实现语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。开始开始读入文法有效？判断句型报错结束语法分析程序流程图是LL(1)文法？1.计算FIRST集对于文法G的任意一个符号串=X1X2…Xn可按下列步骤构造其FIRST()集合：令FIRST()=Æ，i=1；(1)若XiVT，则XiFIRST()；(2)若XiVN：①若eFIRST(Xi)，则FIRST(Xi)FIRST()；②若eFIRST(Xi)，则FIRST(Xi)-{e}FIRST()；i=i+1；重复(1)(2)，直到(XiVT(i=2,3,…,n)或XiVN且eFIRST(Xi)或i>n为止)。(3)若对于一切1≤i≤n，eFIRST(Xi)，则将e符号加进FIRST()。实例中求单个符号的FIRST集的算法描述如下：voidfindSingleFIRST(inti){ 参数i为符号在所有输入符号中的序号 X等于指示器i所指向的符号 在保存终结符元素的terSymbol[]数组查找XifX为终结符(X∈VT)，thenFIRST(X)={X}在保存终结符元素的non_ter[]数组查找XifX是非终结符(X∈VN)在所有产生式中查找X所在的产生式if产生式右部第一个字符为终结符或空(即X→a(a∈VT)或X→ε)then把a或ε加进FIRST(X)if产生式右部第一个字符为非终结符thenif产生式右部的第一个符号等于当前字符then跳到下一条产生式进行查找求当前非终结符在所有字符集中的位置if当前非终结符还没求其FIRST集then查找它的FIRST集并标识此符号已求其FIRST集 求得结果并入到X的FIRST集.if当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符then获取右部符号下一个字符在所有字符集中的位置if此字符的FIRST集还未查找then找其FIRST集,并标其查找状态为1把求得的FIRST集并入到X的FIRST集.if当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为X→Y1Y2…Yk,若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε∈符号加进FIRST(X))then把空字加入到当前字符X的FIRST集. else不能推出空字则结束循环标识当前字符X已查找其FIRST集.}2.计算FOLLOW集FOLLOW集的构造可用如下方法来求：对于文法中的符号XVN，其FOLLOW(A)集合可反复应用下列规则计算，直到FOLLOW(A)集合不再增大为止。(1)对于文法开始符号S，因为SS，故#FOLLOW(S)；(2)若A→B，其中BVN，(VTVN)*、(VTVN)+，则FIRST()-{e}FOLLOW(B)；(3)若A→B或A→B(e)，则FOLLOW(A)FOLLOW(B)。 FOLLOW集的算法描述如下： voidFOLLOW(inti) X为待求的非终结符把当前字符放到一临时数组tempFOLLOW[]中,标识求已求其FOLLOW集.避免循环递归ifX为开始符号then#∈FOLLOW(X) 对全部的产生式找一个右部含有当前字符X的产生式注：比如求FOLLOW(B)则找A→αX或A→X(ε)的产生式ifX在产生式右部的最后(形如产生式A→X)then查找非终结符A是否已经求过其FOLLOW集.避免循环递归if非终结符A已求过其FOLLOW集thenFOLLOW(A)∈FOLLOW(X)继续查下一条产生式是否含有Xelse求A之FOLLOW集，并标识为A已求其FOLLOW集elseifX不在产生式右部的最后(形如A→B)thenif右部X后面的符号串能推出空字then查找是否已经求过其FOLLOW集.避免循环递归if已求过的FOLLOW集thenFOLLOW(A)∈FOLLOW(B)结束本次循环elseif不能推出空字then求FIRST()把FIRST()中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过3.计算SELECT集SELECT集的构造算法如下：对所有的规则产生式A→x：(1)若x不能推出空字e，则SELECT(A→x)=FIRST(x)；(2)若x可推出空字e，则SELECT(A→x)=FIRST(x)–{}FOLLOW(A)。算法描述如下： for(i=0;i<=产生式总数-1;i++)先把当前产生式右部的FIRST集(一切非空元素,不包括ε)放入到当前产生式的SELECT(i); if产生式右部符号串可推出空字ethen把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT(i)中4.判断是否LL(1)文法要判断是否为LL(1)文法，需要输入的文法G有如下要求：具有相同左部的规则的SELECT集两两不相交，即：SELECT(A→)∩SELECT(A→)=Æ如果输入的文法都符合以上的要求，则该文法可以用LL(1)方法分析。算法描述如下： 把第一条产生式的SELECT(0)集放到一个临时数组temp[]中 for(i=1;i<=产生式总数-1;i++)求temp的长度length ifi指向的当前产生式的左部等于上一条产生式的左部then 把SELECT(i)并入到temp数组中 Iftemp的长度小于length加上SELECT(i)的长度 返回0 else把temp清空把SELECT(i)存放到temp中结果返回1；源码/***************************************************LL(1)parsinggrammar25/4/2007***************************************************/#include<stdlib.h>#include<stdio.h>#include<string.h>#include<iostream>#include<windows.h>usingnamespacestd;/**************************************************///用于指向输入输出文件的指针FILE*inparse,*outparse,*inscan; //用于接收输入输出文件名 charinparsefile[300],outparsefile[300],inscanfile[300]; /**************************************************//***************定义产生式的语法集结构*************/typedefstruct{ charformula[200]; //产生式}grammarElement;grammarElementgramOldSet[200];//原始文法的产生式集grammarElementgramNewSet[200];//消除左递归后文法的产生式集/*********************变量定义*********************/intgrammarNum=0; //原始的产生式数目intPcount=0; //分解的产生式的个数charstartSymbol; //开始符号charterSymbol[200]; //终结符号charnon_ter[200]; //非终结符号charallSymbol[400]; //所有符号charleftStr[200]; //消除左递归后产生式左部(不包括"->")charrightStr[200][200]; //消除左递归后产生式右部(不包括"->")/***************************************************/charfirstSET[100][100]; //各产生式右部的FIRST集合charfollowSET[100][100]; //各产生式左部的FOLLOW集合charsingleFIRST[100][100]; //所有单个符号的FIRST集合,函数findSingleFIRST(i)用到charselectSET[100][100]; //各单个产生式的SELECT集合chartempFOLLOW[100]; //求FOLLOW集合时使用charFirstForFollow[100]; //求FOLLOW时存放某一符号串的FIRST集合charfirsted[100]; //记录各符号的FIRST是否已求过,0和1表示其状态charfollowed[100]; //记录各符号的FOLLOW是否已求过,0和1表示其状态charepsilon[100]; //记录可直接推出@("ε")的符号chartempEpsilon[100]; //求someDerivateEpsilon()时使用,标识此字符已查找其是否可推出空字/***************************************************/intvalidity=1; //表示输入文法是否有效intisLL1=1; //表示输入文法是否为LL(1)文法intM[200][200]; //分析表charchoice; //用户输入时使用/*************************************************** 设置彩色文字***************************************************/voidsetcolor(unsignedshortForeColor=4,unsignedshortBackGroundColor=0){ HANDLEhCon=GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hCon,ForeColor|BackGroundColor);}/**************************************************查找字符是否在指定字符串中**************************************************/boolFindChar(charch,char*p){ inti; if(strlen(p)==0) returnfalse; for(i=0;i<(int)strlen(p);i++) { //若存在，返回真 if(p[i]==ch) returntrue; } returnfalse;}/**************************************************得到一个不在non_ter[]数组的非终结符号(消除左递归用到)**************************************************/charget_Char(){ charch='A'; //在非终结符non_ter中查找while(FindChar(ch,non_ter)) ch++; if(ch>90) return('$');//如果大写字母已经用完,出错 return(ch);}/************************************************** 判断输入的文法是直接左递归还是间接左递归 2007-5-6/**************************************************intjudgeLeftRecursive(char*point){ inti,j,k=3,l; l=(int)strlen(point); for(i=0;i<=l-1;i++) { if(point[k]=point[0]) return1;//含有直接左递归 elseif(point[k]!=point[0]&&FindChar(point[k],non_ter)) { for(j=0;j<grammarNum;j++) { } } } return1;}/************************************************** 分解含有直接左递归的产生式 eliminateleftStrrecursive产生式A->Aα|β,可以用非左递归的 A->βA' A'->αA'|ε来代替.PS:这里只是消除直接左递归**************************************************/voidDirectLetfRecursive(char*point){ //point指针指向传递过来的完整的产生式inti,j; intm=0,n=3; chartemp[20],ch; ch=get_Char(); //得到一个非终结符 if(ch=='$') { printf("消除左递归时出错.原因:没有足够的符号(字母)可用.\n"); fprintf(outparse,"消除左递归时出错.原因:没有足够的符号(字母)可用.\n"); system("pause"); exit(0); } i=strlen(non_ter); non_ter[i]=ch; //把获得的非终结符加入到保存非终结符的non_ter[]数组中 non_ter[i+1]='\0'; for(j=0;j<=(int)strlen(point)-1;j++) { if(point[n]==point[0]) { //如果"|"后的首符号和左部相同//A->ABa|Ac for(j=n+1;j<=(int)strlen(point)-1;j++)//j指向当前是左递归字符的下一个字符的位置 { while(point[j]!='|'&&point[j]!='\0')//没到产生式尾部且不等于"|" temp[m++]=point[j++]; //把形如A->ABa的产生式,右部从A以后的字符串存入到临时数组temp[]中 leftStr[Pcount]=ch; //把得到的字符加入到左部数组leftStr[]中 memcpy(rightStr[Pcount],temp,m);//把右部从A以后的字符串存入到新产生式的右部Ba rightStr[Pcount][m]=ch; //把得到的字符加入到新产生式右部的结尾. rightStr[Pcount][m+1]='\0'; //得到新的产生式A'->BaA' m=0; Pcount++; //产生式条数加1 if(point[j]=='|') //把形如A->ABa|Ac的产生式分解成:A->ABa和A->Ac { n=j+1; //记下符号"|"的下一个字符的位置n break; } } } else { //如果"|"后的首符号和左部不同--A->ABa|Cc leftStr[Pcount]=ch; rightStr[Pcount][0]='@'; rightStr[Pcount][1]='\0'; //得到新的产生式A'->@ Pcount++; for(j=n;j<=(int)strlen(point)-1;j++) { if(point[j]!='|') temp[m++]=point[j]; else { leftStr[Pcount]=point[0]; memcpy(rightStr[Pcount],temp,m); rightStr[Pcount][m]=ch; rightStr[Pcount][m+1]='\0'; m=0; Pcount++; } }leftStr[Pcount]=point[0]; memcpy(rightStr[Pcount],temp,m); rightStr[Pcount][m]=ch; rightStr[Pcount][m+1]='\0'; Pcount++; m=0; } }}/**************************************************分解不含有左递归的产生式A->Bb|c**************************************************/voidnonLeftRecursive(char*point){ //指针point指向当前要分解的产生式A->Bb|cintm=0,j; chartemp[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;}/************************************************** 最终的产生式**************************************************/voidlastProduce(){ inti; for(i=0;i<Pcount;i++) { gramNewSet[i].formula[0]=leftStr[i]; gramNewSet[i].formula[1]='-'; gramNewSet[i].formula[2]='>'; strcat(gramNewSet[i].formula,rightStr[i]); }}/**************************************************从文件读入一个文法/**************************************************/voidgetGrammar(char*t,char*n,char*leftStr,charrightStr[200][200]){ charNTtmp;//保存临时非终结符号 charrightTmp[200];//产生式右部 charVn[200];//非终结符集non-terSymbolset charVt[200];//终结符集terSymbolset inttmpIndex; intvtIndex,vnIndex; inti,j,k; intvtLen,vnLen;//终结符,非终结符 charp[200][200];//保存产生式 tmpIndex=0; vtIndex=0; vnIndex=0; while(!feof(inparse)) { //查找特定产生式的位置是否含有"->"字符串 //检查是否是正确的产生式 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<vnIndex;i++) if(NTtmp==Vn[i]) break; //求新非终结符号 if(i==vnIndex) { Vn[vnIndex]=NTtmp; vnIndex++; } i=0; while(rightTmp[i]!='\0') { //不是非终结符(大写字母A-Z),把元符号"|"屏蔽.(求终结符) if(!(rightTmp[i]>=65&&rightTmp[i]<=90||rightTmp[i]=='|')) { for(j=0;j<vtIndex;j++) if(rightTmp[i]==Vt[j]) break; //求新的终结符 if(j==vtIndex) { Vt[vtIndex]=rightTmp[i]; vtIndex++; } } //如果右部有非终结符(大写字母) elseif(rightTmp[i]>=65&&rightTmp[i]<=90) { for(k=0;k<vnIndex;k++) if(rightTmp[i]==Vn[k]) break; if(k==vnIndex) { Vn[vnIndex]=rightTmp[i]; vnIndex++; } } i++; } } Vt[vtIndex]='\0'; Vn[vnIndex]='\0'; vtLen=vtIndex; vnLen=vnIndex; grammarNum=tmpIndex;/**************************************************/ memcpy(n,Vn,vnLen);//求得的非终结符保存到n,n指向non_ter[] memcpy(t,Vt,vtLen);//终结符terSymbol[]/**************************************************/ for(i=0;i<grammarNum;i++) { printf("读入的产生式%d:\t%s\n",i+1,gramOldSet[i].formula); fprintf(outparse,"读入的产生式%d:\t%s\n",i+1,gramOldSet[i].formula); } for(i=0;i<=grammarNum-1;i++) //分解输入的各产生式 { if(p[i][3]==p[i][0]) DirectLetfRecursive(p[i]); //分解含有左递归的产生式 else nonLeftRecursive(p[i]); }}/************************************************** 检查读入文法的正确性checkproduce**************************************************/voidcheckP(){ inti,j; for(i=0;i<=Pcount-1;i++) { if(!FindChar(leftStr[i],non_ter)) { printf("\n文法错误.\n"); fprintf(outparse,"\n文法错误.\n"); printf("原因:非终结符%c不在非终结符集合中!\n",leftStr[i]); fprintf(outparse,"原因:非终结符%c不在非终结符集合中!\n",leftStr[i]); printf("\n按回车键结束..."); system("pause"); exit(0); } for(j=0;j<=strlen(rightStr[i])-1;j++) { if(!FindChar(rightStr[i][j],non_ter)&&!FindChar(rightStr[i][j],terSymbol)&&rightStr[i][j]!='@') { printf("\n文法错误.\n"); fprintf(outparse,"\n文法错误.\n"); printf("原因:右部符号%c不是可用符号,即不属于非终结符也不属于终结符或空字!\n",rightStr[i][j]); fprintf(outparse,"原因:右部符号%c不是可用符号,即不属于非终结符也不属于终结符或空字!\n",rightStr[i][j]); printf("\n按回车键结束..."); system("pause"); exit(0); } if(rightStr[i][j]>=65&&rightStr[i][j]<=90&&!FindChar(rightStr[i][j],leftStr)) { printf("\n文法错误.\n"); fprintf(outparse,"\n文法错误.\n"); printf("原因:非终结符%c未曾在产生式左部出现!\n",rightStr[i][j]); fprintf(outparse,"原因:非终结符%c未曾在产生式左部出现!\n",rightStr[i][j]); printf("\n按回车键结束..."); system("pause"); exit(0); } } }}/************************************************** 连接符号 destination为目标符号串 source为源符号串 type为真是空字"@"并入目串否则不并入/**************************************************/voidjoin(char*destination,char*source,booltype){inti,j; for(i=0;i<=(int)strlen(source)-1;i++) {if(type==false&&source[i]=='@') ; else { for(j=0;;j++) { if(j<(int)strlen(destination)&&source[i]==destination[j]) break; //目串中已含有源串中的字符,内循环结束if(j==(int)strlen(destination)) { destination[j]=source[i]; //把源串并入到目串的尾部 destination[j+1]='\0'; // break; //结束j循环.进入下一个外循环i++ } } } }}/************************************************** 求所有能直接推出"@"("ε")空字的符号 结果保存到epsilon[]中/**************************************************/voidallHasEpsilon(charch){ /*即求所有可推出"@"("ε")epsilon的符号*/ chartemp[10]; inti; for(i=0;i<=Pcount-1;i++) { if(rightStr[i][0]==ch&&strlen(rightStr[i])==1) { temp[0]=leftStr[i]; temp[1]='\0'; join(epsilon,temp,true); //allHasEpsilon(leftStr[i]); } }}/**************************************************求某一符号能否推出空字"@"/**************************************************/intsomeDerivateEpsilon(charc){ //若能推出"@"返回1；否则，返回0 inti,j,k,result=1,mark=0; chartemp[20]; temp[0]=c; temp[1]='\0'; join(tempEpsilon,temp,true);//存放到一个临时数组里,标识此字符已查找其是否可推出空字 if(FindChar(c,epsilon))//如果c在可直接推出空字的epsilon[]中,返回1 return(1); for(i=0;;i++) { if(i==Pcount)return(0); if(leftStr[i]==c)//找一个左部为c的产生式 {j=strlen(rightStr[i]);//j为c所在产生式右部的长度 if(j==1&&FindChar(rightStr[i][0],epsilon))//右部长度为1且右部第一个字符在epsilon[]中.返回1(A->B,B可推出空) return(1); elseif(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<Pcount) //如果当前字符不能推出空字且还没搜索完全部的产生式,则跳出本次循环继续搜索下一条产生式 continue; elseif(result==1&&i<Pcount)//当前字符可推出空字,返回1 return(1); } }}/**************************************************求单个符号的FIRST集 把求得结果保存到singleFIRST[]数组算法:(1)若X∈VT，则FIRST(X)={X}。(2)若X∈VN，且具有形如X→a的产生式(a∈VT)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。(3)设G中有形如X→Y1Y2…Yk的产生式，若Y1∈VN，则把FIRST(Y1)中的一切非ε符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yj)中的一切非ε符号加进FIRST(X)；若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε∈符号加进FIRST(X)。/**************************************************/voidfindSingleFIRST(inti){ //i为符号在所有输入符号中的序号charX,temp[20]; intj,k,m; X=allSymbol[i]; charch='@'; //求所有能直接推出"@"("ε")空字的符号,结果保存到epsilon[]中 allHasEpsilon(ch); if(FindChar(X,terSymbol))//若为终结符--X∈VT，则FIRST(X)={X}{singleFIRST[i][0]=X; singleFIRST[i][1]='\0'; } elseif(FindChar(X,non_ter))//若为非终结符 { for(j=0;j<=Pcount-1;j++) //j为在所有产生式中的序列 {if(leftStr[j]==X) { //产生式右部第一个字符为终结符或空.---产生式X→a(a∈VT)或X→ε,则把a或ε加进FIRST(X)if(FindChar(rightStr[j][0],terSymbol)||rightStr[j][0]=='@') { temp[0]=rightStr[j][0]; temp[1]='\0'; join(singleFIRST[i],temp,true); } //------X→Y1Y2…Yk的产生式，若Y1∈VN，则把FIRST(Y1)中的一切非ε符号加进FIRST(X) elseif(FindChar(rightStr[j][0],non_ter))//产生式右部第一个字符为非终结符 { if(rightStr[j][0]==X) continue;//产生式右部的第一个符号等于当前字符则跳到下一条产生式进行查找 for(k=0;;k++) if(allSymbol[k]==rightStr[j][0]) break;//求当前非终结符在所有字符集中的位置k if(firsted[k]=='0')//5-5---2 { findSingleFIRST(k);//求其FIRST集 firsted[k]='1';//标识其为查找状态 } join(singleFIRST[i],singleFIRST[k],false);//求得结果并入到X的FIRST集.for(k=0;k<=(int)strlen(rightStr[j])-1;k++) { tempEpsilon[0]='\0';//存放到一个临时数组里,标识此字符已查找其是否可推出空字 //当前产生式右部符号是否可推出空字,且当前字符不是右部的最后一个字符 if(someDerivateEpsilon(rightStr[j][k])==1&&k<(int)strlen(rightStr[j])-1) {for(m=0;;m++) if(allSymbol[m]==rightStr[j][k+1])//获取右部符号下一个字符在所有字符集中的位置 break; if(firsted[m]=='0')//如果此字符的FIRST集还未查找,则找其FIRST集,并标其查找状态为1 { findSingleFIRST(m); firsted[m]='1'; } join(singleFIRST[i],singleFIRST[m],false);//把求得结果并入到c的FIRST集. } //当前右部符号串可推出空且是右部符号串的最后一个字符 //----产生式为X→Y1Y2…Yk,若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε∈符号加进FIRST(X) elseif(someDerivateEpsilon(rightStr[j][k])==1&&k==(int)strlen(rightStr[j])-1) { temp[0]='@'; temp[1]='\0'; join(singleFIRST[i],temp,true);//把空字加入到当前字符c的FIRST集. } else break;//不能推出空字则结束循环 } } } } } firsted[i]='1';//标识当前字符c已查找其FIRST集.}/**************************************************求各产生式右部的FIRST 结果保存到firstSET集合(数组)里 FIRST(inti,char*p)参数说明: i不为1时是该字符在产生式的序号, i为-1时,表示求FOLLOW时用到的产生式右部的FIRST集,保存在FirstForFollow[]中 指针p指向该产生式的右部符号串/**************************************************/voidFIRST(inti,char*p){ //指针p指向右部符号串 intlength; //标识右部符号串的长度 intj,k,m; chartemp[20]; length=strlen(p); // if(length==1) //如果右部为单个符号(长度为1) { if(p[0]=='@') //右部符号串第一个字符为"@"空字{ if(i>=0){ firstSET[i][0]='@'; //把"@"加入到当前字符的FIRST集 firstSET[i][1]='\0'; } else { FirstForFollow[0]='@'; FirstForFollow[1]='\0'; } } else { for(j=0;;j++) if(allSymbol[j]==p[0])//求右部符号的第一个字符p[0]在所有字符集中的位置j break; if(i>=0) { //把j所指向的单个符号的FIRST集拷贝到该右部符号串的FIRST集 memcpy(firstSET[i],singleFIRST[j],strlen(singleFIRST[j])); firstSET[i][strlen(singleFIRST[j])]='\0'; } else { memcpy(FirstForFollow,singleFIRST[j],strlen(singleFIRST[j])); FirstForFollow[strlen(singleFIRST[j])]='\0'; }} } else//如果右部为多个符号 { for(j=0;;j++) if(allSymbol[j]==p[0])//求右部符号的第一个字符p[0]在所有字符集中的位置j break; if(i>=0)join(firstSET[i],singleFIRST[j],false); else join(FirstForFollow,singleFIRST[j],false); for(k=0;k<=length-1;k++) { tempEpsilon[0]='\0'; //当前产生式右部符号是否可推出空字,且当前字符不是右部的最后一个字符 if(someDerivateEpsilon(p[k])==1&&k<length-1) {for(m=0;;m++) if(allSymbol[m]==rightStr[i][k+1]) break;if(i>=0) join(firstSET[i],singleFIRST[m],false); else join(FirstForFollow,singleFIRST[m],false); } //当前右部符号串可推出空且是右部符号串的最后一个字符 //----产生式为X→Y1Y2…Yk,若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε∈符号加进FIRST(X)elseif(someDerivateEpsilon(p[k])==1&&k==length-1) { temp[0]='@'; temp[1]='\0'; if(i>=0) join(firstSET[i],temp,true); else join(FirstForFollow,temp,true); } elseif(someDerivateEpsilon(p[k])==0) break; } }}/**************************************************求各产生式左部(非终结符)的FOLLOW集 求得结果保存在followSET中 参数i为该符号在非终结符中的位置算法:(1)对于文法开始符号S，则#∈FOLLOW(S)；(2)若A→αBβ，其中B∈VN，α∈(VTUVN)*、β∈(VTUVN)+，则FIRST(β)-{ε}∈FOLLOW(B)；(3)若A→αB或A→αBβ(β=>*ε)，则FOLLOW(A)∈FOLLOW(B)。/**************************************************/voidFOLLOW(inti){ intj,k,m,n,result=1; charX,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中的位置for(m=0;;m++) if(allSymbol[m]==leftStr[j]) break;//m为产生式左部非终结符在所有符号中的序号 //如果X在产生式右部的最后,形如产生式A→αB,则FOLLOW(A)∈FOLLOW(B) if(k==(int)strlen(rightStr[j])-1) { if(FindChar(allSymbol[m],tempFOLLOW)) //查找该非终结符是否已经求过其FOLLOW集.避免循环递归 { //是则FOLLOW(A)∈FOLLOW(B),如下 join(followSET[i],followSET[m],false); //把X所在产生式的左部非终结符的FOLLOW集加入到FOLLOW(X)中 continue; //结束本次循环,进入j++循环} if(followed[m]=='0') //如果该非终结符的FOLLOW未求过 { FOLLOW(m); //求之FOLLOW集 followed[m]='1'; //标识为1 } join(followSET[i],followSET[m],false); //FOLLOW(A)∈FOLLOW(B) } else//如果X不在产生式右部的最后,形如A→αBβ { for(n=k+1;n<=(int)strlen(rightStr[j])-1;n++) { tempEpsilon[0]='\0'; //把tempEpsilon[]置空, //因为求此字符是否可推出空字someDerivateEpsilon(c)时用到 result*=someDerivateEpsilon(rightStr[j][n]); } if(result==1)//如果右部X后面的符号串能推出@---A→αBβ(β=>*ε)则FOLLOW(A)∈FOLLOW(B) {if(FindChar(allSymbol[m],tempFOLLOW))//查找该非终结符是否已经求过其FOLLOW集.避免循环递归 { join(followSET[i],followSET[m],false);//FOLLOW(A)∈FOLLOW(B) continue; //结束本次循环 } if(followed[m]=='0') { FOLLOW(m); followed[m]='1'; } join(followSET[i],followSET[m],false);//FOLLOW(A)∈FOLLOW(B) } //若A→αBβ，其中B∈VN，α∈(VTUVN)*、β∈(VTUVN)+，则FIRST(β)-{ε}∈FOLLOW(B)； for(n=k+1;n<=(int)strlen(rightStr[j])-1;n++)temp[n-k-1]=rightStr[j][n]; temp[strlen(rightStr[j])-k-1]='\0'; FIRST(-1,temp); //求FIRST(β) join(followSET[i],FirstForFollow,false);//把FIRST(β)中所有非空元素加入到FOLLOW(B)中 } } } followed[i]='1';//标识当前要求的非终结符的FOLLOW集已求过}/**************************************************判断读入文法是否为一个LL(1)文法 判断方法: 具有相同左部的规则的SELECT集两两不相交/**************************************************/intjudgeLL1(){inti,j,length,result=1; chartemp[100]; for(j=0;j<=99;j++) { //初始化 firstSET[j][0]='\0'; followSET[j][0]='\0'; singleFIRST[j][0]='\0'; selectSET[j][0]='\0'; FirstForFollow[j]='\0'; temp[j]='\0'; firsted[j]='0'; //用来记录该字符的FIRST集是否已求过.1表示已求,0表示未求 followed[j]='0'; //用来记录该字符的FOLLOW集是否已求过.1表示已求,0表示未求 }/**************************************************/ for(j=0;j<=(int)strlen(allSymbol)-1;j++) findSingleFIRST(j);//求单个符号的FIRST集合,结果保存在singleFIRST[]里 printf("\n单个符号的FIRST集合:\n"); fprintf(outparse,"\n单个符号的FIRST集合:\n"); for(j=0;j<=(int)strlen(allSymbol)-1;j++) { printf("\tFIRST(%c)={%s}\n",allSymbol[j],singleFIRST[j]); fprintf(outparse,"\tFIRST(%c)={%s}\n",allSymbol[j],singleFIRST[j]); }/**************************************************/printf("\n可推出空字的非终结符:%s",epsilon); fprintf(outparse,"\n可推出空字的非终结符:%s",epsilon);/************************************************** printf("\n求某一符号能否推出空字(这里用@表示空字,1表示可以推出空):\n"); fprintf(outparse,"\n求某一符号能否推出空字(这里用@表示空字,1表示可以推出空):\n"); printf("{"); fprintf(outparse,"{"); for(j=0;j<=(int)strlen(allSymbol)-1;j++){ printf("%d",someDerivateEpsilon(allSymbol[j])); fprintf(outparse,"%d",someDerivateEpsilon(allSymbol[j])); } printf("}"); fprintf(outparse,"}");/*****************求FIRST集************************/ for(i=0;i<=Pcount-1;i++) FIRST(i,rightStr[i]);//i为第几条产生式,求FIRST/******************求FOLLOW集**********************/ for(j=0;j<=(int)strlen(non_ter)-1;j++)//j为非终结符的序号{//求FOLLOW if(tempFOLLOW[j]==0) //字符数组tempFOLLOW[]默认数值都为零,表示其FOLLOW集未求 { tempFOLLOW[0]='\0'; FOLLOW(j); }}/*************打印各产生式右部符号串的FIRST集****************/ printf("\n消除左递归后各产生式右部符号串的FIRST集:\n"); fprintf(outparse,"\n消除左递归后各产生式右部符号串的FIRST集:\n"); for(i=0;i<=Pcount-1;i++) { printf("\tFIRST(%s)={%s}\n",rightStr[i],firstSET[i]); fprintf(outparse,"\tFIRST(%s)={%s}\n",rightStr[i],firstSET[i]); }/*****************打印各非终结符FOLLOW****************/ printf("\n消除左递归后各非终结符的FOLLOW集:\n"); fprintf(outparse,"\n消除左递归后各非终结符的FOLLOW集:\n");for(i=0;i<=(int)strlen(non_ter)-1;i++) { printf("\tFOLLOW(%c)={%s}\n",non_ter[i],followSET[i]); fprintf(outparse,"\tFOLLOW(%c)={%s}\n",non_ter[i],followSET[i]); }/*************求每一产生式的selectset集合************算法:对产生式A→x其SELECT集为:1.若x不能推出空字时,SELECT(A→x)=FIRST(x)2.若x可推出空字时,SELECT(A→x)=FIRST(x)-{ε}UFOLLOW(A)/**************************************************/ for(i=0;i<=Pcount-1;i++) { //先把当前产生式右部的FIRST集(一切非空元素,不包括ε)放入到当前产生式的SELECT集. join(selectSET[i],firstSET[i],false);//firstSET[]存放的是各产生式右部的FIRST集 for(j=0;j<=(int)strlen(rightStr[i])-1;j++) result*=someDerivateEpsilon(rightStr[i][j]);//右部符号x可推出空字"@" if(strlen(rightStr[i])==1&&rightStr[i][0]=='@') //形如产生式A->@ result=1; if(result==1) { for(j=0;;j++) if(allSymbol[j]==leftStr[i]) //j为左部符号在所有字符集中的位置 break; join(selectSET[i],followSET[j],false); //x=>*ε时,把FOLLOW(A)并入到SELECT(A→x)中 } }/*************打印每一产生式的selectset集合************/ printf("\n消除左递归后各产生式的SELECT集:\n"); fprintf(outparse,"\n消除左递归后各产生式的SELECT集:\n"); for(i=0;i<=Pcount-1;i++) { printf("\tSELECT(%s)={%s}\n",gramNewSet[i].formula,selectSET[i]); fprintf(outparse,"\tSELECT(%s)={%s}\n",gramNewSet[i].formula,selectSET[i]); } printf("\n"); fprintf(outparse,"\n");/*******************判断输入文法是否为LL(1)文法******** 具有相同左部的规则的SELECT集两两不相交 比较产生式形如A->B和A->C的SELECT集是否相交,即 SELECT(A->B)∩SELECT(A-C)=Φ 为空时表示此文法为LL(1)文法*******************************************************/ memcpy(temp,selectSET[0],strlen(selectSET[0])); temp[strlen(selectSET[0])]='\0'; for(i=1;i<=Pcount-1;i++) {length=strlen(temp); if(leftStr[i]==leftStr[i-1]) { join(temp,selectSET[i],true); if(strlen(temp)<length+strlen(selectSET[i])) return(0);//比较两个产生式的SELECT长度 } else { temp[0]='\0'; memcpy(temp,selectSET[i],strlen(selectSET[i])); temp[strlen(selectSET[i])]='\0'; } } return(1);}/**************************************************构造分析表analyseTable(LL(1)parsingtable)M[X,a]其中:X是非终结符,a是终结符或"#"1)若a∈SELECT(X->α),则M[X,a]=X->α,其中a∈Vt∪"#"2)M中不能由1)定义的元素均置为空(-1表示出错)/**************************************************/voidMM(){inti,j; intX; //X表示当前产生式左部在非终结符数组中的位置 inta; //a表示在当前产生式的SELECT集中的位置 //初始化分析表,全部置为空(-1) for(i=0;i<=(int)strlen(non_ter);i++) for(j=0;j<=(int)strlen(terSymbol)+1;j++) M[i][j]=-1;i=strlen(terSymbol);terSymbol[i]='#'; //将#加入终结符数组terSymbol[i+1]='\0'; for(i=0;i<=Pcount-1;i++) //查看每个产生式的SELECT集 {for(X=0;;X++) if(non_ter[X]==leftStr[i]) break; //求产生式左部非终结符的序号X for(j=0;j<=(int)strlen(selectSET[i])-1;j++)//对每个SELECT集中的所有元素进行操作 { if(FindChar(selectSET[i][j],terSymbol))//SELECT集中的每个元素都应该是终结符 { for(a=0;;a++) if(terSymbol[a]==selectSET[i][j]) break; //求产生式右部终结符的序号aM[X][a]=i; //记录分析表M[X][a]所要加入的产生式序号i } } }}/**************************************************总控程序算法/**************************************************/voidsyntax(){l: if((inscan=fopen(inscanfile,"rb"))==NULL) { printf("请输入词法分析文件名（包括路径）:"); scanf("%s",inscanfile); gotol; } inti=0,j,k,m,n,o,p,q; intl=0;charch; //分析句子当前指向的字符 charStack[200]; //定义存放文法符号的栈 chartemp[200][200]; charsentence[200]; //保存要分析的句子 charTopChar; //栈顶符号 int isshow=0; //判断是否要输出产生式.0表示不输出,1表示输出 charmatchchar; //当前匹配的字符/************************************************** 读词法分析文件里的单词类型/***