C語言編寫源程序建立LR分析器

1、目 錄前 言1用C語言編寫源程序建立LR(1)分析器2一，設(shè)計目的，要求，算法與設(shè)計思想21.設(shè)計內(nèi)容22.設(shè)計要求23.設(shè)計的基本原理31.CLOSURE(I)的構(gòu)造32.GO(I,X)的構(gòu)造33.FIRST集合的構(gòu)造34.LR(1)分析表的構(gòu)造3二，LR（1）分析器41.LR(1)分析器的實現(xiàn)圖：42.LR分析器與邏輯結(jié)構(gòu)及工作過程4三，總體方案設(shè)計51. 各模塊設(shè)計6四，程序測試71.教科書的第142頁文法的LR1分析器的構(gòu)造和語法分析72.表達式文法的LR1分析器的構(gòu)造和語法分析器8五，源程序10六，總結(jié)19七，參考文獻19前 言編譯原理是計算機專業(yè)的一門重要的專業(yè)課程，其中包含大量軟

2、件設(shè)計細想。通過課程設(shè)計，實現(xiàn)一些重要的算法，或設(shè)計一個完整的編譯程序模型，能夠進一步加深理解和掌握所學(xué)知識，對提高自己的軟件設(shè)計水平具有十分重要的意義。我選的是老師給的題，并予以擴充。即對任意給定的問法G構(gòu)造LR(1)項目集規(guī)范族，其中要實現(xiàn)CLOSURE(1)，GO(I,X)，F(xiàn)IRST集合符。在此基礎(chǔ)上，構(gòu)造了LR(1)分析表。然后對輸入的句子進行語法分析，給出接受或出錯報告。程序采用文件輸入輸出方式。其中包括兩個輸入文件：文法grammar.txt，以及輸入串input.txt；兩個輸出文件:項目集items.txt和文法的LR(1)分析表action_table.txt。由于語法分析

3、的結(jié)果只給出接受或錯誤報告，比較簡單。所以直接在屏幕上輸出，也便于用戶查看。在具體編寫程序中，對文法操作的各個功能模塊獨立成為一個子程序，而對具體輸入穿得分析則放在main()函數(shù)中進行。各個變量奇函數(shù)的意義和用法我將在論述程序設(shè)計的通體方案中向西給出。程序的通體算法細想來自編譯原理課程。具體實現(xiàn)有我獨立完成。程序用C/C+語言編寫。在Microsoft Visual C+2005環(huán)境下調(diào)使通過。用C語言編寫源程序建立LR(1)分析器一，設(shè)計目的，要求，算法與設(shè)計思想1.設(shè)計內(nèi)容 對任意給定的上下文無關(guān)文法G，構(gòu)造其LR(1)項目集族，并且在此基礎(chǔ)上進一步構(gòu)造其LR(1)分析表。然后分析輸入的

4、句子。2.設(shè)計要求對輸入的文法G（要求是上下文無關(guān)文法），在程序終實現(xiàn)CLOSURE(1),GO(I,X)，F(xiàn)RIST等的構(gòu)造，并利用這些功能函數(shù)構(gòu)造出LR(1)項目集族。并且輸出結(jié)果。在此基礎(chǔ)上構(gòu)造G的LR(1)分析表（這個表也輸出給用戶），并對輸入的句子進行語法分析表，給出分析結(jié)果。3.設(shè)計的基本原理1.CLOSURE(I)的構(gòu)造CLOSURE(I)表示和I中項目可以識別同樣活前綴的所有項目的集合。它可以有以下方法得到：(1)I中的所有項目都屬于CLOSURE(I)；(2)若項目Aa.B,a屬于CLOSURE(I)，B是一個產(chǎn)生式，那么，對于FIRST中的每一個中介符b,如果.,b原來不在

5、CLOSURE(I)中，則把它加進去；(3)重復(fù)執(zhí)行步驟（2），直到CLOSURE(I)不再增大為止。2.GO(I,X)的構(gòu)造GO(I,X)=CLOSURE(J)其中J=任何形如AaX.,a的項目Aa.X.,a屬于I3.FIRST集合的構(gòu)造在這個程序中使用的是FIRST(a)，這基于每一個非終結(jié)符的FRIST集合（終結(jié)符的FIRST就是它本身）。所以需要對每一個非終結(jié)符構(gòu)造其FIRST集合。方法如下：連續(xù)使用下面的規(guī)則，直到每個集合FIRST不再增大為止。（1） 若X屬于VT，則FIRST(X)=X。（2）若X屬于VN，且有產(chǎn)生式Xa，則把A加入到FIRST(X)中；若X也是一條產(chǎn)生式，則把也

6、加入到FIRST中。4.LR(1)分析表的構(gòu)造在實現(xiàn)GO(I,X)時，記錄下狀態(tài)的轉(zhuǎn)化。得到分析表中的移進部分。然后再掃描所有的項目集，找到其中包含歸約項目的哪些項目集，根據(jù)其中項目，得到分析表中那些鬼月的部分。二，LR（1）分析器1.LR(1)分析器的實現(xiàn)圖：圖1 LR（1）分析器的實現(xiàn)2.LR分析器與邏輯結(jié)構(gòu)及工作過程圖2 LR分析器的邏輯結(jié)構(gòu)三，總體方案設(shè)計在main()函數(shù)中讀入文件，并堆文法進行擴展，同時記錄下文法的所有終結(jié)符和非終結(jié)符，對每個非終結(jié)符計算它的FIRST集合。以備在計算CLOSURE(1)時使用。然后調(diào)用GO()函數(shù)。完成LR(1)項目集組的計算。計算的結(jié)果記錄到IT

7、EMS.TXT中。并且記錄下狀態(tài)之間轉(zhuǎn)換關(guān)系。接下來，調(diào)用GET_ACTION()根據(jù)上面的項目集族和記錄的狀態(tài)轉(zhuǎn)換數(shù)組獲得LR(1)分析表。然后就可以對輸入的句子進行語法檢查。程序中主要變量以及函數(shù)的說明如下：char str_vn2020; / 存放輸入的文法：為簡單起見，設(shè)問發(fā)的產(chǎn)生式條 數(shù)不多于20條，每個產(chǎn)生式不多與20個字符，用 表示，且產(chǎn)生式輸入的時候要以S結(jié)束。int length 20; / 每條產(chǎn)生式的長度int number=0; / 產(chǎn)生式的條數(shù)bool tempofinput /記錄哪些ASCII字符在文法中，以求得所有的VT和VNchar str_vn20; /記錄

8、所有的非終結(jié)符int size_vn=0; /記錄非終結(jié)符的個數(shù)char str_vt150; /記錄所有的終結(jié)符int size_vt=0; /記錄終結(jié)符的個數(shù)bool first_vn30150; /記錄每個非終結(jié)符的FIRST集char buffer50; /用來存放CLOSURE(I)時需要的FIRST_SET 也用來讀入用戶的輸入電int bsize=0 / buffer的有效長度struct thri int beg; int nex; char ch; ; thri trans200; /定義狀態(tài)轉(zhuǎn)換組中的元素格式 int size-trans=0; /用來在go()函數(shù)中記錄狀

9、態(tài)間的轉(zhuǎn)換trans數(shù)組 的大小 struct proj int part; char expc; ; /定義項目集的格式 proj irems100100; /項目集數(shù)組，假設(shè)項目集的個數(shù)不超過100個， 且每個項目集中的項目個數(shù)不超過100個 int CCOUNT=0; /項目集的個數(shù) int size_item100; /每個項目集中的項目個數(shù) struct action char ch; /定義狀態(tài)轉(zhuǎn)換表的格式int nxt_sta; ; /定義狀態(tài)轉(zhuǎn)換表的格式action action_table100100; /狀態(tài)轉(zhuǎn)換表 int size_act_table100; / 輸入文法

10、的文件指針ifstream G_ifile; / 輸入句子的文件指針ofstream input_ifile; / 輸出項目集族的文件指針ofstream items_ofile; / 輸出轉(zhuǎn)換表的文件指針void read_G() / 計算每個非終結(jié)符的FIRST集合void get_first() / 判斷項目temp是否已經(jīng)在項目集族 itemsT中 bool is_in(proj temp,int,T) / 計算itemTclosure(1)時用到的frst(a) void e_closure(intT) / 計算itemsT的closure閉包 int is_containd() /

11、判斷新生成的項目集是否已經(jīng)de 在項目集 族中 void go() /實現(xiàn)go(1)的功能 void get_action() /生成LR(1)表 int main() / 調(diào)用個個子模塊，并在其中堆輸入串進行語法分析1. 各模塊設(shè)計1.讀入模塊：Read_G()文法要為上下無關(guān)文法。輸入文件的格式為：首先輸入產(chǎn)生式的條數(shù)：每條產(chǎn)生式的第一個字符為非終結(jié)符。以S結(jié)尾。輸入的同時用tempofinputtemp=true來記錄符temp。為統(tǒng)計有哪些非終結(jié)符和終結(jié)符作準(zhǔn)備。這些都通過ASCLL碼對應(yīng)位是否為true來判斷。2.計算FIRST模塊：get_first()現(xiàn)設(shè)計FLAG1表示本輪掃描

12、first_vn中有沒有新增加的內(nèi)容。要是有，還有進行下一次掃描。每一輪掃描所有的產(chǎn)生式，在掃描每一個產(chǎn)生式的時候，設(shè)置一個下標(biāo)指針t用來保證不會掃過本產(chǎn)生式，還設(shè)置flag表示t的位置是否式一個可以推導(dǎo)出的非終結(jié)符。是的話，還有進行下一個t位置的檢查。如果t走到產(chǎn)生式的最后位置的下一個位置，則表明屬于此產(chǎn)生式左邊非終結(jié)符的first集合。3.判斷項目數(shù)是否在項目集里：is_in(proj temp,int T)Scan項目集原有的每一個項目，和新生成的項目作比較。若有相同的就返回true，否則返回false。4. 獲得計算closure(I)時需要的First(a):gete_expc(pr

13、oj temp)設(shè)計Flag表示是否還要進行下一輪計算，若處理的位置已經(jīng)查過了產(chǎn)生式的長度，則直接把項目中的那個搜索字符添加進去。這個模塊的返回結(jié)果放在BUFFER數(shù)據(jù)中。5.項目集的CCLUSER計算：e_closure(int T)在GO()函數(shù)中會產(chǎn)生itemsT的一些基本項目。對itemsT中已經(jīng)有的每一個項目檢查在“?！敝蟮氖欠駷榉墙K結(jié)符；若是，則計算FIRST(a)，把每一個BUFFER中的元素和相應(yīng)的產(chǎn)生式構(gòu)成一個項目，加入到項目集中。（注意，此時的項目記得大小時隨著項目的不斷加入而變大的，所以可以用FOR循環(huán)保證項目集中不會有錯誤。6.檢查項目集是否已經(jīng)在項目族里：is_co

14、ntation()把已經(jīng)有的項目集和新生成的項目集進行比較，要是有相等的話則表示已經(jīng)存在相同的項目集合，此時返回相同的那個項目集的編號，否則，返回0.四，程序測試。7.GO()函數(shù)地實現(xiàn)：第一步制作一個初始項目（即擴展文法的第一條產(chǎn)生式），然后用e_closure構(gòu)造項目集0.在程序中Ccount制作項目集的計數(shù)從0開始到（包括n)，所以在for循環(huán)中是。即掃描每一個項目集，對每一個項目在“.”之后的終結(jié)符，向后移動一位“.”的位置生成新的項目，暫存在buf數(shù)組中。然后預(yù)生成項目集，并且求其closure，再判斷新的項目集是否已經(jīng)存在，若存在了，就刪除這個項目集，并設(shè)置相應(yīng)的trans。否則就

15、生成的項目集，也設(shè)置相應(yīng)的trans。在以上過程中，每次確定生成一個項目集的時候都把它輸出到items.txt中。8. LR(1)分析表的構(gòu)造get_action()Scan 每一個項目集，若其中有規(guī)約項目，則轉(zhuǎn)換表增加一個歸約（用負值表示）。然后，根據(jù)trans 數(shù)組中的元素，構(gòu)造轉(zhuǎn)換表的移進項（用正值表示）。接受項目也是一個歸約項，用0表示。生成的轉(zhuǎn)換表輸出到action_table.txt中。9. 堆輸入串的語法分析：在main()中實現(xiàn)用stack模擬語法分析的過程，先在stack 中放入（0，#），然后，用當(dāng)前棧項狀態(tài)和當(dāng)前輸入字符查找action_table。根據(jù)action_ta

16、ble中的值的情況做相應(yīng)處理（即執(zhí)行移進和歸約動作）。若遇到接受項目則給出接受提示，程序結(jié)束。若遇到出錯的情況給出出錯提示，頁結(jié)束程序。四，程序測試本程序在Dev_C+和Microsoft Visual C+2005中調(diào)試通過。下面給出兩個調(diào)試實例：1.教科書的第142頁文法的LR1分析器的構(gòu)造和語法分析輸入文法： 3 EBBS BaBS BbS 生成的項目集族： 生成的轉(zhuǎn)換表： 輸入句子測試：圖3 輸入句子運行結(jié)果2.表達式文法的LR1分析器的構(gòu)造和語法分析器 生成的項目集族：圖4 生成的項目集組表 生成的轉(zhuǎn)換表： 輸入句子測試圖5 輸入句子運行結(jié)果五，源程序 /* Name: LR(1)分

17、析器的構(gòu)造 Author: ELNUR Date: 08-06-07 Description: 輸入文法，構(gòu)造出相應(yīng)的LR(1)分析器 */#includeiostreamusing namespace std;char G2020; /use a matrix to store grammar Gint length20; /length use to store each formulas lengthint number = 0;bool tempofinput150; /buffer of inputchar str_vn20; /put all vn into itint size_

18、vn = 0; char str_vt150; /put all vt into itint size_vt = 0;bool first_vn30150;char buffer50; /用來存放生成LR（1） 項目集時需要的first_set int bsize = 0;struct thri int beg; int nex; char ch;thri trans200;int size_trans = 0;/*定義項目集的形式 */struct proj int formula_numb; int part; char expc;proj items100100;int Ccount =

19、 0;int size_item100;void Read_G() cin number; /user should give the number of formula first for(int i = 1; i temp; while(temp != $) tempofinputtemp = true; Gij+ = temp; cin temp; lengthi = j; G00 = S; G01 = G10; length0 = 2; for(int i = 0; i 64; i+) if(tempofinputi) str_vtsize_vt+ = i; for(int i = 9

20、1; i 128; i+) if(tempofinputi) str_vtsize_vt+ = i; for(int i = 65; i 91; i+) if(tempofinputi) str_vnsize_vn+ = i; /*for(int i = 0; i size_vn; i+) cout str_vni ; cout endl endl; cout size: size_vt endl; for(int i = 0; i size_vt; i+) cout str_vti ; cout endl; */ void get_first() bool flag1; do flag1 =

21、 false; for(int i = 1; i = A & Git = Z) for(int k = 0; k 64; k+) if(first_vnGit-Ak = true & !first_vnGi0-Ak) first_vnGi0-Ak = true; flag1 = true; for(int k = 91; k 128; k+) if(first_vnGit-Ak = true & !first_vnGi0-Ak) first_vnGi0-Ak = true; flag1 = true; if(first_vnGit-A64 = true) t+; flag2 = true; e

22、lse if(!first_vnGi0-A Git ) first_vnGi0-A Git = true; flag1 = true; while(flag2 & t lengthi); if(t = lengthi) first_vnGi0-A26 = true; while(flag1);/*j判斷項目數(shù)否在項目集里*/bool is_in(proj temp,int T) for(int i = 0; i = lengthtemp.formula_numb) bufferbsize+ = temp.expc; return; else if(Gtemp.formula_numbtt+1

23、Z) bufferbsize+ = Gtemp.formula_numbtt+1; return; else if(Gtemp.formula_numbtt+1 = A & Gtemp.formula_numbtt+1 = Z) for(int i = 0; i 64; i+) if(first_vn Gtemp.formula_numbtt+1-A i) bufferbsize+ = i; for(int i = 91; i 128; i+) if(first_vn Gtemp.formula_numbtt+1-A i) bufferbsize+ = i; if(first_vn Gtemp

24、.formula_numbtt+1-A 64) tt+; flag = true; while(flag);void e_closure(int T) /cout T: T , size_itemT endl; for(int i = 0; i = A & GitemsTi.formula_numbitemsTi.part = Z) for(int j = 0; j 20; j+) if(Gj0 = GitemsTi.formula_numbitemsTi.part) gete_expc(itemsTi); for(int k = 0; k bsize; k+) temp.formula_nu

25、mb = j; temp.part = 1; temp.expc = bufferk; if(!is_in(temp,T) itemsTsize_itemT+ = temp; bsize = 0; /* for(int i = 0; i size_itemT; i+) printf(%d , %d , %cn,itemsTi.formula_numb,itemsTi.part,itemsTi.expc); cout * endl;*/ return ;int is_contained() for(int i = 0; i Ccount; i+) int s = 0; /記錄有多少是匹配的 if

26、(size_itemi = size_itemCcount) for(int j = 0; j size_itemCcount; j+) for(int k = 0; k size_itemi; k+) if(itemsCcountj.formula_numb = itemsik.formula_numb) & (itemsCcountj.part = itemsik.part) & (itemsCcountj.expc = itemsik.expc) s+; break; if(s = size_itemCcount) return i; return 0;void go() proj in

27、it; init.expc = #; init.formula_numb = 0; init.part = 1; items00 = init; size_item0+; e_closure(0); cout I0: endl; for(int i = 0; i size_item0; i+) printf(%d , %d , %cn,items0i.formula_numb,items0i.part,items0i.expc); cout * endl; bool beginflag = true; for(int index = 0; (index Ccount) | beginflag

28、; index+) beginflag = false; for(int j = 0; j size_vt; j+) proj buf50; int buf_size = 0; proj tp; int ccc = 0; for(int p = 0; p size_itemindex; p+) if(itemsindexp.part length itemsindexp.formula_numb ) & ( G itemsindexp.formula_numb itemsindexp.part = str_vtj) ) tp.formula_numb = itemsindexp.formula

29、_numb; tp.expc = itemsindexp.expc; tp.part = itemsindexp.part+1; bufbuf_size+ = tp; /ccc+; printf(/I%d - %c:n,index,str_vtj); if(buf_size != 0) Ccount+; for(int t = 0; t buf_size; t+) itemsCcount size_itemCcount+ = buft; e_closure(Ccount); int next_state = is_contained(); /看生成的項目集是否已經(jīng)在項目集族中了 if(next

30、_state != 0) size_itemCcount = 0; Ccount-; transsize_trans.beg = index; transsize_trans.nex = next_state; transsize_trans.ch = str_vtj; size_trans+; else cout I Ccount : endl; for(int i = 0; i size_itemCcount; i+) printf(%d , %d , %cn,itemsCcounti.formula_numb,itemsCcounti.part,itemsCcounti.expc); c

31、out * endl; transsize_trans.beg = index; transsize_trans.nex = Ccount; transsize_trans.ch = str_vtj; size_trans+; /對文法的每一個終結(jié)符 for(int j = 0; j size_vn; j+) proj buf50; int buf_size = 0; proj tp; int ccc = 0; for(int p = 0; p size_itemindex; p+) if(itemsindexp.part length itemsindexp.formula_numb ) &

32、 ( G itemsindexp.formula_numb itemsindexp.part = str_vnj) ) tp.formula_numb = itemsindexp.formula_numb; tp.expc = itemsindexp.expc; tp.part = itemsindexp.part+1; bufbuf_size+ = tp; /ccc+; printf(/I%d - %c:n,index,str_vnj); if(buf_size != 0) Ccount+; for(int t = 0; t buf_size; t+) itemsCcount size_it

33、emCcount+ = buft; e_closure(Ccount); int next_state = is_contained(); /看生成的項目集是否已經(jīng)在項目集族中了 if(next_state != 0) size_itemCcount = 0; Ccount-; transsize_trans.beg = index; transsize_trans.nex = next_state; transsize_trans.ch = str_vnj; size_trans+; else cout I Ccount : endl; for(int i = 0; i size_itemCcount; i+) printf(%d , %d , %cn,itemsCcounti.formula_numb,itemsCcounti.part,itemsCcounti.expc); cout * endl; transsize_trans.beg = index; transsize_trans.nex = Ccount; transsize_trans.ch = str_vnj; size_trans+; /對文法的每一個非終結(jié)符