LR實驗報告(附代碼)

1、實驗三 LR(1)分析法實驗學(xué)時：4實驗類型：驗證實驗要求：必修一、實驗?zāi)康?構(gòu)造LR(1)分析程序，利用它進(jìn)行語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR（K）分析方法是嚴(yán)格的從左向右掃描，和自底向上的語法分析方法。二、實驗內(nèi)容對下列文法，用LR（1）分析法對任意輸入的符號串進(jìn)行分析：(產(chǎn)生式有誤，進(jìn)行修改) （1）E- E+T（2）E- ET（E-T）（3）T- T*F（4）T- T/F(T-F)（5）F- (E)（6）F- i三、實驗?zāi)康?、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。2、如果遇到錯誤的表達(dá)式，應(yīng)輸出錯誤提示信息。 3、程序輸入/輸出實例： 輸

2、入一以#結(jié)束的符號串(包括+*/（）i#)：在此位置輸入符號串 輸出過程如下：步驟 狀態(tài)棧 符號棧 剩余輸入串 動 作 1 0 # i+i*i# 移進(jìn) i+i*i的LR分析過程步驟狀態(tài)棧符號棧輸入串動作說明10#i+i*i#ACTION0,i=S5,狀態(tài)5入棧205#i+i*i#r6: Fi歸約,GOTO(0,F)=3入棧303#F+i*i#r4: TF歸約,GOTO(0,T)=3入棧402#T+i*i#r2: ET歸約,GOTO(0,E)=1入棧501#E+i*i#ACTION1,+=S6,狀態(tài)6入棧6016#E+i*i#ACTION6,i=S5,狀態(tài)5入棧70165#E+i*i#r6: F

3、i歸約,GOTO(6,F)=3入棧80163#E+F*i#r4: TF歸約,GOTO(6,T)=9入棧90169#E+T*i#ACTION9,*=S7,狀態(tài)7入棧1001697#E+T*i#ACTION7,i=S5,狀態(tài)5入棧11#E+T*i#r6:Fi歸約,GOTO(7,F)=10入棧12#E+T*F#r3: TT*F歸約,GOTO(6,T)=9入棧130169#E+T#r1:EE+T,GOTO(0,E)=1入棧1401#E#Acc：分析成功實驗報告正文的內(nèi)容：u 描述LR(1)語法分析程序的設(shè)計思想:u 定義項目的一般形式是Aab, a1a2ak ，這樣的一個項目稱為一個LR(k)項目。項

4、目中的 a1a2ak 稱為它的向前搜索符串(或展望串)，令K=1,即為LR(1)語法分析程序。在此，重新定義CLOSURE(I)的算法：項目集I 的閉包CLOSURE(I)構(gòu)造方法：1. I的任何項目都屬于CLOSURE(I)。2. 若項目AaBb, a屬于CLOSURE(I)，Bx 是一個產(chǎn)生式，那么，對于FIRST(ba) 中的每個終結(jié)符b，如果Bx, b原來不在CLOSURE(I)中，則把它加進(jìn)去。3. 重復(fù)執(zhí)行步驟2，直至CLOSURE(I)不再增大為止。GO()的算法保持與LR語法分析程序一樣，通過以下方法構(gòu)造文法分析表：動作ACTION和狀態(tài)轉(zhuǎn)換GOTO構(gòu)造如下：1. 若項目Aaa

5、b, b屬于Ik且GO(Ik, a)Ij， a為終結(jié)符，則置ACTIONk, a為 “sj”。2. 若項目Aa，a屬于Ik，則置ACTIONk, a為 “rj”；其中假定Aa為文法G的第j個產(chǎn)生式。3. 若項目SS, #屬于Ik，則置ACTIONk, #為 “acc”。4. 若GO(Ik，A)Ij，則置GOTOk, A=j。5. 分析表中凡不能用規(guī)則1至4填入信息的空白欄均填上“出錯標(biāo)志”。當(dāng)具體面對輸入串時，通過查表進(jìn)行分析該進(jìn)行何種動作。u 程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能均在程序源代碼出注釋出來，在此不再贅述，詳細(xì)含義請參照源代碼cpp文件。u 詳細(xì)的算法描述（

6、程序執(zhí)行流程圖）:(1)總控程序，也可以稱為驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動作就是由棧頂狀態(tài)和當(dāng)前輸入符號所決定。u LR分析器由三個部分組成：u 其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTOi，X=j表示，規(guī)定當(dāng)棧頂狀態(tài)為i，遇到當(dāng)前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。u

7、ACTIONi，a規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應(yīng)執(zhí)行。動作有四種可能：(1)移進(jìn)： actioni，a= Sj：狀態(tài)j移入到狀態(tài)棧，把a移入到文法符號棧，其中i,j表示狀態(tài)號。(2)歸約： actioni，a=rk：當(dāng)在棧頂形成句柄時，則歸約為相應(yīng)的非終結(jié)符A，即文法中有A- B的產(chǎn)生式，若B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R，并把A移入文法符號棧內(nèi)，j=GOTOi,A移進(jìn)狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc: 當(dāng)歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。(4)

8、報錯:當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能接受的符號串。四、實驗要求本程序原本的設(shè)計思想與實驗二相仿，但由于此種設(shè)計思想會導(dǎo)致程序靈活性大大降低，故對設(shè)計思想進(jìn)行優(yōu)化，在此，不在對原程序設(shè)計思想進(jìn)行闡述，僅對改良后的程序設(shè)計思想進(jìn)行闡述。該文法的LR(1)分析表：算術(shù)表達(dá)式文法的LR分析表狀態(tài)ACTIONGOTOi+*()#ET F0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5本程序根據(jù)給出的LR(1

9、)文法分析表，構(gòu)造string 類的action126=S5,0,0,S4,0,0, /ACTION表0,S6,0,0,0,acc,0,r2,S7,0,r2,r2,0,r4,r4,0,r4,r4,S5,0,0,S4,0,0,0,r6,r6,0,r6,r6,S5,0,0,S4,0,0,S5,0,0,S4,0,0,0,S6,0,0,S11,0,0,r1,S7,0,r1,r1,0,r3,r3,0,r3,r3,0,r5,r5,0,r5,r5;int 類的gotoarr123=1,2,3, /GOTO表0,0,0,0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,

10、0,0,0,0,0,0,0,0，用以記錄LR(1)分析表的內(nèi)容。定義終結(jié)符集vt，非終結(jié)符集vn,產(chǎn)生式集合Production,狀態(tài)棧status,用int類的數(shù)組Status記錄棧的內(nèi)容，符號棧Stack，用string類的stacktd記錄棧的內(nèi)容，定義移進(jìn)函數(shù)Shift(),Goto函數(shù)Goto(),歸約函數(shù)Reduction(),具體的分析函數(shù)Analyse()，對于給定的字符串，讀取狀態(tài)棧的棧頂元素及字符串當(dāng)前的首字母，先通過函數(shù)Judge判斷符號棧棧頂元素是否在文法終結(jié)符集中，若不在，則輸出Error，結(jié)束程序，若在其中，則返回字符串首字母在終結(jié)符vt的下表，再通過查action

11、表，執(zhí)行相對應(yīng)的操作，執(zhí)行移進(jìn)函數(shù)Shift()或歸約函數(shù)Reduction()，同時若執(zhí)行歸約操作，再通過查找Goto表判斷應(yīng)轉(zhuǎn)到的狀態(tài)，執(zhí)行相應(yīng)的Goto函數(shù)Goto()，重復(fù)進(jìn)行以上步驟，直至分析執(zhí)行至輸出acc或Error，程序結(jié)束。u 給出軟件的測試方法和測試結(jié)果：根據(jù)程序的提示，輸入一由該文法的終結(jié)符組成的字符串，程序即會進(jìn)行分析，具體的測試實例如下：正確的輸入：錯誤的輸入：u 實驗總結(jié) （設(shè)計的特點、不足、收獲與體會）：本程序摒棄了原設(shè)計思想，改使用構(gòu)造action及Goto表來存儲LR(1)分析表的內(nèi)容,對于不同的產(chǎn)生式，只需修改其對應(yīng)的action表，Goto表，終結(jié)符及非終

12、結(jié)符表即可，大大提高了程序分析的靈活性，但由于時間有限，測試實例不足，程序可能存在未知錯誤，在此需進(jìn)一步改善，通過本次實驗，進(jìn)一步加深了對于LR(1)分析法的理解與應(yīng)用，同時關(guān)于本次實驗，有幾點深刻的體會：程序的設(shè)計思想是程序的靈魂，在程序編寫之前，一定要仔細(xì)閱讀實驗要求，正確理解實驗要求，并綜合考慮程序的算法優(yōu)化，靈活性等諸多方面，作出正確的設(shè)計思想。程序的實際編寫工作是一門細(xì)致的工作，編寫過程中一定要認(rèn)真仔細(xì)，因為程序中的一個小錯誤可能會引起一連串的錯誤，同時編寫時務(wù)必詳細(xì)仔細(xì)，避免程序的邏輯錯誤，因為程序的邏輯錯誤調(diào)試是們十分復(fù)雜耗時的工作，對于程序編寫中的一個小的邏輯錯誤，需要耗費大量

13、時間調(diào)試，而本實驗在編寫完成后，即消耗接近兩天的時間進(jìn)行調(diào)試，所以程序的編寫務(wù)求認(rèn)真、仔細(xì)、準(zhǔn)確。PS:實驗源代碼請參照cpp文件。#include#include#includeusing namespace std;string action126=S5,0,0,S4,0,0, /ACTION表 0,S6,0,0,0,acc, 0,r2,S7,0,r2,r2, 0,r4,r4,0,r4,r4, S5,0,0,S4,0,0, 0,r6,r6,0,r6,r6, S5,0,0,S4,0,0, S5,0,0,S4,0,0, 0,S6,0,0,S11,0, 0,r1,S7,0,r1,r1, 0,r3

14、,r3,0,r3,r3, 0,r5,r5,0,r5,r5;int gotoarr123=1,2,3, /GOTO表 0,0,0, 0,0,0, 0,0,0, 8,2,3, 0,0,0, 0,9,3, 0,0,10, 0,0,0, 0,0,0, 0,0,0, 0,0,0;char vt6=i,+,*,(,),#; /存放終結(jié)符 char vn3=E,T,F; /存放非終結(jié)符 string Production6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/產(chǎn)生式集合int count=0;/記錄當(dāng)前進(jìn)行處理的輸入字符串字符位置int line=1;/記錄處理的步驟數(shù)bool f

15、lag=false;int StatusNumber=1;/棧中狀態(tài)數(shù)string stacktd=#;/記錄符號棧中內(nèi)容int Status50=0;/記錄狀態(tài)棧stack Stack;/創(chuàng)建一個符號棧stack status;/創(chuàng)建一個狀態(tài)棧void Judge(int &i,int j,char arr,char ch,string s)/判斷輸入串是否由文法終結(jié)符組成flag=false;for(int l=0;lj;l+)if(ch=arrl)flag=true;i=l;break;if(flag=false)couttErrorendl;count=s.size();void Ou

16、tputstatus()/輸出狀態(tài)集for(int i=0;iStatusNumber;i+)coutStatusi;void Outputstring(string s)/輸出未處理的字符串for(int i=count;is.size();i+)couts.at(i);void Output(string s)/輸出步驟、狀態(tài)集、符號集、輸入串 coutlinet; Outputstatus(); couttstacktdt; Outputstring(s); couttt; line+;void Shift(int i,string s)/移進(jìn)函數(shù)SOutput(s); coutACTI

17、ONstatus.top(),s.at(count)=Si,狀態(tài)i入棧endl; status.push(i);/將狀態(tài)i壓進(jìn)狀態(tài)棧 StatusStatusNumber=i;/Status記錄狀態(tài)棧的內(nèi)容 Stack.push(s.at(count);/將當(dāng)前面臨的輸入串符號壓進(jìn)符號棧 stacktd=stacktd+s.at(count);/stacktd記錄符號棧的內(nèi)容 count+;/當(dāng)前面臨的輸入串字符往后移一位StatusNumber+;/狀態(tài)數(shù)加一void Goto(stack st1,stack st2,string s)/GoTo語句int j=-1; int ch1=st1

18、.top();char ch2=st2.top();Judge(j,3,vn,ch2,s);/求得ch2在非終結(jié)符表中的位置if(gotoarrch1j=0)couttErrorendl; count=s.size();elsestatus.push(gotoarrch1j);/新狀態(tài)進(jìn)棧 StatusStatusNumber=gotoarrch1j; StatusNumber+; void Reduction(int i,string s)/歸約函數(shù)R Output(s);coutri:Productioni-1歸約，GoTo(;int N=Productioni-1.length()-3;

19、for(int j=0;jN;j+)/消除要歸約的狀態(tài)及符號status.pop();Stack.pop();StatusNumber-;stacktd.erase(stacktd.length()-1);coutstatus.top(),Productioni-1.at(0)=; Stack.push(Productioni-1.at(0);/符號進(jìn)棧stacktd=stacktd+Stack.top(); Goto(status,Stack,s); coutstatus.top()入棧endl;StatusStatusNumber=status.top();void Analyse(str

20、ing s)/具體分析函數(shù)Stack.push(#);/初始化 status.push(0);s=s+#;int t=-1;/記錄ch在數(shù)組vt的位置while(counts.size()int i=status.top();char ch=s.at(count);Judge(t,6,vt,ch,s);if(flag=true)if(actionit!=acc&actionit!=0)if(actionit.at(0)=S) actionit.erase(0,1);/刪除actionit的首字母S Shift(atoi(actionit.c_str(),s);/atoi(actionit.c_str()，將actionit轉(zhuǎn)換為整型 actionit.insert(0,S);/將S添加回actionit else if(