LR實(shí)驗(yàn)報(bào)告(附代碼)

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

2、入一以#結(jié)束的符號(hào)串(包括+*/（）i#)：在此位置輸入符號(hào)串 輸出過(guò)程如下：步驟 狀態(tài)棧 符號(hào)棧 剩余輸入串 動(dòng) 作 1 0 # i+i*i# 移進(jìn) i+i*i的LR分析過(guò)程步驟狀態(tài)棧符號(hào)棧輸入串動(dòng)作說(shuō)明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：分析成功實(shí)驗(yàn)報(bào)告正文的內(nèi)容：u 描述LR(1)語(yǔ)法分析程序的設(shè)計(jì)思想:u 定義項(xiàng)目的一般形式是Aab, a1a2ak ，這樣的一個(gè)項(xiàng)目稱(chēng)為一個(gè)LR(k)項(xiàng)目。項(xiàng)

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

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

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

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

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

9、)文法分析表，構(gòu)造string 類(lèi)的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 類(lèi)的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類(lèi)的數(shù)組Status記錄棧的內(nèi)容，符號(hào)棧Stack，用string類(lèi)的stacktd記錄棧的內(nèi)容，定義移進(jìn)函數(shù)Shift(),Goto函數(shù)Goto(),歸約函數(shù)Reduction(),具體的分析函數(shù)Analyse()，對(duì)于給定的字符串，讀取狀態(tài)棧的棧頂元素及字符串當(dāng)前的首字母，先通過(guò)函數(shù)Judge判斷符號(hào)棧棧頂元素是否在文法終結(jié)符集中，若不在，則輸出Error，結(jié)束程序，若在其中，則返回字符串首字母在終結(jié)符vt的下表，再通過(guò)查action

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

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

13、時(shí)間調(diào)試，而本實(shí)驗(yàn)在編寫(xiě)完成后，即消耗接近兩天的時(shí)間進(jìn)行調(diào)試，所以程序的編寫(xiě)務(wù)求認(rèn)真、仔細(xì)、準(zhǔn)確。PS:實(shí)驗(yàn)源代碼請(qǐng)參照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=#;/記錄符號(hào)棧中內(nèi)容int Status50=0;/記錄狀態(tài)棧stack Stack;/創(chuàng)建一個(gè)符號(hào)棧stack status;/創(chuàng)建一個(gè)狀態(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)集、符號(hào)集、輸入串 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)前面臨的輸入串符號(hào)壓進(jìn)符號(hào)棧 stacktd=stacktd+s.at(count);/stacktd記錄符號(hào)棧的內(nèi)容 count+;/當(dāng)前面臨的輸入串字符往后移一位StatusNumber+;/狀態(tài)數(shù)加一void Goto(stack st1,stack st2,string s)/GoTo語(yǔ)句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īng)顟B(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+)/消除要?dú)w約的狀態(tài)及符號(hào)status.pop();Stack.pop();StatusNumber-;stacktd.erase(stacktd.length()-1);coutstatus.top(),Productioni-1.at(0)=; Stack.push(Productioni-1.at(0);/符號(hào)進(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(