1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 自動(dòng)生成LR(0)分析表 實(shí)驗(yàn)時(shí)間 2013年12月24日 院系 計(jì)算機(jī)科學(xué)與電子技術(shù)系 班級(jí) 11計(jì)算機(jī)軟件 學(xué)號(hào) JV JV JP 姓名 唐茹 韓強(qiáng)強(qiáng) 徐思維 1.試驗(yàn)?zāi)康模狠斎耄喝我獾膲嚎s了的上下文無關(guān)文法。輸出：相應(yīng)的LR（0）分析表。2.實(shí)驗(yàn)原理：對(duì)于LR文法，我們可以自動(dòng)構(gòu)造相應(yīng)的LR分析表。為了構(gòu)造LR分析表，我們需要定義一個(gè)重要概念文法的規(guī)范句型“活前綴”。這種句柄之后不含任何符號(hào)的前綴稱為活前綴。在LR分析工作過程中的任何時(shí)候，棧里的文法符號(hào)（自棧底而上）X1X2Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型（如果整個(gè)輸入串確實(shí)構(gòu)成一

2、個(gè)句子）。因此，只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過的部分沒有錯(cuò)誤。對(duì)于一個(gè)文法G，我們可以構(gòu)造一個(gè)有限自動(dòng)機(jī)，它能識(shí)別G的所有活前綴，然后把這個(gè)自動(dòng)機(jī)轉(zhuǎn)變成LR分析表，按照該LR分析表進(jìn)行LR分析，就能保證在分析的過程中，如果分析的句子是正確的，棧里的文法符號(hào)（自棧底而上）始終構(gòu)成活前綴。假若一個(gè)文法G的拓廣文法的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)（項(xiàng)目集）不存在下述情況：（1）既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目；（2）含有多個(gè)歸約項(xiàng)目，則稱G是一個(gè)LR（0）文法。該自動(dòng)機(jī)的狀態(tài)集合即為該文法的LR（0）項(xiàng)目集規(guī)范族。構(gòu)造識(shí)別文法活前綴DFA有3種方法：（1）根據(jù)形式定義求出活前

3、綴的正則表達(dá)式，然后由此正則表達(dá)式構(gòu)造NFA再確定為DFA；（2）求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的NFA再確定化為DFA；（3）使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GO(I,X)構(gòu)造文法G的LR(0)的項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系來得到識(shí)別活前綴的DFA。符號(hào)串的前綴是指該符號(hào)串的任意首部，包括空串。例如，對(duì)于符號(hào)串a(chǎn)bc，其前綴有，a，ab，abc。如果輸入串沒有錯(cuò)誤的話，一個(gè)規(guī)范句型的活前綴是該句型的一個(gè)前綴，但它不含句柄之后的任何符號(hào)。之所以稱為活前綴，是因?yàn)樵谠撉熬Y后聯(lián)接尚未輸入的符號(hào)串可以構(gòu)成一個(gè)規(guī)范句型?；钋熬Y與句柄的關(guān)系如下：（1）活前綴已

4、含有句柄的全部符號(hào)，表明產(chǎn)生式A的右部已出現(xiàn)在棧頂。（2）活前綴只含句柄的一部分符號(hào)，表明A12的右部子串1已出現(xiàn)在棧頂，期待從輸入串中看到2推出的符號(hào)。（3）活前綴不含有句柄的任何符號(hào)，此時(shí)期望A的右部所推出的符號(hào)串。在文法G的每個(gè)產(chǎn)生式的右部（候選式）的任何位置上添加一個(gè)圓點(diǎn)，所構(gòu)成的每個(gè)產(chǎn)生式稱為L(zhǎng)R（0）項(xiàng)目。如產(chǎn)生式A xyz有如下項(xiàng)目：A.xyz，Ax.yz，Axy.z，Axyz.。為刻劃分析過程中的文法的每一個(gè)產(chǎn)生式的右部符號(hào)已有多大一部分被識(shí)別（出現(xiàn)在棧頂），可以用這種標(biāo)有圓點(diǎn)的產(chǎn)生式來確定。（1）A.刻劃產(chǎn)生式A的右部已出現(xiàn)在棧頂。 （2）A1.2 刻劃A12的右部子串1已出

5、現(xiàn)在棧頂，期待從輸入串中看到2推出的符號(hào)。 （3）A. 刻劃沒有句柄的任何符號(hào)在棧頂，此時(shí)期望A的右部所推出的符號(hào)串。（4）對(duì)于A的LR(0)項(xiàng)目只有A。設(shè)文法G=（VT，VN，S，P）是一個(gè)上下文無關(guān)文法，若存在一個(gè)規(guī)范推導(dǎo)SAw12w（其中A12P），則稱項(xiàng)目A12對(duì)活前綴=1是有效的，即LR(0) 有效項(xiàng)目。從直觀意義上講，一個(gè)LR(0)項(xiàng)目指明了在分析過程中的某一步我們看到產(chǎn)生式的多大部分被識(shí)別，LR(0)項(xiàng)目中的圓點(diǎn)可看成是分析棧棧頂與輸入串的分界線，圓點(diǎn)左邊為已進(jìn)入分析棧的部分，右邊是當(dāng)前輸入或繼續(xù)掃描的符號(hào)串。不同的LR(0)項(xiàng)目，反映了分析棧頂?shù)牟煌闆r。我們根據(jù)LR(0)項(xiàng)目

6、的作用不同，將其分為四類：（1）歸約項(xiàng)目：表現(xiàn)形式：Aa.這類LR(0)項(xiàng)目表示句柄a恰好包含在棧中，即當(dāng)前棧頂?shù)牟糠謨?nèi)容構(gòu)成了所期望的句柄，應(yīng)按Aa進(jìn)行歸約。（2）接受項(xiàng)目：表現(xiàn)形式：a.其中是文法惟一的開始符號(hào)。這類LR(0)項(xiàng)目實(shí)際是特殊的歸約項(xiàng)目，表示分析棧中內(nèi)容恰好為a，用a進(jìn)行歸約，則整個(gè)分析成功。（3）移進(jìn)項(xiàng)目：表現(xiàn)形式：Aa.（bVT）這類LR(0)項(xiàng)目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句柄的活前級(jí)，需將b移進(jìn)分析棧。（4）待約項(xiàng)目：表現(xiàn)形式：A.B （BVN）這類LR(0)項(xiàng)目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句柄的活前綴，應(yīng)把當(dāng)前輸入字符串中

7、的相應(yīng)內(nèi)容先歸約到B。在給出LR(0)項(xiàng)目的定義和分類之后，我們從這些LR(0)項(xiàng)目出發(fā)，來構(gòu)造能識(shí)別文法所有前綴的有限自動(dòng)機(jī)。其步驟是：首先構(gòu)造能識(shí)別文法所有活前綴的非確定的有限自動(dòng)機(jī)，再將其確定化和最小化，最終得到所需的確定的有限自動(dòng)機(jī)。由文法G的LR(0)項(xiàng)目構(gòu)造識(shí)別文法G的所有活前綴的非確定有限自動(dòng)機(jī)的方法：（1）規(guī)定含有文法開始符號(hào)的產(chǎn)生式（設(shè)A）的第一個(gè)LR(0)項(xiàng)目（即.A）為NFA的惟一初態(tài)。（2）令所有LR(0)項(xiàng)目分別對(duì)應(yīng)NFA的一個(gè)狀態(tài)且LR(0)項(xiàng)目為歸約項(xiàng)目的對(duì)應(yīng)狀態(tài)為終態(tài)。（3）若狀態(tài)i和狀態(tài)j出自同一文法G的產(chǎn)生式且兩個(gè)狀態(tài)LR(0)項(xiàng)目的圓點(diǎn)只相差一個(gè)位置，即：

8、若i為XX1X2Xi-1XiXn， j為 XX1X2XiXi+1Xn，則從狀態(tài)i引一條標(biāo)記為Xi的弧到狀態(tài)j。（4）若狀態(tài)i為待約項(xiàng)目（設(shè)XA），則從狀態(tài)i引弧到所有Ar的狀態(tài)。為了使“接受”狀態(tài)易于識(shí)別，我們通常將文法G進(jìn)行拓廣。假定文法G是一個(gè)以S為開始符號(hào)的文法，我們構(gòu)造一個(gè)，它包含了整個(gè)G，但它引進(jìn)了一個(gè)不出現(xiàn)在G中的非終結(jié)符，并加進(jìn)一個(gè)新產(chǎn)生式S，以S為開始符號(hào)。那么，我們稱是G的拓廣文法。這樣，便會(huì)有一個(gè)僅含項(xiàng)目S的狀態(tài)，這就是惟一的“接受”態(tài)。如果I是文法G的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：（1） I的項(xiàng)目都在CLOSURE(I)中。（2） 若Aa.Bb屬

9、于CLOSURE(I)，則每一形如B.g的項(xiàng)目也屬于CLOSURE(I)。（3） 重復(fù)（2）直到CLOSURE(I)不再擴(kuò)大。定義轉(zhuǎn)換函數(shù)如下：GO（I，X）= CLOSURE（J）其中：I為包含某一項(xiàng)目集的狀態(tài)，X為一文法符號(hào)，J= AaX .b | Aa.X bI。圓點(diǎn)不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核，惟一的例外是S.S，因此用GOTO（I，X）狀態(tài)轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)閉包項(xiàng)目集的核。使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)換函數(shù)(GO(I,X)構(gòu)造文法G的LR(0)的項(xiàng)目集規(guī)范族，步驟如下：（1） 置項(xiàng)目S.S為初態(tài)集的核，然后對(duì)核求閉包CLOSURE（S.S）得到初態(tài)的閉包項(xiàng)目集。（

10、2） 對(duì)初態(tài)集或其他所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)= CLOSURE(J)求出新狀態(tài)J的閉包項(xiàng)目集。（3） 重復(fù)（2）直到不出現(xiàn)新的項(xiàng)目集為止。計(jì)算LR（0）項(xiàng)目集規(guī)范族C=I0，I1 , . In 的算法偽代碼如下： Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一項(xiàng)目集I和每一文法符號(hào)X Do if GO(I,X) 非空且不屬于C Then 把 GO(I,X) 放入C中 Until C 不再增大End;一個(gè)項(xiàng)目集可能包含多種項(xiàng)目，若移進(jìn)和歸約項(xiàng)目同時(shí)存在，則稱移進(jìn)-歸約沖突，若歸約和歸約項(xiàng)目同時(shí)存在，

11、則稱歸約-歸約沖突。下面看一個(gè)具體的例子：我們希望能根據(jù)識(shí)別文法的活前綴的DFA建立LR分析器，因此，需要研究這個(gè)DFA的每個(gè)項(xiàng)目集（狀態(tài)）中的項(xiàng)目的不同作用。我們說項(xiàng)目A1.2對(duì)活前綴1是有效的，其條件是存在規(guī)范推導(dǎo)。一般而言，同一項(xiàng)目可能對(duì)幾個(gè)活前綴都是有效的（當(dāng)一個(gè)項(xiàng)目出現(xiàn)在幾個(gè)不同的集合中時(shí)便是這種情形）。若歸約項(xiàng)目A1.對(duì)活前綴是有效的，則它告訴我們應(yīng)把符號(hào)串歸約為A，即把活前綴變成A。若移進(jìn)項(xiàng)目A1.2對(duì)活前綴是有效的，則它告訴我們，句柄尚未形成，因此，下一步動(dòng)作應(yīng)是移進(jìn)。但是，可能存在這樣的情形，對(duì)同一活前綴，存在若干項(xiàng)目對(duì)它都是有效的。而且它們告訴我們應(yīng)做的事情各不相同，互相沖

12、突。這種沖突通過向前多看幾個(gè)輸入符號(hào)，或許能夠獲得解決。對(duì)于每個(gè)活前綴，我們可以構(gòu)造它的有效項(xiàng)目集。實(shí)際上，一個(gè)活前綴的有效項(xiàng)目集正是從上述的DFA的初態(tài)出發(fā)，經(jīng)讀出后而到達(dá)的那個(gè)項(xiàng)目集（狀態(tài)）。換言之，在任何時(shí)候，分析棧中的活前綴X1X2Xm的有效項(xiàng)目集正是棧頂狀態(tài)Sm所代表的那個(gè)集合。這是LR分析理論的一條基本定理。實(shí)際上，棧頂?shù)捻?xiàng)目集（狀態(tài)）體現(xiàn)了棧里的一切有用信息歷史。 前面我們已經(jīng)對(duì)LR（0）文法進(jìn)行了定義,下面我們來看一下LR（0）分析表是如何構(gòu)造的。對(duì)于LR（0）文法，我們可以直接從它的項(xiàng)目集規(guī)范族C和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出LR分析表。下面是構(gòu)造LR（0）分析表

13、的算法。假定C=I0, I1,，In，令每個(gè)項(xiàng)目集Ik的下標(biāo)k為分析器的一個(gè)狀態(tài)，因此，G的LR(0)分析表含有狀態(tài)0，1，n。令那個(gè)含有項(xiàng)目SS的Ik的下標(biāo)k為初態(tài)。ACTION子表和GOTO子表可按如下方法構(gòu)造：（1）若項(xiàng)目A.a屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“把狀態(tài)j和符號(hào)a移進(jìn)棧”，簡(jiǎn)記為“sj”；（2）若項(xiàng)目A屬于Ik，那么，對(duì)任何終結(jié)符a，置ACTIONk，a為“用產(chǎn)生式A進(jìn)行規(guī)約”，簡(jiǎn)記為“rj”；其中，假定A為文法G的第j個(gè)產(chǎn)生式；（3）若項(xiàng)目SS屬于Ik, 則置ACTIONk, #為“接受”，簡(jiǎn)記為“acc”；（4）若GO (

14、Ik, A)= Ij, A為非終結(jié)符，則置GOTOk, A=j；（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)表的文法G稱為一個(gè)LR（0）文法，LR(0)文法是無二義的。例如，文法G（E）的拓廣文法如下：(0)SE(1)EaA(2)EbB(3)AcA(4)Ad(5)BcB(6)Bd該文法的LR（0）分析表如表所示。StateACTIONGOTOAbCD#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r

15、1R1r1r1r17r2R2r2r2r28r3R3r3r3r39r4R4r4r4r410r5R5r5r5r511r6R6r6r6r63.實(shí)驗(yàn)內(nèi)容及其代碼如下所示：#include#include#include#includeusing namespace std;#define OK 1#define ERROR 0#define N 50#define Y 20int vtnum,vnnum,pronum;/依次是終結(jié)符個(gè)數(shù)，非終結(jié)符個(gè)數(shù)，產(chǎn)生式個(gè)數(shù) char vtN;/終結(jié)符集 char vnN;/非終結(jié)符集char oldNN=/0;/用于存儲(chǔ)文法char oldzNN=/0;/用于存

16、儲(chǔ)增廣文法int ACTIONNN=0;/動(dòng)作表int GOTONN=0;/狀態(tài)轉(zhuǎn)換表typedef struct SqE int t;/狀態(tài)編號(hào) char c1;SqE;/堆棧元素typedef struct item int f;/項(xiàng)目前部，表示產(chǎn)生式編號(hào) int l;/項(xiàng)目后部，表示停頓點(diǎn)在產(chǎn)生式的位置item;/定義項(xiàng)目typedef struct link int f;/連接前部，表示所用符號(hào)的編號(hào)，非終結(jié)符編號(hào)=在vn中的下標(biāo)+100 int l;/連接后部，即狀態(tài)編號(hào)link;/定義狀態(tài)之間的連接typedef struct cd int item_num;/狀態(tài)中的項(xiàng)目數(shù) in

17、t link_num;/狀態(tài)的連接數(shù) item wN;/項(xiàng)目集 link uN;/連接集cd;/定義狀態(tài)typedef struct DFA int cd_num;/狀態(tài)個(gè)數(shù) cd sN+1;/狀態(tài)集DFA;/定義規(guī)范LR(0)項(xiàng)目族,D.sN用作狀態(tài)轉(zhuǎn)換函數(shù)go_switch()的存儲(chǔ)空間DFA D;void dfa();/求規(guī)范LR(0)項(xiàng)目族void closure(int);/求閉包void go_switch(int,int);/求轉(zhuǎn)換int test_go_switch();void add_go_switch();/增加新狀態(tài)void del_go_switch();/清空狀態(tài)轉(zhuǎn)

18、換函數(shù)的存儲(chǔ)空間void action();/構(gòu)造ACTION表void go_answer();/構(gòu)造GOTO表int control();/總控程序int length(int);/返回增廣文法產(chǎn)生式右部的長(zhǎng)度int test(char);void printf_ag();/輸出ACTION表和GOTO表bool test_link(int i,int num);void main() int i,j; ifstream in(input1.txt,ios_base:in);/讀文件,從文件中讀入pronum,vtnum,vnnum以及產(chǎn)生式 inpronumvnnumvtnum; inv

19、n; invt; for(i=1;ioldi;/將產(chǎn)生式存入old,old1為第一個(gè)產(chǎn)生式 for(i=1;iS，將原文法擴(kuò)充，使其變?yōu)樵鰪V文法 vtvtnum=$;/把結(jié)束符$加入終結(jié)符集 D.cd_num=0; for(i=0;i=N;i+) D.si.item_num=0; D.si.link_num=0; /初始化狀態(tài)個(gè)數(shù)、連接個(gè)數(shù)、項(xiàng)目個(gè)數(shù) dfa(); action(); go_answer(); printf_ag(); control();/求一個(gè)狀態(tài)的閉包void closure(int i) int j,k,m,x,flag; do j=D.si.item_num;/j是本

20、輪循環(huán)開始前的項(xiàng)目數(shù) for(k=0;kD.si.item_num;k+) for(m=0;ma.Ab應(yīng)找到A-. flag=0;/判斷該項(xiàng)是否在當(dāng)前狀態(tài)i中,即檢查(m,1)是否存在于狀態(tài)i中,保證求閉包時(shí)加入的新項(xiàng)目和原項(xiàng)目集不重合 for(x=0;xD.si.item_num;x+) if(D.si.wx.f=m&D.si.wx.l=1) flag=1; break; if(flag=0)/如果該項(xiàng)不在當(dāng)前狀態(tài)i中，將其加入狀態(tài)i D.si.wD.si.item_num.f=m; D.si.wD.si.item_num.l=1; D.si.item_num+; while(j!=D.si

21、.item_num);/當(dāng)一輪沒有新的項(xiàng)目加入i時(shí)，結(jié)束循環(huán)/狀態(tài)轉(zhuǎn)換函數(shù)，i是狀態(tài)編號(hào)，num是符號(hào)編號(hào)，狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果存于sNvoid go_switch(int i,int num) int j; for(j=0;jD.si.item_num;j+) if(test(oldzD.si.wj.fD.si.wj.l)=num) D.sN.wD.sN.item_num.f=D.si.wj.f; D.sN.wD.sN.item_num.l=D.si.wj.l+1; D.sN.item_num+; closure(N); /返回終結(jié)符和非終結(jié)符的標(biāo)號(hào),判斷符號(hào)的類型,0=終結(jié)符返回值100,1

22、00=非終結(jié)符返回值200,錯(cuò)誤符號(hào)返回值=200int test(char c) int i,j; for(i=0;ivtnum;i+) if(vti=c) break; if(ivtnum) return i;else for(j=0;jvnnum;j+) if(vnj=c) break; if(jvtnum) return (100+j);else return 200; /檢驗(yàn)狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果int test_go_switch() int i,j,k,flag;if(D.sN.item_num=0)/判斷狀態(tài)轉(zhuǎn)換的結(jié)果是否為空，即當(dāng)前狀態(tài)可否接收該字符 return 0;else

23、for(i=0;iD.cd_num;i+)/選定一狀態(tài)，對(duì)sN中的每個(gè)項(xiàng)目進(jìn)行循環(huán)，如果存在一個(gè)項(xiàng)目在當(dāng)前狀態(tài)中未找到，即flag=0，立即跳至下一狀態(tài) flag=1;/判斷狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果是否已經(jīng)完全包含于某一現(xiàn)有狀態(tài)中，例如go_switch(狀態(tài)4,符號(hào)a)依然存在于狀態(tài)4中，go_switch(狀態(tài)4,符號(hào)c)已經(jīng)存在于狀態(tài)5中 for(j=0;jD.sN.item_num;j+)/如果在當(dāng)前狀態(tài)i中找不到sN的當(dāng)前項(xiàng)目j,就跳至下一狀態(tài) for(k=0;k=D.si.item_num) flag=0; break; if(flag=1) return 1000+i; return

24、1;/狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果未被任何現(xiàn)有狀態(tài)完全包含，完全滿足建立新狀態(tài)的條件 /把狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果加入DFA，即當(dāng)建立新狀態(tài)的條件符合時(shí)，建立新的狀態(tài)sD.cd_numvoid add_go_switch() int i; for(i=0;iS加入初狀態(tài)，并求其閉包 do i=D.cd_num;/本輪循環(huán)開始時(shí)狀態(tài)數(shù) for(j=0;jD.cd_num;j+)/對(duì)每個(gè)狀態(tài)進(jìn)行循環(huán) for(k=0;k=1000)/如果狀態(tài)轉(zhuǎn)換的結(jié)果包含于某一現(xiàn)有狀態(tài) D.sj.uD.sj.link_num.f=k+100;/建立當(dāng)前狀態(tài)和該現(xiàn)有狀態(tài)的連接 D.sj.uD.sj.link_num.l=test_g

25、o_switch()-1000; D.sj.link_num+; del_go_switch();/清空 for(k=0;k=1000) D.sj.uD.sj.link_num.f=k; D.sj.uD.sj.link_num.l=test_go_switch()-1000; D.sj.link_num+; del_go_switch(); while(i!=D.cd_num);/當(dāng)一輪沒有新的狀態(tài)產(chǎn)生時(shí)，結(jié)束/構(gòu)造ACTION表void action() int i,j,k; for(i=0;iD.cd_num;i+)/對(duì)每個(gè)狀態(tài)循環(huán) for(j=0;jD.si.link_num;j+)/S

26、，對(duì)每個(gè)狀態(tài)的每個(gè)連接循環(huán)，如果找到當(dāng)前狀態(tài)用終結(jié)符建立的連接，則ACTION當(dāng)前狀態(tài)號(hào)對(duì)應(yīng)終結(jié)符編號(hào)=連接另一端狀態(tài)號(hào) if(D.si.uj.f100) ACTIONiD.si.uj.f=D.si.uj.l; for(j=0;jc. 則ACTION當(dāng)前狀態(tài)所有vt和$=產(chǎn)生式A-c的編號(hào) if(oldzD.si.wj.fD.si.wj.l=/0) for(k=0;k=vtnum;k+) ACTIONik=D.si.wj.f+100; for(j=0;jS. 所在狀態(tài)，則ACTION當(dāng)前狀態(tài)$=300，即acc if(D.si.wj.f=0&D.si.wj.l=2) ACTIONivtnum=

27、300; break; /構(gòu)造GOTO表void go_answer() int i,j; for(i=0;iD.cd_num;i+) for(j=0;j=100) GOTOiD.si.uj.f-100=D.si.uj.l; /總控程序int control() int i,j,num; char cY=/0;/初始化帶分析字符串的存儲(chǔ)空間 SqE stackN; int p1=0,p2=0;/p1是待分析字符串指針,p2是棧頂下一位元素的指針,stack0是棧底 vtnum+;/把$加入終結(jié)符集 for(i=0;ic; printf(/n棧中狀態(tài) 棧中符號(hào) 輸入串 分析動(dòng)作/n);while

28、(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION棧頂狀態(tài)號(hào)當(dāng)前字符編號(hào) for(i=0,j=0;stacki.c1!=/0;i+) printf(%d,stacki.t); j+; for(i=0;i14-j;i+) printf( );/輸出棧中狀態(tài)for(i=0,j=0;stacki.c1!=/0;i+) printf(%c,stacki.c1); j+; for(i=0;i14-j;i+) printf( );/輸出棧中符號(hào) for(i=p1,j=0;ci!=/0;i+) printf(%c,ci); j+; for(i=0;i0&ACTIONstackp

29、2-1.ttest(cp1)100&ACTIONstackp2-1.ttest(cp1)200)/r,歸約 num=ACTIONstackp2-1.ttest(cp1)-100;/num是歸約所用的產(chǎn)生式編號(hào) printf(r%d/n,num); p2=p2-length(num);/彈出length(num)個(gè)元素 stackp2.t=GOTOstackp2-1.ttest(oldznum0)-100;/若T是彈出后的棧頂元素中的狀態(tài)號(hào)，把GOTOToldznum0壓棧，注意-100 stackp2.c1=oldznum0;/把oldznum0壓棧 p2+; stackp2.c1=/0;/封頂 else if(ACTIONstackp2-1.ttest(cp1)=0)/Error printf(Error/n/nError,您輸入的句型和文法不符!/n); return ERROR; printf(01 $%