編譯課程設(shè)計報告

1、華北電力大學(xué)（北京）編譯原理課程設(shè)計LL(1)文法判定 -c語言實現(xiàn)專業(yè)班號_計算機(jī)021_學(xué)生姓名_ _指導(dǎo)教師_ _ 目 錄第一章 前 言11.1 LL(1)文法概述11.2 設(shè)計思想概述1第二章 語言文法規(guī)則12.1 語言的詞法規(guī)則12.2 語言的語法規(guī)則2第三章 程序設(shè)計23.1 詞法分析程序的實現(xiàn)23.1.1 文法輸入規(guī)則23.1.2 數(shù)據(jù)結(jié)構(gòu)23.1.3 程序流程43.2 求解FIRST集、FOLLOW集和SELECT集的實現(xiàn)53.2.1 求出能推出的非終結(jié)符53.2.2 求解產(chǎn)生式的右部的FIRST集63.2.3 求解非終結(jié)符的FOLLOW集73.2.4 求解產(chǎn)生式的SELECT

2、集73.3 判定是否是LL(1)文法的實現(xiàn)73.4 預(yù)測分析表的生成實現(xiàn)73.5 判定給定符號串是否是文法中的句子的實現(xiàn)8第四章 系統(tǒng)運(yùn)行及測試94.1 運(yùn)行和安裝環(huán)境94.2 系統(tǒng)運(yùn)行94.2 系統(tǒng)測試94.2.1 測試一94.2.2 測試二10第五章 結(jié) 論115.1 系統(tǒng)結(jié)論115.2 存在的不足12參考文獻(xiàn)12附 錄13源程序1337第一章 前 言本設(shè)計使用C語言實現(xiàn)了對簡單方法描述的LL(1)文法的判定。該設(shè)計程序?qū)崿F(xiàn)了：分別求出每一產(chǎn)生式的右部的FIRST 集、每一個非終結(jié)符的FOLLOW集和每一產(chǎn)生式的SELECT集；判定是否是LL(1)文法；畫出預(yù)測分析表；對給定的符號串判定是

3、否是文法中的句子，分析過程用計算機(jī)打印出來。1.1 LL(1)文法概述LL(1)文法是一種2型文法，由它所描述的語言可以使用自頂向下語法分析方法進(jìn)行語法分析。LL(1)文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導(dǎo)，1表明只需向右看一個符號便可決定如何推導(dǎo)即選擇哪一個產(chǎn)生式（規(guī)則）進(jìn)行推導(dǎo)。一個上下文無關(guān)文法（即2型文法）是LL（1）文法的充分必要條件是，對每個非終結(jié)符A的兩個不同產(chǎn)生式，A，A，滿足SELECT（A）SELECT（A）= ø其中、不同時能1。1.2 設(shè)計思想概述首先對輸入的文法進(jìn)行詞法分析，識別出所有的文法符號（終結(jié)符

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

5、母的集合，終結(jié)符集VT為所有小寫字母、數(shù)字和四則運(yùn)算符號的集合，取所有文法符號均為單個字符。2.2 語言的語法規(guī)則由2型文法的定義，定義如下：設(shè)G=（VN，VT，P，S），若P中的每一個產(chǎn)生式滿足： 是一非終結(jié)符， (VNVT)*則此文法稱為2型的或上下文無關(guān)的1。規(guī)定產(chǎn)生式的左部必須為非終結(jié)符。第三章 程序設(shè)計3.1 詞法分析程序的實現(xiàn)3.1.1 文法輸入規(guī)則源文法的輸入采用文件輸入的方式，每讀入一個字符就進(jìn)行文法符號的判定、記錄和編碼，同時對產(chǎn)生式以特定格式存儲。文件中源產(chǎn)生式的書寫格式規(guī)定如下：格式為“左部>右部”，左部為一非終結(jié)符，右部的文法符號之間不允許有空格，右部結(jié)束后直接回

6、車或文件結(jié)束，規(guī)定文件的第一個字符為文法的開始符號；格式中使用“>”而非“->”的原因在于簡化詞法分析，可以避免在讀入字符“-”時的分情況處理（因為“-”也是一個終結(jié)符）。舉例如下：/*file:e:demo1.dat參考文獻(xiàn)1例5.5*/S>ABS>bCA>&A>bB>&B>aDC>ADC>bD>aSD>c3.1.2 數(shù)據(jù)結(jié)構(gòu)對非終結(jié)符和終結(jié)符分別采用以下的數(shù)據(jù)結(jié)構(gòu)存儲：typedef struct Vn_struunsigned int ID;char Nch;unsigned int ifgetnul

7、l;Vn_type;Vn_type Vn100;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,202,程序最多允許100個非終結(jié)符，即編碼范圍在200299之間。對于終結(jié)符，采用同樣的規(guī)則對其編碼，編碼范圍在300399之間），Nch存儲其字符，ifgetnull指示該終結(jié)符能否推出，用于對三個集合的求解過程中。Vn存儲所有的非終結(jié)符。Vn_ID_next指示下一個可用的非終結(jié)符的編碼值，初始為20

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

9、;結(jié)點中存儲文法符號的編碼和指向下一結(jié)點的指針。單鏈表集用IDNode*指針數(shù)組表示，即：IDNode *ppro100;詞法分析的結(jié)果，即第i個產(chǎn)生式轉(zhuǎn)存為單鏈表的規(guī)則如下：左部作為第一個結(jié)點，該結(jié)點的地址存儲在pproi中，即第i個產(chǎn)生式的首結(jié)點地址存儲在ppro的第i個元素中,右部第一個符號作為第二個結(jié)點，向右依次將右部所有文法符號對應(yīng)的結(jié)點加入到單鏈表的尾部。例如：S>ABS>bC存儲方法為如圖3-1所示ppro0ppro1ppro2200201202 NULL200300300 NULL 100 101 102 100 200 103 圖3-1（假定S、A、B、C、b的編

10、碼分別為100、101、102、103、200）3.1.3 程序流程詞法分析由函數(shù)File_Input (FILE *fp)實現(xiàn)，具體實現(xiàn)見附錄源程序。以下是程序的流程圖：否從文件中讀入一個字符否否是檢查Vn中是否存在此符號,若無,填之是準(zhǔn)備在pproi+1中填入結(jié)點若字符不是>判定為終結(jié)符檢查Vt中是否存在此符號,若無,填之在pproi中填入代表該字符的結(jié)點讀入下一個字符是結(jié)束是否為非終結(jié)符是否為EOF文件結(jié)束符是否為回車換行圖3-23.2 求解FIRST集、FOLLOW集和SELECT集的實現(xiàn)存儲FIRST集、FOLLOW集和SELECT集的數(shù)據(jù)結(jié)構(gòu)采用如圖3-1的單鏈表集，分別命名

11、為FirstRight、Follow和Select，在這里，每個結(jié)點的ID必然大于等于300，因為這些集合的元素都必然是終結(jié)符。每個單鏈表中的結(jié)點將按其ID的大小順序由小到大排列。需要指出的是，對三個集合的求解在算法上是對單鏈表集ppro進(jìn)行若干種鏈表操作的組合，故具體過程（分別由getFirstVn()、getFirstRight()、etFollow()和getSelect()實現(xiàn)）不再給出，下面給出的是邏輯算法。3.2.1 求出能推出的非終結(jié)符算法如下：1) 將結(jié)構(gòu)體數(shù)組Vn中對應(yīng)每一非終結(jié)符的能否推出的標(biāo)記ifgetnull（如前所述，ifgetnull為結(jié)構(gòu)體變量Vn_type的成員

12、變量，見3.1.2）置初值“未定”即2。2) 掃描方法中的產(chǎn)生式（程序中的掃描對象為ppro的拷貝pprotemp）。a) 刪除所有右部含有終結(jié)符的產(chǎn)生式，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)記值改為“否”，說明該非終結(jié)符不能推出。（在程序中的操作為：刪除含有ID大于或等于300的結(jié)點的單鏈表，若這使得表示某一非終結(jié)符為左部的產(chǎn)生式的所有單鏈表都被刪除，則將Vn中對應(yīng)的ifgetfull置為0）b) 若某一非終結(jié)符的某一產(chǎn)生式右部為,則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。（程序中的操作為：刪除含有對應(yīng)的ID的結(jié)

13、點的單鏈表，置該單鏈表的第一個結(jié)點所表示的非終結(jié)符對應(yīng)的Vn中元素的ifgetnull為1，并從pprotemp刪除所有以該非終結(jié)符對應(yīng)的結(jié)點為第一結(jié)點的單鏈表。）3) 掃描產(chǎn)生式右部的每一符號a) 若所掃描到的非終結(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é)符

14、對應(yīng)的結(jié)點為第一結(jié)點的單鏈表）b) 若所掃描到的非終結(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。）4) 重復(fù)3），直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對應(yīng)的特征再沒有改變?yōu)橹?。（程序中設(shè)置了標(biāo)志變量ifVnChanged用以標(biāo)識非終結(jié)符對應(yīng)的特征有沒有改變。）1該過程由函數(shù)getNULLVn()實現(xiàn)，由于對存儲文法的鏈表

15、有刪除操作，為保護(hù)數(shù)據(jù)，函數(shù)開始時先從ppro拷貝了一個臨時單鏈表集pprotemp,所有刪除操作均在后者中進(jìn)行，并在程序結(jié)束時釋放了pprotemp的地址空間。函數(shù)的結(jié)果存儲在Vn中。3.2.2 求解產(chǎn)生式的右部的FIRST集首先，計算每個文法符號的FIRST集。由定義：FIRST（）=a|a,aVT，a、V*，若，則規(guī)定FIRST（）對每一文法符號XV計算FIRST（X）。a) 若XVT，則FIRST（X）=Xb) 若XVN，且有產(chǎn)生式Xa，aVT則aFIRST（X）c) 若XVN，X，則FIRST（X）d) 若XVN，Y1，Y2，Yi都VN，而有產(chǎn)生式XY1Y2Yn。當(dāng)Y1，Y2，Yi-

16、1都時，（其中1in），則FIRST（Y1）-，F(xiàn)IRST（Y2）-， FIRST（Yi-1）-，F(xiàn)IRST（Yi）都包含在FIRST（X）中。e) 當(dāng)d)中所有Yi ，（i=1，2，n）則FIRST（X）=FIRST（Y1）FIRST（Y2）FIRST（Yn）。反復(fù)使用上述(b)(e)步直到每個符號的FIRST集合不再增大為止。求出每個文法符號的FIRST集合后也就不難求出一個符號串的FIRST集合。若符號串V*，=X1X2Xn，當(dāng)X1不能，則置FIRST（）=FIRST（X1）。若對任何j(1ji-1,2in)，F(xiàn)IRST（Xj）則FIRST（）=（FIRST（Xj）-）FIRST（Xi）

17、當(dāng)所有FIRST（Xj）(1jn)都含有時，則FIRST（）=（FIRST（Xj）1。由此算法可計算出各文法符號的FIRST集和各產(chǎn)生式的右部的FIRST集，分別存儲在FirstVn和FirstRight中。定義如下：/*LL(1).h*/IDNode *FirstVn100; IDNode *FirstRight100;該過程分別由函數(shù)getFirstVn()和getFirstRight()實現(xiàn)，兩者又調(diào)用了兩個鏈表操作函數(shù)insert2link()和add2link()以及一個輔助函數(shù)getFirstExp()來實現(xiàn)具體功能，后三都的功能分別為插入結(jié)點到單鏈表、拷貝單鏈表到另一單鏈表、得到

18、任意字符串的FIRST集。詳見附錄源程序。3.2.3 求解非終結(jié)符的FOLLOW集算法如下：對文法中每一AVN計算FOLLOW(A)a) 設(shè)S為文法中開始符號，把#加入FOLLOW（S）中。b) 若AB是一個產(chǎn)生式，則把FIRST（）的非空元素加入FOLLOW（B）中。如果則把FOLLOW（A）也加入FOLLOW（B）中。c) 反復(fù)使用（b）直到每個非終結(jié)符的FOLLOW集不再增大為止1。由此算法可計算出非終結(jié)符號的FOLLOW集，存儲在Follow中。定義如下：/*LL(1).h*/IDNode *Follow100;該過程由函數(shù)getFollow()實現(xiàn)。函數(shù)中調(diào)用getFirstExp(

19、)取得“FIRST（）的非空元素”；調(diào)用add2link()“把FOLLOW（A）也加入FOLLOW（B）中”。詳見附錄源程序。3.2.4 求解產(chǎn)生式的SELECT集計算SELECT集的算法如下：對于任一產(chǎn)生式，若其左部的非終結(jié)符號不能推出，則其SELECT集等于右部的FIRST集；反之，SELECT集等于右部的FIRST集的非空元素與左部的非終結(jié)符的FOLLOW集的所有元素組成的集合。該過程由函數(shù)getSelect()實現(xiàn)。計算出的表達(dá)式的SELECT集存儲在Select中。定義如下：/*LL(1).h*/IDNode *Select100;3.3 判定是否是LL(1)文法的實現(xiàn)如“1.1

20、LL(1)文法概述”中所述，一個上下文無關(guān)文法是否是LL(1)文法關(guān)鍵在于每個非終結(jié)符的兩個不同產(chǎn)生式的SELECT集是否存在交集，若存在則不是LL(1)文法，反之則可以判定該輸入文法是LL(1)文法。該過程由函數(shù)judgeLL1()實現(xiàn)。3.4 預(yù)測分析表的生成實現(xiàn)預(yù)測分析表可用一個矩陣M(或稱二維數(shù)組)表示。矩陣的元素MA,a中的下標(biāo)A表示非終結(jié)符,a為終結(jié)符或句子括號“#”,矩陣元素MA,a中的內(nèi)容為一條關(guān)于A的產(chǎn)生式,表明當(dāng)用非終結(jié)符A向下推導(dǎo)時,面臨輸入符a時,所應(yīng)采取的候選產(chǎn)生式,當(dāng)元素內(nèi)容無產(chǎn)生式時,則表明用A為左部向下推導(dǎo)時遇到了不該出現(xiàn)的符號,因此元素內(nèi)容為轉(zhuǎn)身出錯處理的信息

21、1。算法如下：對每個終結(jié)符或“#”號用a表示。aSELECT(A),則把的頭指針放入MA,a中。把無定義的MA,a置為NULL空指針。該過程由函數(shù)getpa_table()實現(xiàn)，該函數(shù)以Select為輸入數(shù)據(jù)，計算所得分析表存儲在結(jié)構(gòu)體pa_table的變量中。pa_table的定義如下：/*LL(1).h*/typedef struct pa_tableIDNode *ptb;int *row_info,*col_info;int row_num,col_num;pa_table;3.5 判定給定符號串是否是文法中的句子的實現(xiàn)預(yù)測分析程序的工作過程用示意圖3-3表示圖3-3 第四章 系統(tǒng)運(yùn)行

22、及測試4.1 運(yùn)行和安裝環(huán)境Windows XP Professional + Turbo C2.04.2 系統(tǒng)運(yùn)行a) 首先將所需判定的文法按“3.1.1 文法輸入規(guī)則”中的要求寫入自定義的文件中，該文件稱作文法文件。b) 運(yùn)行程序LL1.exe,按照屏幕提示，輸入文法文件的路徑和文件名。c) 程序?qū)⒁徊讲竭M(jìn)行LL(1)文法的判定。d) 若判定為LL(1)文法，則輸出預(yù)測分析表，并提示輸入符號串進(jìn)行語法分析。4.2 系統(tǒng)測試4.2.1 測試一測試文法一的測試數(shù)據(jù)如下:S->ABS->bCA->A->bB->B->aDC->ADC->bD->

23、;aSD->c圖4-1、圖4-2、圖4-3分別是程序計算FIRST集、FOLLOW集和SELECT集的運(yùn)行截圖（符號“由“&”代替）。圖4-1圖4-2 圖4-3圖4-4是程序根據(jù)得到的SELECT集判定輸入文法是否為LL(1)文法的運(yùn)行截圖。圖4-4如圖4-4所示，經(jīng)程序判定，該輸入文法不是LL(1)文法。4.2.2 測試二測試文法二的測試數(shù)據(jù)如下:E->TDD->+TDD->T->FSS->*FSS->F->iF->(E)圖4-5、圖4-6、圖4-7分別是程序計算FIRST集、FOLLOW集和SELECT集的運(yùn)行截圖（符號“由“&

24、amp;”代替）。圖4-5圖4-6圖4-7圖4-8是程序根據(jù)得到的SELECT集判定輸入文法是否為LL(1)文法的運(yùn)行截圖。圖4-8如圖4-8所示，經(jīng)程序判定，該輸入文法是LL(1)文法。根據(jù)屏幕提示，輸入符號串i+i*i#，由程序判定是否是文法中的句子，分析過程在打印在屏幕上，如圖4-9所示。圖4-9如圖中最后一行所示， i+i*i#是該文法的句子。測試完畢。第五章 結(jié) 論5.1 系統(tǒng)結(jié)論本設(shè)計用C語言成功實現(xiàn)了對LL(1)文法的判定，達(dá)到了課程設(shè)計題目中的所有要求，并且操作簡單、易上手，輸出結(jié)果清晰明了，可以作為編譯原理初學(xué)者的學(xué)習(xí)工具，也可以作為編譯原理課上的演示程序。本設(shè)計的設(shè)計亮點在

25、于使用單鏈表集存儲關(guān)鍵數(shù)據(jù)，實現(xiàn)了判定過程的高效率；同時針對鏈表操作的復(fù)雜和易出錯的特點，設(shè)計者設(shè)計出了幾個基本卻功能強(qiáng)大的鏈表操作函數(shù)，如insert2link()、add2link()，提供給各主要函數(shù)調(diào)用。這樣的做法，既提高的程序的開發(fā)效率和運(yùn)行效率，又增強(qiáng)了程序運(yùn)行的穩(wěn)定性，此外，還大大提高了程序的可重用性。除了高標(biāo)準(zhǔn)的完成了設(shè)計要求，在這次課程設(shè)計中，設(shè)計者對編程技術(shù)也有了更進(jìn)一步的理解和體會，并借此機(jī)會大大提高了對C語言的駕馭能力，可謂受益匪淺。希望以后能有更多的機(jī)會得以鍛煉和施展才能。5.2 存在的不足當(dāng)然，由于能力所限，本設(shè)計也有一些不足：其一，沒有實現(xiàn)實時輸入文法，只采用了文

26、件輸入；其二，對于文法的要求過于苛刻，文法符號只能由一位字符構(gòu)成；其三，程序中過多地采用了全局變量，模塊化的程度太低；其四，程序幾乎處理錯誤能力很低，遇非規(guī)則輸入則死機(jī)?？偟膩碚f，雖然這些不足不影響程序?qū)L(1)文法判定的演示和教學(xué)效果，但是其判定功能卻因為這些不足而被大大削弱。有時間的話，設(shè)計者會對該程序做進(jìn)一步的改進(jìn)。參考文獻(xiàn)1 呂映芝,張素琴,蔣維杜.編譯原理.第1版.北京:清華大學(xué)出版社,2021附 錄源程序#include "stdlib.h"#include "stdio.h"#include <string.h> #inclu

27、de "e:ll1.h"#include "dir.h"/*#define DEBUG*/void initiate()int i;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+)pproi=NULL;Vni.ifgetnull = UNCERTAIN;FirstVni = NULL;FirstRighti = NULL;Followi = NULL;Sel

28、ecti = NULL;int getVnID(char ch)/*get the ID of Vn according to itselt*/int i=0;for (;i<Vn_ID_next-100;i+)if (Vni.Nch=ch) return Vni.ID;return 0;int getVtID(char ch)/*get the ID of Vt according to itselt*/int i=0;for (;i<Vt_ID_next-200;i+)if (Vti.Tch=ch) return Vti.ID;return 0;int getID(char c

29、h)/*get the ID of V*/int i;i = getVnID(ch);if(i=0) i = getVtID(ch);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_ID_next;for (;i<Vn_ID_next-100;i+)if (ch = Vni.Nch)r = Vni.ID;break;return r;int SeekoverVt(char ch) /*scan vt, if ch i

30、n,then return its id,else return Vt_ID_next*/int i=0,r = Vt_ID_next;for (;i<Vt_ID_next-100;i+)if (ch = Vti.Tch)r = Vti.ID;break;return r;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 stor

31、ed in ppro*/char ch;int idcurrent;int ifavailable;/*notes whether to be transformed*/IDNode *pnewnode = NULL; /*pointer to the last node*/IDNode *pt;/*temp pointer*/Line_Num = -1;ch = fgetc(fp);while (ch != EOF)ifavailable = 0;/*to get ready*/if (ch='|')/*for example S->AB|bC,'|'

32、means a new expression*/ifavailable = 1;/*notes to be transformed*/idcurrent = pproLine_Num->ID;/*left part*/pnewnode = NULL;/*a new expression*/else if (ch>='A') && (ch<='Z')idcurrent = SeekoverVn(ch); /*get the id of ch*/if (idcurrent=Vn_ID_next)VnVn_ID_next-100.ID

33、 = Vn_ID_next;/*add it in Vn*/VnVn_ID_next-100.Nch = ch;Vn_ID_next+;ifavailable = 1;/*notes to be transformed*/else if (ch='n')/*carriage return*/pnewnode = NULL;else if(ch!='>') idcurrent = SeekoverVt(ch); /*get the id of ch*/if (idcurrent = Vt_ID_next)VtVt_ID_next-200.ID = Vt_ID

34、_next;/*add it in Vt*/VtVt_ID_next-200.Tch = ch;Vt_ID_next+;ifavailable = 1;if (ifavailable)/*to be transformed*/pt = CreateNewIDNode;pt->ID= idcurrent; pt->next= NULL;if (pnewnode = NULL) /*notes CR*/Line_Num+;pproLine_Num = pnewnode = pt;else pnewnode->next = pt;pnewnode = pt;ch = fgetc(f

35、p);return OK;Status File_Print (FILE *fp) /*print the file onto the screen*/char ch;printf("File Content: (Press any key to continue.)n");getch();ch = fgetc(fp);while (ch!= EOF)printf("%c",ch);ch = fgetc(fp);printf("nPress any key to continue.n");getch();#ifdef DEBUGvoi

36、d debugprint()int i;IDNode *pt;for (i=0;i<Vn_ID_next-100;i+) printf (" %c ",Vni.Nch);printf ("n");for (i=0;i<Vn_ID_next-100;i+) printf ("%d ",Vni.ID);printf("n");for (i=0;i<Vt_ID_next-200;i+) printf (" %c ",Vti.Tch);printf("n");for

37、 (i=0;i<Vt_ID_next-200;i+) printf ("%d ",Vti.ID);printf("n");for(i=0;i<=Line_Num;i+)pt = pproi;printf("%d.",i);while(pt)printf("%d-",pt->ID);pt=pt->next;printf("ENDn");#endifint insert2link(IDNode *pdes,IDNode *pNode,int iffreeit)/*insert

38、 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*/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 = C

39、reateNewIDNode;pt->ID=pNode->ID;pt->next = NULL;/*to avoid error*/if(*pdes = NULL)/*insert directly*/*pdes = pt;return 1;else if(pt->ID<=(*pdes)->ID)/*at the head*/if(pt->ID!=(*pdes)->ID)pt->next = *pdes;*pdes = pt;return 1;elseif(iffreeit) free(pt);return 0;elseptd1 = *pd

40、es; ptd2 = ptd1->next;if(ptd2) cID = ptd2->ID;else cID = -1; /*if at the tail*/while(ptd2&&(pt->ID>cID)ptd1 = ptd2; ptd2 = ptd2->next;if(ptd2) cID = ptd2->ID;else cID = -1;if(pt->ID!=cID)pt->next = ptd2; ptd1->next = pt;return 1;else if(iffreeit) free(pt);return 0;

41、int add2link(IDNode *pdes,IDNode *psrc,int ifdelsrc,int ifcopyNULL)/*the return value notes if the *pdes is changed*/int mark=0,NULLID=getVtID('&');/*return value*/IDNode *ps = psrc,*pt;while(ps)if(ifcopyNULL|(ps->ID!=NULLID)/*about '&'*/if(ifdelsrc) pt=ps;else pt = Create

42、NewIDNode;pt->ID = ps->ID;ps = ps->next;pt->next=NULL;mark=insert2link(pdes,pt,1)|mark;/*make sure mark is in the right*/else ps = ps->next;return mark;void DeleteLink(IDNode *p)/*delete the link that p points to*/IDNode *pt;while(p)pt=p;p = p->next;free(pt);void DeleteAllVnExp(IDN

43、ode *pprotemp,int VnID)/*delet all Vn's expression*/IDNode *pt;int i;for(i=0;i<=Line_Num;i+)pt=*(pprotemp+i);if(pt&&(pt->ID=VnID)DeleteLink(pt);*(pprotemp+i)=NULL;void PrintLink(IDNode *pt,char ins)/*print Link,use ins to divide each character,if ins=0,the result will be consistant

44、*/int num;char ch;while(pt)num = pt->ID;if(num>=200) ch = Vtnum-200.Tch;else ch = Vnnum-100.Nch;printf("%c",ch);if(ins&&pt->next) printf("%c",ins);pt = pt->next;int CheckVnNoExist(IDNode *pprotemp,int VnID)/*check whether Vn's expression exists.if no,mark

45、it NO*/IDNode *pt;int i;for(i=0;i<=Line_Num;i+)pt=*(pprotemp+i);if(pt&&(pt->ID=VnID)return 0;return 1;IDNode* getFirstExp(IDNode *pExp,int *ifgetnull)/*get First set of one expression that pExp points to,with no '&' in the return link*/*ifgetnull returns whether the exp can

46、 => &*/IDNode *phead=NULL;/*point to the new created link*/IDNode *pt;while(1)if(!pExp)/*get to the tail*/*ifgetnull = 1;return phead;else if(pExp->ID>=200)pt = CreateNewIDNode;pt->ID = pExp->ID;pt->next = NULL;insert2link(&phead,pt,1);*ifgetnull=0;if (pExp->ID=getVtID(&

47、#39;&') *ifgetnull = 1;/*in case that S->&*/return phead;else/*Vn*/add2link(&phead,FirstVnpExp->ID-100,0,0);if(VnpExp->ID-100.ifgetnull)pExp = pExp->next;else*ifgetnull = 0;return phead;/*while*/int ifCross(IDNode *p1,IDNode *p2)/*judge if p1 p2 has the same node,if has t

48、hen print out in the form of .,.,.*/IDNode *pt1=p1,*pt2=p2;int ID1,ID2,mark=0,r=0;/*mark notes if it's the first same character,used to control if print out ','*/while(pt1)ID1 = pt1->ID;while(pt2)ID2 = pt2->ID;if(ID1=ID2) if(mark) printf(",");/*if not the first, print 

49、9;,'*/else printf("");printf("%c",VtID1-200.Tch);mark = 1;r = r|1;/*r stores the result*/pt2 = pt2->next;pt1 = pt1->next;if(r) printf("");/*if not LL(1),print the remaining ''*/return r;void getNULLVn()/*to decide the Vn that can deduct,the result is s

50、tored in Vn &*/int i,j,LeftID;IDNode *pprotemp=(IDNode*)malloc(sizeof(IDNode*)*(Line_Num+1);IDNode *pt1,*pt2;/*temp pointers*/int ifVnChanged; /*mark whether the ifgetnull changes in stage 3*/char ch; /*for printing*/for(i=0;i<=Line_Num;i+)*(pprotemp+i)=NULL;/*Copy PProArray*/for(i=0;i<=Li

51、ne_Num;i+)pt1=pproi;*(pprotemp+i) = pt2 = CreateNewIDNode;pt2->ID = pt1->ID;pt2->next = NULL;while(pt1->next!=NULL)pt1 = pt1->next;pt2->next = CreateNewIDNode;pt2 = pt2->next;pt2->ID = pt1->ID;pt2->next = NULL;/*#ifdef DEBUGfor(i=0;i<=Line_Num;i+)pt1 = pprotempi;prin

52、tf("%d.",i);while(pt1)printf("%d-",pt1->ID);pt1=pt1->next;printf("ENDn");#endif*/*The second stage*/for(i=0;i<=Line_Num;i+)pt1 = *(pprotemp+i);if(pt1) /*in case that this link was deleted*/LeftID = pt1->ID;pt2 = pt1->next; /*point to the right part*/if(pt2->ID = getVtID('&')VnLeftID-100.ifgetnull = YES;DeleteAllVnExp(pprotemp,LeftID);/*de