北郵《語法分析程序》實驗報告

1、語法分析程序?qū)嶒瀳蟾嫘枨蠓治鲱}目：語法分析程序的設(shè)計與實現(xiàn)。實驗內(nèi)容：編寫語法分析程序，實現(xiàn)對算術(shù)表達(dá)式的語法分析。要求所分析算術(shù)表達(dá)式由如下的文法產(chǎn)生。E . E T |E -T |TT T*F |T/F |FF id | (E) | num實驗要求：在對輸入表達(dá)式進(jìn)行分析的過程中，輸出所采用的產(chǎn)生式。方法1 :編寫LL(1赭法分析程序，要求如下。(1)編程實現(xiàn)算法4.2,為給定文法自動構(gòu)造預(yù)測分析表。(2)編程實現(xiàn)算法4.1,構(gòu)造LL(1)B測分析程序。方法2:編寫語法分析程序?qū)崿F(xiàn)自底向上的分析，要求如下。(1)構(gòu)造識別所有活前綴的 DFA(2)構(gòu)造LR分析表。(3)編程實現(xiàn)算法4.3,構(gòu)

2、造LR分析程序。概要設(shè)計1. LL(1)語法分析程序(1) .原文法E E T|E -T |TT T* F |T/F |FF - id |(E) | num(2) .消除左遞歸和回溯E-TR R-+TR R-TRR-e T-FW W-*FW W-/FW W-e F-id F-(E) F-num(3) . FISRT集和 FOLLOWFIRST(S)=FIRST(E)=FIRST(T)=FIRST(F)= id, num, ( id, num, ( id, num, ( id, num, ( FOLLOW (S)=FOLLOW (E)=FOLLOW (T)=FOLLOW (F)= $ $ , +

3、，-, ) $ , + ,-,*,/,) $ , + , - , * , / , ) (4) .LL(1預(yù)測分析表*/dnsEerrerrerrE-TAL-TAerrE-TR號1*產(chǎn)Aeri*ei*Ferrerrft-eeri*A - eTeirerrei*rerrT-FBT-FBerrT-FBei*pBB-eB-eerrerrH-eeriB-eFei*rerrerret*i*F-dF-CEerFF-nerr2. LR實現(xiàn)，自底向上分析(1) .原文法E . E T|E -T |TT T* F |T/F |F F id |(E) | num(2) .文法對應(yīng)的拓廣文法為:1 E - E+T2

4、E - E-T3 E - T4 T - T*F5 T - T/F6 T - F7 F - (E)8 F - id9 F - num(3) . FISRT集和 FOLLOWFIRST(S)=FIRST(E)=FIRST(T)=FIRST(F)= id, num, ( id, num, ( id, num, ( id, num, ( FOLLOW (S)=FOLLOW (E)=FOLLOW (T)=FOLLOW (F)= $ $ , +，-, ) $ , + ,-,*,/,) $ , + , - , * , / , ) (4).構(gòu)造項目集規(guī)范族Io = closure(S- E)S- E, E-

5、E+T, E- E-T, E- T, T- T*F, T- T/F, T- F； F- id,F- (E), F- num;從10出發(fā)：i = go(I 0, E) = closure(S-E,E-E +T, E-E -T) = S-E , E-E +T, E-E -T;2 = go(I 0, T) = closure(E-T,T-T *F, T-T /F) = E-T , T-T *F, T-T /F;3 = go(I 0, F) = closure(T-F ) = T-F ; 4 = go(I 0, id) = closure(F-id ) = F-id ; 5 = go(10, () =

6、 closure(F-(E) = F-( E), E- E+T, E- E-T, E- T, T- T*F, T- T/F,T- F, F- id, F- (E), F- num;I6 = go(I 0, num) = closure(F-num ) = F-num :從Ii出發(fā)：I7 = go(I i, +) = closure(E-E+ T) = E-E+ T, T- T*F, T- T/F, T- F, F- id, F- (E), F- num;I8 = go(I 1, -) = closure(E-E- T) = E-E- T, T- T*F, T- T/F, T- F, F- id

7、, F- (E),F- num;從I2出發(fā):I9 = go(I 2, *) = closure(T-T*F) = - T-T* F,- F- id, F- (E), F- num;Iio = go(I 2, /) = closure(T-T/F) = T-T/ F, F- id, F-(E), F-num;從I5出發(fā):111 = go(I 5, E) = closure(F-(E ), E-E + T, E-E -T) = F-(E ), E-E +T, E-E -T;從I7出發(fā)：112 = go(I 7, T) = closure(E-E+T , T-T *F, T-T /F) = E-E+

8、T , T-T *F, T-T /F;從I8出發(fā)：113 = go(I 8, T) = closure(E-E-T , T-T *F, T-T /F) = E-E-T , T-T *F, T-T /F;從I9出發(fā)：Ii4 = go(I 9, F) = closure(T-T*F ) = -T-T*F ; -從Iio出發(fā)：Ii5 = go(I 10, F) = closure(T-T/F ) = T-T/F ; 從Iii出發(fā)：Ii6 = go(I ii, ) = closure(F-(E) ) = F-(E) ; LR分析表如下：goto0,E = i; goto0,T = 2; goto0,F

9、 = 3;action0,id = S4; action0,( = S5; action0,num = S6;actioni,$ = ACC.; actioni,+ = S7; actioni,- = S8; ;action2,) = action2,+ = action2,- = action2,$ = R4;action2,* = S9; action2,/ = SiO;action3,) = action3,+ = action3,- = action3,* = action3,/ = action3,$ = R7;action4,) = action4,+ = action4,- =

10、action4,* = action4,/ = action4,$ = R8;goto5,E = ii; goto5,T = 2; goto5,F = 3;action5,id = S4; action5,( = S5; action5,num = S6;action6,) = action6,+ = action6,- = action6,* = action6,/ = action6,$ = RiO;goto7,T = i2; goto7,F = 3;action7,id = S4; action7,( = S5; action7,num = S6; goto8,T = 13; goto8

11、,F = 3;action8,id = S4; action8,( = S5; action8,num = S6;goto9,F = 14;action9,id = S4; action9,( = S5; action9,num = S6;goto10,F = 15;action10,id = S4; action10,( = S5; action10,num = S6;action11,) = S16; action11,+ = S7; action11,- = S8;action12,) = action12,+ = action12,- = action12,$ = R2; action

12、12,* = S9; action12,/ = S10;action13,) = action13,+ = action13,- = action13,$ = R3; action13,* = S9; action13,/ = S10;action14,) =action14,+=action14,-= action14,*= action14,/=action14,$=R5;action15,) =action15,+=action15,-= action15,*= action15,/=action15,$=R6;action16,) =action16,+=action16,-= act

13、ion16,*= action16,/=action16,$=R9;DFA:開始U：TfFIi- ETE E-E可 EtE -TE- E- Ef T-T- T- F- FT FtE+T E-T T T*F T/FF id (E) num5： 口(E) E- E+T Ef E-T E寸“ 0 -PF r-，I/F U-F Ft，id Ff , (E) F3 , nunK：EE+ , I 5RF 5 T/F T-F F+id H -(E) F num1山:Is：Efi+T- JTtT , *F T-T - /FE-E-I叫num%:Ft n Um 12：EtTTtT 怦 *田*4T-F1%：TtT

14、/FI$TtT*F113：E-E-T r t *fIT /FF-* ii 5 (E) Ft，mmLo： TH/， Ft - id Ft , (E)F- numt 為*T”避Li； F-(E*) E -E - +T E E - -TT-T+ - FF- id Ft - (E) F- num(5) .LR分析表狀態(tài)actiongoto+-*/idnum()$ETF0s4S6S51231s7s8acc2r3r3s9s10r3r33r6r6r6r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s5

15、1511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r8運行結(jié)果/分析算數(shù)表達(dá)式由如下文法產(chǎn)E-E+T：E-T!TT-T*F!T/FiFF-id：!nun請選擇所需分析方法；1,LL2,L 的.退出輸入錯誤，請重新輸入n 悄除左遞歸和回溯；E-TA甘一,1口A-e T-FB B-/FE B-e F-dF-XEJ F-nLL(1):希除左遞歸和回潮E-TAR-e T-FB B-*FBB-e F-dF-XE F-ft4-0餐Zd+lACFFerreprerrA-eerrfl-eJepr

16、errerp16FFT-FBT-FEei*i*I-FBerraB-eB-eepi*eprBeerrB-eFerrerrerrerrF-dF3eirrF-oerr提示可用分析成功用例：和(nam*id+id)*num/num； 諳輸，.仔分析，苻串；測試用例：(1+(a+b)*5/6)示1用分近成功用例上和uun 必工dnuiihilae) 輸入存分析字符號1 +步驟棧輸入輸出0iE1崖壯+10-5/6沖1$T-FD2$aqtCl+5/6JF-XE3$AUE(匹配成功45rh，el+(a+b*Sj/l$E-ia5$ABAT一心嗎鵬鴻T-PB6$ABABFl+*5/6$F-n7$AHABnl+*5

17、/6$匹配成功8*$B-e9$ADA5z6$1P$ftRAT*5Z6$n配成功11$ABATCab5/6$T-FB12$ABABF 山,Cab-5/65F-XE5E $AT $ABFADAB $ABI $nBfti+ $ABAT 領(lǐng) BMBF $ABnnEAlBE $RB?HBAT $ABAlBABF$ABIBAT $AB)ABABF $ADftDftDd $AB)ABAB領(lǐng)BHE $ABAiDF* $AEAlBF $ABABn $RRAR$ABAB $AB)*$AB) $AB 5A $l+a*bJ5z6?$ $ l+*5/6$ 1 +a*5/6?$lt*5/6?$ lKa+b)*5/6$ +

18、Ca+h*Ey65 +*5/6)5 +Ca+h*5j/b$ (a+b)5/6$ ;(a*b)*5zG$ a*b5*5/6$ ab*5/6i ab*5/6? ab*5/6?$+b)崎/6,$ b-5/&)Sb*C/C54/05 3*5/G$ *5*濟(jì) -5z6)$ 5/T6$小，5 zt? 6$ 6$E-TAT-FB F-XE 匹配成功 E-TA TFBF-ri 匹配成力 B - 9匹配成功 T-FB F-XE) 匹配成功 E-rfiT-FB F-d 匹配成力A-*TA 匹配成力 T-FB F-d 匹配成功 JB-e A一mEM附 B-*FB 匹配成力 F-n 匹配成力 B- /FB 匹配成力匹

19、配成功 Be由.出 匹配成加 B-is 由一九 分析成小測試用例：1育輸入待分析學(xué)存串了 橫1$E?AT：ABTI柏BnI i$A輸入1$151515輸出E-TfiT-FEF-n 匹配成功 B-bX 分析成功似字符串分析成幻程.用，琴庠畜目例:Cnnn+niim/nnr步驟 棧輸入輸出B $EE-Tfl1 SAT日2*k$T-FE2 SfiBFa2k$F-d3 5ABCa2*h匹配成功4 2+k$prr5 $A2+k$eri*6 $2+k$ 土 XI-D 統(tǒng) J 胃 _Ld_1 1 LR:謂選擇所需分析方法:1-LL2.LU隊退出菜用LR分析法的柘廣文法如T ：A-E E-E+T i-r*F

20、F-XE-E-T I-T/FF-XEE-T T-F F-n裝態(tài)actiongoto4*dCnJETFn1 11er2e r i* gepi*和 h*s4sei*F上6e ri*1d上s7.fM總epi*errem*ei*i*e*revpaiccPl*l*eFe i*i*2*3i*3s9slQeri*ei*i*i*2ei*i*2eF3誣i*&*6eri*eri*err*rteisFe ri*T 1J-X-KJ!-J 88m T Q工f1-1ta, Bi1wrHrRTPactiongoto+M/dlniJETF04errQerr邙errer-ps4sSEFTs6errJ1s7口零8EFTei*pT

21、PBFl*err6FP4CCerrerrerr2r3甘3s?slSerrerrr3errr-3errerrerr3r6F6i*6r66FFtrr爐6err1*6ci*rcpfeir4*7i*7i7v7ei*i*ei*p7甘上上好箝eFVerFept*5er i*efrerr6rl*s4后Serrs6err1123br9i9r?r9errerrp?ei*r尸9e 1*1*e i*eii,7errerreri*eirs4s5errs6erper-r1238errerrerret*ps4*5errs6errerr1339firi*ftFFeri*E1Ws4fiprft Fl*errei*r1410e

22、rrerrerrerr各4errerrerrei*F1511s7sHeriGFFerrF116etFeFl*er*rerrerr12rlrls9毋10errerrrleirrlC1*FGl*l*6113r2產(chǎn)2s?slQerr*BtFp2ei*rr2ei*rerierr14r41*4r4r4CTFerrr4ei*pr4ei*perrerr15r5i*5rSf5v5ei*r產(chǎn)5errerrerr16r8r8r8r8err&5r8errr8errerr測試用例：(1+(a+b)*5/6)：可用 分析曲止月傳:Cnuin+id+idinum/niJini 入卷餌斤將號串心個加嗎弓)步驟棧目01趴52

23、職 5n63QEF340(512bMCSkllG0GE1117705E11*758WCSE11*7(S(14y P90F1005EH5T2輸入1 +5/6$ l+(a+b*5/6?$+5/6)$+5/6)$+*b/6)$*5/C$Mb*5/GS+b*bA$+b5/6$分析動作shift 5 shift 6 reduce hy T-?nroduca by 7-Pinduce hy E-fshift 7 ihift 虧shift 4i*eflujce nreduce hreduce bE-T測試用例：a2+ky T-F1G05E117E+T1605Eli*7C5Ell畤76畤1705E11*716

24、V F-XE180$y T-F1905E11+?T1.2*5/2&05E11+7T12210$y F-r220Sy T-T*F2305E11*7T12專2405E11+7T12Z0250$y F- n260$0 T-VT川270iy E- E *T2805290l&y F-XEiI300F3$310T2$32en該字符串分析成功一 9ireduce b shift 16 reduce h reduce b shift 9 shift G reduce b） if?（lure b） vhift 10 Shift 6 reduce h reduce h reduce bshift ICreduce

25、 b reduce bv TF veduc by ET acc測試用例:提示：可用分聽成功月例：numidnQMiium/nijuO 造輸入容分析符號串力步驟 材M1即62MF3&T24Utl該字符串分析成功輸入分析動作Zisliift； 6$reducebyF-n$產(chǎn)fisiiiic0hyT-F審reducebyET$acc號F人*月座|用例:mi (zld+id*n um/n uni步驟棧輸入分析動作00a2*k$shift 410d42+kSj_I l_lJ I * j i_I源代碼#include#include#include#include#include using namesp

26、ace std;/非終結(jié)字符類class Charpublic:string FIRST; /first 集string FOLLOW; /follow 集Char(); 構(gòu)造函數(shù)Char();析構(gòu)函數(shù)void first(string s) FIRST=FIRST+s; / 讀入 first 集void follow(string s) FOLLOW=FOLLOW+s; / 讀入 follow 集 ;/產(chǎn)生式類class Genepublic:char left;/產(chǎn)生式左部非終結(jié)符string right; /產(chǎn)生式右部字符串string FIRST; 右部的 first 集 string

27、 FOLLOW; / 左部的 follow 集Gene();Gene();void product(string a)left=a0;int k=a.size();for(int i=3;ik;i+)righti-3=ai;void first(string a) FIRST=FIRST+a; void follow(string a) FOLLOW=FOLLOW+a; ;int find(string s,char ch)int k=s.size();for(int i=0;iTA;G11=A-+TA;G12=A-TA;G13=A-e;G14=T-FB;G15=B-*FB;G16=B-/FB

28、;G17=B-e;G18=F-d;G19=F-(E);G110=F-n;coutn*LL(1)*”coutn 消除左遞歸和回溯：0;i-)coutG111-it;if(i%3=0)coutendl;coutendl;/ 存入非終結(jié)字符的first 集 follow 集Char E;E.first(d(n);E.follow($);Char A;A.first(+_e);A.follow($);/A=EChar T;T.first(d(n);T.follow(+-$);Char B;B.first(*/e);B.follow(+-$);/B=TChar F;F.first(d(n);T.foll

29、ow(*/+-$);/ 定義一個Gene 類的 vector 存入全部產(chǎn)生式的左部和右部vector g(11);duct(G10);g0.FIRST=T.FIRST;g0.FOLLOW=E.FOLLOW;duct(G11);g1.FIRST=+;g1.FOLLOW=A.FOLLOW;duct(G12);g2.FIRST=-;g2.FOLLOW=A.FOLLOW;duct(G13);g3.FIRST=e;g3.FOLLOW=A.FOLLOW;duct(G14);g4.FIRST=F.FIRST;g4.FOLLOW=T.FOLLOW;g

30、5.product(G15);g5.FIRST=*;g5.FOLLOW=B.FOLLOW;duct(G16);g6.FIRST=/;g6.FOLLOW=B.FOLLOW;duct(G17);g7.FIRST=e;g7.FOLLOW=B.FOLLOW;duct(G18);g8.FIRST=d;g8.FOLLOW=F.FOLLOW;duct(G19);g9.FIRST=(;g9.FOLLOW=F.FOLLOW;duct(G110);g10.FIRST=n;g10.FOLLOW=F.FOLLOW;/ 預(yù)測分析表的構(gòu)造string M610

31、;/ 初始化分析表，表的第一行和第一列分別存入終結(jié)符和非終結(jié)符M00=0;M01=+;M02=-;M03=*;M04=/;M05=d;M06=(;M07=);M08=n;M09=$;M10=E;M20=A;M30=T;M40=B;M50=F;for(int i=1;i6;i+)for(int j=1;j10;j+)Mij=err;/ 初始化，把除第一行和第一列的元素均設(shè)為err / 算法 4.2string VN=0EATBF; /用數(shù)組記錄分析表的行和列，方便后面查找需要填入表格的 位置string VT=0+-*/d()n$;for(int i=0;i11;i+)int m=gi.FIRS

32、T.size();int row=find(VN,gi.left);for(int j=0;jm;j+)if(gi.FIRSTj!=e)int line=find(VT,gi.FIRSTj);Mrowline=G1i;elseint t=gi.FOLLOW.size();for(int k=0;kt;k+)int line=find(VT,gi.FOLLOWk);Mrowline=G1i;) )coutn*LL 預(yù) 測 分 析 表endl;*for(int i=0;i6;i+)for(int j=0;j10;j+) coutMijt;coutendl;)算法4.1string w=;strin

33、g state=;string output=;/output 為輸出串cout提示：可用分析成功用例：和 (num+(id+id)*num/num)endl;cout”請輸入待分析字符串:;cinw;coutendl;w+=$;輸入串末尾加上$結(jié)束符cout步驟%=8)/控制輸出格式對齊/控制輸出格式對齊/控制輸出格式對齊coutsumtstatetwtt;elsecoutsumtstatettwtt;if(w.size()=A& a=a& a=0& a=A&X=A&X=3;k-) state+=outputk;else if(output3=e)/如果產(chǎn)生式右部為e (空符)，不用壓棧el

34、se break;/ 否則出錯跳出循環(huán)coutoutputtendl;/ 輸出分析動作sum+;/ 步驟數(shù) +1if(output= 分析成功)cout 該字符串分析成功nnE;G21=E-E+T;G22=E-E-T;G23=E-T;G24=T-T*F;G25=T-T/F;G26=T-F;G27=F-d;G28=F-(E);G29=F-n;coutn*LR*n.coutn采用LR分析法的拓廣文法如下：endl;for(int i=0;i10;i+)coutG2it;if(i%3=0)coutendl;/*構(gòu)造分*string M1813;/ 初始化分析表，在表的第一行和第一列分別存入終結(jié)符和狀

35、態(tài)M00=0;M01=+;M02=-;M03=*;M04=/;M05=d;M06=(;M07=);M08=n;M09=$;M010=E;M011=T;M012=F;M10=0;M20=1;M30=2;M40=3;M50=4;M60=5;M70=6;M80=7;M90=8;M100=9;M110=10;M120=11;M130=12;M140=13;M150=14;M160=15;M170=16;for(int i=1;i18;i+)for(int j=1;j13;j+)Mij=err;/ 分析表除第一行和第一列外初始化為err/*存入LR 分 析 表*M15=s4;M16=s5;M18=s6;M110=1;M111=2;M112=3;M21=s7;M22=s8;M29=acc;M31=r3;M32=r3;M33=s9;M34=s10;M37=r3;M39=r3;M41=r6;M42=r6;M43=r6;M44=r6;M47=r6;M49=r6;M51=r7;M52=r7;M53=r7;M54=r7;M57=r7;M59=r7;M65=s4;M66=s5;M68=s6;M610=11;M611=2;M612=3;M71=r9;M72=r9;M73=r9;M74=r9;M77=r9;