北邮《语法分析程序》实验报告

1、语法分析程序实验报告需求分析题目：语法分析程序的设计与实现。实验内容：编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。E . E T |E -T |TT T*F |T/F |FF id | (E) | num实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。方法1 :编写LL(1赭法分析程序，要求如下。(1)编程实现算法4.2,为给定文法自动构造预测分析表。(2)编程实现算法4.1,构造LL(1)B测分析程序。方法2:编写语法分析程序实现自底向上的分析，要求如下。(1)构造识别所有活前缀的 DFA(2)构造LR分析表。(3)编程实现算法4.3,构

2、造LR分析程序。概要设计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预测分析表*/dnsEerrerrerrE-TAL-TAerrE-TR号1*产Aeri*ei*Ferrerrft-eeri*A - eTeirerrei*rerrT-FBT-FBerrT-FBei*pBB-eB-eerrerrH-eeriB-eFei*rerrerret*i*F-dF-CEerFF-nerr2. LR实现，自底向上分析(1) .原文法E . E T|E -T |TT T* F |T/F |F F id |(E) | num(2) .文法对应的拓广文法为: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).构造项目集规范族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出发：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出发：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出发: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出发:111 = go(I 5, E) = closure(F-(E ), E-E + T, E-E -T) = F-(E ), E-E +T, E-E -T;从I7出发：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出发：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出发：Ii4 = go(I 9, F) = closure(T-T*F ) = -T-T*F ; -从Iio出发：Ii5 = go(I 10, F) = closure(T-T/F ) = T-T/F ; 从Iii出发：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分析表状态actiongoto+-*/idnum()$ETF0s4S6S51231s7s8acc2r3r3s9s10r3r33r6r6r6r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s5

15、1511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r8运行结果/分析算数表达式由如下文法产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 领 BMBF $ABnnEAlBE $RB?HBAT $ABAlBABF$ABIBAT $AB)ABABF $ADftDftDd $AB)ABAB领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*济 -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育输入待分析学存串了 横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 统 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装态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产2s?slQerr*BtFp2ei*rr2ei*rerierr14r41*4r4r4CTFerrr4ei*pr4ei*perrerr15r5i*5rSf5v5ei*r产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$产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;/非终结字符类class Charpublic:string FIRST; /first 集string FOLLOW; /follow 集Char(); 构造函数Char();析构函数void first(string s) FIRST=FIRST+s; / 读入 first 集void follow(string s) FOLLOW=FOLLOW+s; / 读入 follow 集 ;/产生式类class Genepublic:char left;/产生式左部非终结符string right; /产生式右部字符串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;/ 存入非终结字符的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 存入全部产生式的左部和右部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;/ 预测分析表的构造string M610

31、;/ 初始化分析表，表的第一行和第一列分别存入终结符和非终结符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;/ 初始化，把除第一行和第一列的元素均设为err / 算法 4.2string VN=0EATBF; /用数组记录分析表的行和列，方便后面查找需要填入表格的 位置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 预 测 分 析 表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+=$;输入串末尾加上$结束符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)/如果产生式右部为e (空符)，不用压栈el

34、se break;/ 否则出错跳出循环coutoutputtendl;/ 输出分析动作sum+;/ 步骤数 +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;/*构造分*string M1813;/ 初始化分析表，在表的第一行和第一列分别存入终结符和状

35、态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;