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

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

2、(2) 所開發(fā)的程序可適用于不同的文法和任意輸入串，且能判斷該文法是否為 LL(1)文法。(3)如完成前兩項(xiàng)，可增加運(yùn)行實(shí)例，對(duì)于輸入的文法和符號(hào)串，所編制的語法分析程序應(yīng)能正確判斷此串是否為文法的句子，并要求輸出分析過程。2、 要求： 輸入文法，輸出判定該文法是否是LL（1）的。計(jì)劃與進(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)功能劃分成各個(gè)不同的模塊；5月30日5月31日：根據(jù)不同的模塊，設(shè)計(jì)與其相對(duì)應(yīng)的函數(shù)，并依據(jù)分析函數(shù)的功能設(shè)置函數(shù)的參

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

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

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

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

7、：該函數(shù)通過調(diào)用in(char c,char *p)函數(shù)，返回一個(gè)不是非終結(jié)符的符號(hào)。（5）void merge(char *d,char *s,int type)功能：將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串 說明：d指向目標(biāo)符號(hà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)功能：讀入一個(gè)文法。 說明：char *t指向終結(jié)符號(hào)的集合；char *n指向非終結(jié)符號(hào)的集合；char *left指向文法產(chǎn)生式的左部；char right5050傳遞的參數(shù)是文法產(chǎn)生式的右部。（11）void FOLLOW(int i)功能：求各產(chǎn)生

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

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

11、（2）確定FIRST集FIRST集使用以下四個(gè)步驟判定：1)、若XVTT,則FIRST(X)=X 2)、若XVN,且有產(chǎn)生式Xa，aVT則把a(bǔ)加入到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個(gè)方法都很好處理，關(guān)鍵是第四個(gè)方法判斷時(shí)首先判斷第一個(gè)字符為非終結(jié)符，設(shè)定一個(gè)布爾型掃描標(biāo)志FLAG，賦初值TRUE，接下去依次掃描產(chǎn)生式右部每一個(gè)字符Yi，假如第i個(gè)字符可以推出空，那么就把這個(gè)字符的FIRST集去除$加入到產(chǎn)生式左部字符的FIRST集中，即FIRST(Yi)-$ÌFIRST(X),假如Yi是終結(jié)符或者不可以推出$，那么就把這個(gè)字符的FIRST集直接加入到FIRST(X)中，即FIRST(Yi)ÌFIRST(X)同時(shí)置FLAG為FALSE不再向下掃描，假如Yi恰好是最后一個(gè)字符，那么不管它

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

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

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

16、很好求了，掃描每一個(gè)產(chǎn)生式，使用以下三個(gè)步驟確定： 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集求出來后就可以判斷是不是一個(gè)文法是不是LL(1)文法了，掃描產(chǎn)生式左部相同的SELLCET集是否含有相同元素，一旦發(fā)現(xiàn)相同元素立刻返回0，掃描結(jié)束沒有發(fā)現(xiàn)相同元素則返回1。（6）句子的判定當(dāng)一個(gè)文法確定是LL(1

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

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

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

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

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

22、/*求FOLLOW時(shí)存放某一符號(hào)串的FIRST集合*/int validity=1; /*表示輸入文法是否有效*/int ll=1; /*表示輸入文法是否為LL(1)文法*/int M2020; /*分析表*/char choose; /*用戶輸入時(shí)使用*/char empt20; /*求_emp()時(shí)使用*/char fo20; /*求FOLLOW集合時(shí)使用*/* 判斷一個(gè)字符是否在指定字符串中*/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*/* 得到一個(gè)不是非終結(jié)符的符號(hào)*/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(); /*得到一個(gè)非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1='0'for(j=0;j<=strlen(point)-

24、1;j+)if(pointn=point0) /*如果|后的首符號(hào)和左部相同*/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 /*如果|后的首符號(hào)和左部不同*/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;/* 讀入一個(gè)文法*/char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j,k;printf("請輸入文法的非終結(jié)符號(hào)串："); scanf("%s",vn);getchar(); i=strlen(vn); memcpy(n,vn,i);ni='0'printf

28、("請輸入文法的終結(jié)符號(hào)串："); scanf("%s",vt);getchar(); i=strlen(vt); memcpy(t,vt,i);ti='0' printf("請輸入文法的開始符號(hào)：");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'); /*檢測輸入錯(cuò)誤*/ for(k=0;k<=i-1;k+) /*分解輸入的各產(chǎn)生式*/ if(pk3=pk0) recur(pk);else non_re(pk);return(s);/* 將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串*/

30、void merge(char *d,char *s,int type) /*d是目標(biāo)符號(hà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;/* 求所有能直接推出的符號(hào)*/void emp(char c) /*即

31、求所有由 推出的符號(hào)*/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);/* 求某一符號(hào)能否推出 */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) /*找一個(gè)左部為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é)符中，報(bào)錯(cuò)*/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!='') /*若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為 ，報(bào)錯(cuò)*/printf("nerror2!");validity=0;return(0);return(1);/* 求單個(gè)符號(hào)的FIRST*/void first2(int i) /*i為符號(hào)在所有輸入符號(hào)中的序號(hào)*/ 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) /*如果右部為單個(gè)符號(hào)*/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 /*如果右部為符號(hào)串*/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) /*若為開始符號(hào)*/temp0='#'temp1='0'

41、;merge(followi,temp,1); for(j=0;j<=count-1;j+)if(in(c,rightj)=1) /*找一個(gè)右部含有c的產(chǎn)生式*/for(k=0;k+)if(rightjk=c)break; /*k為c在該產(chǎn)生式右部的序號(hào)*/ for(m=0;m+)if(vm=leftj)break; /*m為產(chǎn)生式左部非終結(jié)符在所有符號(hào)中的序號(hào)*/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后面的符號(hào)串能推出*/ 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);