廖力编译原理课件第5章

[e-mail]37932352•–––LL(1)•––LR31•2••3PDA4a+b……##–“”–51“”2abcd6••1S→aAcBe•2A→b•3A→Ab•4B→dabbcde7112,3,4,1S10aAcBe92,3,4eaAcB8eaAcd7deaAc62,3cdeaA5cdeaAb42bcdeaA3bcdeab2bbcdea1abbcde0SdAcBeAbdb81PrecedenceParser)••–2LR95.11234105.11Gε(X,Y)2•XYGP→…XY…•XYGP→…XQ…Q→Y…•XYYGGP→…QR…Q→…XYfirst(R)•XS→X…,X;S→…XX++115.11Warshall2•PDA“”125.1135.212()31)2)3)145.24E→E+E|E-E|E*E|E/E|(E)|i15i+i-i*(i+i)1)i+i-i*(i+i)2)E+i-i*(i+i)3)E+E-i*(i+i)“”4)E-i*(i+i)5)E-E*(i+i)“”6)E-E*(E+i)7)E-E*(E+E)8)E-E*(E)9)E-E*E“”“”10)E-E11)E165.22a,b“…ab…”“…aQb…”,Qab1)abab2)abab3)abab4)abab175.21)2)185.2#i)(*+#i)(*+195.2•1*/“”•2–ai–b“”a#aa#,•3()•4abba205.21PDAa+b……#OPNDOPTRπθ#215.21PDA1OPTROPNDOPTRθ,OPNDπ2OPNDOPTR“”222OPND=“”;OPTR=“#”;flag=true;advance;/**/whileflag{ifθ=“#”andSYM=“#”thenflag=false/**/elseifθ=“(“andSYM=“)”then/**/{OPTRadvance;}elseifSYMthen/**/{SYMOPNDadvance;}elseifθSYMthen/**/{SYMOPTRadvance;}23elseifθSYMthen/**/{OPNDπ1π2OPTRθπ1θπ2OPND}elseERROR;}}245.23•1–2π1θπ2θπ1π2T•1–2255.21–GGG–2•Ga,b∈VT;P,Q,R∈VN,265.22•abGP→…ab…P→…aQb…•abGP→…aR…R→b…,R→Qb…;•abGP→…Rb…R→…aR→…aQ.•Ga,bGOPG++++275.23•–A1A2…Ai-1AiAi+1…AnG–1Ai∈VNAi-1Ai+1∈VT–2B1B2…BmAi28a)B1B2…Bmb)B1B2…BmbAi-1bc)B1B2…BmbbAi+1.GP295.24P1•FIRSTVTP=–{a|P→a…P→Qa…a∈VT;P,Q∈VN}•LASTVTP=–{a|P→…aP→…aQa∈VT;P,Q∈VN}•++++305.22•…aP…–b∈FIRSTVT(P),ab;–…Pb…–a∈LASTVT(P),ab;•:GS→aAcBeA→Ab|bB→dFIRSTVTLASTVT31•FIRSTVT(S)={a}LASTVT(S)={e}•FIRSTVT(A)={b}LASTVT(A)={b}•FIRSTVT(B)={d}LASTVT(B)={d}edcbaedcba325.251FIRSTVT(P)a)1•FIRSTVT(P)•(1)P→a…P→Qa…a∈FIRSTVT(P)•(2)a∈FIRSTVT(Q)P→Q…a∈FIRSTVT(P)335.251FIRSTVT(P)a)1•11PFIRSTONEaP→a…P→Qa…22PFIRST*QPQ∈VWarshallFIRSTVT(P)=(FIRST*)(FIRSTONE)345.251FIRSTVT(P)b)2•–FPaF[P,a]truea∈FIRSTVT(P)–STACKF[P,a](P,a)•351F21P→a…P→Qa…F[P,a](P,a)32•(Q,a)P→Q…a∉FIRSTVT(P)F[P,a]F[P,a](P,a)43F[P,a]“”P365.252•FORP→X1X2…XnDO•{FOR(i=1,i=n-1,i++)•{ifXiXi+1thenXiXi+1•ifi=n-2andXiXi+2andXi+1thenXiXi+1•ifXiXi+1then37•forFIRSTVT(Xi+1)aDO•{Xia}•ifXiXi+1then•forLASTVT(Xi)aDO•{aXi}•}GG38S→ifEbthenEelseEE→E+T|TT→T*F|FF→iEb→b1“”S’→S•FIRSTVT(S)={if}LASTVT(S)={else,+,*,i}•FIRSTVT(E)={+,*,i}LASTVT(E)={+,*,i}•FIRSTVT(T)={*,i}LASTVT(T)={*,i}•FIRSTVT(F)={i}LASTVT(F)={i}•FIRSTVT(Eb)={b}LASTVT(Eb)={b}2)39#bi*+elsethenif#bi*+elsethenif405.21•2•1–415.2G(E)–E→E+T|TT→T*F|FF→(E)|i–i+i*i•1–i+i*i#–1.F+i*i#6.E+T*F#–2.T+i*i#7.E+T#–3.E+i*i#8.E#–4.E+F*i#–5.E+T*i#425.222)••–i+i*i#–1.E+i*i#4.E+T#–2.E+T*i#5.E#–3.E+T*F#43•EETTT*FFFiiiEETiT*Fii445.222)•:•G(E)–E→E+T|TT→T*F|FF→(E)|i–#T+T*F+i#45EETE+TFTT*Fi•T*F,i•T*F465.231)•:#N1a1N2a2…NnanNn+1#aiNi,aj…NiaiNi1,aj-1ajai+1…aiai+1ajNi…NiaiNi1•475.232){k=1;s[k]=‘#’;/*S*/repeatSYMIFS[k]∈VTTHENj=kELSEj=k-1;Whiles[j]SYM/**/{repeatq=s[j];/**/ifs[j-1]∈VTthenj=j-1elsej=j-2untils[j]Q;48s[j+1]…s[k]N/**/k=j+1;s[k]=N}/*endofwhile*/ifs[j]SYMors[j]SYMthen{k=k+1;s[k]=SYM}/**/elseERROR/**/untilSYM=‘#’/**/}495.232)1“”“”23505.2#ifbthenielsei#S→ifEbthenEelseEE→E+T|TT→T*F|FF→iEb→b51#bi*+elsethenif#bi*+elsethenif52##N10i##ifNthenNelseN9##ifNthenNelsei8i##ifNthenNelse7ielsei##ifNthenN6elsei##ifNtheni5ielsei##ifNthen4bthenielsei##ifN3thenielsei##ifb2bthenielsei##if1ifbthenielsei##0*535.24•A•B•C545.3•θf(θ),g(θ)f(θ)θg(θ)θ•f(θ),g(θ)–θ1θ2f(θ1)g(θ2)–θ1θ2f(θ1)g(θ2)–θ1θ2f(θ1)g(θ2)•n*n2*n555.3111–1a#f(a)g(a)=cc–2•abf(a)=g(b),f(a)=g(b)1•abf(a)=g(b),g(b)=f(a)+1•abf(a)g(b),f(a)=g(b)=max(f(a),g(b))–32f(a)g(b)f(a)g(b)=2n+c256#i)(*+#i)(*+57•1c=1111111g111111f#i)(*+•2151532g144142f#i)(*+58•32161642g155153f#i)(*+•43161642g155153f#i)(*+•435595.322Bell•1a(#)fagafagaabab,fagb,abab,gbfa•2f(a)fag(a)ga;•3f(a)g(a),60#i)(*+#i)(*+61*()i#*()i#62192974g188286f#i)(*+•635.3•1,•2•f(a)=g(a),f(a)g(b),f(b)=g(a),f(b)=g(b)•f(a)g(b)f(b)=g(a)=f(a),baba645.3•3•65•1•2–FIRSTVTLASTVT•3