【正文】 FiF(E)圖4圖4圖47分別是程序計(jì)算FIRST集、FOLLOW集和SELECT集的運(yùn)行截圖（符號(hào)“ε“由“amp。 系統(tǒng)測(cè)試 測(cè)試一測(cè)試文法一的測(cè)試數(shù)據(jù)如下:SABSbCAεAbBεBaDCADCbDaSDc圖4圖4圖43分別是程序計(jì)算FIRST集、FOLLOW集和SELECT集的運(yùn)行截圖（符號(hào)“ε“由“amp。 判定給定符號(hào)串是否是文法中的句子的實(shí)現(xiàn)預(yù)測(cè)分析程序的工作過(guò)程用示意圖33表示圖33 第四章 系統(tǒng)運(yùn)行及測(cè)試 運(yùn)行和安裝環(huán)境Windows XP Professional + Turbo 系統(tǒng)運(yùn)行a) 首先將所需判定的文法按“ 文法輸入規(guī)則”中的要求寫(xiě)入自定義的文件中，該文件稱作文法文件。pa_table的定義如下：/*LL(1).h*/typedef struct pa_table{ IDNode **ptb。算法如下：對(duì)每個(gè)終結(jié)符或“”號(hào)用a表示。 判定是否是LL(1)文法的實(shí)現(xiàn)如“ LL(1)文法概述”中所述，一個(gè)上下文無(wú)關(guān)文法是否是LL(1)文法關(guān)鍵在于每個(gè)非終結(jié)符的兩個(gè)不同產(chǎn)生式的SELECT集是否存在交集，若存在則不是LL(1)文法，反之則可以判定該輸入文法是LL(1)文法。 求解產(chǎn)生式的SELECT集計(jì)算SELECT集的算法如下：對(duì)于任一產(chǎn)生式，若其左部的非終結(jié)符號(hào)不能推出ε，則其SELECT集等于右部的FIRST集；反之，SELECT集等于右部的FIRST集的非空元素與左部的非終結(jié)符的FOLLOW集的所有元素組成的集合。定義如下：/*LL(1).h*/IDNode *Follow[100]。b) 若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST（β）的非空元素加入FOLLOW（B）中。 IDNode *FirstRight[100]。若符號(hào)串α∈V*，α=X1X2…Xn，當(dāng)X1不能ε，則置FIRST（α）=FIRST（X1）。當(dāng)Y1，Y2，…，Yi1都ε時(shí)，（其中1≤i≤n），則FIRST（Y1）{ε}，F(xiàn)IRST（Y2）{ε}，…， FIRST（Yi1）{ε}，F(xiàn)IRST（Yi）都包含在FIRST（X）中。函數(shù)的結(jié)果存儲(chǔ)在Vn[]中。（程序中的操作為：刪除含有對(duì)應(yīng)的ifgetnull==0的結(jié)點(diǎn)的單鏈表，若這使表示產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式的單鏈表都被刪去，則把左部非終結(jié)符對(duì)應(yīng)的ifgetnull置為0。（在程序中的操作為：刪除含有ID大于或等于300的結(jié)點(diǎn)的單鏈表，若這使得表示某一非終結(jié)符為左部的產(chǎn)生式的所有單鏈表都被刪除，則將Vn[]中對(duì)應(yīng)的ifgetfull置為0）b) 若某一非終結(jié)符的某一產(chǎn)生式右部為ε,則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。需要指出的是，對(duì)三個(gè)集合的求解在算法上是對(duì)單鏈表集ppro[]進(jìn)行若干種鏈表操作的組合，故具體過(guò)程（分別由getFirstVn()、getFirstRight()、etFollow()和getSelect()實(shí)現(xiàn)）不再給出，下面給出的是邏輯算法。 詞法分析的結(jié)果，即第i個(gè)產(chǎn)生式轉(zhuǎn)存為單鏈表的規(guī)則如下：左部作為第一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的地址存儲(chǔ)在ppro[i]中，即第i個(gè)產(chǎn)生式的首結(jié)點(diǎn)地址存儲(chǔ)在ppro[]的第i個(gè)元素中,右部第一個(gè)符號(hào)作為第二個(gè)結(jié)點(diǎn)，向右依次將右部所有文法符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)加入到單鏈表的尾部。 struct IDNode *next。需要指出的是，出于降低程序復(fù)雜度的考慮，‘ε’（程序中以‘a(chǎn)mp。 int Vt_ID_next。typedef struct Vt_stru{ unsigned int ID。結(jié)構(gòu)體中ID存儲(chǔ)非終結(jié)符的編碼（關(guān)于編碼，程序中規(guī)定非終結(jié)符的編碼從200開(kāi)始，第一個(gè)被“發(fā)現(xiàn)”的非終結(jié)符被編碼為200，按照被“發(fā)現(xiàn)”順序依次編碼為201,202,…,程序最多允許100個(gè)非終結(jié)符，即編碼范圍在200~299之間。 }Vn_type。AbBamp。規(guī)定產(chǎn)生式的左部必須為非終結(jié)符。第二步，針對(duì)單鏈表型數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)算法計(jì)算出每一個(gè)表達(dá)式右部的FIRST 集、每一非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集，其結(jié)果均以單鏈表集的形式存儲(chǔ)。LL(1)文法的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過(guò)程中將用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)即選擇哪一個(gè)產(chǎn)生式（規(guī)則）進(jìn)行推導(dǎo)。華北電力大學(xué)（北京）編譯原理課程設(shè)計(jì)LL(1)文法判定 c語(yǔ)言實(shí)現(xiàn)專(zhuān)業(yè)班號(hào)____計(jì)算機(jī)021_____學(xué)生姓名____3122020130____指導(dǎo)教師____齊林海________ 2006年 3 月 6 日35目 錄第一章 前 言 1 LL(1)文法概述 1 設(shè)計(jì)思想概述 1第二章 語(yǔ)言文法規(guī)則 1 語(yǔ)言的詞法規(guī)則 1 語(yǔ)言的語(yǔ)法規(guī)則 2第三章 程序設(shè)計(jì) 2 詞法分析程序的實(shí)現(xiàn) 2 文法輸入規(guī)則 2 數(shù)據(jù)結(jié)構(gòu) 2 程序流程 4 求解FIRST集、FOLLOW集和SELECT集的實(shí)現(xiàn) 5 求出能推出的非終結(jié)符ε 5 求解產(chǎn)生式的右部的FIRST集 6 求解非終結(jié)符的FOLLOW集 7 求解產(chǎn)生式的SELECT集 7 判定是否是LL(1)文法的實(shí)現(xiàn) 7 預(yù)測(cè)分析表的生成實(shí)現(xiàn) 7 判定給定符號(hào)串是否是文法中的句子的實(shí)現(xiàn) 8第四章 系統(tǒng)運(yùn)行及測(cè)試 9 運(yùn)行和安裝環(huán)境 9 系統(tǒng)運(yùn)行 9 系統(tǒng)測(cè)試 9 測(cè)試一 9 測(cè)試二 10第五章 結(jié) 論 11 系統(tǒng)結(jié)論 11 存在的不足 12參考文獻(xiàn) 12附 錄 13源程序 13第一章 前 言 本設(shè)計(jì)使用C語(yǔ)言實(shí)現(xiàn)了對(duì)簡(jiǎn)單方法描述的LL(1)文法的判定。一個(gè)上下文無(wú)關(guān)文法（即2型文法）是LL（1）文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A→α，A→β，滿足SELECT（A→α）∩SELECT（A→β）= 248。最后，由求出的SELECT集經(jīng)由相應(yīng)算法判定出該輸入文法是否為L(zhǎng)L(1)文法，若是，則在屏幕上輸出預(yù)測(cè)分析表，并對(duì)給定的符號(hào)串判定是否是文法中的句子，分析過(guò)程用計(jì)算機(jī)打印出來(lái)。第三章 程序設(shè)計(jì) 詞法分析程序的實(shí)現(xiàn) 文法輸入規(guī)則源文法的輸入采用文件輸入的方式，每讀入一個(gè)字符就進(jìn)行文法符號(hào)的判定、記錄和編碼，同時(shí)對(duì)產(chǎn)生式以特定格式存儲(chǔ)。BaDCADCbDaSDc 數(shù)據(jù)結(jié)構(gòu)對(duì)非終結(jié)符和終結(jié)符分別采用以下的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)：typedef struct Vn_stru{ unsigned int ID。Vn_type Vn[100]。對(duì)于終結(jié)符，采用同樣的規(guī)則對(duì)其編碼，編碼范圍在300~399之間），Nch存儲(chǔ)其字符，ifgetnull指示該終結(jié)符能否推出ε，用于對(duì)三個(gè)集合的求解過(guò)程中。 char Tch。 以上為終結(jié)符的存儲(chǔ)結(jié)構(gòu)，在結(jié)構(gòu)體中，ID存儲(chǔ)其編碼，Tch存儲(chǔ)其字符。’指代）和‘’均被以終結(jié)符的身份處理。}IDNode。例如：SABSbC存儲(chǔ)方法為如圖31所示ppro[0]ppro[1]ppro[2]200201202 NULL200300300 NULL 100 101 102 100 200 103 圖31（假定S、A、B、C、b的編碼分別為100、101010200） 程序流程 詞法分析由函數(shù)File_Input (FILE *fp)實(shí)現(xiàn)，具體實(shí)現(xiàn)見(jiàn)附錄源程序。 求出能推出的非終結(jié)符ε算法如下：1) 將結(jié)構(gòu)體數(shù)組Vn[]中對(duì)應(yīng)每一非終結(jié)符的能否推出ε的標(biāo)記ifgetnull（如前所述，ifgetnull為結(jié)構(gòu)體變量Vn_type的成員變量，）置初值“未定”即2。（程序中的操作為：刪除含有對(duì)應(yīng)ε的ID的結(jié)點(diǎn)的單鏈表，置該單鏈表的第一個(gè)結(jié)點(diǎn)所表示的非終結(jié)符對(duì)應(yīng)的Vn[]中元素的ifgetnull為1，并從pprotemp[]刪除所有以該非終結(jié)符對(duì)應(yīng)的結(jié)點(diǎn)為第一結(jié)點(diǎn)的單鏈表。）4) 重復(fù)3），直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對(duì)應(yīng)的特征再?zèng)]有改變?yōu)橹埂? 求解產(chǎn)生式的右部的FIRST集首先，計(jì)算每個(gè)文法符號(hào)的FIRST集。e) 當(dāng)d)中所有Yi ε，（i=1，2，…n）則FIRST（X）=FIRST（Y1）∪FIRST（Y2）…∪FIRST（Yn）∪{ε}。若對(duì)任何j( 1≤j≤i1,2≤i≤n)，ε∈FIRST（Xj）則FIRST（α）=（FIRST（Xj）{ε}）∪FIRST（Xi）當(dāng)所有FIRST（Xj）( 1≤j≤n)都含有ε時(shí)，則FIRST（α）=（FIRST（Xj））∪{ε}[1]。 該過(guò)程分別由函數(shù)getFirstVn()和getFirstRight()實(shí)現(xiàn)，兩者又調(diào)用了兩個(gè)鏈表操作函數(shù)insert2link()和add2link()以及一個(gè)輔助函數(shù)getFirstExp()來(lái)實(shí)現(xiàn)具體功能，后三都的功能分別為插入結(jié)點(diǎn)到單鏈表、拷貝單鏈表到另一單鏈表、得到任意字符串的FIRST集。如果βε則把FOLLOW（A）也加入FOLLOW（B）中。該過(guò)程由函數(shù)getFollow()實(shí)現(xiàn)。該過(guò)程由函數(shù)getSelect()實(shí)現(xiàn)。該過(guò)程由函數(shù)judgeLL1()實(shí)現(xiàn)。a∈SELECT(A→α),則把α的頭指針?lè)湃隡[A,a]中。 int *row_info,*col_info。b) ,按照屏幕提示，輸入文法文件的路徑和文件名?！贝妫??！贝妫D49如圖中最后一行所示， i+i*i是該文法的句子。這樣的做法，既提高的程序的開(kāi)發(fā)效率和運(yùn)行效率，又增強(qiáng)了程序運(yùn)行的穩(wěn)定性，此外，還大大提高了程序的可重用性?？偟膩?lái)說(shuō)，雖然這些不足不影響程序?qū)L(1)文法判定的演示和教學(xué)效果，但是其判定功能卻因?yàn)檫@些不足而被大大削弱。 /*special used in input*/ Vn_ID_next = 100。i++){ ppro[i]=NULL。 Follow[i] = NULL。iVn_ID_next100。 for (。}int getID(char ch){/*get the ID of V*/ int i。}int SeekoverVn(char ch){ /*scan vn, if ch in,then return its id,else return Vn_ID_next*/ int i=0,r = Vn_ID_next。 break。iVt_ID_next100。}Status File_Input (FILE *fp) { /*read file fp points to, get all fags,and transform the oriental words to the form that the syntax analyser can read which is stored in ppro[]*/ char ch。 /*pointer to the last node*/ IDNode *pt。 /*to get ready*/ if (ch==39。 means a new expression*/ ifavailable = 1。A39。Z39。 Vn_ID_next++。){/*carriage return*/ pnewnode = NULL。 /*get the id of ch*/ if (idcurrent == Vt_ID_next){ Vt[Vt_ID_next200].ID = Vt_ID_next。 } if (ifavailable){/*to be transformed*/ pt = CreateNewIDNode。 ppro[Line_Num] = pnewnode = pt。 } return OK。 ch = fgetc(fp)。 getch()。iVn_ID_next100。iVn_ID_next100。iVt_ID_next200。iVt_ID_next200。i=Line_Num。 pt=ptnext。int cID。 } ptnext = NULL。 *pdes = pt。 } } else{ ptd1 = *pdes。 /*if at the tail*/ while(ptd2amp。 if(ptd2) cID = ptd2ID。 return 1。amp。 while(ps){ if(ifcopyNULL||(psID!=NULLID)){/*about 39。 else { pt = CreateNewIDNode。 mark=insert2link(pdes,pt,1)||mark。 while(p){ pt=p。s expression*/ IDNode *pt。