編譯課程設(shè)計(jì)報(bào)告--ll(1)文法判定

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

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

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

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

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

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

7、</p><p><b>　　參考文獻(xiàn)12</b></p><p><b>　　附 錄13</b></p><p><b>　　源程序13</b></p><p>　　第一章 前 言</p><p>　　本設(shè)計(jì)使用C語(yǔ)言實(shí)現(xiàn)了對(duì)簡(jiǎn)單方

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

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

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

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

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

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

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

15、字符“-”時(shí)的分情況處理（因?yàn)椤?”也是一個(gè)終結(jié)符）。舉例如下：</p><p>　　/*file:e:\demo1.dat參考文獻(xiàn)1例5.5*/</p><p><b>　　S>AB</b></p><p><b>　　S>bC</b></p><p><b>　　A>

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

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

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

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

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

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

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

23、　　typedef struct IDNode{</p><p>　　unsigned int ID;</p><p>　　struct IDNode *next;</p><p><b>　　}IDNode;</b></p><p>　　結(jié)點(diǎn)中存儲(chǔ)文法符號(hào)的編碼和指向下一結(jié)點(diǎn)的指針。單鏈表集用IDNode*指針數(shù)組表示

24、，即：</p><p>　　IDNode *ppro[100];</p><p>　　詞法分析的結(jié)果，即第i個(gè)產(chǎn)生式轉(zhuǎn)存為單鏈表的規(guī)則如下：</p><p>　　左部作為第一個(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)加入到單鏈表的尾部。例

25、如：</p><p><b>　　S>AB</b></p><p><b>　　S>bC</b></p><p>　　存儲(chǔ)方法為如圖3-1所示</p><p>　　100 101 102</p><p>　　100

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

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

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

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

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

31、<p>　　若某一非終結(jié)符的某一產(chǎn)生式右部為ε,則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。（程序中的操作為：刪除含有對(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)的單鏈表。）</p><p>　　掃描產(chǎn)生式右部的每一符號(hào)</p&

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

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

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

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

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

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

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

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

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

41、;p>　　該過(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集。詳見(jiàn)附錄源程序。</p><p>　　3.2.3 求解非終結(jié)符的FOLLOW集</p>

42、;<p><b>　　算法如下：</b></p><p>　　對(duì)文法中每一A∈VN計(jì)算FOLLOW(A)</p><p>　　設(shè)S為文法中開(kāi)始符號(hào)，把{#}加入FOLLOW（S）中。</p><p>　　若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST（β）的非空元素加入FOLLOW（B）中。</p><p>　　

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

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

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

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

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

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

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

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

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

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

53、號(hào)串進(jìn)行語(yǔ)法分析。</p><p><b>　　4.2 系統(tǒng)測(cè)試</b></p><p>　　4.2.1 測(cè)試一</p><p>　　測(cè)試文法一的測(cè)試數(shù)據(jù)如下:</p><p><b>　　S->AB</b></p><p><b>　　S->bC&

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

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

56、3分別是程序計(jì)算FIRST集、FOLLOW集和SELECT集的運(yùn)行截圖（符號(hào)“ε“由“&”代替）。</p><p><b>　　圖4-2 </b></p><p><b>　　圖4-3</b></p><p>　　圖4-4是程序根據(jù)得到的SELECT集判定輸入文法是否為L(zhǎng)L(1)文法的運(yùn)行截圖。</p>

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

58、<p><b>　　D->+TD</b></p><p><b>　　D->ε</b></p><p><b>　　T->FS</b></p><p><b>　　S->*FS</b></p><p><b>　

59、　S->ε</b></p><p><b>　　F->i</b></p><p><b>　　F->(E)</b></p><p>　　圖4-5、圖4-6、圖4-7分別是程序計(jì)算FIRST集、FOLLOW集和SELECT集的運(yùn)行截圖（符號(hào)“ε“由“&”代替）。</p>&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

80、;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return r;</b></p><p><b>　　}&

81、lt;/b></p><p>　　Status File_Input (FILE *fp) { /*read file fp points to, get all fags,</p><p>　　and transform the oriental words to the form that the syntax analyser can read which is stored

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

109、　　if(iffreeit) free(pt);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else{</b></p>

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

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

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

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

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

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

116、=ps;</p><p><b>　　else {</b></p><p>　　pt = CreateNewIDNode;</p><p>　　pt->ID = ps->ID;</p><p><b>　　}</b></p><p>　　ps = ps->n

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

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

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

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

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

122、Link(pt);</p><p>　　*(pprotemp+i)=NULL;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void PrintLink(ID

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

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

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

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

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

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

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

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

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

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

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