編譯課程設(shè)計報告--ll(1)文法判定

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：37 大?。?10.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩36頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　編譯原理課程設(shè)計　　LL(1)文法判定　　---c語言實現(xiàn)　　2006年 3 月 6 日　　目錄<

2、;/b>　　第一章前言1　　1.1 LL(1)文法概述1　　1.2 設(shè)計思想概述1　　第二章語言文法規(guī)則1　　2.1 語言的詞法規(guī)則1　　2.2 語

3、言的語法規(guī)則2　　第三章程序設(shè)計2　　3.1 詞法分析程序的實現(xiàn)2　　3.1.1 文法輸入規(guī)則2　　3.1.2 數(shù)據(jù)結(jié)構(gòu)2　　3.1.3 程序流程4　　3.2 求解FI

4、RST集、FOLLOW集和SELECT集的實現(xiàn)5　　3.2.1 求出能推出的非終結(jié)符ε5　　3.2.2 求解產(chǎn)生式的右部的FIRST集6　　3.2.3 求解非終結(jié)符的FOLLOW集7　　3.2.4 求解產(chǎn)生式的SELECT集7&l

5、t;p>　　3.3 判定是否是LL(1)文法的實現(xiàn)7　　3.4 預(yù)測分析表的生成實現(xiàn)7　　3.5 判定給定符號串是否是文法中的句子的實現(xiàn)8　　第四章系統(tǒng)運行及測試9　　4.1 運行和安裝環(huán)境9　　4.2

6、系統(tǒng)運行9　　4.2 系統(tǒng)測試9　　4.2.1 測試一9　　4.2.2 測試二10　　第五章結(jié) 論11　　5.1 系統(tǒng)結(jié)論11　　5.2 存在的不足12

7、　　參考文獻12　　附錄13　　源程序13　　第一章前言　　本設(shè)計使用C語言實現(xiàn)了對簡單方

8、法描述的LL(1)文法的判定。該設(shè)計程序?qū)崿F(xiàn)了：⑴分別求出每一產(chǎn)生式的右部的FIRST 集、每一個非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集；⑵判定是否是LL(1)文法；⑶畫出預(yù)測分析表；⑷對給定的符號串判定是否是文法中的句子，分析過程用計算機打印出來。　　1.1 LL(1)文法概述　　LL(1)文法是一種2型文法，由它所描述的語言可以使

9、用自頂向下語法分析方法進行語法分析。LL(1)文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導(dǎo)，1表明只需向右看一個符號便可決定如何推導(dǎo)即選擇哪一個產(chǎn)生式（規(guī)則）進行推導(dǎo)。　　一個上下文無關(guān)文法（即2型文法）是LL（1）文法的充分必要條件是，對每個非終結(jié)符A的兩個不同產(chǎn)生式，A→α，A→β，滿足　　SELEC

10、T（A→α）∩SELECT（A→β）= ø　　其中α、β不同時能ε[1]。　　1.2 設(shè)計思想概述　　首先對輸入的文法進行詞法分析，識別出所有的文法符號（終結(jié)符和非終結(jié)符）并對其編碼生成相應(yīng)ID，同時用單鏈表型數(shù)據(jù)結(jié)構(gòu)存儲單個產(chǎn)生式，產(chǎn)生式的文法符號在單鏈表中以其相應(yīng)ID表示，即所有的產(chǎn)生式以規(guī)定形式

11、存儲在一個單鏈表集中。第二步，針對單鏈表型數(shù)據(jù)結(jié)構(gòu)，設(shè)計相應(yīng)算法計算出每一個表達式右部的FIRST 集、每一非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集，其結(jié)果均以單鏈表集的形式存儲。最后，由求出的SELECT集經(jīng)由相應(yīng)算法判定出該輸入文法是否為LL(1)文法，若是，則在屏幕上輸出預(yù)測分析表，并對給定的符號串判定是否是文法中的句子，分析過程用計算機打印出來。　　第二章語言文法規(guī)則&l

12、t;/p>　　2.1 語言的詞法規(guī)則　　為簡單起見，本設(shè)計規(guī)定非終結(jié)符集VN為所有大寫字母的集合，終結(jié)符集VT為所有小寫字母、數(shù)字和四則運算符號的集合，取所有文法符號均為單個字符。　　2.2 語言的語法規(guī)則　　由2型文法的定義，定義如下：

13、　設(shè)G=（VN，VT，P，S），若P中的每一個產(chǎn)生式α→β滿足： α是一非終結(jié)符， β∈(VN∪VT)*則此文法稱為2型的或上下文無關(guān)的[1]。　　規(guī)定產(chǎn)生式的左部必須為非終結(jié)符。　　第三章程序設(shè)計　　3.1 詞法分析程序的實現(xiàn)

14、　　3.1.1 文法輸入規(guī)則　　源文法的輸入采用文件輸入的方式，每讀入一個字符就進行文法符號的判定、記錄和編碼，同時對產(chǎn)生式以特定格式存儲。文件中源產(chǎn)生式的書寫格式規(guī)定如下：格式為“左部>右部”，左部為一非終結(jié)符，右部的文法符號之間不允許有空格，右部結(jié)束后直接回車或文件結(jié)束，規(guī)定文件的第一個字符為文法的開始符號；格式中使用“>”而非“->”的原因在于簡化詞法分析，可以避免在讀入

15、字符“-”時的分情況處理（因為“-”也是一個終結(jié)符）。舉例如下：　　/*file:e:\demo1.dat參考文獻1例5.5*/　　S>AB　　S>bC　　A>

16、&　　A>b　　B>&　　B>aD　　C>AD</p&

17、gt;　　C>b　　D>aS　　D>c　　3.1.2 數(shù)據(jù)結(jié)構(gòu)　　對非終結(jié)符和終結(jié)符分別采用以下的數(shù)據(jù)結(jié)構(gòu)存儲：<

18、;/p>　　typedef struct Vn_stru{　　unsigned int ID;　　char Nch;　　unsigned int ifgetnull;　　}Vn_typ

19、e;　　Vn_type Vn[100];　　int Vn_ID_next;　　以上為非終結(jié)符的存儲結(jié)構(gòu)，對非終結(jié)符采用結(jié)構(gòu)體數(shù)組存儲。結(jié)構(gòu)體中ID存儲非終結(jié)符的編碼（關(guān)于編碼，程序中規(guī)定非終結(jié)符的編碼從200開始，第一個被“發(fā)現(xiàn)”的非終結(jié)符被編碼為200，按照被“發(fā)現(xiàn)”順序依次編碼為201

20、,202,…,程序最多允許100個非終結(jié)符，即編碼范圍在200~299之間。對于終結(jié)符，采用同樣的規(guī)則對其編碼，編碼范圍在300~399之間），Nch存儲其字符，ifgetnull指示該終結(jié)符能否推出ε，用于對三個集合的求解過程中。Vn[]存儲所有的非終結(jié)符。Vn_ID_next指示下一個可用的非終結(jié)符的編碼值，初始為200。　　typedef struct Vt_stru{

21、　　unsigned int ID;　　char Tch;　　}Vt_type;　　Vt_type Vt[100];　　int Vt_ID_next;</p&

22、gt;　　以上為終結(jié)符的存儲結(jié)構(gòu)，在結(jié)構(gòu)體中，ID存儲其編碼，Tch存儲其字符。所有終結(jié)符存儲在Vt[]中。Vt_ID_next提示下一個可用的終結(jié)符的編碼值。需要指出的是，出于降低程序復(fù)雜度的考慮，‘ε’（程序中以‘&’指代）和‘#’均被以終結(jié)符的身份處理。　　如前所述，分析所得的文法存儲在單鏈表集中。鏈表的結(jié)點結(jié)構(gòu)如下：

23、　　typedef struct IDNode{　　unsigned int ID;　　struct IDNode *next;　　}IDNode;　　結(jié)點中存儲文法符號的編碼和指向下一結(jié)點的指針。單鏈表集用IDNode*指針數(shù)組表示

24、，即：　　IDNode *ppro[100];　　詞法分析的結(jié)果，即第i個產(chǎn)生式轉(zhuǎn)存為單鏈表的規(guī)則如下：　　左部作為第一個結(jié)點，該結(jié)點的地址存儲在ppro[i]中，即第i個產(chǎn)生式的首結(jié)點地址存儲在ppro[]的第i個元素中,右部第一個符號作為第二個結(jié)點，向右依次將右部所有文法符號對應(yīng)的結(jié)點加入到單鏈表的尾部。例

25、如：　　S>AB　　S>bC　　存儲方法為如圖3-1所示　　100 101 102　　100

26、 200 103　　圖3-1　　（假定S、A、B、C、b的編碼分別為100、101、102、103、200）　　3.1.3 程序流程　　詞法分析由函數(shù)File_Input (FILE *fp)實現(xiàn)，具體實現(xiàn)見附錄源程

27、序。　　以下是程序的流程圖：　　圖3-2　　3.2 求解FIRST集、FOLLOW集和SELECT集的實現(xiàn)　　存儲FIRST集、FOLLOW集和SELECT集的數(shù)據(jù)結(jié)構(gòu)采用如圖3-1的單鏈表集，分別命名為FirstRight[]、F

28、ollow[]和Select[]，在這里，每個結(jié)點的ID必然大于等于300，因為這些集合的元素都必然是終結(jié)符。每個單鏈表中的結(jié)點將按其ID的大小順序由小到大排列。需要指出的是，對三個集合的求解在算法上是對單鏈表集ppro[]進行若干種鏈表操作的組合，故具體過程（分別由getFirstVn()、getFirstRight()、etFollow()和getSelect()實現(xiàn)）不再給出，下面給出的是邏輯算法。<

29、p>　　3.2.1 求出能推出的非終結(jié)符ε　　算法如下：　　將結(jié)構(gòu)體數(shù)組Vn[]中對應(yīng)每一非終結(jié)符的能否推出ε的標(biāo)記ifgetnull（如前所述，ifgetnull為結(jié)構(gòu)體變量Vn_type的成員變量，見3.1.2）置初值“未定”即2。　　掃描方法中的產(chǎn)生式（程序中的

30、掃描對象為ppro[]的拷貝pprotemp[]）。　　刪除所有右部含有終結(jié)符的產(chǎn)生式，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)記值改為“否”，說明該非終結(jié)符不能推出ε。（在程序中的操作為：刪除含有ID大于或等于300的結(jié)點的單鏈表，若這使得表示某一非終結(jié)符為左部的產(chǎn)生式的所有單鏈表都被刪除，則將Vn[]中對應(yīng)的ifgetfull置為0）

31、　　若某一非終結(jié)符的某一產(chǎn)生式右部為ε,則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。（程序中的操作為：刪除含有對應(yīng)ε的ID的結(jié)點的單鏈表，置該單鏈表的第一個結(jié)點所表示的非終結(jié)符對應(yīng)的Vn[]中元素的ifgetnull為1，并從pprotemp[]刪除所有以該非終結(jié)符對應(yīng)的結(jié)點為第一結(jié)點的單鏈表。）　　掃描產(chǎn)生式右部的每一符號</p&

32、gt;　　若所掃描到的非終結(jié)符號在數(shù)組中對應(yīng)的標(biāo)志是“是”，則刪去該非終結(jié)符，若這使產(chǎn)生式右部為空，則對產(chǎn)生式左部的非終結(jié)符在數(shù)組中對應(yīng)的標(biāo)志改為“是”，并刪除該非終結(jié)符為左部的所有產(chǎn)生式。（程序中的操作為：若所掃描到的結(jié)點所表示的非終結(jié)符號的ifgetnull被標(biāo)記為1,則刪去該結(jié)點，若這使該單鏈表只剩一個結(jié)點，則標(biāo)記該產(chǎn)生式左部的非終結(jié)符的ifgetnull為1，并刪除pprotemp[]中所有以該非終結(jié)符對應(yīng)

33、的結(jié)點為第一結(jié)點的單鏈表）　　若所掃描到的非終結(jié)符號在數(shù)組中對應(yīng)的標(biāo)志是“否”，則刪去該產(chǎn)生式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對應(yīng)的標(biāo)志改為“否”。（程序中的操作為：刪除含有對應(yīng)的ifgetnull==0的結(jié)點的單鏈表，若這使表示產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式的單鏈表都被刪去，則把左部非終結(jié)符對應(yīng)的ifgetnull置為0。）<

34、p>　　重復(fù)3），直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對應(yīng)的特征再沒有改變?yōu)橹?。（程序中設(shè)置了標(biāo)志變量ifVnChanged用以標(biāo)識非終結(jié)符對應(yīng)的特征有沒有改變。）[1]　　該過程由函數(shù)getNULLVn()實現(xiàn)，由于對存儲文法的鏈表有刪除操作，為保護數(shù)據(jù)，函數(shù)開始時先從ppro[]拷貝了一個臨時單鏈表集pprotemp[],所有刪除操作均在后者中進行，并在程序結(jié)束時釋放了pprot

35、emp[]的地址空間。函數(shù)的結(jié)果存儲在Vn[]中。　　3.2.2 求解產(chǎn)生式的右部的FIRST集　　首先，計算每個文法符號的FIRST集。　　由定義：FIRST（α）={a|aαβ,a∈VT，a、β∈V*}，若αε，則規(guī)定ε∈FIRST（α）　　對每一文法符號X∈V計算

36、FIRST（X）。　　若X∈VT，則FIRST（X）={X}　　若X∈VN，且有產(chǎn)生式X→a…，a∈VT則a∈FIRST（X）　　若X∈VN，X→ε，則ε∈FIRST（X）　　若X∈VN，Y1，Y2，…，Yi都∈VN，而有產(chǎn)生式X→Y1Y2…Yn。當(dāng)Y1，Y2，…，Yi-

37、1都ε時，（其中1≤i≤n），則FIRST（Y1）-{ε}，F(xiàn)IRST（Y2）-{ε}，…， FIRST（Yi-1）-{ε}，F(xiàn)IRST（Yi）都包含在FIRST（X）中。　　當(dāng)d)中所有Yi ε，（i=1，2，…n）　　則FIRST（X）=FIRST（Y1）∪FIRST（Y2）…∪FIRST（Yn）∪{ε}。

38、　反復(fù)使用上述(b)~(e)步直到每個符號的FIRST集合不再增大為止。　　求出每個文法符號的FIRST集合后也就不難求出一個符號串的FIRST集合。　　若符號串α∈V*，α=X1X2…Xn，　　當(dāng)X1不能ε，則置FIRST（α）=FIRST（X1）。

39、　若對任何j　　(1≤j≤i-1,2≤i≤n)，ε∈FIRST（Xj）　　則FIRST（α）=（FIRST（Xj）-{ε}）∪FIRST（Xi）　　當(dāng)所有FIRST（Xj）(1≤j≤n)都含有ε時，則FIRST（α）=（FIRST（Xj））∪{ε}[1]。<p

40、>　　由此算法可計算出各文法符號的FIRST集和各產(chǎn)生式的右部的FIRST集，分別存儲在FirstVn[]和FirstRight[]中。定義如下：　　/*LL(1).h*/　　IDNode *FirstVn[100]; 　　IDNode *FirstRight[100];<

41、;p>　　該過程分別由函數(shù)getFirstVn()和getFirstRight()實現(xiàn)，兩者又調(diào)用了兩個鏈表操作函數(shù)insert2link()和add2link()以及一個輔助函數(shù)getFirstExp()來實現(xiàn)具體功能，后三都的功能分別為插入結(jié)點到單鏈表、拷貝單鏈表到另一單鏈表、得到任意字符串的FIRST集。詳見附錄源程序。　　3.2.3 求解非終結(jié)符的FOLLOW集

42、;　　算法如下：　　對文法中每一A∈VN計算FOLLOW(A)　　設(shè)S為文法中開始符號，把{#}加入FOLLOW（S）中。　　若A→αBβ是一個產(chǎn)生式，則把FIRST（β）的非空元素加入FOLLOW（B）中。

43、如果βε則把FOLLOW（A）也加入FOLLOW（B）中。　　反復(fù)使用（b）直到每個非終結(jié)符的FOLLOW集不再增大為止[1]。　　由此算法可計算出非終結(jié)符號的FOLLOW集，存儲在Follow[]中。定義如下：　　/*LL(1).h*/　　IDNode *Follow[

44、100];　　該過程由函數(shù)getFollow()實現(xiàn)。函數(shù)中調(diào)用getFirstExp()取得“FIRST（β）的非空元素”；調(diào)用add2link()“把FOLLOW（A）也加入FOLLOW（B）中”。詳見附錄源程序。　　3.2.4 求解產(chǎn)生式的SELECT集　　計算SELECT集的算法如下：

45、;　　對于任一產(chǎn)生式，若其左部的非終結(jié)符號不能推出ε，則其SELECT集等于右部的FIRST集；反之，SELECT集等于右部的FIRST集的非空元素與左部的非終結(jié)符的FOLLOW集的所有元素組成的集合。　　該過程由函數(shù)getSelect()實現(xiàn)。計算出的表達式的SELECT集存儲在Select[]中。定義如下：　　/*LL(1).h

46、*/　　IDNode *Select[100];　　3.3 判定是否是LL(1)文法的實現(xiàn)　　如“1.1 LL(1)文法概述”中所述，一個上下文無關(guān)文法是否是LL(1)文法關(guān)鍵在于每個非終結(jié)符的兩個不同產(chǎn)生式的SELECT集是否存在交集，若存在則不是LL(1)文法，反之則可以判定該輸入文法是LL(1)文法。&l

47、t;/p>　　該過程由函數(shù)judgeLL1()實現(xiàn)。　　3.4 預(yù)測分析表的生成實現(xiàn)　　預(yù)測分析表可用一個矩陣M(或稱二維數(shù)組)表示。矩陣的元素M[A,a]中的下標(biāo)A表示非終結(jié)符,a為終結(jié)符或句子括號“#”,矩陣元素M[A,a]中的內(nèi)容為一條關(guān)于A的產(chǎn)生式,表明當(dāng)用非終結(jié)符A向下推導(dǎo)時,面臨輸入符a時,所應(yīng)采取的候選產(chǎn)生式,

48、當(dāng)元素內(nèi)容無產(chǎn)生式時,則表明用A為左部向下推導(dǎo)時遇到了不該出現(xiàn)的符號,因此元素內(nèi)容為轉(zhuǎn)身出錯處理的信息[1]。　　算法如下：　　對每個終結(jié)符或“#”號用a表示。　　a∈SELECT(A→α),則把α的頭指針放入M[A,a]中。把無定義的M[A,a]置為NULL空指針。<

49、/p>　　該過程由函數(shù)getpa_table()實現(xiàn)，該函數(shù)以Select[]為輸入數(shù)據(jù)，計算所得分析表存儲在結(jié)構(gòu)體pa_table的變量中。pa_table的定義如下：　　/*LL(1).h*/　　typedef struct pa_table{　　IDNode **ptb;<

50、/p>　　int *row_info,*col_info;　　int row_num,col_num;　　}pa_table;　　3.5 判定給定符號串是否是文法中的句子的實現(xiàn)　　預(yù)測分析程序的工作過程用示意圖3-3表示</p&

51、gt;　　圖3-3 　　第四章系統(tǒng)運行及測試　　4.1 運行和安裝環(huán)境　　Windows XP Professional + Turbo C2.0　　4.2 系統(tǒng)運行

52、　　首先將所需判定的文法按“3.1.1 文法輸入規(guī)則”中的要求寫入自定義的文件中，該文件稱作文法文件。　　運行程序LL1.exe,按照屏幕提示，輸入文法文件的路徑和文件名。　　程序?qū)⒁徊讲竭M行LL(1)文法的判定。　　若判定為LL(1)文法，則輸出預(yù)測分析表，并提示輸入符

53、號串進行語法分析。　　4.2 系統(tǒng)測試　　4.2.1 測試一　　測試文法一的測試數(shù)據(jù)如下:　　S->AB　　S->bC&

54、lt;/b>　　A->ε　　A->b　　B->ε　　B->aD&l

55、t;p>　　C->AD　　C->b　　D->aS　　D->c　　圖4-1、圖4-2、圖4-

56、3分別是程序計算FIRST集、FOLLOW集和SELECT集的運行截圖（符號“ε“由“&”代替）。　　圖4-2 　　圖4-3　　圖4-4是程序根據(jù)得到的SELECT集判定輸入文法是否為LL(1)文法的運行截圖。

57、;　　圖4-4　　如圖4-4所示，經(jīng)程序判定，該輸入文法不是LL(1)文法。　　4.2.2 測試二　　測試文法二的測試數(shù)據(jù)如下:　　E->TD

58、　　D->+TD　　D->ε　　T->FS　　S->*FS

59、　S->ε　　F->i　　F->(E)　　圖4-5、圖4-6、圖4-7分別是程序計算FIRST集、FOLLOW集和SELECT集的運行截圖（符號“ε“由“&”代替）。&

60、lt;p>　　圖4-5　　圖4-6　　圖4-7　　圖4-8是程序根據(jù)得到的SELECT集判定輸入文法是否為LL(1)文法的運行截圖。

61、　圖4-8　　如圖4-8所示，經(jīng)程序判定，該輸入文法是LL(1)文法。　　根據(jù)屏幕提示，輸入符號串i+i*i#，由程序判定是否是文法中的句子，分析過程在打印在屏幕上，如圖4-9所示。　　圖4-9　　如圖中最后一行所

62、示， i+i*i#是該文法的句子。　　測試完畢。　　第五章結(jié) 論　　5.1 系統(tǒng)結(jié)論　　本設(shè)計用C語言成功實現(xiàn)了對LL(1)文法的判定，達到了課程設(shè)計題目中的所有要求，并且操作簡單、易上

63、手，輸出結(jié)果清晰明了，可以作為《編譯原理》初學(xué)者的學(xué)習(xí)工具，也可以作為《編譯原理》課上的演示程序。　　本設(shè)計的設(shè)計亮點在于使用單鏈表集存儲關(guān)鍵數(shù)據(jù)，實現(xiàn)了判定過程的高效率；同時針對鏈表操作的復(fù)雜和易出錯的特點，設(shè)計者設(shè)計出了幾個基本卻功能強大的鏈表操作函數(shù)，如insert2link()、add2link()，提供給各主要函數(shù)調(diào)用。這樣的做法，既提高的程序的開發(fā)效率和運行效率，又增強了程序運行的穩(wěn)

64、定性，此外，還大大提高了程序的可重用性。　　除了高標(biāo)準(zhǔn)的完成了設(shè)計要求，在這次課程設(shè)計中，設(shè)計者對編程技術(shù)也有了更進一步的理解和體會，并借此機會大大提高了對C語言的駕馭能力，可謂受益匪淺。希望以后能有更多的機會得以鍛煉和施展才能。　　5.2 存在的不足　　當(dāng)然，由于能力所限，本設(shè)計也有一些不足：</p&g

65、t;　　其一，沒有實現(xiàn)實時輸入文法，只采用了文件輸入；　　其二，對于文法的要求過于苛刻，文法符號只能由一位字符構(gòu)成；　　其三，程序中過多地采用了全局變量，模塊化的程度太低；　　其四，程序幾乎處理錯誤能力很低，遇非規(guī)則輸入則死機。　　總的來說，雖然這些

66、不足不影響程序?qū)L(1)文法判定的演示和教學(xué)效果，但是其判定功能卻因為這些不足而被大大削弱。有時間的話，設(shè)計者會對該程序做進一步的改進。　　參考文獻　　1 呂映芝,張素琴,蔣維杜.編譯原理.第1版.北京:清華大學(xué)出版社,1998　　附錄</b

67、>　　源程序　　#include "stdlib.h"　　#include "stdio.h"　　#include <string.h> <p&g

68、t;　　#include "e:\ll1.h"　　#include "dir.h"　　/*#define DEBUG*/　　void initiate(){　　int i;

69、　　Line_Num = -1;/*special used in input*/　　Vn_ID_next = 100; /*Vn 100...199*/　　Vt_ID_next = 200; /*Vt 200...299*/　　for (i=0;i<100;i++){<

70、;/p>　　ppro[i]=NULL;　　Vn[i].ifgetnull = UNCERTAIN;　　FirstVn[i] = NULL;　　FirstRight[i] = NULL;　　Follow[i] = NULL;

71、　　Select[i] = NULL;　　}　　}　　int getVnID(char ch){/*get the ID of Vn according to itselt*/

72、　　int i=0;　　for (;i<Vn_ID_next-100;i++){　　if (Vn[i].Nch==ch) return Vn[i].ID;　　}　　retu

73、rn 0;　　}　　int getVtID(char ch){/*get the ID of Vt according to itselt*/　　int i=0;　　for (

74、;i<Vt_ID_next-200;i++){　　if (Vt[i].Tch==ch) return Vt[i].ID;　　}　　return 0;　　}

75、;　　int getID(char ch){/*get the ID of V*/　　int i;　　i = getVnID(ch);　　if(i==0) i = getVtID(ch);&l

76、t;b>　　return i;　　}　　int SeekoverVn(char ch){ /*scan vn, if ch in,then return its id,else return Vn_ID_next*/　　int i=0,r = Vn_

77、ID_next;　　for (;i<Vn_ID_next-100;i++){　　if (ch == Vn[i].Nch){　　r = Vn[i].ID;　　break;

78、　　}　　}　　return r;　　}　　int SeekoverVt(char ch){ /*scan vt, if ch in,th

79、en return its id,else return Vt_ID_next*/　　int i=0,r = Vt_ID_next;　　for (;i<Vt_ID_next-100;i++){　　if (ch == Vt[i].Tch){　　r = Vt[i].ID

80、;　　break;　　}　　}　　return r;　　}&

81、lt;/b>　　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

82、in ppro[]*/　　char ch;int idcurrent;　　int ifavailable;/*notes whether to be transformed*/　　IDNode *pnewnode = NULL; /*pointer to the last node*/&

83、lt;p>　　IDNode *pt;/*temp pointer*/　　Line_Num = -1;　　ch = fgetc(fp);　　while (ch != EOF){　　ifavailable = 0;/*to get ready*/</p&

84、gt;　　if (ch=='|'){/*for example S->AB|bC,'|' means a new expression*/　　ifavailable = 1;/*notes to be transformed*/　　idcurrent = ppro[Line_Num]->

85、;ID;/*left part*/　　pnewnode = NULL;/*a new expression*/　　}　　else if ((ch>='A') && (ch<='Z')){

86、　　idcurrent = SeekoverVn(ch); /*get the id of ch*/　　if (idcurrent==Vn_ID_next){　　Vn[Vn_ID_next-100].ID = Vn_ID_next;/*add it in Vn*/　　Vn[Vn_ID_next

87、-100].Nch = ch;　　Vn_ID_next++;　　}　　ifavailable = 1;/*notes to be transformed*/　　}<

88、p>　　else if (ch=='\n'){/*carriage return*/　　pnewnode = NULL;　　}　　else if(ch!='>') {　　idcurrent

89、= SeekoverVt(ch); /*get the id of ch*/　　if (idcurrent == Vt_ID_next){　　Vt[Vt_ID_next-200].ID = Vt_ID_next;/*add it in Vt*/　　Vt[Vt_ID_next-200].Tch = ch;<

90、/p>　　Vt_ID_next++;　　}　　ifavailable = 1;　　}　　if (ifavailable){/*to be transformed*/&l

91、t;/p>　　pt = CreateNewIDNode;　　pt->ID= idcurrent; pt->next= NULL;　　if (pnewnode == NULL){ /*notes CR*/　　Line_Num++;

92、ppro[Line_Num] = pnewnode = pt;　　}　　else {　　pnewnode->next = pt;　　pnewnode = pt;<

93、;p>　　}　　}　　ch = fgetc(fp);　　}　　return OK;　　}&l

94、t;/b>　　Status File_Print (FILE *fp) { /*print the file onto the screen*/　　char ch;　　printf("File Content: (Press any key to contin

95、ue...)\n");　　getch();　　ch = fgetc(fp);　　while (ch!= EOF){　　printf("%c",ch);　　ch =

96、 fgetc(fp);　　}　　printf("\nPress any key to continue...\n");　　getch();　　}</b

97、>　　#ifdef DEBUG　　void debugprint(){　　int i;　　IDNode *pt;　　for (i=0;i<Vn_ID_next-100;i++){&

98、lt;/p>　　printf (" %c ",Vn[i].Nch);　　}　　printf ("\n");　　for (i=0;i<Vn_ID_next-100;i++){&l

99、t;p>　　printf ("%d ",Vn[i].ID);　　}　　printf("\n");　　for (i=0;i<Vt_ID_next-200;i++){　　printf (

100、" %c ",Vt[i].Tch);　　}　　printf("\n");　　for (i=0;i<Vt_ID_next-200;i++){　　printf ("%d "

101、;,Vt[i].ID);　　}　　printf("\n");　　for(i=0;i<=Line_Num;i++){　　pt = ppro[i];　　printf(&q

102、uot;%d.",i);　　while(pt){　　printf("%d-",pt->ID);　　pt=pt->next;　　}　　printf(&q

103、uot;END\n");　　}　　}　　#endif　　int insert2link(IDNode **pdes,IDNode *pNode,in

104、t iffreeit){　　/*insert pNode to *pdes,with the order small to large*/　　/*no same 2, if can't insert,according to iffreeit,free pNode or not, and return 0,else return 1*/</

105、p>　　IDNode *ptd1,*ptd2,*pt=pNode;int cID;　　if(!iffreeit) {/*if iffreeit==0,it means this node is in another link,i can't change it,so copy a new one*/　　pt = Cr

106、eateNewIDNode;　　pt->ID=pNode->ID;　　}　　pt->next = NULL;/*to avoid error*/　　if(*pdes == NULL){/*insert direc

107、tly*/　　*pdes = pt;　　return 1;}　　else if(pt->ID<=(*pdes)->ID){/*at the head*/　　if(pt->ID!=(*pdes)->ID){<p&g

108、t;　　pt->next = *pdes;　　*pdes = pt;　　return 1;　　}　　else{

109、　　if(iffreeit) free(pt);　　return 0;　　}　　}　　else{

110、　　ptd1 = *pdes; ptd2 = ptd1->next;　　if(ptd2) cID = ptd2->ID;　　else cID = -1; /*if at the tail*/　　while(ptd2&&(pt->ID>cID)){</

111、p>　　ptd1 = ptd2; ptd2 = ptd2->next;　　if(ptd2) cID = ptd2->ID;　　else cID = -1;　　}　　if(pt->ID!=c

112、ID){　　pt->next = ptd2; ptd1->next = pt;　　return 1;　　}　　else {

113、　　if(iffreeit) free(pt);　　return 0;　　}　　}　　}</p&

114、gt;　　int add2link(IDNode **pdes,IDNode *psrc,int ifdelsrc,int ifcopyNULL){　　/*the return value notes if the *pdes is changed*/　　int mark=0,NULLID=getVtID('&

115、9;);/*return value*/　　IDNode *ps = psrc,*pt;　　while(ps){　　if(ifcopyNULL||(ps->ID!=NULLID)){/*about '&'*/　　if(ifdelsrc) pt

116、=ps;　　else {　　pt = CreateNewIDNode;　　pt->ID = ps->ID;　　}　　ps = ps->n

117、ext;　　pt->next=NULL;　　mark=insert2link(pdes,pt,1)||mark;/*make sure mark is in the right*/　　}　　else ps = ps->ne

118、xt;　　}　　return mark;　　}　　void DeleteLink(IDNode *p){/*delete the link that p points to*/

119、　　IDNode *pt;　　while(p){　　pt=p;　　p = p->next;　　free(pt);

120、;　　}　　}　　void DeleteAllVnExp(IDNode **pprotemp,int VnID){/*delet all Vn's expression*/　　IDNode *pt;</

121、p>　　int i;　　for(i=0;i<=Line_Num;i++){　　pt=*(pprotemp+i);　　if(pt&&(pt->ID==VnID)){　　Delete

122、Link(pt);　　*(pprotemp+i)=NULL;　　}　　}　　}　　void PrintLink(ID

123、Node *pt,char ins){/*print Link,use ins to divide each character,if ins==0,the result will be consistant*/　　int num;　　char ch;&l

124、t;p>　　while(pt){　　num = pt->ID;　　if(num>=200) ch = Vt[num-200].Tch;　　else ch = Vn[num-100].Nch;　　printf("%c",ch);<

125、;/p>　　if(ins&&pt->next) printf("%c",ins);　　pt = pt->next;　　}　　}<p&

126、gt;　　int CheckVnNoExist(IDNode **pprotemp,int VnID){/*check whether Vn's expression exists.if no,mark it NO*/　　IDNode *pt;　　int i;　　fo

127、r(i=0;i<=Line_Num;i++){　　pt=*(pprotemp+i);　　if(pt&&(pt->ID==VnID))　　return 0;　　}<

128、/p>　　return 1;　　}　　IDNode* getFirstExp(IDNode *pExp,int *ifgetnull){　　/*get First set of one expression t

129、hat pExp points to,with no '&' in the return link*/　　/*ifgetnull returns whether the exp can => &*/　　IDNode *phead=NULL;/*point to the new created link*/</p

130、>　　IDNode *pt;　　while(1){　　if(!pExp){/*get to the tail*/　　*ifgetnull = 1;　　return phead;<

131、;p>　　}　　else if(pExp->ID>=200){　　pt = CreateNewIDNode;　　pt->ID = pExp->ID;pt->next = NULL;　　insert2

132、link(&phead,pt,1);　　*ifgetnull=0;　　if (pExp->ID==getVtID('&')) *ifgetnull = 1;/*in case that S->&*/　　return phead;<p

133、>　　}　　else{/*Vn*/　　add2link(&phead,FirstVn[pExp->ID-100],0,0);　　if(Vn[pExp->ID-100].ifgetnull){　　pExp =

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

編譯課程設(shè)計報告--ll(1)文法判定

文檔簡介

溫馨提示

最新文檔

評論

編譯課程設(shè)計報告--ll(1)文法判定

文檔簡介

溫馨提示

最新文檔

評論

免費下載