廖力编译原理课件第4章

[e-mail]379323521–2–3–341•2•4(PDA)1PDAFA2PDA3PDA5(PDA)46PDA)1PDAM=(Q,Σ,H,δ,q0,z0,F)–H–z0H–δQ(Σ{ε})HQH*δ(q,a,z){(q1,r1),(q2r2)……(qn,rn)},q,a,a(){(q1,r1),(q2r2)……(qn,rn)}(qi,riz)–F⊆Q7PDA)1)PDAPDAPDAMPDA2)PDA“”PDA3)8back•CFGG(VN,Σ,P,S),PDAM=(Q,Σ,H,δ,q0,z0,F)•1)Q=F={q0}•2)H=VNΣ•3)z0=S•4)δ–A→ωδ(q,ε,A)=(q,ω),–δ(q,a,a)=(q,ε)a∈Σ•5)PDA9PDA)L{ancbn|n=0}1LS→aSb|c2PDAM=(Q,Σ,H,δ,q0,z0,F)PDAM=({q},{a,b,c},{S,a,b,c},δ,q,S,{q})δ1)δ(q,a,a)=(q,ε)2)δ(q,b,b)=(q,ε)3)δ(q,c,c)=(q,ε)4)δ(q,εS)={(q,aSb),(q,c)}10aaacbb#S#(q,aacbb,S)1(q,aacbb,aSb)(q,acbb,Sb)1(q,acbb,aSbb)(q,cbb,Sbb)2(q,cbb,cbb)(q,bb,bb)(q,b,b)(q,ε,ε)11–121‘#S’‘#’‘S’a+b……#S#1321xxx——2xxx——3xx()——14245“”“”15x*y#1)S→xAy2)A→**3)A→*x*y#S#16x*y#1)S→xAy2)A→**3)A→*x*y#xAy#117x*y#1)S→xAy2)A→**3)A→*x*y#Ay#118x*y#1)S→xAy2)A→**3)A→*x*y#**y#1,219x*y#1)S→xAy2)A→**3)A→*x*y#*y#1,220x*y#1)S→xAy2)A→**3)A→*x*y#Ay#121x*y#1)S→xAy2)A→**3)A→*x*y#*y#1,322x*y#1)S→xAy2)A→**3)A→*x*y#y#1,323x*y#1)S→xAy2)A→**3)A→*x*y##1,32431234251•1)–P→Pa–P→Pa–P→Aa,A→Pb•2)––262G=(VN,VT,P,S)PP→Pα|β,α∈V+β∈V+βPP→βP’P’→αP’|εP→Pα1|Pα2|….|Pαm|β1|β2|….|βnP→β1P`|β2p`|……|βnP`P`→α1P`|α2P`|……|αmP`|ε27G:(1)E→E+T|T(2)T→T*F|F(3)F→(E)|iG`:(1)→E→TE`E`→+TE`|ε(2)→T→FT`T`→*FT`|ε(3)→F→(E)|i28G:P→PaPb|BaPP→BaPP`P`→aPbP`|εP291•1)–P→Pa–P→Pa–P→Aa,A→Pb•2)––3031GP1,P2,…,Pn,22For(I=1,I=n,I++){for(k=1,k=I-1,k++){Pi→PkγPi→δ1γ|δ2γ|……|δnγ/*Pk→δ1|δ2|……|δn*/}Pi}3)3131)P→Pε2)a)b)c)32(1)S→Qc|c(2)Q→Rb|b(3)R→Sa|a1RQS2RSRQ:R1Q2,Q→Rb|bR→Sa|aRQ→Sab|ab|b,(2`)SQ,SQ2S3,S→Qc|cQ→Sab|ab|bQS→Sabc|abc|bc|c;S→(abc|bc|c)S`S`→abcS`|ε333R→Sa|aQ→Sab|ab|bR,QSS→(abc|bc|c)S`S`→abcS`|ε123441)2)3543)4)3645)GGαFirst(α).First(α){a|α→a……,a∈VT}:α→ε,ε∈First(α)First(α)αε**3745)AA→α|βAaA(a)a∈First(α),a∉First(β)A→α(b)a∉First(α),a∈First(β)A→β(c)a∉First(α),a∉First(β),(d)a∈First(α),a∈First(β),First(α)={ε}3846)PDA•AAPDAA;•3947)A→δβ1|δβ2|….|δβn|δA→δA`A`→β1|β2|….|βn|ε1)2)ε40LL(1)1PDAPDAPDAa+b……#S#M[A,a]41LL(1)2PDA1242LL(1)2M[A,a]AaM[A,a]AAa“”Aa43LL(1)3a……X#44LL(1)3Xa1)X=a=‘#’2)X=a≠’#’XXX≠aerror3)X∈VNMM[X,a]XXM[X,a]Error45LL(1)α1αFirst(α)a)αGα∈V*First(α){a|α→a……,a∈VT}1)α→ε,ε∈First(α)2)First(α)αεb)α=X1X2…XnXi∈(VN∪VT),1≤i≤n,αXiα**46LL(1)α1αFirst(α)b)1(1)x∈VTFirst(x)={x};(2)X∈VNX→a……aFirst(X);X→ε,εFirst(X)47LL(1)α1αFirst(α)b)1(3)X→Y1Y2…YkYj∈(VN∪VT),1≤j≤k,First(X)j=0;FIRST(X)={};//REPEATj=j+1;FIRST(X)=FIRST(X)∪(FIRST(Yj)-{ε})UNTILε∉FIRST(Yj)j=kIF(j=kε∈FIRST(Yk))THENFIRST(X)=FIRST(X)∪{ε}48LL(1)αA1αFirst(α)b)2First(α)α=X1X2…XnXi∈(VN∪VT),1≤i≤n,First(α)i=0;FIRST(α)={};//REPEATi=i+1;FIRST(α)=FIRST(α)∪(FIRST(Xi)-{ε})UNTILε∉FIRST(Xi)i=nIF(i=nε∈FIRST(Xn))THENFIRST(α)=FIRST(α)∪{ε}49LL(1)αA2AFollow(A)a)SGGAFollow(A){a|S→…Aa…,a∈VT}1)S→…A,#∈Follow(A)2)Follow(A)A#++50LL(1)αA2AFollow(A)b)1)S‘#’Follow(S)2)B→αAβGFirst(β)-εFollow(A);3)B→αAG,B→αAβG,β→εFollow(B)Follow(A)+51LL(1)αAG()1.E→TE`2.E`→+TE`3.E`→ε4.T→FT`5.T`→*FT`6.T`→ε7.F→i8.F→(E)52First(E)=First(T)=First(F)={(,i}First(E`)={+,ε}First(T`)={*,ε}Follow(E)=Follow(E`)={),#}Follow(T)=Follow(T`)={+,),#}Follow(F)={*,+,),#}53LL(1)11A→αa∈First(α),AaαAM[A,a]A→α2A→ααεα→εAaa∈Follow(A),AεAM[A,a]A→α(αεα→ε)++54LL(1)21A→αa∈First(α),AaA→αA→αM[A,a]2A→αε∈First(α),a∈Follow(A),M[A,a]A→α(A→ε)3M[A,a]1GM2MM[A,a]55G,1.E→TE`2.E`→+TE`3.E`→ε4.T→FT`5.T`→*FT`6.T`→ε7.F→i8.F→(E)1FirstFollowFirst(E)=First(T)=First(F)={(,i}First(E`)={+,ε}First(T`)={*,ε}Follow(E)=Follow(E`)={),#}Follow(T)=Follow(T`)={+,),#}Follow(F)={*,+,),#}562F→(E)F→iFT`→εT`→εT`→*FT`T`→εT`T→FT`T→FT`TE`→εE`→εE`→+TE`E`E→TE`E→TE`E#)(*+i57LL(1)LL(1)1GMGLL(1)1)LL(1)LL(1)2)LL3)14)LL(1)LL(k)LL(k)kMnkn=|Σ|+1k158LL(1)LL(1)2GLL(1)GAA→α|β1First(α)First(β)=Φ2ε∈First(β)First(α)Follow(A)=Φ1LL(1),LL(1)2LL(1)59LL(1)S→ifEthenSelseS|ifEthenS|otherE→bS→ifEthenSS`|otherS`→elseS|εE→b602First(S)={if,other},First(S`)={else,ε}First(E)={b}Follow(S)=Follow(S`)={else,#}Follow(E)={then}3LL(1)1)First(ifEthenSS`)First(other)=ΦFirst(elseS)First(ε)=Φ2)First(elseS)Follow(S`)={else}LL(1)61LL(1)11262LL(1)21–INITIAL“S”–NEXT–PROCESSM[X,a]2M[X,a]–Xa63LL(1)23–X–a–––64LL(1)23a)Y1Y2…YNY1PROCESSb)Y1Y2…YNY1aY2…YNNEXT;Y1aERRORε“”PROCESS.65LL(1)23c)“”NEXT,PROCESS,ERROR,RETURNd)LL(1)66GG——67LL(1)εCFGCFG681LL(1)LL(1)2BNFBNF691LL(1)27012LL(1)FirstFollow3BNF