【文章內(nèi)容簡(jiǎn)介】 ndex。 vnLen=vnIndex。 grammarNum=tmpIndex。 /**************************************************/ memcpy(n,Vn,vnLen)。//求得的非終結(jié)符保存到 n,n 指向 non_ter[] memcpy(t,Vt,vtLen)。//終結(jié)符 terSymbol[] /**************************************************/ for(i=0。igrammarNum。i++) { printf(讀入的產(chǎn)生式 %d:\t%s\n,i+1,gramOldSet[i].formula)。 fprintf(outparse,讀入的產(chǎn)生式 %d:\t%s\n,i+1,gramOldSet[i].formula)。 } for(i=0。i=grammarNum1。i++) //分解輸入的各產(chǎn)生式 { if(p[i][3]==p[i][0]) DirectLetfRecursive(p[i])。 //分解含有左遞歸的產(chǎn)生式 else nonLeftRecursive(p[i])。 } } /************************************************** 檢查讀入文法的正確性 checkproduce **************************************************/ void checkP() { int i,j。 for(i=0。i=Pcount1。i++) { if(!FindChar(leftStr[i],non_ter)) { printf(\n 文法錯(cuò)誤 .\n)。 fprintf(outparse,\n 文法錯(cuò)誤 .\n)。 printf(原因 :非終結(jié)符 %c 不在非終結(jié)符集合中 !\n,leftStr[i])。 fprintf(outparse,原因 :非終結(jié)符 %c 不在非終結(jié)符集合中 !\n,leftStr[i])。 printf(\n 按回車鍵結(jié)束 ...)。 system(pause)。 exit(0)。 } for(j=0。j=strlen(rightStr[i])1。j++) { if(!FindChar(rightStr[i][j],non_ter)amp。amp。!FindChar(rightStr[i][j],terSymbol)amp。amp。rightStr[i][j]!=39。@39。) { printf(\n 文法錯(cuò)誤 .\n)。 fprintf(outparse,\n 文法錯(cuò)誤 .\n)。 printf(原因 :右部符號(hào) %c 不是可用符號(hào) ,即不屬于非終結(jié)符也不屬于終結(jié)符或空字 !\n,rightStr[i][j])。 fprintf(outparse,原因 :右部符號(hào) %c 不是可用符號(hào) ,即不屬于非終結(jié)符也不屬于終結(jié)符或空字 !\n,rightStr[i][j])。 printf(\n 按回車鍵結(jié)束 ...)。 system(pause)。 exit(0)。 } if(rightStr[i][j]=65amp。amp。rightStr[i][j]=90amp。amp。!FindChar(rightStr[i][j],leftStr)) { printf(\n 文法錯(cuò)誤 .\n)。 fprintf(outparse,\n 文法錯(cuò)誤 .\n)。 printf(原因 :非終結(jié)符 %c 未曾在產(chǎn)生式左部出現(xiàn) !\n,rightStr[i][j])。 fprintf(outparse, 原因 : 非 終 結(jié) 符 %c 未 曾 在 產(chǎn) 生 式 左 部 出現(xiàn) !\n,rightStr[i][j])。 printf(\n 按回車鍵結(jié)束 ...)。 system(pause)。 exit(0)。 } } } } /************************************************** 連接符號(hào) destination 為目標(biāo)符號(hào)串 source 為源符號(hào)串 type 為真是空字 @并入目串否則不并入 /**************************************************/ void join(char *destination,char *source,bool type) { int i,j。 for(i=0。i=(int)strlen(source)1。i++) { if(type==falseamp。amp。source[i]==39。@39。) 。 else { for(j=0。j++) { if(j(int)strlen(destination)amp。amp。source[i]==destination[j]) break。 //目串中已含有源串中的字符 ,內(nèi)循環(huán)結(jié)束 if(j==(int)strlen(destination)) { destination[j]=source[i]。 //把源串并入到目串的尾部 destination[j+1]=39。\039。 // break。 //結(jié)束 j 循環(huán) .進(jìn)入下一個(gè)外循環(huán) i++ } } } } } /************************************************** 求所有能直接推出 @(ε )空字的符號(hào) 結(jié)果保存到 epsilon[]中 /**************************************************/ void allHasEpsilon(char ch) { /*即求所有可推出 @(ε )epsilon 的符號(hào) */ char temp[10]。 int i。 for(i=0。i=Pcount1。i++) { if(rightStr[i][0]==champ。amp。strlen(rightStr[i])==1) { temp[0]=leftStr[i]。 temp[1]=39。\039。 join(epsilon,temp,true)。 //allHasEpsilon(leftStr[i])。 } } } /************************************************** 求某一符號(hào)能否推出空字 @ /**************************************************/ int someDerivateEpsilon(char c) { //若能推出 @返回 1；否則，返回 0 int i,j,k,result=1,mark=0。 char temp[20]。 temp[0]=c。 temp[1]=39。\039。 join(tempEpsilon,temp,true)。//存放到一個(gè)臨時(shí)數(shù)組里 ,標(biāo)識(shí)此字符已查找其是否可推出空字 if(FindChar(c,epsilon))//如果 c 在可直接推出空字的 epsilon[]中 ,返回 1 return(1)。 for(i=0。i++) { if(i==Pcount) return(0)。 if(leftStr[i]==c) //找一個(gè)左部為 c 的產(chǎn)生式 { j=strlen(rightStr[i])。 //j 為 c 所在產(chǎn)生式右部的長(zhǎng)度 if(j==1amp。amp。FindChar(rightStr[i][0],epsilon))//右部長(zhǎng)度為 1 且右部第一個(gè)字符在epsilon[]中 .返回 1(AB,B 可推出空 ) return(1)。 else if(j==1amp。amp。FindChar(rightStr[i][0],terSymbol))//右部 長(zhǎng)度為 1 但第一個(gè)字符為終結(jié)符 ,返回 0(Aa,a 為終結(jié)符 ) return(0)。 else { for(k=0。k=j1。k++) if(FindChar(rightStr[i][k],tempEpsilon))// 查 找 臨 時(shí) 數(shù) 組tempEpsilon[].(AAB) mark=1。 if(mark==1)//找到的字符與當(dāng)前字符相同 (AAB) continue。//結(jié)束本 次循環(huán) else//(mark 等于 0) { for(k=0。k=j1。k++) { result*=someDerivateEpsilon(rightStr[i][k])。//查找右部符號(hào)是否可推出空字 ,把返回值賦給 result temp[0]=rightStr[i][k]。 temp[1]=39。\039。 join(tempEpsilon,temp,true)。// 把 當(dāng)前符 號(hào)加 入到 臨時(shí)數(shù) 組tempEpsilon[]里 . } } } if(result==0amp。amp。iPcount) //如果當(dāng)前字符不能推出空字且還沒(méi)搜索完全部的產(chǎn)生式 ,則跳出本次循環(huán)繼續(xù)搜索下一條產(chǎn)生式 continue。 else if(result==1amp。amp。iPcount)//當(dāng)前字符可推出空字 ,返回 1 return(1)。 } } } /************************************************** 求單個(gè)符號(hào)的 FIRST 集 把求得結(jié)果保存到 singleFIRST[]數(shù)組 算法 : (1)若 X∈ VT，則 FIRST(X)={X}。 (2)若 X∈ VN，且具有形如 X→ a 的產(chǎn)生式 (a∈ VT)，或具有形如 X→ε的產(chǎn)生式，則把 a 或ε加進(jìn) FIRST(X)。 (3)設(shè) G 中有形如 X→ Y1Y2… Yk 的產(chǎn)生式，若 Y1∈ VN，則把 FIRST(Y1)中的一切非ε符號(hào)加進(jìn) FIRST(X)； 對(duì)于一切 2≤ i≤ k，若 Y1， Y2，…， Yi1 均為非終結(jié)符號(hào)，且ε∈ FIRST(Yj)， 1≤ j≤ i1， 則將 FIRST(Yj)中的一切非ε符號(hào)加進(jìn) FIRST(X)；若對(duì)一切 1≤ i≤ k，均有ε∈ FIRST(Yi)，則將ε∈符號(hào)加進(jìn) FIRST(X)。 /**************************************************/ void findSingleFIRST(int i) { //i為符號(hào)在所有輸入符號(hào)中的序號(hào) char X,temp[20]。 int j,k,m。 X=allSymbol[i]。 char ch=39。@39。 //求所有能直接推出 @(ε )空字的符號(hào) ,結(jié)果保存到 epsilon[]中 allHasEpsilon(ch)。 if(FindChar(X,terSymbol)) //若為終結(jié)符 X∈ VT，則 FIRST(X)={X} { singleFIRST[i][0]=X。 singleFIRST[i][1]=39。\039。 } else if(FindChar(X,non_ter)) //若為非終結(jié)符 { for(j=0。j=Pcount1。j++) //j 為在 所有產(chǎn)生式中的序列 { if(leftStr[j]==X) { //產(chǎn)生式右部第一個(gè)字符為終結(jié)符或空 .產(chǎn)生式 X→ a (a∈ VT)或 X→ε ,則把 a 或ε加進(jìn) FIRST(X) if(FindChar(rightStr[j][0],terSymbol)||rightStr[j][0]==39。@39。) { temp[0]=rightStr[j][0]。 temp[1]=39。\039。