【導(dǎo)讀】建立一個針對LL文法編譯器的自動生成器。對源文件進行兩遍處理：第一遍詞法分析，第二遍語法分析。首先輸入定義好的文法書寫文件(所用的文法可以用LL(1). 分析)，然后建立詞法分析器，包括詞法分析主程序、掃描器部分、關(guān)鍵字表等。法符合LL文法則可以進行分析。語義分析和代碼生成作準備。語法分析程序的流程圖如圖5-4所示。Xn可按下列步驟構(gòu)造其FIRST(?求得結(jié)果并入到X的FIRST集.Yk,若對一切1≤i≤k，均有ε∈FIRST，則將ε∈符號加。把空字加入到當(dāng)前字符X的FIRST集.直到FOLLOW集合不再增大為止。elseifX不在產(chǎn)生式右部的最后(形如A→?是否已經(jīng)求過其FOLLOW集.避免循環(huán)遞歸。if產(chǎn)生式右部符號串可推出空字?

　　

【正文】 n++) { tempEpsilon[0]=39。\039。 //把 tempEpsilon[]置空 , // 因為求此字符是否可推出空字someDerivateEpsilon(c)時用到 result*=someDerivateEpsilon(rightStr[j][n])。 } if(result==1)//如果右部 X 后面的符號串能推出 @A→α Bβ (β =*ε )則FOLLOW(A)∈ FOLLOW(B) { if(FindChar(allSymbol[m],tempFOLLOW))//查找該非終結(jié)符是否已經(jīng)求過其 FOLLOW 集 .避免循環(huán)遞歸 { join(followSET[i],followSET[m],false)。//FOLLOW(A) ∈FOLLOW(B) continue。 //結(jié)束本次循環(huán) } if(followed[m]==39。039。) { FOLLOW(m)。 followed[m]=39。139。 } join(followSET[i],followSET[m],false)。//FOLLOW(A)∈ FOLLOW(B) } //若 A→α Bβ，其中 B∈ VN，α∈ (VT U VN)*、β∈ (VT U VN)+，則FIRST(β ){ε }∈ FOLLOW(B)； for(n=k+1。n=(int)strlen(rightStr[j])1。n++) temp[nk1]=rightStr[j][n]。 temp[strlen(rightStr[j])k1]=39。\039。 FIRST(1,temp)。 //求 FIRST(β ) join(followSET[i],FirstForFollow,false)。//把 FIRST(β )中所有非空元素加入到 FOLLOW(B)中 } } } followed[i]=39。139。//標識當(dāng)前要求的非終結(jié)符的 FOLLOW 集已求過 } /************************************************** 判斷讀入文法是否為一個 LL(1)文法 判斷方法 : 具有相同左部的規(guī)則的 SELECT 集兩兩不相交 /**************************************************/ int judgeLL1() { int i,j,length,result=1。 char temp[100]。 for(j=0。j=99。j++) { //初始化 firstSET[j][0]=39。\039。 followSET[j][0]=39。\039。 singleFIRST[j][0]=39。\039。 selectSET[j][0]=39。\039。 FirstForFollow[j]=39。\039。 temp[j]=39。\039。 firsted[j]=39。039。 //用來記錄該字符的 FIRST 集是否已求過 .1 表示已求 ,0表示未求 followed[j]=39。039。 //用來記錄該字符的 FOLLOW 集是否已求過 .1 表示已求 ,0 表示未求 } /**************************************************/ for(j=0。j=(int)strlen(allSymbol)1。j++) findSingleFIRST(j)。 //求單個符號的 FIRST 集合 ,結(jié)果保存在 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 可推出空字的非終結(jié)符 :%s,epsilon)。 fprintf(outparse,\n 可推出空字的非終結(jié)符 :%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=Pcount1。i++) FIRST(i,rightStr[i])。 //i 為第幾條產(chǎn)生式 ,求 FIRST /******************求 FOLLOW集 **********************/ for(j=0。j=(int)strlen(non_ter)1。j++)//j 為非終結(jié)符的序號 { //求 FOLLOW if(tempFOLLOW[j]==0) //字符數(shù)組 tempFOLLOW[]默認數(shù)值都為零 ,表示其 FOLLOW 集未求 { tempFOLLOW[0]=39。\039。 FOLLOW(j)。 } } /*************打印各產(chǎn)生式右部符號串的 FIRST 集 ****************/ printf(\n 消除左遞歸后各產(chǎn)生式右部符號串的 FIRST 集 :\n)。 fprintf(outparse,\n 消除左遞歸后各產(chǎn)生式右部符號串的 FIRST 集 :\n)。 for(i=0。i=Pcount1。i++) { printf(\tFIRST( %s ) = { %s }\n,rightStr[i],firstSET[i])。 fprintf(outparse,\tFIRST( %s ) = { %s }\n,rightStr[i],firstSET[i])。 } /*****************打印各非終結(jié)符 FOLLOW****************/ printf(\n 消除左遞歸后各非終結(jié)符的 FOLLOW 集 :\n)。 fprintf(outparse,\n 消除左遞歸后各非終結(jié)符的 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])。 } /*************求每一產(chǎn)生式的 selectset 集合 ************ 算法 : 對產(chǎn)生式 A→ x其 SELECT 集為 : x不能推出空字時 ,SELECT(A→ x)=FIRST(x) x可推出空字時 ,SELECT(A→ x)=FIRST(x){ε } U FOLLOW(A) /**************************************************/ for(i=0。i=Pcount1。i++) { //先把當(dāng)前產(chǎn)生式右部的 FIRST 集 (一切非空元素 ,不包括ε )放入到當(dāng)前產(chǎn)生式的SELECT 集 . join(selectSET[i],firstSET[i],false)。//firstSET[]存放的是各產(chǎn)生式右部的 FIRST 集 for(j=0。j=(int)strlen(rightStr[i])1。j++) result*=someDerivateEpsilon(rightStr[i][j])。//右部符號 x可推出空字 @ if(strlen(rightStr[i])==1amp。amp。rightStr[i][0]==39。@39。) //形如產(chǎn)生式 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)中 } } /*************打印每一產(chǎn)生式的 selectset 集合 ************/ printf(\n 消除左遞歸后各產(chǎn)生式的 SELECT 集 :\n)。 fprintf(outparse,\n 消除左遞歸后各產(chǎn)生式的 SELECT 集 :\n)。 for(i=0。i=Pcount1。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)文法 ******** 具有相同左部的規(guī)則的 SELECT 集兩兩不相交 比較產(chǎn)生式形如 AB 和 AC 的 SELECT 集是 否相交 ,即 SELECT(AB) ∩ SELECT(AC) = Φ 為空時表示此文法為 LL(1)文法 *******************************************************/ memcpy(temp,selectSET[0],strlen(selectSET[0]))。 temp[strlen(selectSET[0])]=39。\039。 for(i=1。i=Pcount1。i++) { length=strlen(temp)。 if(leftStr[i]==leftStr[i1]) { join(temp,selectSET[i],true)。 if(strlen(temp)length+strlen(selectSET[i])) return(0)。//比較兩個產(chǎn)生式的 SELECT 長度 } else { temp[0]=39。\039。 memcpy(temp,selectSET[i],strlen(selectSET[i]))。 temp[strlen(selectSET[i])]=39。\039。 } } return(1)。 } /************************************************** 構(gòu)造分析表 analyseTable(LL(1) parsing table) M[X,a]其中 : X 是非終結(jié)符 ,a 是終結(jié)符或 1)若 a∈ SELECT(Xα ),則 M[X,a]=Xα ,其中 a∈ Vt∪ 2)M 中不能由 1)定義的元素均置為空 (1 表示出錯 ) /*****************