【正文】 count=0。 //開始符號 char terSymbol[200]。 //非終結符號 char allSymbol[400]。 //消除左遞歸后產生式左部 (不包括 ) char rightStr[200][200]。//各產生式右部的 FIRST 集合 char followSET[100][100]。 //所有單個符號的 FIRST 集合 ,函數 findSingleFIRST(i)用到 char selectSET[100][100]。 //求 FOLLOW 集合時使用 char FirstForFollow[100]。 //記錄各符號的 FIRST 是否已求過 ,0 和 1 表示其狀態(tài) char followed[100]。 //記錄可直接推出 (ε )的符號 char tempEpsilon[100]。 //表示輸入文法是否有效 int isLL1=1。 //分析表 char choice。 SetConsoleTextAttribute(hCon,ForeColor|BackGroundColor)。 if(strlen(p)==0) return false。i(int)strlen(p)。 } return false。A39。 if(ch90) return(39。)。 } /************************************************** 判斷輸入的文法是直接左遞歸還是間接左遞歸 202156 /************************************************** int judgeLeftRecursive(char *point) { int i,j,k=3,l。 for(i=0。i++) { if(point[k]=point[0]) return 1。amp。jgrammarNum。 } /************************************************** 分解含有直接左遞歸的產生式 eliminate leftStr recursive 產生式 AAα |β ,可以用非左遞歸的 AβA39。αA39。 int m=0,n=3。 ch=get_Char()。$39。 fprintf(outparse,消除左遞歸時出錯 .原因 :沒有足夠的符號 (字母 )可用 .\n)。 exit(0)。 non_ter[i]=ch。\039。j=(int)strlen(point)1。j=(int)strlen(point)1。|39。amp。\039。 //把形如 AABa的產生式 ,右部從 A以后的字符串存入到臨時數組 temp[]中 leftStr[Pcount]=ch。//把右部從 A 以后的字符串存入到新產生式的右部 Ba rightStr[Pcount][m]=ch。\039。BaA39。 Pcount++。|39。 //記下符號 |的下一個字符的位置 n break。 rightStr[Pcount][0]=39。 rightStr[Pcount][1]=39。 //得到新的產生式 A39。 for(j=n。j++) { if(point[j]!=39。) temp[m++]=point[j]。 memcpy(rightStr[Pcount],temp,m)。 rightStr[Pcount][m+1]=39。 m=0。 } } leftStr[Pcount]=point[0]。 rightStr[Pcount][m]=ch。\039。 m=0。 char temp[20]。j=(int)strlen(point)1。|39。 else//產生式形如 ABb|c,分解為 ABb 和 Ac { leftStr[Pcount]=point[0]。 rightStr[Pcount][m]=39。 m=0。 } } leftStr[Pcount]=point[0]。 rightStr[Pcount][m]=39。 Pcount++。 } /************************************************** 最終的產生式 **************************************************/ void lastProduce() { int i。iPcount。 gramNewSet[i].formula[1]=39。 gramNewSet[i].formula[2]=39。 strcat(gramNewSet[i].formula,rightStr[i])。//保存臨時非終結符號 char rightTmp[200]。//非終結符集 nonterSymbol set char Vt[200]。 int vtIndex,vnIndex。 int vtLen,vnLen。//保存產生式 tmpIndex=0。 vnIndex=0。NTtmp,amp。 //產生式無效 break。 } gramOldSet[tmpIndex].formula[0]=NTtmp。39。39。 strcpy(p[tmpIndex],gramOldSet[tmpIndex].formula)。 for(i=0。i++) if(NTtmp==Vn[i]) break。 vnIndex++。 while(rightTmp[i]!=39。) { //不是非終結符 (大寫字母 AZ),把元符號 |屏蔽 .(求終結符 ) if(!(rightTmp[i]=65amp。rightTmp[i]=90||rightTmp[i]==39。)) { for(j=0。j++) if(rightTmp[i]==Vt[j]) break。 vtIndex++。amp。kvnIndex。 if(k==vnIndex) { Vn[vnIndex]=rightTmp[i]。 } } i++。\039。\039。 vnLen=vnIndex。 /**************************************************/ memcpy(n,Vn,vnLen)。//終結符 terSymbol[] /**************************************************/ for(i=0。i++) { printf(讀入的產生式 %d:\t%s\n,i+1,gramOldSet[i].formula)。 } for(i=0。i++) //分解輸入的各產生式 { if(p[i][3]==p[i][0]) DirectLetfRecursive(p[i])。 } } /************************************************** 檢查讀入文法的正確性 checkproduce **************************************************/ void checkP() { int i,j。i=Pcount1。 fprintf(outparse,\n 文法錯誤 .\n)。 fprintf(outparse,原因 :非終結符 %c 不在非終結符集合中 !\n,leftStr[i])。 system(pause)。 } for(j=0。j++) { if(!FindChar(rightStr[i][j],non_ter)amp。!FindChar(rightStr[i][j],terSymbol)amp。rightStr[i][j]!=39。) { printf(\n 文法錯誤 .\n)。 printf(原因 :右部符號 %c 不是可用符號 ,即不屬于非終結符也不屬于終結符或空字 !\n,rightStr[i][j])。 printf(\n 按回車鍵結束 ...)。 exit(0)。amp。amp。 fprintf(outparse,\n 文法錯誤 .\n)。 fprintf(outparse, 原因 : 非 終 結 符 %c 未 曾 在 產 生 式 左 部 出現 !\n,rightStr[i][j])。 system(pause)。 } } } } /************************************************** 連接符號 destination 為目標符號串 source 為源符號串 type 為真是空字 并入目串否則不并入 /**************************************************/ void join(char *destination,char *source,bool type) { int i,j。i=(int)strlen(source)1。amp。39。 else { for(j=0。amp。 //目串中已含有源串中的字符 ,內循環(huán)結束 if(j==(int)strlen(destination)) { destination[j]=source[i]。\039。 //結束 j 循環(huán) .進入下一個外循環(huán) i++ } } } } } /************************************************** 求所有能直接推出 (ε )空字的符號 結果保存到 epsilon[]中 /**************************************************/ void allHasEpsilon(char ch) { /*即求所有可推出 (ε )epsilon 的符號 */ char temp[10]。 for(i=0。i++) { if(rightStr[i][0]==champ。strlen(rightStr[i])==1) { temp[0]=leftStr[i]。\039。 //allHasEpsilon(leftStr[i])。 char temp[20]。 temp[1]=39。 join(tempEpsilon,temp,true)。 for(i=0。 if(leftStr[i]==c) //找一個左部為 c 的產生式 { j=strlen(rightStr[i])。amp。 else if(j==1amp。FindChar(rightStr[i][0],terSymbol))//右部 長度為 1 但第一個字符為終結符 ,返回 0(Aa,a 為終結符 ) return(0)。k=j1。 if(mark==1)//找到的字符與當前字符相同 (AAB) continue。k=j1。//查找右部符號是否可推出空字 ,把返回值賦給 result temp[0]=rightStr[i][k]。\039。// 把 當前符 號加 入到 臨時數 組tempEpsilon[]里 . } } } if(result==0amp。iPcount) //如果當前字符不能推出空字且還沒搜索完全部的產生式 ,則跳出本次循環(huán)繼續(xù)搜索下一條產生式 continue。amp。 } } } /************************************************** 求單個符號的 FIRST 集 把求得結果保存到 singleFIRST[]數組 算法 : (1)若 X∈ VT，則 FIRST(X)={X}。 (3)設 G 中有形如 X→ Y1Y2… Yk 的產生式，若 Y1∈ VN，則把 FIRST(Y1)中的一切非ε符號加進 FIRST(X)； 對于一切 2≤ i≤ k，若 Y1， Y2，…， Yi1 均為非終結符號，且ε∈ FIRST(Yj)， 1≤