語法分析器的設(shè)計(jì)實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)內(nèi)容語法分析程序用LL（1)語法分析方法。一方面輸入定義好的文法書寫文獻(xiàn)(所用的文法可以用LL（１)分析)，先求出所輸入的文法的每個(gè)非終結(jié)符是否能推出空，再分別計(jì)算非終結(jié)符號(hào)的FIRＳT集合,每個(gè)非終結(jié)符號(hào)的ＦＯＬLOW集合,以及每個(gè)規(guī)則的SELECT集合，并判斷任意一個(gè)非終結(jié)符號(hào)的任意兩個(gè)規(guī)則的SＥLEＣT集的交集是不是都為空，假如是，則輸入文法符合LL（1)文法，可以進(jìn)行分析。對于文法：Ｇ[E]:E->Ｅ+T｜ＴT->T*F｜FF->i|(Ｅ)分析句子i+i*i是否符合文法。二、基本思想1、語法分析器實(shí)現(xiàn)語法分析是編譯過程的核心部分，它的重要任務(wù)是按照程序的語法規(guī)則,從由詞法分析輸出的源程序符號(hào)串中辨認(rèn)出各類語法成分,同時(shí)進(jìn)行詞法檢查,為語義分析和代碼生成作準(zhǔn)備。這里采用自頂向下的LＬ(1)分析方法。語法分析程序的流程圖如圖5-4所示。開始開始讀入文法有效？判斷句型報(bào)錯(cuò)結(jié)束語法分析程序流程圖是LL(1)文法？該程序可分為如下幾步:(1)讀入文法(2）判斷正誤(３)若無誤，判斷是否為LL（1)文法（4）若是，構(gòu)造分析表;(５)由句型判別算法判斷輸入符號(hào)串是為該文法的句型。三、核心思想該分析程序有１5部分組成：(1）一方面定義各種需要用到的常量和變量;（2）判斷一個(gè)字符是否在指定字符串中；（３)讀入一個(gè)文法;(４)將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串;（5)求所有能直接推出＆的符號(hào);(6)求某一符號(hào)能否推出‘&’;（7）判斷讀入的文法是否對的;（8）求單個(gè)符號(hào)的ＦＩRＳT；（９)求各產(chǎn)生式右部的FIＲＳＴ;（1０）求各產(chǎn)生式左部的FOLＬOW；（11)判斷讀入文法是否為一個(gè)LＬ（1)文法;(12）構(gòu)造分析表M;(１３）句型判別算法；(14）一個(gè)用戶調(diào)用函數(shù)；(１5）主函數(shù);下面是其中幾部分程序段的算法思想：１、求能推出空的非終結(jié)符集Ⅰ、實(shí)例中求直接推出空的ｅmpｔｙ集的算法描述如下:voidemｐ(charc){參數(shù)c為空符號(hào) ｃhａrｔemp[1０];定義臨時(shí)數(shù)組?intｉ；?fｏr(i=0；ｉ<＝counｔ-1;i++)從文法的第一個(gè)產(chǎn)生式開始查找?{ ?ｉf產(chǎn)生式右部第一個(gè)符號(hào)是空符號(hào)并且右部長度為1,then將該條產(chǎn)生式左部符號(hào)保存在臨時(shí)數(shù)組temp中將臨時(shí)數(shù)組中的元素合并到記錄可推出&符號(hào)的數(shù)組emｐty中。?}Ⅱ、求某一符號(hào)能否推出＇＆'ｉnt_emp(ｃharc){//若能推出＆，返回1;否則,返回0 ｉntｉ,j，k,ｒesult＝1,mark=0; chａｒtemp[20];?temp[0]=c; temp[１］='＼0';?存放到一個(gè)臨時(shí)數(shù)組ｅmｐt里,標(biāo)記此字符已查找其是否可推出空字假如c在可直接推出空字的empty[]中,返回1 for(i=0;;i++） { ?ｉf(i==count)ｒetuｒn(0);??找一個(gè)左部為c的產(chǎn)生式?j=strlen(ｒight［i])；//ｊ為c所在產(chǎn)生式右部的長度? ?if右部長度為1且右部第一個(gè)字符在empｔy［]中．then返回1（Ａ-＞B，B可推出空)???if右部長度為1但第一個(gè)字符為終結(jié)符,tｈen返回0(A->a,ａ為終結(jié)符)???else ??{??? fｏr(k=0；ｋ＜=j-1；k+＋)? ??{ ???查找臨時(shí)數(shù)組eｍpt[].并標(biāo)記maｒk－=１(Ａ－>AB)?? ｉf找到的字符與當(dāng)前字符相同(Ａ-＞AB)?? ? 結(jié)束本次循環(huán) ??else(maｒk等于０)查找右部符號(hào)是否可推出空字,把返回值賦給result ?? 把當(dāng)前符號(hào)加入到臨時(shí)數(shù)組eｍpｔ[]里．｝ ? iｆ當(dāng)前字符不能推出空字且還沒搜索完所有的產(chǎn)生式then跳出本次循環(huán)繼續(xù)搜索下一條產(chǎn)生式? ｅｌseif/／當(dāng)前字符可推出空字,返回1}}}??2、計(jì)算每個(gè)符號(hào)的firsｔ集：實(shí)例中求單個(gè)符號(hào)的ＦIRST集的算法描述如下：vｏｉｄｆirsｔ2(iｎtｉ){ 參數(shù)i為符號(hào)在所有輸入符號(hào)中的序號(hào)?ｃ等于指示器i所指向的符號(hào)?在保存終結(jié)符元素的tｅｒｍｉn[]數(shù)組查找cifｃ為終結(jié)符（c∈VT)，tｈenFIRＳT(c)={c｝在保存終結(jié)符元素的ｎoｎ_tｅr[］數(shù)組查找cｉfｃ是非終結(jié)符(ｃ∈VN）在所有產(chǎn)生式中查找ｃ所在的產(chǎn)生式ｉｆ產(chǎn)生式右部第一個(gè)字符為終結(jié)符或空(即c→a(a∈VT）或c→&)ｔhen把a(bǔ)或＆加進(jìn)FIＲST(ｃ）iｆ產(chǎn)生式右部第一個(gè)字符為非終結(jié)符ｔheｎiｆ產(chǎn)生式右部的第一個(gè)符號(hào)等于當(dāng)前字符theｎ跳到下一條產(chǎn)生式進(jìn)行查找求當(dāng)前非終結(jié)符在所有字符集中的位置if當(dāng)前非終結(jié)符還沒求其FＩＲST集theｎ查找它的FIRSＴ集并標(biāo)記此符號(hào)已求其FＩRST集?求得結(jié)果并入到c的FＩRＳＴ集.ｉｆ當(dāng)前產(chǎn)生式右部符號(hào)可推出空字且當(dāng)前字符不是右部的最后一個(gè)字符then獲取右部符號(hào)下一個(gè)字符在所有字符集中的位置if此字符的ＦIRST集尚未查找then找其FＩRＳＴ集,并標(biāo)其查找狀態(tài)為1把求得的FＩRST集并入到c的ＦIRＳＴ集.if當(dāng)前右部符號(hào)串可推出空且是右部符號(hào)串的最后一個(gè)字符(即產(chǎn)生式為c→Y1Ｙ2…Yｋ,若對一切1<=i<=k,均有＆∈FIRST（Yi)，則將&∈符號(hào)加進(jìn)ＦIRST(c)）ｔhen把空字加入到當(dāng)前字符c的FIRST集. eｌsｅ不能推出空字則結(jié)束循環(huán)標(biāo)記當(dāng)前字符c已查找其FIRST集.}３．計(jì)算FOLLOW集ＦOLLOW集的構(gòu)造可用如下方法來求：對于文法中的符號(hào)XVN,其ＦOLLOW(Ａ）集合可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到ＦOLLOW(A)集合不再增大為止。(1）對于文法開始符號(hào)S，由于ＳS，故＃FOLLOW(S);(2)若Ａ→B，其中ＢVN，(ＶTVＮ)*、(VＴVＮ)＋,則FIＲST()－{e}ＦＯLLOW(Ｂ)；（3)若A→B或A→B(e)，則FOLLOW(A)FＯLLOW（B)。 ＦOLＬOW集的算法描述如下: voidFOLLOW(ｉnti)??X為待求的非終結(jié)符把當(dāng)前字符放到一臨時(shí)數(shù)組ｆoｌl［］中,標(biāo)記求已求其FＯLLOW集.避免循環(huán)遞歸ｉfX為開始符號(hào)then#∈ＦOLLＯW(Ｘ) 對所有的產(chǎn)生式找一個(gè)右部具有當(dāng)前字符X的產(chǎn)生式注:比如求FOLLOW(B)則找Ａ→αX或A→X(ε)的產(chǎn)生式ifX在產(chǎn)生式右部的最后(形如產(chǎn)生式A→X)then查找非終結(jié)符Ａ是否已經(jīng)求過其ＦOLＬＯW集．避免循環(huán)遞歸if非終結(jié)符Ａ已求過其ＦOＬLOW集thenＦOＬLOW(A)∈FOＬＬOW(X）繼續(xù)查下一條產(chǎn)生式是否具有Ｘelse求A之ＦOLＬOW集,并標(biāo)記為A已求其FOLLOＷ集elseifX不在產(chǎn)生式右部的最后(形如A→B)theｎif右部X后面的符號(hào)串能推出空字ｔhｅn查找是否已經(jīng)求過其FOLLOＷ集．避免循環(huán)遞歸iｆ已求過的FＯLＬOW集thenFOLLＯW(A)∈FOＬＬＯW（B)結(jié)束本次循環(huán)ｅlseif不能推出空字then求FIRST()把FIRＳT()中所有非空元素加入到FOLLOW（B)中標(biāo)記當(dāng)前規(guī)定的非終結(jié)符X的FOLＬＯW集已求過4．計(jì)算SＥLＥCＴ集SＥLECＴ集的構(gòu)造算法如下：對所有的規(guī)則產(chǎn)生式A→x：(1)若x不能推出空字e,則SＥLＥＣＴ(A→ｘ)＝FIＲSＴ(ｘ）;(２)若x可推出空字e,則ＳELＥCT（A→x)＝FIＲST(ｘ)–{}FOLLOW(A）。算法描述如下:?ｆor(i＝0;i<=產(chǎn)生式總數(shù)－1;i++)先把當(dāng)前產(chǎn)生式右部的FIRST集(一切非空元素,不涉及ε)放入到當(dāng)前產(chǎn)生式的SELEＣT(i）; if產(chǎn)生式右部符號(hào)串可推出空字ethｅn把i指向的當(dāng)前產(chǎn)生式左部的非終結(jié)符號(hào)的FOLＬOW集并入到ＳELEＣＴ(i)中5.判斷是否ＬL(1）文法要判斷是否為LL（1)文法,需要輸入的文法G有如下規(guī)定:具有相同左部的規(guī)則的SELECＴ集兩兩不相交，即:SELECT(A→)∩SELECT(A→)=?假如輸入的文法都符合以上的規(guī)定,則該文法可以用LL（１）方法分析。算法描述如下：?把第一條產(chǎn)生式的SELECＴ(0）集放到一個(gè)臨時(shí)數(shù)組temｐ[]中?ｆor(i=1；ｉ＜=產(chǎn)生式總數(shù)-1;i＋+)求tｅmp的長度leｎgth??ｉｆi指向的當(dāng)前產(chǎn)生式的左部等于上一條產(chǎn)生式的左部then? 把SＥＬＥCＴ(i)并入到temp數(shù)組中???Iftemp的長度小于ｌeｎｇｔh加上ＳEＬECＴ（ｉ)的長度 返回0 elｓｅ把temp清空把SELＥCT（i)存放到ｔeｍｐ中結(jié)果返回1;四、算法#iｎｃlｕｄe<stdlｉb．h>＃incｌudｅ＜ｓｔdio.h>#iｎclude<sｔrｉｎg.ｈ>/＊***＊*＊＊＊*****＊*＊*****＊******＊****＊*＊******／iｎtcounｔ=０；//產(chǎn)生式的個(gè)數(shù)intnuｍber;//所有終結(jié)符和非終結(jié)符的總數(shù)charｓtaｒt；/／開始符號(hào)ｃｈａrｔerｍin［５0];/／終結(jié)符號(hào)chaｒnon_teｒ[50］;//非終結(jié)符號(hào)ｃhaｒv［50]；//所有符號(hào)ｃhaｒleft[5０];//左部cｈarright[5０][5０];//右部ｃｈarfｉrｓt[５0][50］，foｌlow［５０][50];／/各產(chǎn)生式右部的FＩRST和左部的FOLＬＯW集合chａrfirｓt1[50］[50];//所有單個(gè)符號(hào)的FIRST集合charseleｃｔ[50][50]；/／各個(gè)產(chǎn)生式的SELEＣT集合ｃｈarｆirsｔfｌag[50],foｌlowfｌag[5０];//記錄各符號(hào)的FIＲＳT和FOＬLＯW是否已求過charemｐty［20]；//記錄可推出&的符號(hào)ｃｈarnｏnemｐty[2０］;?/／記錄不可推出＆的符號(hào)ｃharｅｍｐt[2０];//求_emp(）時(shí)使用chaｒTＥMP[5０];／／求FOLＬOW時(shí)存放某一符號(hào)串的FIRＳT集合inｔvａlidity=1;//表達(dá)輸入文法是否有效intll＝１;／/表達(dá)輸入文法是否為ＬＬ(1)文法intM[2０][20]；／/分析表ｃhaｒcｈoose;//用戶輸入時(shí)使用chａrfoll［２０］;／/求FOＬLOＷ集合時(shí)使用/＊**＊*＊＊*************＊**＊****＊*******＊******判斷一個(gè)字符c是否在指定字符串p中**＊**＊**＊*＊*********＊＊**＊＊＊**＊***********＊**/intｉn(ｃharc,chaｒ*p)｛?ｉnｔｉ； ｉf(sｔrleｎ（p）=＝0) ｒeturn(0); for(ｉ=0；；ｉ++)?{ ?ｉf(p[i]==c)? ?rｅtｕrn(1);/／若在，返回1? if(i==（int)stｒlｅｎ（ｐ）)?? reｔurｎ(0)；／/若不在,返回0 }}/*＊****＊＊***＊***＊**＊*********＊*＊**＊*＊****＊**將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串*********＊＊************＊********＊****＊***＊**／voidmｅrｇe(ｃhar＊d,char*s,inttｙｐｅ）{/／是目的符號(hào)串,s是源串，tyｐe=1,源串中的'&＇一并并入目串;／/typｅ＝2,源串中的'&'不并入目串ｉnti，ｊ; ｆｏr(i=0;i<＝(int)stｒlen(s)-1;i+＋)?{? if(ｔｙpe==2&&s[i]=＝'＆＇);??ｅｌｓｅ? ｛???for（j＝0；;ｊ++)???{?? ?ｉf（j<(iｎt)ｓtrleｎ（d)&&ｓ[i]==ｄ［j]) ???brｅak;//若已存在,則退出，繼續(xù)看下一個(gè)源串字符 ???ｉｆ(j==(inｔ）strlen（ｄ))//若不存在，則并入 ???{??? ?d[j]=ｓ[i］; ????d［j＋1]='\０＇; ?? ?ｂreak； ? }?? } ?｝?}}/＊*＊********＊＊＊*＊＊*********＊***＊*****＊*****＊讀入一個(gè)文法＊***＊＊＊**＊*＊***＊**＊****＊＊**＊******＊**＊＊*****/ｃhａrｇｒaｍmｅr(cｈaｒ＊t,char＊n,char*ｌｅft,ｃhaｒｒighｔ［５0]［５0]){?cｈａrvn[50],vt[５0];?ｃhars; ｃharp[50][50];?ｉntｉ，j; pｒｉntf("請輸入文法的非終結(jié)符號(hào)串:");scａｎf（"%ｓ",ｖn); getｃｈar（);i=ｓtｒlen(vn）;memcｐy(n,vn，i);?n[i]=＇\0';?prｉntf（"請輸入文法的終結(jié)符號(hào)串：");sｃａｎf(＂%s"，ｖt）; getchar（）;i=ｓtrlｅｎ(vt）；memｃpy(ｔ,vｔ,i）； t[i]='\0＇;printｆ（"請輸入文法的開始符號(hào):＂)；?ｓcanｆ("％c＂,＆s); getｃhar()；?priｎｔf("請輸入文法產(chǎn)生式的條數(shù):"）;scanf（"%d＂,&i)； gｅtchar();?couｎt＝i;for(j=1；j<＝i；j+＋)?｛? pｒiｎｔf("請輸入文法的第%d條（共％d條)產(chǎn)生式:"，j,i)； sｃａnf("%s",p[j-1])；getchａr()； }ｆｏｒ(j=０;j<=ｉ-１;j++)?｛??if(ｐ[j][1]！='-'||p[j][2］！='>')/／檢測輸入錯(cuò)誤? ｛? ?ｐrｉnｔf(＂\n輸入錯(cuò)誤！"); ??valｉdity＝0; ??return('＼０'）;} } ?retuｒn(s);｝/**＊************＊*＊*****＊****＊**********＊＊＊*判斷讀入的文法是否對的***＊**＊＊＊******＊＊***＊***＊＊*＊＊*＊********＊***＊/ｉntjudge()｛ｉntｉ，ｊ； ｆｏｒ（ｉ=0;i<=coｕnt-1;i+＋) ｛? ｉf(iｎ(lｅｆｔ［ｉ],ｎon_teｒ)==0) {//若左部不在非終結(jié)符中,報(bào)錯(cuò)?? ｐｒintf("＼ｎ文法左部犯錯(cuò)!")； validity=0；? ?return(0);??} foｒ（ｊ＝0;j＜=(iｎt）ｓtrｌｅn(righｔ[ｉ］)-１;j+＋)? ｛? if(in(rｉghｔ[ｉ][ｊ］,ｎon_ter）==0&&in(rigｈｔ[i］[ｊ］,ｔermｉn)==０＆&right[i］[ｊ］!='＆＇) ? ｛//若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為'＆＇,報(bào)錯(cuò)? ? ｐrintｆ("\n文法右部犯錯(cuò)!＂）; ??vaｌｉdiｔy＝０；?? retｕｒn(0)；?? ｝??}?} return(1);｝/＊*＊＊***＊*＊*＊＊***＊*＊********＊＊*****＊***＊**＊＊求所有能直接推出＆的符號(hào)＊＊＊*＊**＊***＊*****＊**＊**＊**＊**＊***＊**********/vｏｉdemp(ｃhａｒｃ）｛ cｈartｅｍｐ[1０］；?inti; fｏr（ｉ=0；i<=cｏunt-1;i＋+)?{??if(rｉgｈt［i][０]＝=c&&strｌｅｎ(rigｈt[ｉ])==1)? { ??temp［０]=left［i］; ｔemｐ[１]＝'\０';? ?mｅｒge（eｍｐty,teｍp,1);//求所有能直接推出'&"的符號(hào),結(jié)果保存到emptｙ［］中 ? emp(ｌｅft[i］）;? }?}}/＊*＊*******＊＊＊＊＊＊*＊********＊******＊＊＊***＊***求某一符號(hào)能否推出＇&'***＊***＊**＊*＊*＊****＊**＊*******＊＊＊*＊********＊/iｎt_eｍｐ(charc）{／/若能推出＆,返回1;否則,返回0 inti,j,ｋ，resuｌt=１,mark＝0;?ｃhａrｔeｍp[2０];?tｅmp［0］＝c;?ｔemp[1]='\0';?mｅrge(ｅmｐt,ｔemｐ，１);／/存放到一個(gè)臨時(shí)數(shù)組emｐt里,標(biāo)記此字符已查找其是否可推出空字?iｆ(in（ｃ,emptｙ）=＝1)//假如c在可直接推出空字的emptｙ［]中,返回1? retuｒn(1）; for(ｉ=０;；i++）?{ ?ｉｆ(ｉ=＝couｎt)reｔurn（0);??ｉｆ(leｆt[ｉ］==c)/／找一個(gè)左部為c的產(chǎn)生式? ｛j=stｒｌen(rｉgｈｔ［i］)；//j為c所在產(chǎn)生式右部的長度 ?ｉf(ｊ==1＆&in(ｒigｈt[ｉ][0]，ｅｍｐｔｙ）=＝1)//右部長度為1且右部第一個(gè)字符在emｐｔｙ[]中.返回1(A－>B,B可推出空）? ??ｒetｕrｎ(1);?? ｅlseif(ｊ＝=1&&in(riｇht［i][０],terｍin)==1)//右部長度為1但第一個(gè)字符為終結(jié)符，返回0（A-＞ａ,a為終結(jié)符)? ? cｏntinuｅ; ? ｅlse?? {????ｆor(k=0；k＜＝ｊ-1；ｋ++) ? ｛ ? ??if(in(righｔ［i］[k],ｅmpt)==1)//查找臨時(shí)數(shù)組empt[]．（Ａ－＞AB）???? maｒk=1； ? ｝ ? if(ｍａｒk==１）/／找到的字符與當(dāng)前字符相同(Ａ-＞ＡＢ)?? ? coｎtinuｅ;／/結(jié)束本次循環(huán)? ?else//(ｍaｒk等于0)????{ ?? ?? ? fｏr(k=0；ｋ＜=j-1；ｋ+＋) ? {? ????result＊＝_ｅmp(righｔ[i］[k]);／/遞歸調(diào)用,查找右部符號(hào)是否可推出空字，把返回值賦給rｅsuｌｔ ? ?? temp[0]＝ｒigｈt[i]［ｋ］；???? tｅｍp［1］=＇\０';? ? ?merge(emｐt,ｔｅmp,1);//把當(dāng)前符號(hào)加入到臨時(shí)數(shù)組eｍpt［]里，標(biāo)記已查找? ? ?} ? }? } ? ｉf(resuｌｔ＝=０&&i<count)//假如當(dāng)前字符不能推出空字且還沒搜索完所有的產(chǎn)生式,則跳出本次循環(huán)繼續(xù)搜索下一條產(chǎn)生式 contｉnue; ?eｌseif(result==1&&i＜cｏuｎｔ)//當(dāng)前字符可推出空字，返回1 ??reｔurn(1);? ｝ }｝/*＊****＊＊**********＊*＊***＊*＊*＊＊******＊******求單個(gè)符號(hào)的FIRST***＊*****＊****＊＊＊**＊**＊＊*****＊*****＊*＊＊*＊＊**/voiｄfiｒｓｔ２(intｉ){/／i為符號(hào)在所有輸入符號(hào)中的序號(hào)chａrc,temp[20];?ｉnｔj，k,m；?ｃｈarch='&'； c＝ｖ[i]；??emp（ch)；／/求所有能直接推出空字的符號(hào),結(jié)果保存到eｍｐty［]中 if(in（c,termin)==1)／／若為終結(jié)符－-c∈VT,則ＦIRST(c）={c}{fｉrst1[i][0]=c; ?firsｔ１[i][1］＝'\0'; } elseif(ｉn（c,ｎon_ｔer)＝=1)//若為非終結(jié)符?{ for(j=０;ｊ<=count－1；j＋＋)//j為所有產(chǎn)生式中的序列??{if(left[j]==c)//找一個(gè)左部為c的產(chǎn)生式 ??｛??? iｆ（ｉn（right[j]［0],termin)==1｜｜rigｈｔ[ｊ]［０]=＝＇＆＇)? {/／若產(chǎn)生式右部第一個(gè)字符為終結(jié)符或空.-－-產(chǎn)生式Ｘ→a（a∈VＴ）或X→&，則把a(bǔ)或&加進(jìn)FIRSＴ(X)temｐ[0]=rｉgｈt[j]［０］;??? ?tｅｍp[1］='\０';? ? ｍerｇe(fiｒst1[ｉ],temｐ,1); ???}//---－--X→Y1Y2…Yｋ的產(chǎn)生式,若Ｙ１∈VN，則把FIＲST(Y1)中的一切非空符號(hào)加進(jìn)ＦIRST(X)?? eｌseif(in(ｒｉght[j]［0],nｏｎ＿ter)==1)/／產(chǎn)生式右部第一個(gè)字符為非終結(jié)符 { ? if(right[j][0]==c)//產(chǎn)生式右部的第一個(gè)符號(hào)等于當(dāng)前字符,則跳到下一條產(chǎn)生式進(jìn)行查找 ? ? ?contiｎue;??? for(k=0;;k＋+)? ?{ ??? if(v[k]=＝ｒiｇｈｔ[ｊ][0]）//求右部第一個(gè)字符在所有字符集中的位置k? ??? ?breａk; ??? ｝??? ｉｆ(firｓtflag［k]=＝＇0') ? {? ? ?fiｒst2(ｋ)；//求其FＩＲST集?? ??fｉｒｓtflag[k]='1';//標(biāo)記其為查找狀態(tài)?? ? ｝ ??? meｒge(first1［ｉ],ｆirst1[k],２)；//求得結(jié)果并入到Ｘ的FIRST集. ?? fｏr(k＝0；k＜（inｔ)stｒｌeｎ(rigｈt［j])；k++）?? ? ｛ ????empt[0]＝'＼0＇;／/存放到一個(gè)臨時(shí)數(shù)組里,標(biāo)記此字符已查找其是否可推出空字? ? if(_ｅmp(ｒｉｇht［j］[k]）==１&＆k<（ｉnｔ）ｓｔrlen(rｉght[j])-1)? ? {／／當(dāng)前產(chǎn)生式右部符號(hào)可推出空字,且當(dāng)前字符不是右部的最后一個(gè)字符??? ｆor（m＝0；;m++)??? ? ?{ ?? ????if（v[m］=＝rigｈt[j］[k+1])/／獲取右部符號(hào)下一個(gè)字符在所有字符集中的位置 ?? ? ｂｒｅak; ?? ?｝? ??? ?if（ｆｉrstflａg[ｍ］=='0＇)//假如此字符的FIＲSＴ集尚未查找,則找其FIＲST集,并標(biāo)其查找狀態(tài)為1????? ｛?? ? ???fiｒst2(m); ? ? firstｆｌａｇ[m]='1';? ? ??}? ? merge(fｉrsｔ1[i],fｉｒsｔ１[m],2);//把求得結(jié)果并入到X的FIＲＳT集. ?? ? ｝//----產(chǎn)生式為Ｘ→Y1Y2…Yｋ,若對一切1<=i<=ｋ，均有&∈FＩRST（Ｙi)，則將&∈符號(hào)加進(jìn)ＦＩRＳＴ(Ｘ) ???ｅlseif（_ｅmｐ(rｉgｈｔ[ｊ］[ｋ］)==1&＆k=＝(ｉｎt)ｓtrｌen（riｇht[ｊ]）－1) ???{//當(dāng)前右部符號(hào)串可推出空且是右部符號(hào)串的最后一個(gè)字符 ?? ?temp[0]＝'＆';? ?ｔｅmp[1]＝'＼0'; ?? ? ｍergｅ(firｓt1［i］,ｔeｍp,1);/／把空字加入到當(dāng)前字符Ｘ的FＩRＳＴ集. ? ? ?} else ? ??break;/／不能推出空字則結(jié)束循環(huán) ???} ? ?｝ ｝ } }?fｉrstflａｇ[i]=＇1';／／標(biāo)記當(dāng)前字符c已查找其FＩRＳT集}/＊************＊*****＊****＊****＊***＊**＊***＊**求各產(chǎn)生式右部的FＩＲST**＊*＊*＊＊********＊***＊*******＊******＊*＊＊***＊＊／vｏｉdＦIRＳT(intｉ，ｃhar*ｐ) ? ｛//指針ｐ指向右部符號(hào)串 inｔlengｔh；／／標(biāo)記右部符號(hào)串的長度?intj，k，ｍ; ｃhartemp[2０];?length＝strlｅn(p);?iｆ(ｌength=＝1)／／假如右部為單個(gè)符號(hào)?{? if(p[0]＝＝'&'）／/右部符號(hào)串字符為"&＂空字｛? ?ｉf(i>=0）//i不為-１時(shí)是產(chǎn)生式的序號(hào)｛? ? firsｔ[i][0］='&＇; ／/把＂＆"加入到當(dāng)前符號(hào)串的FIＲST集??? ｆｉrｓt[i］[1]='\0'； ｝ ? ｅlsｅ／／ｉ為-1時(shí),表達(dá)求FOLLOW時(shí)用到的產(chǎn)生式右部的FIRST集,保存在TEMP［]中?? {????TＥMP[0]='&';? TEＭP[1]='\0';?? ｝??｝? else／/右部符號(hào)串字符不為"&"空字 {?? fｏr(j=0;;j++)???｛?? ｉｆ（v[j]==p[0]）//求右部符號(hào)的第一個(gè)字符ｐ[０]在所有字符集中的位置j? ??brｅaｋ; ?}???ｉf(i>=0)?? {?? mｅmcpｙ(fiｒｓｔ［i],fｉrsｔ1[j],strｌen(fｉrst１[ｊ］));/／把ｊ所指向的單個(gè)符號(hào)的ＦIRＳＴ集拷貝到該右部符號(hào)串的FIRST集 ???ｆｉrｓt[ｉ][strlen(fiｒｓt１[j])]＝＇\0'； }? ?elsｅ ?{?? ｍemｃｐy(TEＭＰ,first1［j]，ｓｔｒｌeｎ(first1[j])）;? TEMＰ[ｓtrｌen(first1[j])］='\0'; ??}} }?elsｅ／/假如右部為符號(hào)串?｛? ｆoｒ(j=０;；j++) ?{?? if（v[ｊ]==p［０]）／/求右部符號(hào)的第一個(gè)字符p[0]在所有字符集中的位置j? ??ｂrｅak; ?} ｉｆ(ｉ>=０)? meｒge(firｓt［i]，firｓt1[j］,2）;? eｌｓe???mergｅ（TEMＰ,fｉrst1［ｊ],２); for(k＝0;ｋ<＝lengｔh-1;k++） ?{ ??ｅｍpt［0]=＇\0＇；???if(_emp(p[k］）=＝1&＆k<leｎgth-1）? {/／當(dāng)前產(chǎn)生式右部符號(hào)可推出空字,且當(dāng)前字符不是右部的最后一個(gè)字符 ? ?ｆｏr(m=０;;ｍ++) ? ｛ ??if(v[m]==right[i][ｋ＋1]) ?break;? } ? ｉf(ｉ>＝0) ????merge(first[ｉ]，first１［m］,2);? ? ｅlsｅ? ? meｒge(TEMP，first1[ｍ],2);?? ｝ ??elseiｆ(＿emｐ(p[k]）==１&&k==ｌenｇｔh-1) ?{／/當(dāng)前右部符號(hào)串可推出空且是右部符號(hào)串的最后一個(gè)字符????ｔｅｍp[0]=＇&';? ??temp[1]='\0';? if（ｉ＞=0) ?? ?mｅrge(ｆirst[ｉ]，tｅmｐ，１）; ???else ????merge(TEMＰ，ｔemｐ,1); ｝ ? ｅｌseiｆ(＿ｅmp（p［k])＝=0)????ｂreaｋ;??}?｝｝/＊＊*＊*＊****＊***＊********＊***＊＊＊＊************求各產(chǎn)生式左部的FＯLLOW＊**＊*＊*****＊****＊*＊＊****＊＊*****＊********＊＊**／voｉdFＯＬLOＷ(inti){//參數(shù)ｉ為該符號(hào)在非終結(jié)符中的位置 intｊ，k,ｍ,ｎ，resｕlt＝１；?charc,tｅmp[２０]； c=non_tｅr[i]；//ｃ為待求的非終結(jié)符?teｍp[0]=ｃ;?tｅmp[1]＝'＼0＇；?merｇe(fｏlｌ，teｍp,1);//把當(dāng)前字符放到一臨時(shí)數(shù)組fｏll[］中，標(biāo)記求已求其ＦOＬＬＯW集.避免循環(huán)遞歸 if（ｃ==sｔａｒt) {／/若為開始符號(hào)-－---開始符號(hào)S，則#∈FOＬＬOＷ(Ｓ)??temｐ［0]='#'; teｍp［1］='＼0'; ?mergｅ（follow［i]，temp，１);?}foｒ（j＝0;j<=coｕnt-１;j＋＋)?｛??ｉｆ(in(c,right［ｊ])＝=1)／/找一個(gè)右部具有當(dāng)前字符c的產(chǎn)生式 ｛//比如求ＦＯLLOW(B)則找Ａ→αB或Ａ→αBβ(β=>*&）的產(chǎn)生式 ??for(k=0;；k+＋) ?{? ? ｉf(ｒｉght[ｊ]［k]==c) ? ? ｂreａk;//k為c在該產(chǎn)生式右部的序號(hào),如Ｂ在產(chǎn)生式A→αB中的位置???｝ｆｏr(m＝0;;m++)???{ ? if(v［ｍ]==left[ｊ]) ? ?breａk；//ｍ為產(chǎn)生式左部非終結(jié)符在所有符號(hào)中的序號(hào)? ?}／/假如c在產(chǎn)生式右部的最后,形如產(chǎn)生式A→αＢ,則FOLLOＷ(A)∈FOLＬＯW（B) ? ｉf(k＝=(int）strlen(right［j］)-1)? ｛??? if（in(v[ｍ],folｌ)＝=1)//查找該非終結(jié)符是否已經(jīng)求過其ＦＯLLOＷ集.避免循環(huán)遞歸 ?? {//是則ＦOＬLＯW(A）∈FOＬLOW(B） ? ?merge（folｌow[ｉ],follow［m］，1);//把c所在產(chǎn)生式的左部非終結(jié)符的FOLLOW集加入到FOLＬOＷ（c)中?? ?ｃｏntinuｅ；／/結(jié)束本次循環(huán)，進(jìn)入j++循環(huán)｝ ? ?iｆ(fｏllｏwflａg[m]=='0＇) ? {//假如該非終結(jié)符的FOLLOW未求過??? FOLLOW(m);//求之ＦOLＬOW集? ? ?foｌｌoｗfｌaｇ[m]＝'１＇;//標(biāo)記為1 ???}?? ?ｍergｅ(folｌow［i]，foｌlｏw［ｍ],1);／/ＦOＬLOW(Ａ)∈FOLLOW(B)? ?｝ ｅlｓe ?{//假如ｃ不在產(chǎn)生式右部的最后,形如A→αBβ ??fｏr（ｎ=k+1；n＜=(iｎt)strlen(ｒight［j］）-１；n+＋)? ?{? ???ｅｍpt[0］＝'\0'；//把empt［]置空,由于求此字符是否可推出空字＿emp(c)時(shí)用到? ?rｅｓult*＝_emp（ｒｉght[j］[n])；????} ｉf（rｅsuｌｔ==1) {/／假如右部c后面的符號(hào)串能推出空,Ａ→αBβ(β=＞*&)則ＦOLＬOW（A)∈FOLLOW(Ｂ)if（in（v[ｍ],ｆoll)＝＝1）??? ｛//查找該非終結(jié)符是否已經(jīng)求過其FOLLOW集．避免循環(huán)遞歸?? ?mｅrｇe(foｌｌoｗ[ｉ],folｌｏｗ[m］,1）;//ＦＯＬLOＷ(A)∈ＦOＬLOＷ(B) ?????conｔinue;?? ??} ?ｉf(ｆｏllowflaｇ[m］==＇0'） ?? {? ?ＦOＬＬOW(m); ??? followfｌag［ｍ］＝＇1'; ? } ?? meｒge（folｌow[i],fｏllow[m］，1);? ??}／/若Ａ→αＢβ,其中B∈ＶN,α∈(VTＵVＮ)*、β∈(VTUVＮ)+,則ＦIRＳT(β)-{ε}∈ＦＯLLＯW(B);??? foｒ(n=k+１;n<=(iｎt)strｌen(ｒiｇht[j]）-1;n+＋) ? {ｔｅmp[n-k-1]=riｇht[j][n]；??? ｝?? ?temｐ[strｌｅn(ｒiｇht[j］)-k-１］＝'＼０'; FIＲＳT(-1,ｔemp）;／／求FIＲST(β)? ??meｒｇe(foｌｌoｗ［i],TＥMP，２);//把FＩＲST(β)中所有非空元素加入到FOLLOW(B)中???}??｝ } fｏlｌowfｌａg［ｉ]＝'1'；／/標(biāo)記當(dāng)前規(guī)定的非終結(jié)符的FOＬLOW集已求過｝/*＊＊**＊**＊*＊＊*****＊＊＊*******＊＊*********＊*＊**判斷讀入文法是否為一個(gè)LL(1)文法*＊*＊*＊****＊****＊***＊****＊＊＊**＊＊＊************/intＬL１（){ｉntｉ,ｊ，lｅngth，rｅsuｌt=1; cｈarｔemp[50]; for（j＝0；ｊ<＝4９;j+＋)?{//初始化??firｓｔ[j］[0]＝'\0';foｌlow［j］[0]=＇\０';??ｆｉrst1[j][0]='\0'; ?ｓelecｔ[ｊ][0]='\0'; TEMP[j]='\0';? ｔemp[j]='\0＇; firｓtflａg[ｊ］=＇0';//用來記錄該字符的FIＲST集是否已求過.１表達(dá)已求，0表達(dá)未求 ?folｌowｆlag[ｊ]＝'0＇；//用來記錄該字符的ＦOLLOW集是否已求過.1表達(dá)已求,0表達(dá)未求 } fｏr(j=０;j<=（iｎt)strleｎ(v)－１;j+＋) { ?firｓt2(j)；//求單個(gè)符號(hào)的FIRST集合，結(jié)果保存在first1[]里?}?priｎtf("\ｎ各非終結(jié)符推出的fｉrst集:\ｎ");?foｒ(ｊ=0;j<＝(ｉnt）ｓtrlｅｎ(v）-1；j＋+) { priｎtf("%c：%s"，v[j]，first1[j]);?｝ｐrintf(＂\ｎ能導(dǎo)空的非終結(jié)符集合:%ｓ",empty）; pｒintf("\ｎ_eｍp:＂)；?fｏr(ｊ=０;j<＝(inｔ）sｔrlen(v)－1;j++） pｒintf（"%d",_emp(v[ｊ])); foｒ（ｉ＝0；i<=coｕnt-1;i++) ?FIRST（i,rigｈt[ｉ]);//求FIＲST for(j＝0;j<＝（ｉnt)strlen（non_ｔｅr）－1;j++）｛//求FOLLＯW??iｆ(foll［j]==0) ?{ ??ｆoｌl[０]＝＇\0'; ?FＯLLOW(ｊ); }} priｎtf("\nfirst集：");?foｒ（i＝0;i<=cｏuｎt-1；i++) printf（"%ｓ"，first[ｉ］); ｐｒiｎtｆ(＂\nfollｏw集合：＂）;foｒ（ｉ=０;i＜＝(ｉｎｔ)strlen(nｏn＿ｔer）－1；i++)? pｒintf("%s＂,folｌoｗ[ｉ]);?for（i＝０；ｉ<＝count－1;i+＋)?｛/／求每一產(chǎn)生式的ＳEＬECＴ集合memcpy(selｅｃt[i],fiｒst[ｉ],strleｎ(first[i］))；//first[]存放的是各產(chǎn)生式右部的ＦIRST集selｅｃt[i］[strlen(first［ｉ])］='\0'; for(j=0;j＜＝(iｎt)strlｅn(right[i])-1;ｊ++)? rｅｓｕlt*=_emp(riｇht[i］[j])；? iｆ(strleｎ(ｒiｇht［ｉ]）==1&＆ｒｉｇht[i］[0]=='&')//形如產(chǎn)生式A->& ? reｓｕlｔ＝1;? if(ｒｅsuｌt=＝１）? {? ?for(j=0;；j++) ?ｉｆ(v[ｊ］=＝leｆt[i])//j為左部符號(hào)在所有字符集中的位置???? breａｋ;? ? merｇｅ(sｅleｃt［i],ｆolloｗ[ｊ］,1)；? }?} ｐrintｆ("\nseｌecｔ集合順序是:＂); fｏr(ｉ=0;i＜=cｏｕｎｔ－1；i＋+) ?ｐrintf("％ｓ"，select[i］）;?memｃｐy(tｅmp，ｓelｅct［０］,sｔrｌen(ｓelect[０])); tｅmp[strlen(ｓｅleｃｔ[0])]='\0＇；?for(i=1;ｉ＜＝coｕnｔ－１;ｉ+＋) {／＊判斷輸入文法是否為LL(1)文法*/leｎgｔh=strlｅｎ(temp）; ?if(leｆｔ[i]＝=ｌeft[i-1］) ｛? ?mｅrge(temp,ｓeｌecｔ[i］,1）;???if（sｔrleｎ(tｅmｐ)<length+strｌen(select[i]))/／比較兩個(gè)產(chǎn)生式的SELＥCT長度 ???rｅturn(0); } ｅlse ?｛?? tｅmp［０]＝'\０＇； ? mｅmcpｙ(teｍp,selｅct[i]，ｓｔｒlｅn（sｅlecｔ[i］));???ｔemp[sｔrlｅn(selｅｃｔ[i])]＝'\0'; ?｝ }?return(１);｝/******＊****＊***＊*＊*＊*＊＊**＊***＊*＊***********構(gòu)造分析表M*****＊***＊**************＊**＊**＊********＊**＊＊/voidMＭ（){inti,ｊ,k,m； for(ｉ=０;i<=1９；i＋+)?{ ?for(j=0;j＜=19;j++）//初始化分析表,所有置為空（-1)? { ??M[i][j]＝-１； } } i＝stｒlｅn(ｔermiｎ）; ｔermｉn[ｉ]='＃＇;／/將＃加入終結(jié)符數(shù)組 ｔｅｒmin[i+1]='\0＇; ｆor（i＝0；i<=cｏunt－1;ｉ++)／/查看每個(gè)產(chǎn)生式的SELＥＣＴ集?｛ｆoｒ(m=０;;m++)?{ if(non_ter[m］＝=left[ｉ]） ?ｂｒeａk;//m為產(chǎn)生式左部非終結(jié)符的序號(hào)?} ｆor（j=0;j<＝(iｎt)strｌen（select[i])-1;ｊ++)/／對每個(gè)SＥＬECT集中的所有元素進(jìn)行操作?{??ｉｆ（in(sｅｌect[i][ｊ],terｍiｎ)==1) ?{???fｏr(k＝0；；k+＋) ?{ ? ?if(termin[k]＝=selｅcｔ[i］[j])? ? ｂreak;/／ｋ為產(chǎn)生式右部終結(jié)符的序號(hào)?? }?? M[m][k]=i; }?｝ }｝/***＊*＊********＊************************＊***判斷符號(hào)串是否是該文法的句型**＊＊**＊***＊＊＊********＊********＊＊**＊*＊*****＊*/voidsｙnｔax()｛ inti,j,ｋ,m,n,p，q;cｈarｃｈ; charS［5０]，stｒ[5０];pｒｉntf("請輸入該文法的句型："）; sｃanｆ("%s",stｒ); getcｈａr(）;?i=strlｅn(stｒ);?sｔr[i］=＇＃';?str[i＋1]='\0'； S[0]=＇#';?Ｓ[1]=start；?Ｓ[２］＝'\0'; j=0;?ch=str[j］；wｈiｌe(1） {? iｆ(in(S[ｓtrlen(S)－１],ｔermｉn)==１）??{ｉf(S［stｒlen(S)-1]!＝cｈ) ??{??? ｐｒintf("該符號(hào)串不是文法的句型!")；returｎ; ??} ??eｌｓｅiｆ(S［sｔrlen(S)-1]=='＃＇) ?{printf（"該符號(hào)串是文法的句型.")；ｒeturn；?? } else???｛S[strlen（S)-１]='\0＇;????ｊ++；? ch=str［j]; ? ｝? } ｅｌse ?{ｆor（ｉ=0;；i＋+) ???if（non_ter［i］=＝S[strlen（S)-１])? ? ｂreaｋ;??? for(ｋ=0;;k+＋） ? {?? ? if(ｔermｉn[k］==cｈ)? ????breａk;? ? if（k＝=(ｉnt)ｓtrlen（ｔｅrmin）) ? ??{?? ?printｆ("詞法錯(cuò)誤！")；??? ? return;? ???｝? ?}