【正文】 FiF(E)圖4圖4圖47分別是程序計算FIRST集、FOLLOW集和SELECT集的運行截圖（符號“ε“由“amp。 系統(tǒng)測試 測試一測試文法一的測試數(shù)據(jù)如下:SABSbCAεAbBεBaDCADCbDaSDc圖4圖4圖43分別是程序計算FIRST集、FOLLOW集和SELECT集的運行截圖（符號“ε“由“amp。 判定給定符號串是否是文法中的句子的實現(xiàn)預測分析程序的工作過程用示意圖33表示圖33 第四章 系統(tǒng)運行及測試 運行和安裝環(huán)境Windows XP Professional + Turbo 系統(tǒng)運行a) 首先將所需判定的文法按“ 文法輸入規(guī)則”中的要求寫入自定義的文件中，該文件稱作文法文件。pa_table的定義如下：/*LL(1).h*/typedef struct pa_table{ IDNode **ptb。算法如下：對每個終結(jié)符或“”號用a表示。 判定是否是LL(1)文法的實現(xiàn)如“ LL(1)文法概述”中所述，一個上下文無關文法是否是LL(1)文法關鍵在于每個非終結(jié)符的兩個不同產(chǎn)生式的SELECT集是否存在交集，若存在則不是LL(1)文法，反之則可以判定該輸入文法是LL(1)文法。 求解產(chǎn)生式的SELECT集計算SELECT集的算法如下：對于任一產(chǎn)生式，若其左部的非終結(jié)符號不能推出ε，則其SELECT集等于右部的FIRST集；反之，SELECT集等于右部的FIRST集的非空元素與左部的非終結(jié)符的FOLLOW集的所有元素組成的集合。定義如下：/*LL(1).h*/IDNode *Follow[100]。b) 若A→αBβ是一個產(chǎn)生式，則把FIRST（β）的非空元素加入FOLLOW（B）中。 IDNode *FirstRight[100]。若符號串α∈V*，α=X1X2…Xn，當X1不能ε，則置FIRST（α）=FIRST（X1）。當Y1，Y2，…，Yi1都ε時，（其中1≤i≤n），則FIRST（Y1）{ε}，F(xiàn)IRST（Y2）{ε}，…， FIRST（Yi1）{ε}，F(xiàn)IRST（Yi）都包含在FIRST（X）中。函數(shù)的結(jié)果存儲在Vn[]中。（程序中的操作為：刪除含有對應的ifgetnull==0的結(jié)點的單鏈表，若這使表示產(chǎn)生式左部非終結(jié)符的有關產(chǎn)生式的單鏈表都被刪去，則把左部非終結(jié)符對應的ifgetnull置為0。（在程序中的操作為：刪除含有ID大于或等于300的結(jié)點的單鏈表，若這使得表示某一非終結(jié)符為左部的產(chǎn)生式的所有單鏈表都被刪除，則將Vn[]中對應的ifgetfull置為0）b) 若某一非終結(jié)符的某一產(chǎn)生式右部為ε,則將數(shù)組中對應該非終結(jié)符的標志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。需要指出的是，對三個集合的求解在算法上是對單鏈表集ppro[]進行若干種鏈表操作的組合，故具體過程（分別由getFirstVn()、getFirstRight()、etFollow()和getSelect()實現(xiàn)）不再給出，下面給出的是邏輯算法。 詞法分析的結(jié)果，即第i個產(chǎn)生式轉(zhuǎn)存為單鏈表的規(guī)則如下：左部作為第一個結(jié)點，該結(jié)點的地址存儲在ppro[i]中，即第i個產(chǎn)生式的首結(jié)點地址存儲在ppro[]的第i個元素中,右部第一個符號作為第二個結(jié)點，向右依次將右部所有文法符號對應的結(jié)點加入到單鏈表的尾部。 struct IDNode *next。需要指出的是，出于降低程序復雜度的考慮，‘ε’（程序中以‘a(chǎn)mp。 int Vt_ID_next。typedef struct Vt_stru{ unsigned int ID。結(jié)構(gòu)體中ID存儲非終結(jié)符的編碼（關于編碼，程序中規(guī)定非終結(jié)符的編碼從200開始，第一個被“發(fā)現(xiàn)”的非終結(jié)符被編碼為200，按照被“發(fā)現(xiàn)”順序依次編碼為201,202,…,程序最多允許100個非終結(jié)符，即編碼范圍在200~299之間。 }Vn_type。AbBamp。規(guī)定產(chǎn)生式的左部必須為非終結(jié)符。第二步，針對單鏈表型數(shù)據(jù)結(jié)構(gòu)，設計相應算法計算出每一個表達式右部的FIRST 集、每一非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集，其結(jié)果均以單鏈表集的形式存儲。LL(1)文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導，1表明只需向右看一個符號便可決定如何推導即選擇哪一個產(chǎn)生式（規(guī)則）進行推導。華北電力大學（北京）編譯原理課程設計LL(1)文法判定 c語言實現(xiàn)專業(yè)班號____計算機021_____學生姓名____3122020130____指導教師____齊林海________ 2006年 3 月 6 日35目 錄第一章 前 言 1 LL(1)文法概述 1 設計思想概述 1第二章 語言文法規(guī)則 1 語言的詞法規(guī)則 1 語言的語法規(guī)則 2第三章 程序設計 2 詞法分析程序的實現(xiàn) 2 文法輸入規(guī)則 2 數(shù)據(jù)結(jié)構(gòu) 2 程序流程 4 求解FIRST集、FOLLOW集和SELECT集的實現(xiàn) 5 求出能推出的非終結(jié)符ε 5 求解產(chǎn)生式的右部的FIRST集 6 求解非終結(jié)符的FOLLOW集 7 求解產(chǎn)生式的SELECT集 7 判定是否是LL(1)文法的實現(xiàn) 7 預測分析表的生成實現(xiàn) 7 判定給定符號串是否是文法中的句子的實現(xiàn) 8第四章 系統(tǒng)運行及測試 9 運行和安裝環(huán)境 9 系統(tǒng)運行 9 系統(tǒng)測試 9 測試一 9 測試二 10第五章 結(jié) 論 11 系統(tǒng)結(jié)論 11 存在的不足 12參考文獻 12附 錄 13源程序 13第一章 前 言 本設計使用C語言實現(xiàn)了對簡單方法描述的LL(1)文法的判定。一個上下文無關文法（即2型文法）是LL（1）文法的充分必要條件是，對每個非終結(jié)符A的兩個不同產(chǎn)生式，A→α，A→β，滿足SELECT（A→α）∩SELECT（A→β）= 248。最后，由求出的SELECT集經(jīng)由相應算法判定出該輸入文法是否為LL(1)文法，若是，則在屏幕上輸出預測分析表，并對給定的符號串判定是否是文法中的句子，分析過程用計算機打印出來。第三章 程序設計 詞法分析程序的實現(xiàn) 文法輸入規(guī)則源文法的輸入采用文件輸入的方式，每讀入一個字符就進行文法符號的判定、記錄和編碼，同時對產(chǎn)生式以特定格式存儲。BaDCADCbDaSDc 數(shù)據(jù)結(jié)構(gòu)對非終結(jié)符和終結(jié)符分別采用以下的數(shù)據(jù)結(jié)構(gòu)存儲：typedef struct Vn_stru{ unsigned int ID。Vn_type Vn[100]。對于終結(jié)符，采用同樣的規(guī)則對其編碼，編碼范圍在300~399之間），Nch存儲其字符，ifgetnull指示該終結(jié)符能否推出ε，用于對三個集合的求解過程中。 char Tch。 以上為終結(jié)符的存儲結(jié)構(gòu)，在結(jié)構(gòu)體中，ID存儲其編碼，Tch存儲其字符?！复┖汀灰越K結(jié)符的身份處理。}IDNode。例如：SABSbC存儲方法為如圖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)實現(xiàn)，具體實現(xiàn)見附錄源程序。 求出能推出的非終結(jié)符ε算法如下：1) 將結(jié)構(gòu)體數(shù)組Vn[]中對應每一非終結(jié)符的能否推出ε的標記ifgetnull（如前所述，ifgetnull為結(jié)構(gòu)體變量Vn_type的成員變量，）置初值“未定”即2。（程序中的操作為：刪除含有對應ε的ID的結(jié)點的單鏈表，置該單鏈表的第一個結(jié)點所表示的非終結(jié)符對應的Vn[]中元素的ifgetnull為1，并從pprotemp[]刪除所有以該非終結(jié)符對應的結(jié)點為第一結(jié)點的單鏈表。）4) 重復3），直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對應的特征再沒有改變?yōu)橹埂? 求解產(chǎn)生式的右部的FIRST集首先，計算每個文法符號的FIRST集。e) 當d)中所有Yi ε，（i=1，2，…n）則FIRST（X）=FIRST（Y1）∪FIRST（Y2）…∪FIRST（Yn）∪{ε}。若對任何j( 1≤j≤i1,2≤i≤n)，ε∈FIRST（Xj）則FIRST（α）=（FIRST（Xj）{ε}）∪FIRST（Xi）當所有FIRST（Xj）( 1≤j≤n)都含有ε時，則FIRST（α）=（FIRST（Xj））∪{ε}[1]。 該過程分別由函數(shù)getFirstVn()和getFirstRight()實現(xiàn)，兩者又調(diào)用了兩個鏈表操作函數(shù)insert2link()和add2link()以及一個輔助函數(shù)getFirstExp()來實現(xiàn)具體功能，后三都的功能分別為插入結(jié)點到單鏈表、拷貝單鏈表到另一單鏈表、得到任意字符串的FIRST集。如果βε則把FOLLOW（A）也加入FOLLOW（B）中。該過程由函數(shù)getFollow()實現(xiàn)。該過程由函數(shù)getSelect()實現(xiàn)。該過程由函數(shù)judgeLL1()實現(xiàn)。a∈SELECT(A→α),則把α的頭指針放入M[A,a]中。 int *row_info,*col_info。b) ,按照屏幕提示，輸入文法文件的路徑和文件名?！贝妫??！贝妫?。圖49如圖中最后一行所示， i+i*i是該文法的句子。這樣的做法，既提高的程序的開發(fā)效率和運行效率，又增強了程序運行的穩(wěn)定性，此外，還大大提高了程序的可重用性?？偟膩碚f，雖然這些不足不影響程序?qū)L(1)文法判定的演示和教學效果，但是其判定功能卻因為這些不足而被大大削弱。 /*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。