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

1、實(shí)驗(yàn)三lr(1)分析法實(shí)驗(yàn)學(xué)時(shí)： 4實(shí)驗(yàn)類型：驗(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

3、#e+i*i#r6: fi 歸約,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 入棧11016975#e+t*i#r6:fi 歸約,goto(7,f)=10入棧120169710#e+t*f #r3: t t*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)容：描述 lr(1) 語(yǔ)法分析程序的設(shè)計(jì)思想:定義項(xiàng)目的一般形式

4、是a , a1a2ak ，這樣的一個(gè)項(xiàng)目稱為一個(gè) lr(k) 項(xiàng)目。項(xiàng)目中的 a1a2ak稱為它的向前搜索符串(或展望串 ) ，令 k=1,即為 lr(1) 語(yǔ)法分析程序。在此，重新定義closure(i) 的算法：項(xiàng)目集 i 的閉包 closure(i) 構(gòu)造方法：1. i的任何項(xiàng)目都屬于closure(i) 。2. 若項(xiàng)目ab, a屬于 closure(i) ，b是一個(gè)產(chǎn)生式， 那么， 對(duì)于 first(a) 中的每個(gè)終結(jié)符b， 如果b, b 原來(lái)不在 closure(i) 中，則把它加進(jìn)去。3. 重復(fù)執(zhí)行步驟 2，直至 closure(i) 不再增大為止。go()的算法保持與 lr語(yǔ)法分

5、析程序一樣， 通過(guò)以下方法構(gòu)造文法分析表：動(dòng)作 action 和狀態(tài)轉(zhuǎn)換 goto 構(gòu)造如下：1. 若項(xiàng)目aa , b 屬于 ik且 go(ik, a) ij， a 為終結(jié)符，則置 actionk, a 為 “sj ”。2. 若項(xiàng)目a，a 屬于 ik，則置 actionk, a 為 “rj ”；其中假定 a為文法 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)行

6、何種動(dòng)作。程序結(jié)構(gòu)描述： 函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能均在程序源代碼出注釋出來(lái)，在此不再贅述，詳細(xì)含義請(qǐng)參照源代碼 cpp 文件。詳細(xì)的算法描述（程序執(zhí)行流程圖）:(1) 總控程序，也可以稱為驅(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)所決定。lr分析器由三個(gè)部分組成：

7、其中: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é)符。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)，即

8、棧指針sp減去r，并把 a移入文法符號(hào)棧內(nèi)， j=gotoi,a 移進(jìn)狀態(tài)棧，其中 i 為修改指針后的棧頂狀態(tài)。(3) 接受 acc:當(dāng)歸約到文法符號(hào)棧中只剩文法的開始符號(hào)s時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是# ，則為分析成功。(4) 報(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)actiongot

9、oi+*()#et f0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5本程序根據(jù)給出的lr(1)文法分析表，構(gòu)造string 類的action126=s5,0,0,s4,0,0, ength()-3;for(int j=0;jn;j+)t(0)=; (productioni-1.at(0);t(0)=s) actionit.erase(0,1); _str(),s);_str()，將 actionit轉(zhuǎn)換為整型 actionit.insert(0,

10、s);t(0)=r) actionit.erase(0,1);_str(),s);_str()，將actionit轉(zhuǎn)換為整型 actionit.insert(0,r);/將 r 添加回actionit else if(actionit=0)coutterrorendl;break; else if(actionit=acc) output(s); coutacct分析成功 endl; break; else if(flag=false)break;int main()string s;cout*lr(1)分析*endl; cout本分析文法產(chǎn)生式為 endl;for(int j=0;j6;j+)coutproductionjendl;cout*lr(1)分析*endl;char t;docout 輸入字符串 s;/輸入要分析的字符串cout*現(xiàn)進(jìn)行如下分析*endl;cout 步驟t狀態(tài)棧 t符號(hào)棧 t剩余輸入串 t動(dòng)作