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

一 要求：建立一个针对LL(1)文法编译器的自动生成器。要完成此编译器的生成器需对源文件进行两遍处理：第一遍词法分析，第二遍语法分析。语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，然后建立词法分析器，包括词法分析主程序、扫描器部分、关键字表等。经词法分析后分别计算所输入的文法的每个非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是则输入文法符合LL(1)文法则可以进行分析。二 语法分析器实现语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。开始读入文法有效？判断句型报错结束语法分析程序流程图是LL(1) 文法？1.计算FIRST集对于文法G的任意一个符号串a=X1X2Xn可按下列步骤构造其FIRST(a)集合：令FIRST(a)=，i=1；(1) 若 XiVT，则XiFIRST(a)；(2) 若XiVN：若eFIRST(Xi)，则FIRST(Xi) FIRST(a)；若eFIRST(Xi)，则FIRST(Xi)-e FIRST(a)；i=i+1；重复(1)(2)，直到(XiVT(i=2,3,n)或XiVN 且eFIRST(Xi)或in为止)。(3)若对于一切1in，eFIRST(Xi)，则将e符号加进FIRST(a)。实例中求单个符号的FIRST集的算法描述如下：void findSingleFIRST(int i)参数i为符号在所有输入符号中的序号X等于指示器i所指向的符号在保存终结符元素的terSymbol数组查找Xif X为终结符(XVT )，then FIRST(X)=X在保存终结符元素的non_ter数组查找Xif X是非终结符(XVN )在所有产生式中查找X所在的产生式if 产生式右部第一个字符为终结符或空(即Xa (aVT)或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当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为XY1Y2Yk,若对一切1ik，均有FIRST(Yi)，则将符号加进FIRST(X) ) then把空字加入到当前字符X的FIRST集.else不能推出空字则结束循环标识当前字符X已查找其FIRST集. 2. 计算FOLLOW集FOLLOW集的构造可用如下方法来求：对于文法中的符号X VN ，其FOLLOW(A)集合可反复应用下列规则计算，直到FOLLOW(A)集合不再增大为止。(1)对于文法开始符号S，因为SS，故#FOLLOW(S)；(2)若Aa Bb，其中BVN，a(VT UVN)*、b(VT UVN)+，则FIRST(b)-eFOLLOW(B)；(3)若Aa B或Aa Bb (b e)，则FOLLOW(A) FOLLOW(B)。FOLLOW集的算法描述如下：void FOLLOW(int i)X为待求的非终结符把当前字符放到一临时数组tempFOLLOW中,标识求已求其FOLLOW集.避免循环递归if X为开始符号 then #FOLLOW(X)对全部的产生式找一个右部含有当前字符X的产生式注：比如求FOLLOW(B)则找AX或AaXb(b)的产生式if X在产生式右部的最后(形如产生式AaX) then查找非终结符A是否已经求过其FOLLOW集.避免循环递归if 非终结符A已求过其FOLLOW集 thenFOLLOW(A)FOLLOW(X)继续查下一条产生式是否含有Xelse求A之FOLLOW集，并标识为A已求其FOLLOW集else if X不在产生式右部的最后(形如AaBb) thenif右部X后面的符号串b能推出空字e then查找b是否已经求过其FOLLOW集.避免循环递归if 已求过b的FOLLOW集 then FOLLOW(A)FOLLOW(B)结束本次循环else if b不能推出空字 then 求FIRST(b)把FIRST(b)中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过3.计算SELECT集SELECT集的构造算法如下：对所有的规则产生式Ax：(1)若x不能推出空字e，则SELECT(Ax) = FIRST(x)；(2)若x可推出空字e，则SELECT(Ax)=FIRST(x)e U FOLLOW(A)。算法描述如下： for(i=0;i=产生式总数-1;i+)先把当前产生式右部的FIRST集(一切非空元素,不包括)放入到当前产生式的SELECT(i);if 产生式右部符号串可推出空字e then把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT(i)中4.判断是否LL(1)文法要判断是否为LL(1)文法，需要输入的文法G有如下要求：具有相同左部的规则的SELECT集两两不相交，即：SELECT(Aa) SELECT(Ab)= 如果输入的文法都符合以上的要求，则该文法可以用LL(1)方法分析。算法描述如下：把第一条产生式的SELECT(0)集放到一个临时数组temp中for(i=1;i=产生式总数-1;i+) 求temp的长度lengthif i指向的当前产生式的左部等于上一条产生式的左部 then把SELECT(i)并入到temp数组中If temp的长度小于length加上SELECT (i)的长度返回0else把temp清空把SELECT (i)存放到temp中结果返回1；源码/* LL(1)parsing grammar 25/4/2007*/#include #include #include #include #include using namespace std;/*/用于指向输入输出文件的指针FILE *inparse,*outparse,*inscan;/用于接收输入输出文件名char inparsefile300,outparsefile300,inscanfile300;/*/*定义产生式的语法集结构*/typedef structchar formula200;/产生式grammarElement;grammarElement gramOldSet200;/原始文法的产生式集grammarElement gramNewSet200;/消除左递归后文法的产生式集/*变量定义*/int grammarNum=0;/原始的产生式数目int Pcount=0;/分解的产生式的个数char startSymbol;/开始符号char terSymbol200;/终结符号char non_ter200;/非终结符号char allSymbol400;/所有符号char leftStr200;/消除左递归后产生式左部(不包括-)char rightStr200200;/消除左递归后产生式右部(不包括-)/*/char firstSET100100;/各产生式右部的FIRST集合char followSET100100;/各产生式左部的FOLLOW集合char singleFIRST100100;/所有单个符号的FIRST集合,函数findSingleFIRST(i)用到char selectSET100100;/各单个产生式的SELECT集合char tempFOLLOW100;/求FOLLOW集合时使用char FirstForFollow100;/求FOLLOW时存放某一符号串的FIRST集合char firsted100;/记录各符号的FIRST是否已求过,0和1表示其状态char followed100;/记录各符号的FOLLOW是否已求过,0和1表示其状态char epsilon100;/记录可直接推出()的符号char tempEpsilon100;/求someDerivateEpsilon()时使用,标识此字符已查找其是否可推出空字/*/int validity=1;/表示输入文法是否有效int isLL1=1;/表示输入文法是否为LL(1)文法int M200200;/分析表char choice;/用户输入时使用/*设置彩色文字*/void setcolor(unsigned short ForeColor=4,unsigned short BackGroundColor=0)HANDLE hCon=GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleTextAttribute(hCon,ForeColor|BackGroundColor);/* 查找字符是否在指定字符串中*/bool FindChar(char ch,char *p)int i;if(strlen(p)=0)return false;for(i=0;i90)return($);/如果大写字母已经用完,出错return(ch);/*判断输入的文法是直接左递归还是间接左递归2007-5-6/*int judgeLeftRecursive(char *point)int i,j,k=3,l;l=(int)strlen(point);for(i=0;i=l-1;i+)if(pointk=point0)return 1;/含有直接左递归else if(pointk!=point0&FindChar(pointk,non_ter)for(j=0;jA|,可以用非左递归的A-AA-A|来代替.PS:这里只是消除直接左递归*/void DirectLetfRecursive(char *point) /point指针指向传递过来的完整的产生式 int i,j;int m=0,n=3;char temp20,ch;ch=get_Char();/得到一个非终结符if(ch=$)printf(消除左递归时出错.原因:没有足够的符号(字母)可用.n);fprintf(outparse,消除左递归时出错.原因:没有足够的符号(字母)可用.n);system(pause);exit(0);i=strlen(non_ter);non_teri=ch;/把获得的非终结符加入到保存非终结符的non_ter数组中non_teri+1=0;for(j=0;jABa|Acfor(j=n+1;jABa的产生式,右部从A以后的字符串存入到临时数组temp中leftStrPcount=ch;/把得到的字符加入到左部数组leftStr中memcpy(rightStrPcount,temp,m);/把右部从A以后的字符串存入到新产生式的右部BarightStrPcountm=ch;/把得到的字符加入到新产生式右部的结尾.rightStrPcountm+1=0;/得到新的产生式A-BaAm=0;Pcount+;/产生式条数加1if(pointj=|)/把形如A-ABa|Ac的产生式分解成:A-ABa和A-Acn=j+1;/记下符号|的下一个字符的位置nbreak;else /如果|后的首符号和左部不同-A-ABa|CcleftStrPcount=ch;rightStrPcount0=;rightStrPcount1=0;/得到新的产生式A-Pcount+;for(j=n;jBb|c*/void nonLeftRecursive(char *point)/指针point指向当前要分解的产生式A-Bb|c int m=0,j;char temp20;for(j=3;jBb tempm+=pointj;else/产生式形如A-Bb|c,分解为A-Bb和A-c leftStrPcount=point0; memcpy(rightStrPcount,temp,m); rightStrPcountm=0;m=0;Pcount+; leftStrPcount=point0; memcpy(rightStrPcount,temp,m); rightStrPcountm=0; Pcount+;m=0;/* 最终的产生式*/void lastProduce()int i;for(i=0;i;strcat(gramNewSeti.formula,rightStri);/* 从文件读入一个文法/*/void getGrammar(char *t,char *n,char *leftStr,char rightStr200200)char NTtmp;/保存临时非终结符号char rightTmp200;/产生式右部char Vn200;/非终结符集non-terSymbol setchar Vt200;/终结符集terSymbol setint tmpIndex;int vtIndex,vnIndex;int i,j,k;int vtLen,vnLen;/终结符,非终结符char p200200;/保存产生式tmpIndex=0;vtIndex=0;vnIndex=0;while(!feof(inparse)/查找特定产生式的位置是否含有-字符串/检查是否是正确的产生式if(fscanf(inparse,%c-%srn,&NTtmp,&rightTmp)!=2)validity=0;/产生式无效break;/结束循环/求开始符号if(tmpIndex=0)startSymbol=NTtmp;gramOldSettmpIndex.formula0=NTtmp;gramOldSettmpIndex.formula1=-;gramOldSettmpIndex.formula2=;strcat(gramOldSettmpIndex.formula,rightTmp);strcpy(ptmpIndex,gramOldSettmpIndex.formula);tmpIndex+;for(i=0;i=65&rightTmpi=90|rightTmpi=|)for(j=0;j=65&rightTmpi=90)for(k=0;kvnIndex;k+)if(rightTmpi=Vnk)break;if(k=vnIndex)VnvnIndex=rightTmpi;vnIndex+;i+;VtvtIndex=0;VnvnIndex=0;vtLen=vtIndex;vnLen=vnIndex;grammarNum=tmpIndex;/*/memcpy(n,Vn,vnLen);/求得的非终结符保存到n,n指向non_termemcpy(t,Vt,vtLen);/终结符terSymbol/*/for(i=0;igrammarNum;i+)printf(读入的产生式 %d:t%sn,i+1,gramOldSeti.formula);fprintf(outparse,读入的产生式 %d:t%sn,i+1,gramOldSeti.formula);for(i=0;i=grammarNum-1;i+)/分解输入的各产生式if(pi3=pi0)DirectLetfRecursive(pi);/分解含有左递归的产生式elsenonLeftRecursive(pi);/*检查读入文法的正确性checkproduce*/void checkP()int i,j;for(i=0;i=Pcount-1;i+)if(!FindChar(leftStri,non_ter)printf(n文法错误.n);fprintf(outparse,n文法错误.n);printf(原因:非终结符 %c 不在非终结符集合中!n,leftStri);fprintf(outparse,原因:非终结符 %c 不在非终结符集合中!n,leftStri);printf(n按回车键结束.);system(pause);exit(0);for(j=0;j=65&rightStrij=90&!FindChar(rightStrij,leftStr)printf(n文法错误.n);fprintf(outparse,n文法错误.n);printf(原因:非终结符 %c 未曾在产生式左部出现!n,rightStrij);fprintf(outparse,原因:非终结符 %c 未曾在产生式左部出现!n,rightStrij);printf(n按回车键结束.);system(pause);exit(0);/*连接符号destination为目标符号串source为源符号串type为真是空字并入目串否则不并入/*/void join(char *destination,char *source,bool type) int i,j;for(i=0;i=(int)strlen(source)-1;i+) if(type=false&sourcei=);elsefor(j=0;j+) if(j(int)strlen(destination)&sourcei=destinationj) break;/目串中已含有源串中的字符,内循环结束 if(j=(int)strlen(destination) destinationj=sourcei;/把源串并入到目串的尾部 destinationj+1=0;/ break;/结束j循环.进入下一个外循环i+/* 求所有能直接推出()空字的符号结果保存到epsilon中/*/void allHasEpsilon(char ch)/*即求所有可推出()epsilon的符号*/char temp10;int i;for(i=0;iB,B可推出空) return(1);else if(j=1&FindChar(rightStri0,terSymbol)/右部长度为1但第一个字符为终结符,返回0(A-a,a为终结符)return(0);else for(k=0;kAB)mark=1;if(mark=1)/找到的字符与当前字符相同(A-AB)continue;/结束本次循环else/(mark等于0) for(k=0;k=j-1;k+)result*=someDerivateEpsilon(rightStrik);/查找右部符号是否可推出空字,把返回值赋给resulttemp0=rightStrik;temp1=0;join(tempEpsilon,temp,true);/把当前符号加入到临时数组tempEpsilon里. if(result=0&iPcount)/如果当前字符不能推出空字且还没搜索完全部的产生式,则跳出本次循环继续搜索下一条产生式 continue; else if(result=1&iPcount)/当前字符可推出空字,返回1 return(1);/* 求单个符号的FIRST集把求得结果保存到singleFIRST数组算法:(1)若XVT，则FIRST(X)=X。(2)若XVN，且具有形如Xa 的产生式(aVT)，或具有形如X的产生式，则把a或加进FIRST(X)。(3)设G中有形如XY1Y2Yk的产生式，若Y1VN，则把FIRST(Y1)中的一切非符号加进FIRST(X)；对于一切2ik，若Y1，Y2，Yi-1均为非终结符号，且FIRST(Yj)，1ji-1，则将FIRST(Yj)中的一切非符号加进FIRST(X)；若对一切1ik，均有FIRST(Yi)，则将符号加进FIRST(X)。/*/void findSingleFIRST(int i)/i为符号在所有输入符号中的序号 char X,temp20;int j,k,m;X=allSymboli;char ch=;/求所有能直接推出()空字的符号,结果保存到epsilon中allHasEpsilon(ch);if(FindChar(X,terSymbol) /若为终结符-XVT，则FIRST(X)=X singleFIRSTi0=X; singleFIRSTi1=0; else if(FindChar(X,non_ter) /若为非终结符for(j=0;j=Pcount-1;j+)/j为在所有产生式中的序列 if(leftStrj=X)/产生式右部第一个字符为终结符或空.-产生式Xa (aVT)或X,则把a或加进FIRST(X) if(FindChar(rightStrj0,terSymbol)|rightStrj0=) temp0=rightStrj0; temp1=0;join(singleFIRSTi,temp,true);/-XY1Y2Yk的产生式，若Y1VN，则把FIRST(Y1)中的一切非符号加进FIRST(X)else if(FindChar(rightStrj0,non_ter)/产生式右部第一个字符为非终结符if(rightStrj0=X)continue;/产生式右部的第一个符号等于当前字符则跳到下一条产生式进行查找for(k=0;k+)if(allSymbolk=rightStrj0)break;/求当前非终结符在所有字符集中的位置kif(firstedk=0)/5-5-2