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

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)串(包括+*/ ()1#):在此位置輸入符號(hào)串輸岀過程如下：步驟 狀態(tài)棧 符號(hào)棧剩余輸入串動(dòng)作10#i+i*i #移進(jìn)i+i*i的LR分析過程步驟狀態(tài)棧符號(hào)棧輸入串動(dòng)作說明10i+i*i#ACTION0,i二S“ 狀態(tài) 5 入棧205#i+i*i#r： F-i 歸約,GOTO(0,F)=3 入棧303#F+i*i#n: T-F 歸約,GOTO(0,T)=3 入棧402+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-i

3、 歸約,G0T0(6,F)=3 入棧80163#E+F*i#r1： T-F 歸約,G0T0(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*ir6：F-*i 歸約,GOTO(7,F)=10 入棧120169710#E+T*Fr3： T-T*F 歸約,GOTO(6,T) =9 入棧130169#E+Tr,：E-E+T,G0T0(0,E)=l 入棧1401Acc：分析成功實(shí)驗(yàn)報(bào)告正文的內(nèi)容：描述LR(1)語(yǔ)法分析程序的設(shè)計(jì)思想：定義項(xiàng)目的一般形式是A, agaj ,這

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

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

6、參照源代碼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è)部分組成：LR分析器結(jié)構(gòu)二向狀態(tài)j, x為終結(jié)符或非終結(jié)符。ACTIONti, a規(guī)定了棧頂狀態(tài)為i時(shí)遇到輸入符號(hào)a應(yīng)執(zhí)行。動(dòng)作有四種

7、可能：(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(即則從狀態(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)棧中只剩文法的開始符號(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ò)，說明

8、輸 入端不是該文法能接受的符號(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)ACTIONGOTO1+*()#ETF0s5s,1231s6acc2r2S7r2r234S5s,8235r6r6r6r66S5S,937S5s,108s6SH9ris7ririIOr3r3r3r3IIr5r5r5r5本程序根據(jù)給出的LR(1)文法分析表，構(gòu)造string類的action126 = ,rS5K0,r0,rS

9、4,f0E:studyPPT 傑譯原理Debugg隧乙 exe”r-FF-XEF-i味”於十興其x xx x x x興其x農(nóng)其x xx x其減興L K1)為彳斤* 輸入字符串，r0S2 J狀態(tài)桟305乘殺輸入*i*i#303UF402#T5ttE1U16501630169E+i #E+F ttE*T789316?12 31X 4X JIUlbVVb ttE+r*i 0169710 #E+T*F 0169 ttE*T1401UE是否維續(xù)分析段或y維綣動(dòng)作說明，一、ACIION0.iJ=S5.狀態(tài) 5 入棧 &P6歸纟 r4：T-F歸約，GoTo=2/ p2：E-T歸纟勺，Goro=l? fiCT

10、I0Nl. + l=S6.狀態(tài)6 入核 ACT I ON 6 一 1 -35 ,狀態(tài)入棧 M：F-i.歸約，Goro6J.F)=3/? r4：T-F歸約,Goro=9 / ACTI ON 9 ,* =S7,狀態(tài)”蘋 ACTION：?,i-S5,狀態(tài) 5 入棧 rb：F-i歸約，Goro=10 p3：T-T*F歸約.GoIoE*T歸約？ Goro = acc分?jǐn)D舷功GoT o(0 j. E:studyPPT 倫譯原澄DebugWB2.exe”szi*i*x* 覺*) x x xx x x 興 x k xx x xx x x 減興 L KE*TE-TpT*FT-FPi兵”疋舟味其x其夫x其減興其x

11、 xx x其m xx減興L R36789狀態(tài)棧5 3 2 8 84 4 4 4 4 3 2Si 0 0 0 MV 0 0符號(hào)棧tt動(dòng)作說明 fiCTIONr0,l=S4 nciiONti,iFTEO zx /X #001HE是否繼續(xù)分析段媯竝續(xù)麟4辱 狀態(tài)5入棧 rb：F-i歸約，GoToeF=3入楞 M：T-F歸約，Go4,T=2入孩 v2：E-T歸約，Co“4,E=8入棧 ACTION8,-S1狀態(tài)迫入棧 rb：F-XE歸約，GoToF”3入棧 M：T-F歸約.Goro=2人様 i*2：E-T歸糾 Co“0，ET入棧 込分祈成功5042tt#6048#74811tt#903ttFtt?02

12、UTUIMaiHEE:studyPPT 傑譯原爰Debug 破遲 2.exe”是否継續(xù)分析丿或9繼績(jī)r(jià)2：E-T0約，Goro=8入桟 ACIION8,=S11,歸約，GoTo=3人棧 M：T-P歸約，CoToT=2入核 匕2；E-T歸約，GoTo=1A棧 acc分坊成功狀態(tài)棧 符號(hào)棧 剩金緒入0#M#04045tt*#43#*#042tt*#048U*#04811tt03#F*tt02ttT027ttTxOttError8910帛否繼續(xù)分析段或;繼纏鎰入宇符串動(dòng)作說明、ACTION【0,i歸約，GoTo4，F(xiàn)=3入桟 v4：T-F歸約，GoTo4.T=2入戔 i2：E-T歸約,GoTo=8/

13、棧 ACTI0N8Q-SM狀態(tài)丄丄入棧 r5：F-XE歸約，GoToF=3入棧 r4：T-F歸纟勺Goro=2人棧 AC710NC2,* =97.狀態(tài)”蘋 A CT I ON ? , -S 4 ,橫態(tài)4入棧ength () -3；for(int j=0； jN； j+) t(0)=,r； (Productioni-1. at(0)；t(0)=S)actioni t. erase(0,1) ； _str() s) ；_str(),將actioni t轉(zhuǎn)換為整型actionit. insert(0,nSn);t(0)=,r,)actionEi t. erase (0,1) ；_str (), s)

14、 ；_str () 將actioni t轉(zhuǎn)換為整型actioni t. insert (0, wrw);將 r 添加回 actionEi t else if (actionEi t = ,l0,t) cout ”tErrorwendl ；break；else if (actionEi t=waccfT) Output(s)；coutwacc*wt 分析成功endl;break；else if(flag=false)break；int main() string s；cout *未未未未*未未*審*車審律未律未未未療*1(1)分析#*# wendl；cout本分析文法產(chǎn)生式為endl；for(int j=0;j6；j+) coutProduction j endl ；coutw *lr (1)分析本未未*#*車車車審車車車木未木未未*寧*w endl ；char T；docout 輸入字符串endl ； cins；/輸入要分析的