編譯原理實驗-LR(0)文法(共17頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理實驗報告實驗名稱_LR(0)文法_實驗時間_2015-6-11_院 系_管理信息工程學(xué)院_班 級_12級計算機科學(xué)與技術(shù)_學(xué) 號_2_姓 名_王博一_1、 實驗?zāi)康模狠斎耄喝我獾膲嚎s了的上下文無關(guān)文法。輸出：相應(yīng)的LR（0）分析表。2、 實驗原理對于LR文法，我們可以自動構(gòu)造相應(yīng)的LR分析表。為了構(gòu)造LR分析表，我們需要定義一個重要概念文法的規(guī)范句型“活前綴”。這種句柄之后不含任何符號的前綴稱為活前綴。在LR分析工作過程中的任何時候，棧里的文法符號（自棧底而上）X1X2Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型（如果整個輸入串確實構(gòu)成一個句

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

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

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

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

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

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

8、產(chǎn)生式且兩個狀態(tài)LR(0)項目的圓點只相差一個位置，即：若i為XX1X2·Xi-1·XiXn， j為 XX1X2Xi·Xi+1Xn，則從狀態(tài)i引一條標(biāo)記為Xi的弧到狀態(tài)j。（4）若狀態(tài)i為待約項目（設(shè)X·A），則從狀態(tài)i引弧到所有A·r的狀態(tài)。為了使“接受”狀態(tài)易于識別，我們通常將文法G進行拓廣。假定文法G是一個以S為開始符號的文法，我們構(gòu)造一個，它包含了整個G，但它引進了一個不出現(xiàn)在G中的非終結(jié)符，并加進一個新產(chǎn)生式S，以S為開始符號。那么，我們稱是G的拓廣文法。這樣，便會有一個僅含項目S的狀態(tài)，這就是惟一的“接受”態(tài)。如果I是文法G的一個項

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

10、集規(guī)范族，步驟如下：（1） 置項目S.S為初態(tài)集的核，然后對核求閉包CLOSURE（S.S）得到初態(tài)的閉包項目集。（2） 對初態(tài)集或其他所構(gòu)造的項目集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)= CLOSURE(J)求出新狀態(tài)J的閉包項目集。（3） 重復(fù)（2）直到不出現(xiàn)新的項目集為止。計算LR（0）項目集規(guī)范族C=I0，I1 , . In 的算法偽代碼如下： Procedure itemsets(G); Begin C := CLOSURE (S®.S) Repeat For C 中每一項目集I和每一文法符號X Do if GO(I,X) 非空且不屬于C Then 把 GO(I,X) 放入C中 Un

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

12、一步動作應(yīng)是移進。但是，可能存在這樣的情形，對同一活前綴，存在若干項目對它都是有效的。而且它們告訴我們應(yīng)做的事情各不相同，互相沖突。這種沖突通過向前多看幾個輸入符號，或許能夠獲得解決。對于每個活前綴，我們可以構(gòu)造它的有效項目集。實際上，一個活前綴的有效項目集正是從上述的DFA的初態(tài)出發(fā)，經(jīng)讀出后而到達的那個項目集（狀態(tài)）。換言之，在任何時候，分析棧中的活前綴X1X2Xm的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。這是LR分析理論的一條基本定理。實際上，棧頂?shù)捻椖考顟B(tài)）體現(xiàn)了棧里的一切有用信息歷史。 前面我們已經(jīng)對LR（0）文法進行了定義,下面我們來看一下LR（0）分析表是如何構(gòu)造的。對于

13、LR（0）文法，我們可以直接從它的項目集規(guī)范族C和活前綴識別自動機的狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出LR分析表。下面是構(gòu)造LR（0）分析表的算法。假定C=I0, I1,，In，令每個項目集Ik的下標(biāo)k為分析器的一個狀態(tài)，因此，G'的LR(0)分析表含有狀態(tài)0，1，n。令那個含有項目S'S的Ik的下標(biāo)k為初態(tài)。ACTION子表和GOTO子表可按如下方法構(gòu)造：（1）若項目A.a屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“把狀態(tài)j和符號a移進?！?，簡記為“sj”；（2）若項目A屬于Ik，那么，對任何終結(jié)符a，置ACTIONk，a為“用產(chǎn)生式A進行規(guī)約”，簡

14、記為“rj”；其中，假定A為文法G'的第j個產(chǎn)生式；（3）若項目S'S屬于Ik, 則置ACTIONk, #為“接受”，簡記為“acc”；（4）若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTOk, A=j；（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出錯標(biāo)志”。按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)表的文法G稱為一個LR（0）文法，LR(0)文法是無二義的。例如，文法G（E）的拓廣文法如下：(0)S'E(1)EaA(2)EbB(3)AcA(4)Ad(5

15、)BcB3、 實驗內(nèi)容Vtnum= 8vnnum =3pronum =3產(chǎn)生式：E->E+T|E-T|TT->T/F|T*F|FF->i|n|(E)4、 代碼實現(xiàn)#include<iostream>#include<stdio.h>#include<fstream>#include<malloc.h>using namespace std;#define OK 1#define ERROR 0#define N 50#define Y 20int vtnum,vnnum,pronum;/依次是終結(jié)符個數(shù)，非終結(jié)符個數(shù)，產(chǎn)生式個數(shù)

16、 char vtN;/終結(jié)符集 char vnN;/非終結(jié)符集char oldNN='/0'/用于存儲文法char oldzNN='/0'/用于存儲增廣文法int ACTIONNN=0;/動作表int GOTONN=0;/狀態(tài)轉(zhuǎn)換表typedef struct SqE int t;/狀態(tài)編號 char c1;SqE;/堆棧元素typedef struct item int f;/項目前部，表示產(chǎn)生式編號 int l;/項目后部，表示停頓點在產(chǎn)生式的位置item;/定義項目typedef struct link int f;/連接前部，表示所用符號的編號，非終結(jié)符

17、編號=在vn中的下標(biāo)+100 int l;/連接后部，即狀態(tài)編號link;/定義狀態(tài)之間的連接typedef struct cd int item_num;/狀態(tài)中的項目數(shù) int link_num;/狀態(tài)的連接數(shù) item wN;/項目集 link uN;/連接集cd;/定義狀態(tài)typedef struct DFA int cd_num;/狀態(tài)個數(shù) cd sN+1;/狀態(tài)集DFA;/定義規(guī)范LR(0)項目族,D.sN用作狀態(tài)轉(zhuǎn)換函數(shù)go_switch()的存儲空間DFA D;void dfa();/求規(guī)范LR(0)項目族void closure(int);/求閉包void go_switch

18、(int,int);/求轉(zhuǎn)換int test_go_switch();void add_go_switch();/增加新狀態(tài)void del_go_switch();/清空狀態(tài)轉(zhuǎn)換函數(shù)的存儲空間void action();/構(gòu)造ACTION表void go_answer();/構(gòu)造GOTO表int control();/總控程序int length(int);/返回增廣文法產(chǎn)生式右部的長度int test(char);void printf_ag();/輸出ACTION表和GOTO表bool test_link(int i,int num);void main() int i,j; ifstr

19、eam in("input1.txt",ios_base:in);/讀文件,從文件中讀入pronum,vtnum,vnnum以及產(chǎn)生式 in>>pronum>>vnnum>>vtnum; in>>vn; in>>vt; for(i=1;i<=pronum;i+) in>>oldi;/將產(chǎn)生式存入old,old1為第一個產(chǎn)生式 for(i=1;i<=pronum;i+) for(j=0;oldij!='/0'j+) oldzij=oldij;/將產(chǎn)生式從old錄入oldz ol

20、dz00='P' oldz01=old10;/加入P->S，將原文法擴充，使其變?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)個數(shù)、連接個數(shù)、項目個數(shù) dfa(); action(); go_answer(); printf_ag(); control();/求一個狀態(tài)的閉包void closure(int i) int j,k,m,x,flag; do j=D.si.item_n

21、um;/j是本輪循環(huán)開始前的項目數(shù) for(k=0;k<D.si.item_num;k+) for(m=0;m<=pronum;m+) if(oldzm0=oldzD.si.wk.fD.si.wk.l)/對當(dāng)前狀態(tài)i中的每個項目，查詢每個產(chǎn)生式，例如：A->a.Ab應(yīng)找到A->. flag=0;/判斷該項是否在當(dāng)前狀態(tài)i中,即檢查(m,1)是否存在于狀態(tài)i中,保證求閉包時加入的新項目和原項目集不重合 for(x=0;x<D.si.item_num;x+) if(D.si.wx.f=m&&D.si.wx.l=1) flag=1; break; if(

22、flag=0)/如果該項不在當(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.item_num);/當(dāng)一輪沒有新的項目加入i時，結(jié)束循環(huán)/狀態(tài)轉(zhuǎn)換函數(shù)，i是狀態(tài)編號，num是符號編號，狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果存于sNvoid go_switch(int i,int num) int j; for(j=0;j<D.si.item_num;j+) if(test(oldzD.si.wj.fD.si.wj.l)=num) D.sN.wD.sN.item_num.

23、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)號,判斷符號的類型,0<=終結(jié)符返回值<100,100<=非終結(jié)符返回值<200,錯誤符號返回值=200int test(char c) int i,j; for(i=0;i<vtnum;i+) if(vti=c) break; if(i<vtnum) return i;else for(j=0;j<vnnum;j+) if(vnj=c) break; if(j<vtnu

24、m) return (100+j);else return 200; /檢驗狀態(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 for(i=0;i<D.cd_num;i+)/選定一狀態(tài)，對sN中的每個項目進行循環(huán)，如果存在一個項目在當(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,符號a)依然存在于狀態(tài)4中，go_switch

25、(狀態(tài)4,符號c)已經(jīng)存在于狀態(tài)5中 for(j=0;j<D.sN.item_num;j+)/如果在當(dāng)前狀態(tài)i中找不到sN的當(dāng)前項目j,就跳至下一狀態(tài) for(k=0;k<D.si.item_num;k+) if(D.si.wk.f=D.sN.wj.f&&D.si.wk.l=D.sN.wj.l) break; if(k>=D.si.item_num) flag=0; break; if(flag=1) return 1000+i; return 1;/狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果未被任何現(xiàn)有狀態(tài)完全包含，完全滿足建立新狀態(tài)的條件 /把狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果加入DFA，即當(dāng)建

26、立新狀態(tài)的條件符合時，建立新的狀態(tài)sD.cd_numvoid add_go_switch() int i; for(i=0;i<D.sN.item_num;i+) D.sD.cd_num.wD.sD.cd_num.item_num.f=D.sN.wi.f; D.sD.cd_num.wD.sD.cd_num.item_num.l=D.sN.wi.l; D.sD.cd_num.item_num+; D.cd_num+;/清空狀態(tài)轉(zhuǎn)換函數(shù)的存儲空間void del_go_switch() D.sN.item_num=0;/構(gòu)造規(guī)范LR(0)項目族void dfa() int i,j,k; D.

27、s0.w0.f=0; D.s0.w0.l=1; D.cd_num+; D.s0.item_num+; closure(0);/把P->S加入初狀態(tài)，并求其閉包 do i=D.cd_num;/本輪循環(huán)開始時狀態(tài)數(shù) for(j=0;j<D.cd_num;j+)/對每個狀態(tài)進行循環(huán) for(k=0;k<vnnum;k+)/對當(dāng)前狀態(tài)，每個非終結(jié)符 if(!test_link(j,k+100)/檢驗當(dāng)前狀態(tài)用當(dāng)前非終結(jié)符構(gòu)造的連接是否已經(jīng)存在，若存在，則跳至下一非終結(jié)符，這樣可以防止do_while()二次執(zhí)行時，將連接集重新加入當(dāng)前狀態(tài)，比如s0 go_switch(j,k+100

28、);/對當(dāng)前狀態(tài)，當(dāng)前符號調(diào)用狀態(tài)轉(zhuǎn)換 if(test_go_switch()=1)/如果符合建立新狀態(tài)的條件 add_go_switch(); D.sj.uD.sj.link_num.f=k+100;/建立當(dāng)前狀態(tài)和新狀態(tài)的連接 D.sj.uD.sj.link_num.l=D.cd_num-1; D.sj.link_num+; else if(test_go_switch()>=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_go_switc

29、h()-1000; D.sj.link_num+; del_go_switch();/清空 for(k=0;k<vtnum;k+)/對當(dāng)前狀態(tài)，每個終結(jié)符 if(!test_link(j,k) go_switch(j,k); if(test_go_switch()=1) add_go_switch(); D.sj.uD.sj.link_num.f=k; D.sj.uD.sj.link_num.l=D.cd_num-1; D.sj.link_num+; else if(test_go_switch()>=1000) D.sj.uD.sj.link_num.f=k; D.sj.uD.s

30、j.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)生時，結(jié)束/構(gòu)造ACTION表void action() int i,j,k; for(i=0;i<D.cd_num;i+)/對每個狀態(tài)循環(huán) for(j=0;j<D.si.link_num;j+)/S，對每個狀態(tài)的每個連接循環(huán)，如果找到當(dāng)前狀態(tài)用終結(jié)符建立的連接，則ACTION當(dāng)前狀態(tài)號對應(yīng)終結(jié)符編號=連接另一端狀態(tài)號 if(D.si.uj.f<100) ACTIONiD.si.u

31、j.f=D.si.uj.l; for(j=0;j<D.si.item_num;j+)/r，對每個狀態(tài)的每個項目循環(huán)，如果找到一個終結(jié)項目，例如A->c. 則ACTION當(dāng)前狀態(tài)所有vt和$=產(chǎn)生式A->c的編號 if(oldzD.si.wj.fD.si.wj.l='/0') for(k=0;k<=vtnum;k+) ACTIONik=D.si.wj.f+100; for(j=0;j<D.si.item_num;j+)/acc，對每個狀態(tài)的每個項目循環(huán)，如果找到P->S. 所在狀態(tài)，則ACTION當(dāng)前狀態(tài)$=300，即acc if(D.si.w

32、j.f=0&&D.si.wj.l=2) ACTIONivtnum=300; break; /構(gòu)造GOTO表void go_answer() int i,j; for(i=0;i<D.cd_num;i+) for(j=0;j<D.si.link_num;j+)/對每個狀態(tài)的每個連接循環(huán)，如果找到當(dāng)前狀態(tài)用非終結(jié)符建立的連接，則GOTO當(dāng)前狀態(tài)號對應(yīng)非終結(jié)符編號=連接另一端狀態(tài)號 if(D.si.uj.f>=100) GOTOiD.si.uj.f-100=D.si.uj.l; /總控程序int control() int i,j,num; char cY='

33、;/0'/初始化帶分析字符串的存儲空間 SqE stackN; int p1=0,p2=0;/p1是待分析字符串指針,p2是棧頂下一位元素的指針,stack0是棧底 vtnum+;/把'$'加入終結(jié)符集 for(i=0;i<N;i+) stacki.c1='/0'/初始化符號棧 stackp2.t=0; stackp2.c1='$'/把(0,$)壓棧 p2+;/指針更新 printf("/n請輸入要分析的字符串(以$結(jié)尾):"); cin>>c; printf("/n棧中狀態(tài) 棧中符號 輸入

34、串 分析動作/n");while(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION棧頂狀態(tài)號當(dāng)前字符編號 for(i=0,j=0;stacki.c1!='/0'i+) printf("%d",stacki.t); j+; for(i=0;i<14-j;i+) printf(" ");/輸出棧中狀態(tài)for(i=0,j=0;stacki.c1!='/0'i+) printf("%c",stacki.c1); j+; for(i=0;i<14-j;i+) p

35、rintf(" ");/輸出棧中符號 for(i=p1,j=0;ci!='/0'i+) printf("%c",ci); j+; for(i=0;i<14-j;i+) printf(" ");/輸出剩余字符串if(ACTIONstackp2-1.ttest(cp1)>0&&ACTIONstackp2-1.ttest(cp1)<100)/S printf("S%d/n",ACTIONstackp2-1.ttest(cp1);/輸出分析動作 stackp2.t=ACTI

36、ONstackp2-1.ttest(cp1);/將狀態(tài)壓棧 stackp2.c1=cp1;/將當(dāng)前字符壓棧 p2+; p1+;/更新兩個指針 else if(ACTIONstackp2-1.ttest(cp1)>100&&ACTIONstackp2-1.ttest(cp1)<200)/r,歸約 num=ACTIONstackp2-1.ttest(cp1)-100;/num是歸約所用的產(chǎn)生式編號 printf("r%d/n",num); p2=p2-length(num);/彈出length(num)個元素 stackp2.t=GOTOstackp

37、2-1.ttest(oldznum0)-100;/若T是彈出后的棧頂元素中的狀態(tài)號，把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 $%c $ acc/n",oldz10); printf("/nSucceed,您輸入句型和文法匹配!/n"); return OK;/返回增廣文法產(chǎn)生式右部的長度int length(int i) int j; for(j=1;oldzij!='/0'j+) return (j-1);/j-1