1、精選優(yōu)質(zhì)文檔-傾情為你奉上目 錄前 言編譯原理是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)課程，其中包含大量軟件設(shè)計(jì)細(xì)想。通過課程設(shè)計(jì)，實(shí)現(xiàn)一些重要的算法，或設(shè)計(jì)一個(gè)完整的編譯程序模型，能夠進(jìn)一步加深理解和掌握所學(xué)知識(shí)，對(duì)提高自己的軟件設(shè)計(jì)水平具有十分重要的意義。我選的是老師給的題，并予以擴(kuò)充。即對(duì)任意給定的問法G構(gòu)造LR(1)項(xiàng)目集規(guī)范族，其中要實(shí)現(xiàn)CLOSURE(1)，GO(I,X)，F(xiàn)IRST集合符。在此基礎(chǔ)上，構(gòu)造了LR(1)分析表。然后對(duì)輸入的句子進(jìn)行語法分析，給出接受或出錯(cuò)報(bào)告。程序采用文件輸入輸出方式。其中包括兩個(gè)輸入文件：文法grammar.txt，以及輸入串input.txt；兩個(gè)輸出文件:

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

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

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

5、（2）若X屬于VN，且有產(chǎn)生式Xa，則把A加入到FIRST(X)中；若X也是一條產(chǎn)生式，則把也加入到FIRST中。4.LR(1)分析表的構(gòu)造在實(shí)現(xiàn)GO(I,X)時(shí)，記錄下狀態(tài)的轉(zhuǎn)化。得到分析表中的移進(jìn)部分。然后再掃描所有的項(xiàng)目集，找到其中包含歸約項(xiàng)目的哪些項(xiàng)目集，根據(jù)其中項(xiàng)目，得到分析表中那些鬼月的部分。二，LR（1）分析器1.LR(1)分析器的實(shí)現(xiàn)圖：圖1 LR（1）分析器的實(shí)現(xiàn)2.LR分析器與邏輯結(jié)構(gòu)及工作過程圖2 LR分析器的邏輯結(jié)構(gòu)三，總體方案設(shè)計(jì)在main()函數(shù)中讀入文件，并堆文法進(jìn)行擴(kuò)展，同時(shí)記錄下文法的所有終結(jié)符和非終結(jié)符，對(duì)每個(gè)非終結(jié)符計(jì)算它的FIRST集合。以備在計(jì)算CLO

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

7、 /記錄哪些ASCII字符在文法中，以求得所有的VT和VNchar str_vn20; /記錄所有的非終結(jié)符int size_vn=0; /記錄非終結(jié)符的個(gè)數(shù)char str_vt150; /記錄所有的終結(jié)符int size_vt=0; /記錄終結(jié)符的個(gè)數(shù)bool first_vn30150; /記錄每個(gè)非終結(jié)符的FIRST集char buffer50; /用來存放CLOSURE(I)時(shí)需要的FIRST_SET 也用來讀入用戶的輸入電int bsize=0 / buffer的有效長度struct thri int beg; int nex; char ch; ; thri trans200;

8、/定義狀態(tài)轉(zhuǎn)換組中的元素格式 int size-trans=0; /用來在go()函數(shù)中記錄狀態(tài)間的轉(zhuǎn)換trans數(shù)組 的大小 struct proj int part; char expc; ; /定義項(xiàng)目集的格式 proj irems100100; /項(xiàng)目集數(shù)組，假設(shè)項(xiàng)目集的個(gè)數(shù)不超過100個(gè)， 且每個(gè)項(xiàng)目集中的項(xiàng)目個(gè)數(shù)不超過100個(gè) int CCOUNT=0; /項(xiàng)目集的個(gè)數(shù) int size_item100; /每個(gè)項(xiàng)目集中的項(xiàng)目個(gè)數(shù) struct action char ch; /定義狀態(tài)轉(zhuǎn)換表的格式int nxt_sta; ; /定義狀態(tài)轉(zhuǎn)換表的格式action action_ta

9、ble100100; /狀態(tài)轉(zhuǎn)換表 int size_act_table100; / 輸入文法的文件指針ifstream G_ifile; / 輸入句子的文件指針ofstream input_ifile; / 輸出項(xiàng)目集族的文件指針ofstream items_ofile; / 輸出轉(zhuǎn)換表的文件指針void read_G() / 計(jì)算每個(gè)非終結(jié)符的FIRST集合void get_first() / 判斷項(xiàng)目temp是否已經(jīng)在項(xiàng)目集族 itemsT中 bool is_in(proj temp,int,T) / 計(jì)算itemTclosure(1)時(shí)用到的frst(a) void e_closure

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

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

12、alse。4. 獲得計(jì)算closure(I)時(shí)需要的First(a):gete_expc(proj temp)設(shè)計(jì)Flag表示是否還要進(jìn)行下一輪計(jì)算，若處理的位置已經(jīng)查過了產(chǎn)生式的長度，則直接把項(xiàng)目中的那個(gè)搜索字符添加進(jìn)去。這個(gè)模塊的返回結(jié)果放在BUFFER數(shù)據(jù)中。5.項(xiàng)目集的CCLUSER計(jì)算：e_closure(int T)在GO()函數(shù)中會(huì)產(chǎn)生itemsT的一些基本項(xiàng)目。對(duì)itemsT中已經(jīng)有的每一個(gè)項(xiàng)目檢查在“。”之后的是否為非終結(jié)符；若是，則計(jì)算FIRST(a)，把每一個(gè)BUFFER中的元素和相應(yīng)的產(chǎn)生式構(gòu)成一個(gè)項(xiàng)目，加入到項(xiàng)目集中。（注意，此時(shí)的項(xiàng)目記得大小時(shí)隨著項(xiàng)目的不斷加入而變

13、大的，所以可以用FOR循環(huán)保證項(xiàng)目集中不會(huì)有錯(cuò)誤。6.檢查項(xiàng)目集是否已經(jīng)在項(xiàng)目族里：is_contation()把已經(jīng)有的項(xiàng)目集和新生成的項(xiàng)目集進(jìn)行比較，要是有相等的話則表示已經(jīng)存在相同的項(xiàng)目集合，此時(shí)返回相同的那個(gè)項(xiàng)目集的編號(hào)，否則，返回0.四，程序測(cè)試。7.GO()函數(shù)地實(shí)現(xiàn)：第一步制作一個(gè)初始項(xiàng)目（即擴(kuò)展文法的第一條產(chǎn)生式），然后用e_closure構(gòu)造項(xiàng)目集0.在程序中Ccount制作項(xiàng)目集的計(jì)數(shù)從0開始到（包括n)，所以在for循環(huán)中是。即掃描每一個(gè)項(xiàng)目集，對(duì)每一個(gè)項(xiàng)目在“.”之后的終結(jié)符，向后移動(dòng)一位“.”的位置生成新的項(xiàng)目，暫存在buf數(shù)組中。然后預(yù)生成項(xiàng)目集，并且求其closu

14、re，再判斷新的項(xiàng)目集是否已經(jīng)存在，若存在了，就刪除這個(gè)項(xiàng)目集，并設(shè)置相應(yīng)的trans。否則就生成的項(xiàng)目集，也設(shè)置相應(yīng)的trans。在以上過程中，每次確定生成一個(gè)項(xiàng)目集的時(shí)候都把它輸出到items.txt中。8. LR(1)分析表的構(gòu)造get_action()Scan 每一個(gè)項(xiàng)目集，若其中有規(guī)約項(xiàng)目，則轉(zhuǎn)換表增加一個(gè)歸約（用負(fù)值表示）。然后，根據(jù)trans 數(shù)組中的元素，構(gòu)造轉(zhuǎn)換表的移進(jìn)項(xiàng)（用正值表示）。接受項(xiàng)目也是一個(gè)歸約項(xiàng)，用0表示。生成的轉(zhuǎn)換表輸出到action_table.txt中。9. 堆輸入串的語法分析：在main()中實(shí)現(xiàn)用stack模擬語法分析的過程，先在stack 中放入（0

15、，#），然后，用當(dāng)前棧項(xiàng)狀態(tài)和當(dāng)前輸入字符查找action_table。根據(jù)action_table中的值的情況做相應(yīng)處理（即執(zhí)行移進(jìn)和歸約動(dòng)作）。若遇到接受項(xiàng)目則給出接受提示，程序結(jié)束。若遇到出錯(cuò)的情況給出出錯(cuò)提示，頁結(jié)束程序。四，程序測(cè)試本程序在Dev_C+和Microsoft Visual C+2005中調(diào)試通過。下面給出兩個(gè)調(diào)試實(shí)例：1.教科書的第142頁文法的LR1分析器的構(gòu)造和語法分析輸入文法： 3 EBBS BaBS BbS 生成的項(xiàng)目集族： 生成的轉(zhuǎn)換表： 輸入句子測(cè)試：圖3 輸入句子運(yùn)行結(jié)果2.表達(dá)式文法的LR1分析器的構(gòu)造和語法分析器 生成的項(xiàng)目集族：圖4 生成的項(xiàng)目集組表

16、 生成的轉(zhuǎn)換表： 輸入句子測(cè)試圖5 輸入句子運(yùn)行結(jié)果五，源程序 /* Name: LR(1)分析器的構(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 i

17、nputchar str_vn20; /put all vn into itint size_vn = 0; char str_vt150; /put all vt into itint size_vt = 0;bool first_vn30150;char buffer50; /用來存放生成LR（1） 項(xiàng)目集時(shí)需要的first_set int bsize = 0;struct thri int beg; int nex; char ch;thri trans200;int size_trans = 0;/*定義項(xiàng)目集的形式 */struct proj int formula_numb; in

18、t part; char expc;proj items100100;int Ccount = 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(

19、tempofinputi) str_vtsize_vt+ = i; for(int i = 91; 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 e

20、ndl; */ void get_first() bool flag1; do flag1 = 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;

21、 if(first_vnGit-A64 = true) t+; flag2 = true; else 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判斷項(xiàng)目數(shù)否在項(xiàng)目集里*/bool is_in(proj temp,int T) for(int i = 0; i = lengthtemp.formula_numb) bufferbsize+ = tem

22、p.expc; return; else if(Gtemp.formula_numbtt+1 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_nu

23、mbtt+1-A i) bufferbsize+ = i; if(first_vn Gtemp.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(itemsT

24、i); for(int k = 0; k bsize; k+) temp.formula_numb = 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(in

25、t i = 0; i Ccount; i+) int s = 0; /記錄有多少是匹配的 if(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_i

26、temCcount) return i; return 0;void go() proj init; 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;

27、 for(int index = 0; (index Ccount) | beginflag ; 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 = s

28、tr_vtj) ) 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_vtj); if(buf_size != 0) Ccount+; for(int t = 0; t buf_size; t+) itemsCcount size_itemCcount+ = buft; e_closure(Ccount); int next_stat

29、e = is_contained(); /看生成的項(xiàng)目集是否已經(jīng)在項(xiàng)目集族中了 if(next_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.formu

30、la_numb,itemsCcounti.part,itemsCcounti.expc); cout * endl; transsize_trans.beg = index; transsize_trans.nex = Ccount; transsize_trans.ch = str_vtj; size_trans+; /對(duì)文法的每一個(gè)終結(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(items

31、indexp.part length itemsindexp.formula_numb ) & ( 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

32、(int t = 0; t buf_size; t+) itemsCcount size_itemCcount+ = buft; e_closure(Ccount); int next_state = is_contained(); /看生成的項(xiàng)目集是否已經(jīng)在項(xià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 co

33、ut 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+; /對(duì)文法的每一個(gè)非終結(jié)符 int main() for(int i = 0; i 150;