編譯原理課程設(shè)計-LL(1)文法的判定

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程設(shè)計報告課程：編譯原理課程設(shè)計學(xué)號： 姓名： 班級： 教師： 時間： 計算機科學(xué)與技術(shù)系專心-專注-專業(yè)設(shè)計名稱：LL（1）文法的判定（假設(shè)文法符合的First和Follow集未知）設(shè)計內(nèi)容、目的與要求：1、 設(shè)計內(nèi)容(1) LL（1）文法的判定（假設(shè)文法符合的First和Follow集未知）根據(jù)LL(1) 分析法編寫一個語法分析程序，可根據(jù)自己實際情況，選擇以下一項作為分 析算法的輸入： a.直接輸入根據(jù)已知文法構(gòu)造的分析表M; b.輸入文法的FIRST()和FOLLOW(U)集合，由程序自動生成文法的分析表M； c.輸入已知文法，由程序自動構(gòu)造文法的分析表M。

2、(2) 所開發(fā)的程序可適用于不同的文法和任意輸入串，且能判斷該文法是否為 LL(1)文法。(3)如完成前兩項，可增加運行實例，對于輸入的文法和符號串，所編制的語法分析程序應(yīng)能正確判斷此串是否為文法的句子，并要求輸出分析過程。2、 要求： 輸入文法，輸出判定該文法是否是LL（1）的。計劃與進(jìn)度安排：5月20日5月23日：查閱資料，進(jìn)一步掌握LL（1）文法的定義，掌握LL（1）分析法及其原理；5月24日5月26日：分析題目，畫出系統(tǒng)的流程圖；5月27日5月29日：根據(jù)流程圖，將系統(tǒng)功能劃分成各個不同的模塊；5月30日5月31日：根據(jù)不同的模塊，設(shè)計與其相對應(yīng)的函數(shù)，并依據(jù)分析函數(shù)的功能設(shè)置函數(shù)的參

3、數(shù)和返回值；6月1日6月2日：根據(jù)上一步的各個函數(shù)，編寫對應(yīng)的代碼；6月3日6月4日：對各個函數(shù)進(jìn)行編譯和檢查；6月5日 6月6日：編寫程序執(zhí)行的入口函數(shù)main（）函數(shù)，通過調(diào)用各個函數(shù)，實現(xiàn)整個程序的基本功能；6月7日 6月8日：編寫程序執(zhí)行的入口函數(shù)main（）函數(shù)，通過調(diào)用各個函數(shù)，實現(xiàn)整個程序的基本功能；6月9日 6月10日：編譯整個程序，并根據(jù)調(diào)試信息進(jìn)行相應(yīng)的修改，同時 設(shè)計相關(guān)的文法進(jìn)行測試，檢查程序是否滿足設(shè)計要求；6月11日 6月12日：使用不同的實例進(jìn)行測試，同時修改并完善設(shè)計；6月13日 6月17日：完成設(shè)計并答辯。設(shè)計過程、步驟（可加頁）：1、 數(shù)據(jù)結(jié)構(gòu)設(shè)計 數(shù)據(jù)結(jié)構(gòu)

4、設(shè)計的合理性直接關(guān)系著系統(tǒng)功能的實現(xiàn)方便與否。本系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)包含全局變量的定義和一位數(shù)組以及二維數(shù)組的定義。int count=0; /*分解的產(chǎn)生式的個數(shù)*/int number; /*所有終結(jié)符和非終結(jié)符的總數(shù)*/char start; /*開始符號*/char termin50; /*終結(jié)符號*/char non_ter50; /*非終結(jié)符號*/char v50; /*所有符號*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/char fir

5、st15050; /*所有單個符號的FIRST集合*/char select5050; /*各單個產(chǎn)生式的SELECT集合*/char f50,F50; /*記錄各符號的FIRST和FOLLOW是否已求過*/char empty20; /*記錄可直接推出的符號*/char TEMP50; /*求FOLLOW時存放某一符號串的FIRST集合*/int validity=1; /*表示輸入文法是否有效*/int ll=1; /*表示輸入文法是否為LL(1)文法*/int M2020; /*分析表*/char choose; /*用戶輸入時使用*/char empt20; /*求_emp()時使用*

6、/char fo20; /*求FOLLOW集合時使用*/int dg=0; /*標(biāo)志輸入文法是否是由有遞歸的文法哈成的LL（）*/2、 函數(shù)設(shè)計及其說明（1）int in(char c,char *p)功能：判斷一個字符是否在指定字符串中說明：若該字符在指定字符串中，函數(shù)返回1；否則返回0。（2）void MM()功能：構(gòu)造預(yù)測分析表M。說明：在該函數(shù)中，把預(yù)測分析表設(shè)計成二維數(shù)組，構(gòu)造預(yù)測分析表時，文法用其序號代替。（3）void menu() 功能：設(shè)置用戶界面。 說明：該函數(shù)將設(shè)計一個人機交互界面，從而選擇實現(xiàn)各種功能。（4）void Ch( ) 功能：得到一個不是非終結(jié)符的符號。 說明

7、：該函數(shù)通過調(diào)用in(char c,char *p)函數(shù)，返回一個不是非終結(jié)符的符號。（5）void merge(char *d,char *s,int type)功能：將單個符號或符號串并入另一符號串 說明：d指向目標(biāo)符號串，s指向源串，type1，源串中的一并并入目串；type2，源串中的不并入目串。（6）void recur(char *point)功能：分解含有左遞歸的產(chǎn)生式。說明：完整的產(chǎn)生式在point 中。（7）void non_re(char *point)功能：分解不含有左遞歸的產(chǎn)生式，即將形如P*Qa|F的產(chǎn)生式分解為P*Qa和PF。說明：完整的產(chǎn)生式在point 中。（8

8、）int judge() 功能：判斷讀入的文法是否正確 說明：若讀入的文法不正確則返回0，否則返回1。（9）void syntax()功能：檢查輸入串是否滿足，通過分析表判斷。 說明：通過分析表判斷，檢查輸入的字符串是否滿足。（10）char grammer(char *t,char *n,char *left,char right5050)功能：讀入一個文法。 說明：char *t指向終結(jié)符號的集合；char *n指向非終結(jié)符號的集合；char *left指向文法產(chǎn)生式的左部；char right5050傳遞的參數(shù)是文法產(chǎn)生式的右部。（11）void FOLLOW(int i)功能：求各產(chǎn)生

9、式左部的FOLLOW集。 說明：i為分解后的產(chǎn)生式的序號。（12）void first2(int i)功能：求單個符號的FIRST集。 說明：i為符號在所有輸入符號中的序號。（13）void FIRST(int i,char *p)功能：求各產(chǎn)生式右部的FIRST集。 說明：i為分解后的產(chǎn)生式的序號；char *p指向產(chǎn)生式的右部。（14）int ll1()功能：判斷讀入文法是否為一個LL(1)文法。 說明：若輸入的文法是LL(1)文法，返回1，否則報錯，返回0。（15）void emp(char c)功能：求所有能直接推出的符號,這里利用代替。 說明：char c 是需要判斷的符號。（16）

10、int _emp(char c)功能：求某一符號能否推出 說明：char c 是需要判斷的符號，若能推出，則返回1，否則返回0。3、 總控算法及流程（1） 推導(dǎo)出非終結(jié)符首先進(jìn)行第一次掃描，把能夠直接推出$的非終結(jié)符號記錄到空串表，把不能直接推出$的符號依次記錄下來，然后單個掃描每一個不能直接推出$的符號。掃描這個符號能夠直接推出的第一個非終結(jié)符記錄到一個隊列，接下來依次檢查隊列中每一個元素，把二次能夠推出$的符號記錄到空串表，把二次也推不出空串的繼續(xù)送入到隊列，然后再從隊列取元素掃描，直到隊列為空沒能找到能夠星推導(dǎo)出$的終結(jié)符，那么可以確定這個非終結(jié)符推導(dǎo)不出$，接下去掃描下一個非終結(jié)符。

11、（2）確定FIRST集FIRST集使用以下四個步驟判定：1)、若XVTT,則FIRST(X)=X 2)、若XVN,且有產(chǎn)生式Xa，aVT則把a加入到FIRST(X)中，即aFIRST(X) 3)、若XVN,且有產(chǎn)生式X$，則把$也加到FIRST(X)中，即$FIRST(X) 4)、若XVN, Y1，Y2，Yi 都VN，且有產(chǎn)生式XY1Y2Yn。 當(dāng)Y1，.Yi-1=>$ (1in)，則FIRST(Y1)-$，F(xiàn)IRST(Yi-1)- $，F(xiàn)IRST(Yi)都包含在FIRST(X)中，即： FIRST(Yi-1)-$ FIRST(X) 所有Y1,Yn *=> $ ,則把$加到FIRS

12、T(X)中,即: FIRST(Yi) FIRST(X) 其中第1-3個方法都很好處理，關(guān)鍵是第四個方法判斷時首先判斷第一個字符為非終結(jié)符，設(shè)定一個布爾型掃描標(biāo)志FLAG，賦初值TRUE，接下去依次掃描產(chǎn)生式右部每一個字符Yi，假如第i個字符可以推出空，那么就把這個字符的FIRST集去除$加入到產(chǎn)生式左部字符的FIRST集中，即FIRST(Yi)-$ÌFIRST(X),假如Yi是終結(jié)符或者不可以推出$，那么就把這個字符的FIRST集直接加入到FIRST(X)中，即FIRST(Yi)ÌFIRST(X)同時置FLAG為FALSE不再向下掃描，假如Yi恰好是最后一個字符，那么不管它

13、能不能星推導(dǎo)出空都直接把它的FIRST集加入到FIRST(X)中。同時要設(shè)置一個隊列和一組布爾型變量記錄FIRST集是否完成，隊列用來記錄FIRST(X)用到了哪些其它非終結(jié)符的FIRST集。 第一遍掃描完成后就掃描隊列，把FIRST集完成的非終結(jié)符的FIRST集加入到那些沒有完成的非終結(jié)符的FIRST集中去，沒有完成的非終結(jié)符再送回到隊列，這時候可能出現(xiàn)死循環(huán)，比如FIRST(S)用到了FIRST(A),而FIRST(A)用到了FIRST(B)，F(xiàn)IRST(B)又用到了FIRST(S),這時候S,A,B的FIRST標(biāo)志均為FALSE，無限循環(huán)下去。這時候可以記錄一下，比如循環(huán)了100次，強行

14、設(shè)置FIRST(S)的標(biāo)志為TRUE，那么FIRST(A),FIRST(B)也就依次可以求出了。我們在實際計算時也是這樣處理的，只是沒有把標(biāo)志寫出來而是記錄在心里的。（3）確定FOLLOW集FOLLOW集使用以下三個步驟判定： 1)、如果 X 是開始符 那么把 # 加入到 FOLLOW(X) 2)、若=>B是一個產(chǎn)生式,則把FIRST()$加至FOLLOW(B)中 3)、若=>B是一個產(chǎn)生式，或=>B是一個產(chǎn)生式而*=>$(即$FIRST()），則把 FOLLOW(A)加至FOLLOW(B)中。 FOLLOW集的求法與FIRST集類似，但有不同的地方。FOLLOW集需要

15、掃描每一個產(chǎn)生式。而FIRST集掃描的是產(chǎn)生式左部不同的產(chǎn)生式，然后掃描左部相同的產(chǎn)生式的每一個右部。FOLLOW集第一次掃描可以確定哪些FIRST集或FOLLOW集屬于所求的FOLLOW集，由于FIRST集已經(jīng)求出，所以第一次掃描就可以把相應(yīng)的FIRST集加入到FOLLOW集中，設(shè)置FOLLOW集完成標(biāo)記位，設(shè)置隊列，把未完成的非終結(jié)符送入隊列，依次取出隊列元素，把求出FOLLOW集的非終結(jié)符的FOLLOW集加入到相應(yīng)的FOLLOW集中，把未求出的送回隊列。如果碰到死循環(huán)使用FIRST集一樣的方法處理就可以。（4）確定SELLECT集FIRST集FOLLOW集都已經(jīng)求出來后SELLECT集就

16、很好求了，掃描每一個產(chǎn)生式，使用以下三個步驟確定： A AVN，V*， 1)、若是終結(jié)符，那么SELLECT(A)=； 2)、若是$，則SELECT(A)=FOLLOW(A)； 3)、若是非終結(jié)符，那么 若*=>$，則SELECT(A)=(FIRST()-$)FOLLOW(A)； 若*=>$ 則SELECT(A)=FIRST()。（5）LL(1)文法的判定當(dāng)SELLECT集求出來后就可以判斷是不是一個文法是不是LL(1)文法了，掃描產(chǎn)生式左部相同的SELLCET集是否含有相同元素，一旦發(fā)現(xiàn)相同元素立刻返回0，掃描結(jié)束沒有發(fā)現(xiàn)相同元素則返回1。（6）句子的判定當(dāng)一個文法確定是LL(1

17、)文法時就可以對輸入的語句進(jìn)行判定了。首先要安裝SELLECT集生成LL(1)預(yù)測分析表，最簡單的方法是使用哈希表來表示，把每一個產(chǎn)生式左部依次和這個產(chǎn)生式SELLECT集中的每一個終結(jié)符組成關(guān)鍵字，其值即為這個產(chǎn)生式，送入哈希表。這樣在進(jìn)行句子的分析時就可以很容易判斷是否使用某一個產(chǎn)生式來進(jìn)行規(guī)約。在實際分析時設(shè)置兩個棧，把"#"壓入分析棧和剩余棧，把開始符壓入分析棧，把輸入串從右向左送入剩余棧，然后只要兩個棧元素個數(shù)同時大于1，那么依次從兩個棧中取出兩個元素進(jìn)行比較，假如一樣就匹配，假如可以規(guī)約就規(guī)約，否則就不是該文法的句子。圖1 整個系統(tǒng)控制流程圖結(jié)果與分析（可以加頁

18、）： 1、 輸入一個LL(1)進(jìn)行測試，測試文法，測試結(jié)果如下圖所示G(Z)：Z->dAZ | bAc A->aA|圖4 輸入LL(1)文法并測試2、 輸入上述文法的一個句型進(jìn)行測試，測試結(jié)果如下圖所示a 待測試的句型1： bac 圖5 測試滿足指定文法的句型待測試句型2：abc圖6 測試不滿足指定文法的句型3、測試一個非LL(1)文法圖7 測試非LL(1)文法設(shè)計體會與建議： 近一個月的設(shè)計過程，雖然題目早已經(jīng)布下，但當(dāng)時正在學(xué)習(xí)中，看到題目僅是一頭霧水，沒有一點頭緒。剛拿到題目的時候，乍看很簡單，但當(dāng)真正入手做的時候，覺得設(shè)計一個合理的數(shù)據(jù)結(jié)構(gòu)不是一件很容易的事。因為一個好的軟

19、件設(shè)計，應(yīng)該考慮到它的健壯性和可擴充性，而且能夠做的比較完善，對于系統(tǒng)運行中可能遇到的問題能夠給出人性化的提示。這需要在問題分析和題目設(shè)計的過程中逐漸改進(jìn)。就本次設(shè)計而言，要構(gòu)造預(yù)測分析表，就要考慮輸入的文法是否是LL（1）文法，對檢測的結(jié)果應(yīng)該給予適當(dāng)?shù)奶幚?。?jīng)過查找資料和他人的耐心答疑，我終于設(shè)計處理較為合理的程序，達(dá)到了預(yù)期的課程設(shè)計目的。隨著課程的深入，逐漸了解到一點解題的方法，但對于上機實踐還是沒有什么想法，后來到圖書館和網(wǎng)上找了很多資料，才了解到大致的實現(xiàn)方法，有根據(jù)以前的一點編程經(jīng)驗，于是開始一個模塊一個模塊的去實現(xiàn)，然后在進(jìn)行整合，合并成一個完整的程序。通過本次課程設(shè)計，使學(xué)到

20、的理論知識得到了實踐，清晰地看到了LL（1）分析的全過程，掌握了first，follow，select的機上實現(xiàn)方法，掌握了分析表的構(gòu)造過程和方法，但遺憾的是，對于一些實現(xiàn)方法，例如句型分析的跟蹤過程，仍是參考的網(wǎng)上的源程序，感到了自己的不足，還需更加努力！附錄：程序代碼#include<stdlib.h>#include<stdio.h>#include<string.h>/*/int count=0; /*分解的產(chǎn)生式的個數(shù)*/int number; /*所有終結(jié)符和非終結(jié)符的總數(shù)*/char start; /*開始符號*/char termin50;

21、/*終結(jié)符號*/char non_ter50; /*非終結(jié)符號*/char v50; /*所有符號*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有單個符號的FIRST集合*/char select5050; /*各單個產(chǎn)生式的SELECT集合*/char f50,F50; /*記錄各符號的FIRST和FOLLOW是否已求過*/char empty20; /*記錄可直接推出的符號*/char TEMP50;

22、/*求FOLLOW時存放某一符號串的FIRST集合*/int validity=1; /*表示輸入文法是否有效*/int ll=1; /*表示輸入文法是否為LL(1)文法*/int M2020; /*分析表*/char choose; /*用戶輸入時使用*/char empt20; /*求_emp()時使用*/char fo20; /*求FOLLOW集合時使用*/* 判斷一個字符是否在指定字符串中*/int in(char c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c)return(1); /*若在，返回1*/if(i=

23、strlen(p) return(0); /*若不在，返回0*/* 得到一個不是非終結(jié)符的符號*/char c()char c='A' while(in(c,non_ter)=1)c+;return(c);/* 分解含有左遞歸的產(chǎn)生式*/void recur(char *point) /*完整的產(chǎn)生式在point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c(); /*得到一個非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1='0'for(j=0;j<=strlen(point)-

24、1;j+)if(pointn=point0) /*如果|后的首符號和左部相同*/for(j=n+1;j<=strlen(point)-1;j+) while(pointj!='|'&&pointj!='0') tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1='0'm=0;count+;if(pointj='|')n=j+1;break;else /*如果|后的首符號和左部不同*/leftcou

25、nt=ch;rightcount0=''rightcount1='0'count+;for(j=n;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj; else leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'printf(" count=%d ",count);m=0; count+; leftcount=point0; memcpy(rig

26、htcount,temp,m); rightcountm=ch; rightcountm+1='0'count+; m=0;/* 分解不含有左遞歸的產(chǎn)生式*/void non_re(char *point) int m=0,j;char temp20;for(j=3;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj;else leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0'm=0;count+; leftcount

27、=point0; memcpy(rightcount,temp,m); rightcountm='0' count+;m=0;/* 讀入一個文法*/char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j,k;printf("請輸入文法的非終結(jié)符號串："); scanf("%s",vn);getchar(); i=strlen(vn); memcpy(n,vn,i);ni='0'printf

28、("請輸入文法的終結(jié)符號串："); scanf("%s",vt);getchar(); i=strlen(vt); memcpy(t,vt,i);ti='0' printf("請輸入文法的開始符號：");scanf("%c",&s);getchar();printf("請輸入文法產(chǎn)生式的條數(shù)："); scanf("%d",&i);getchar(); for(j=1;j<=i;j+)printf("請輸入文法的第%d條（共%d條

29、）產(chǎn)生式：",j,i);scanf("%s",pj-1); getchar(); for(j=0;j<=i-1;j+)if(pj1!='-'|pj2!='>')printf("ninput error!"); validity=0;return('0'); /*檢測輸入錯誤*/ for(k=0;k<=i-1;k+) /*分解輸入的各產(chǎn)生式*/ if(pk3=pk0) recur(pk);else non_re(pk);return(s);/* 將單個符號或符號串并入另一符號串*/

30、void merge(char *d,char *s,int type) /*d是目標(biāo)符號串，s是源串，type1，源串中的 一并并入目串； type2，源串中的 不并入目串*/ int i,j;for(i=0;i<=strlen(s)-1;i+) if(type=2&&si='');elsefor(j=0;j+) if(j<strlen(d)&&si=dj) break; if(j=strlen(d) dj=si; dj+1='0' break;/* 求所有能直接推出的符號*/void emp(char c) /*即

31、求所有由 推出的符號*/char temp10;int i;for(i=0;i<=count-1;i+)if(righti0=c&&strlen(righti)=1)temp0=lefti;temp1='0'merge(empty,temp,1);emp(lefti);/* 求某一符號能否推出 */int _emp(char c) /*若能推出，返回1；否則，返回0*/int i,j,k,result=1,mark=0;char temp20;temp0=c;temp1='0'merge(empt,temp,1);if(in(c,empty

32、)=1)return(1);for(i=0;i+)if(i=count) return(0);if(lefti=c) /*找一個左部為c的產(chǎn)生式*/ j=strlen(righti); /*j為右部的長度*/if(j=1&&in(righti0,empty)=1) return(1);else if(j=1&&in(righti0,termin)=1)return(0);else for(k=0;k<=j-1;k+) if(in(rightik,empt)=1)mark=1;if(mark=1)continue;else for(k=0;k<=j-1

33、;k+)result*=_emp(rightik);temp0=rightik;temp1='0'merge(empt,temp,1); if(result=0&&i<count) continue; else if(result=1&&i<count) return(1);/* 判斷讀入的文法是否正確*/int judge() int i,j;for(i=0;i<=count-1;i+)if(in(lefti,non_ter)=0) /*若左部不在非終結(jié)符中，報錯*/printf("nerror1!");v

34、alidity=0;return(0);for(j=0;j<=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&&in(rightij,termin)=0&&rightij!='') /*若右部某一符號不在非終結(jié)符、終結(jié)符中且不為 ，報錯*/printf("nerror2!");validity=0;return(0);return(1);/* 求單個符號的FIRST*/void first2(int i) /*i為符號在所有輸入符號中的序號*/ char c,temp20;int

35、 j,k,m;char ch=''c=vi;emp(ch);if(in(c,termin)=1) /*若為終結(jié)符*/ first1i0=c; first1i1='0' else if(in(c,non_ter)=1) /*若為非終結(jié)符*/for(j=0;j<=count-1;j+) if(leftj=c) if(in(rightj0,termin)=1|rightj0='') temp0=rightj0; temp1='0'merge(first1i,temp,1);else if(in(rightj0,non_ter)=1

36、)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk='0') first2(k); fk='1'merge(first1i,first1k,2); for(k=0;k<=strlen(rightj)-1;k+)empt0='0'if(_emp(rightjk)=1&&k<strlen(rightj)-1) for(m=0;m+)if(vm=rightjk+1)break;if(fm='0')first2(m);fm='1'

37、;merge(first1i,first1m,2);else if(_emp(rightjk)=1&&k=strlen(rightj)-1)temp0=''temp1='0'merge(first1i,temp,1);else break;fi='1'/* 求各產(chǎn)生式右部的FIRST*/void FIRST(int i,char *p)int length;int j,k,m;char temp20;length=strlen(p);if(length=1) /*如果右部為單個符號*/if(p0='') if(i&

38、gt;=0) firsti0='' firsti1='0'elseTEMP0=''TEMP1='0'elsefor(j=0;j+)if(vj=p0)break;if(i>=0) memcpy(firsti,first1j,strlen(first1j); firstistrlen(first1j)='0'elsememcpy(TEMP,first1j,strlen(first1j);TEMPstrlen(first1j)='0' else /*如果右部為符號串*/for(j=0;j+)if(v

39、j=p0)break;if(i>=0) merge(firsti,first1j,2);elsemerge(TEMP,first1j,2);for(k=0;k<=length-1;k+)empt0='0'if(_emp(pk)=1&&k<length-1) for(m=0;m+)if(vm=rightik+1)break; if(i>=0) merge(firsti,first1m,2);elsemerge(TEMP,first1m,2); else if(_emp(pk)=1&&k=length-1) temp0=

40、9;'temp1='0'if(i>=0) merge(firsti,temp,1); elsemerge(TEMP,temp,1);else if(_emp(pk)=0)break;/* 求各產(chǎn)生式左部的FOLLOW*/void FOLLOW(int i)int j,k,m,n,result=1;char c,temp20;c=non_teri; /*c為待求的非終結(jié)符*/temp0=c;temp1='0'merge(fo,temp,1);if(c=start) /*若為開始符號*/temp0='#'temp1='0'

41、;merge(followi,temp,1); for(j=0;j<=count-1;j+)if(in(c,rightj)=1) /*找一個右部含有c的產(chǎn)生式*/for(k=0;k+)if(rightjk=c)break; /*k為c在該產(chǎn)生式右部的序號*/ for(m=0;m+)if(vm=leftj)break; /*m為產(chǎn)生式左部非終結(jié)符在所有符號中的序號*/if(k=strlen(rightj)-1) /*如果c在產(chǎn)生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue; if(Fm='0')FOLLOW

42、(m);Fm='1'merge(followi,followm,1);else /*如果c不在產(chǎn)生式右部的最后*/for(n=k+1;n<=strlen(rightj)-1;n+)empt0='0'result*=_emp(rightjn);if(result=1) /*如果右部c后面的符號串能推出*/ if(in(vm,fo)=1) /*避免循環(huán)遞歸*/merge(followi,followm,1);continue;if(Fm='0') FOLLOW(m); Fm='1' merge(followi,followm,1);for(n=k+1;n<=strlen(rightj)-1;n+) tempn-k-1=rightjn; tempstrlen(rightj)-k-1='0'FIRST(-1,temp);