LL1語法分析程序

第頁 《編譯原理》上機實驗報告題目：LL(1)語法分析程序1.設(shè)計要求（1）對輸入文法，它能判斷是否為LL(1)文法，若是，則轉(zhuǎn)（2）；否則報錯并終止；（2）輸入已知文法，由程序自動生成它的LL(1)分析表；（3）對于給定的輸入串，應(yīng)能判斷識別該串是否為給定文法的句型。2.分析該程序可分為如下幾步：（1）讀入文法（2）判斷正誤（3）若無誤，判斷是否為LL(1)文法（4）若是，構(gòu)造分析表；（5）由總控算法判斷輸入符號串是否為該文法的句型。有效？讀入文法開始3.流程圖有效？讀入文法開始 是是LL(1)文法？是LL(1)文法？結(jié)束報錯判斷句型 是結(jié)束報錯判斷句型4.源程序LL1語法分析程序#include<stdlib.h>#include<stdio.h>#include<string.h>intcount=0;/*分解的產(chǎn)生式的個數(shù)*/intnumber;/*所有終結(jié)符和非終結(jié)符的總數(shù)*/charstart;/*開始符號*/chartermin[50];/*終結(jié)符號*/charnon_ter[50];/*非終結(jié)符號*/charv[50];/*所有符號*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有單個符號的FIRST集合*/charselect[50][50];/*各單個產(chǎn)生式的SELECT集合*/charf[50],F[50];/*記錄各符號的FIRST和FOLLOW是否已求過*/charempty[20];/*記錄可直接推出^的符號*/charTEMP[50];/*求FOLLOW時存放某一符號串的FIRST集合*/intvalidity=1;/*表示輸入文法是否有效*/intll=1;/*表示輸入文法是否為LL(1)文法*/intM[20][20];/*分析表*/charchoose;/*用戶輸入時使用*/charempt[20];/*求_emp()時使用*/charfo[20];/*求FOLLOW集合時使用*/判斷一個字符是否在指定字符串中intin(charc,char*p) //inti; size_ti; if(strlen(p)==0) return(0); for(i=0;;i++) if(p[i]==c) return(1);/*若在，返回1*/ if(i==strlen(p)) return(0);/*若不在，返回0*/得到一個不是非終結(jié)符的符號charc() charc='A';while(in(c,non_ter)==1) c++; return(c);分解含有左遞歸的產(chǎn)生式voidrecur(char*point){/*完整的產(chǎn)生式在point[]中*/intj,m=0,n=3,k; chartemp[20],ch; ch=c();/*得到一個非終結(jié)符*/ k=strlen(non_ter); non_ter[k]=ch; non_ter[k+1]='\0'; for(j=0;size_t(j)<=strlen(point)-1;j++) if(point[n]==point[0]) {/*如果'|'后的首符號和左部相同*/ for(j=n+1;size_t(j)<=strlen(point)-1;j++) while(point[j]!='|'&&point[j]!='\0') temp[m++]=point[j++]; left[count]=ch; memcpy(right[count],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;size_t(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;分解不含有左遞歸的產(chǎn)生式voidnon_re(char*point)intm=0,j; chartemp[20]; for(j=3;size_t(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;讀入一個文法chargrammer(char*t,char*n,char*left,charright[50][50]) charvn[50],vt[50]; chars; charp[50][50]; inti,j,k; printf("\n請輸入文法的非終結(jié)符號串：");scanf("%s",vn); getchar();i=strlen(vn);memcpy(n,vn,i); n[i]='\0'; printf("請輸入文法的終結(jié)符號串：");scanf("%s",vt); getchar();i=strlen(vt);memcpy(t,vt,i); t[i]='\0';printf("請輸入文法的開始符號："); scanf("%c",&s); getchar(); printf("請輸入文法產(chǎn)生式的條數(shù)：");scanf("%d",&i); getchar();for(j=1;j<=i;j++) printf("請輸入文法的第%d條（共%d條）產(chǎn)生式：",j,i); scanf("%s",p[j-1]);getchar();for(j=0;j<=i-1;j++) if(p[j][1]!='-'||p[j][2]!='>') { printf("\ninputerror!"); validity=0; return('\0');}/*檢測輸入錯誤*/for(k=0;k<=i-1;k++){/*分解輸入的各產(chǎn)生式*/if(p[k][3]==p[k][0])recur(p[k]); else non_re(p[k]); return(s);將單個符號或符號串并入另一符號串voidmerge(char*d,char*s,inttype){/*d是目標(biāo)符號串，s是源串，type＝1，源串中的'^'一并并入目串； type＝2，源串中的'^'不并入目串*/inti,j; for(i=0;size_t(i)<=strlen(s)-1;i++)if(type==2&&s[i]=='^') else for(j=0;;j++) if(size_t(j)<strlen(d)&&s[i]==d[j]) break;if(size_t(j)==strlen(d)) d[j]=s[i]; d[j+1]='\0'; break;求所有能直接推出^的符號voidemp(charc){/*即求所有由'^'推出的符號*/ chartemp[10]; inti; 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(charc){/*若能推出，返回1；否則，返回0*/ inti,j,k,result=1,mark=0; chartemp[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的產(chǎn)生式*/j=strlen(right[i]);/*j為右部的長度*/ if(j==1&&in(right[i][0],empty)==1) return(1); elseif(j==1&&in(right[i][0],termin)==1) return(0); elsefor(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; elseif(result==1&&i<count) return(1);判斷讀入的文法是否正確intjudge()inti,j; for(i=0;i<=count-1;i++) if(in(left[i],non_ter)==0) {/*若左部不在非終結(jié)符中，報錯*/ printf("\nerror1!"); validity=0; return(0); for(j=0;size_t(j)<=strlen(right[i])-1;j++) if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^') {/*若右部某一符號不在非終結(jié)符、終結(jié)符中且不為'^'，報錯*/ printf("\nerror2!"); validity=0; return(0); return(1);求單個符號的FIRSTvoidfirst2(inti){/*i為符號在所有輸入符號中的序號*/charc,temp[20]; intj,k,m; c=v[i]; charch='^'; emp(ch); if(in(c,termin)==1)/*若為終結(jié)符*/first1[i][0]=c; first1[i][1]='\0'; elseif(in(c,non_ter)==1)/*若為非終結(jié)符*/ 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); elseif(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;size_t(k)<=strlen(right[j])-1;k++) empt[0]='\0'; if(_emp(right[j][k])==1&&size_t(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); elseif(_emp(right[j][k])==1&&size_t(k)==strlen(right[j])-1) temp[0]='^'; temp[1]='\0'; merge(first1[i],temp,1); else break; f[i]='1';求各產(chǎn)生式右部的FIRSTvoidFIRST(inti,char*p) intlength; intj,k,m; chartemp[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);elseif(_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); elseif(_emp(p[k])==0) break;求各產(chǎn)生式左部的FOLLOWvoidFOLLOW(inti) intj,k,m,n,result=1; charc,temp[20]; c=non_ter[i];/*c為待求的非終結(jié)符*/ 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的產(chǎn)生式*/ for(k=0;;k++) if(right[j][k]==c) break;/*k為c在該產(chǎn)生式右部的序號*/for(m=0;;m++) if(v[m]==left[j]) break;/*m為產(chǎn)生式左部非終結(jié)符在所有符號中的序號*/ if(size_t(k)==strlen(right[j])-1) {/*如果c在產(chǎn)生式右部的最后*/ 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不在產(chǎn)生式右部的最后*/ for(n=k+1;size_t(n)<=strlen(right[j])-1;n++) empt[0]='\0'; result*=_emp(right[j][n]); if(result==1) {/*如果右部c后面的符號串能推出^*/if(in(v[m],fo)==1) {/*避免循環(huán)遞歸*/ 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;size_t(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)文法intll1()inti,j,length,result=1; chartemp[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;size_t(j)<=strlen(v)-1;j++) first2(j);/*求單個符號的FIRST集合*/ printf("\nfirst1:"); for(j=0;size_t(j)<=strlen(v)-1;j++) printf("%c:%s",v[j],first1[j]);printf("\nempty:%s",empty); printf("\n:::\n_emp:"); for(j=0;size_t(j)<=strlen(v)-1;j++)printf("%d",_emp(v[j])); for(i=0;i<=count-1;i++) FIRST(i,right[i]);/*求FIRST*/ printf("\n"); for(j=0;size_t(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;size_t(i)<=strlen(non_ter)-1;i++) printf("%s",follow[i]); for(i=0;i<=count-1;i++) {/*求每一產(chǎn)生式的SELECT集合*/memcpy(select[i],first[i],strlen(first[i]));select[i][strlen(first[i])]='\0'; for(j=0;size_t(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);構(gòu)造分析表MvoidMM()inti,j,k,m; for(i=0;i<=19;i++) for(j=0;j<=19;j++) M[i][j]=-1;i=strlen(termin);termin[i]='#';/*將#加入終結(jié)符數(shù)組*/termin[i+1]='\0'; for(i=0;i<=count-1;i++)for(m=0;;m++) if(non_ter[m]==left[i]) break;/*m為產(chǎn)生式左部非終結(jié)符的序號*/ for(j=0;size_t(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為產(chǎn)生式右部終結(jié)符的序號*/M[m][k]=i;總控算法voidsyntax() inti,j,k,m,n,p,q;charch; charS[50],str[50];printf("請輸入該文法的句型："); 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; elseif(S[strlen(S)-1]=='#')printf("\n該符號串是文法的句型.");return; elseS[strlen(S)-1]='\0'; j++; ch=str[j]; elsefor(i=0;;i++) if(non_ter[i]==S[strlen(S)-1]) break; for(k=0;;k++) if(termin[k]==ch) break; if(size_t(k)==strlen(termin)) printf("\n詞法錯誤！"); return; if(M[i][k]==-1) printf("\n語法錯誤！")