廖力编译原理课件第2章

[e-mail]379323522.0••32.0••••0.5*x1+c–0.5x1c*+–0.5*x1+c42.01–•–––52.012–•–––62.0–––––72.0••82.192.11––ΣV23––ε102.145•a,b,c…α,β,γ…A,B,C…112.11–A={α1α2…}B={β1β2…}AB={αβ|α∈Aandβ∈B}12A0={ε}3AnAn122.1•A={a,b};B={c,e,d}•AB={ac,ae,ad,bc,be,bd}•A{a}–A0={ε}–A1=A={a}–……–An=AAn-1(n0)={a…a}132.1•1AA*A*=A0∪A1∪A2∪…–Aε•2AA+–A+=A1∪A2∪…=A*-{ε}–Aε•3:–142.2152.21•–Youngmenlikepopmusic.162.21•–→–→–→–→–→Young|pop–→men|music–→like172.22•(1)––VN•(2)–()–VT182.22•(3)––•(4)–()–A→αAα192.22•5––202.22•6––()()–212.22(7)•–S0α–Sαα∈VN∪VT*•*22•“Youngmenlikepopmusic”•–→–→–→–→–→Young|pop–→men|music–→like23→→→Young→Youngmen→Youngmen→Youngmenlike→Youngmenlike→Youngmenlikepop→Youngmenlikepopmusic24Youngmenlikepopmusic25YoungmenlikepopmusicYoungmusiclikepopmanPopmenlikeyoungmusic………………262.22(7)•–S11–L(G)L(G)={α|Sαα∈VT*}(8)––+27•A{0,1},→|→0|1•A{0,1},→→0|1282.22(8)——BNF•()——–:U→ax|ay|azU→a(x|y|z)•{}——–→{|}50.•[]——–:→[+|-]{}292.22(9)“→”“|”302.21ChomskyG(VN,VT,P,S)2Chomsky–0–1–2–3312.22Chomsky(1)0()•Pα→βα∈V+,β∈V*.•a)0(TM).•b)0•c)0•d)0322.22Chomsky(2)1•Pα→β,S→ε|β|=|α|,S→εS.•Pα→β,S→εαAβ→αγβ,α,β∈V*,A∈VN,γ∈V+.•a)1;b)1(LBA);c)1εε331•G(VN,VT,P,S)•VN{S,B,E},VT{a,b,e}•P:(0)S→aSBE•(1)S→aBE•(2)EB→BE•(3)aB→ab•(4)bB→bb•(5)bE→be•(6)eE→ee342.22Chomsky(3)2•PA→βA∈VNβ∈V*.•a)2VNVTε;•b)2(PDA);•c)2352•G(VN,VT,P,S)•VN{S,A,B},VT{a,b}•P:(0)S→aB•(1)S→bA•(2)A→a•(3)A→aS|bAA•(4)B→b•(5)B→bS|aBB362.22Chomsky(4)3•PA→αBA→αA→BαA→αAB∈VNα∈VT*•a)3RG•b)3•c)3372.23i–ii–L(G)L(G)={w|w∈VT*S→w}+38•1G1({S},{a,b},P,S)•P:(0)S→aS•(1)S→a•(2)S→bL(G1)={ai(a|b)|i=0}•2G2({S},{a,b},P,S)•P:(0)S→aSb•(1)S→abL(G2)={anbn|n=1}392.2•–P→P–P•SS→αPβ•P:P→γ;γ∈VT**+402.3412.3•2.6L1={a2nbn|n=1a,b∈VT}L1G1n=1L1=aabn=2L1=aaaabbn=3L1=aaaaaabbb……S→aaSb–S→aab422.3•2.7L2={aibjck|i,j,k=1a,b,c∈VT}L2G2S→aSS→aBB→bBB→bCC→cC|c432.3•2.8L3={ω|ω∈(a,b)*ωab}L3G3S→εS→bB|aAA→bS|aAAB→aS|bBB(0)S→ε(1)S→aSbS(2)S→bSaS442.3L4={ω|ω∈(0,1)*ω1}L4G4S→εS→0SS→1AA→0A,A→1S452.31••–––P→P462.32•P→P•••472.3•10–(0)S→Be(1)S→Ec(2)A→Ae(3)A→e–(4)A→A(5)B→Ce(6)B→Af(7)C→Cf–(8)D→f•(0)S→Be(1)A→Ae(2)A→e(3)B→Af482.3ε1ε2ε–PεS→ε–S→εS3ε–G=(VN,VT,P,S)G’=(V’N,V’T,P’,S’)1GεV02G’P’492.3ε32G’P’•A)V0εP’•B)PεP’•C)PS→εP’S‘→ε|SS’VNV’N50•11G1=({S},{a,b},P,S),–P:(0)S→ε(1)S→aSbS(2)S→bSaS•(1)V0={S}•(2)P’:(1)→S→abS|aSbS|aSb|ab•(2)→S→baS|bSaS|bSa|ba•(0)→S’→ε|S•G1’=({S’,S},{a,b},P’,S’),•P’:(0)S’→ε|S•(1)S→abS|aSbS|aSb|ab•(2)S→baS|bSaS|bSa|ba512.4522.41–2–532.4•2•G=({S,A,B},{a,b},P,S),P:–(0)S→aB|bA(1)A→a|aS|bAA(2)B→b|bS|aBB•aabbab:–S→aB→aaBB→aabSB→aabbAB→aabbaB→aabbab54SaBaBBbSbAabbackS→aB→aaBB→aabSB→aabbAB→aabbaB→aabbab552.43123562.434•1•5backSaBaBBbSbAab582.41–2•592.4•G=({E}{+,*,(,),i}PE)E→E+E|E*E|(E)|ii*i+i)1E→(E)→(E+E)→(E*E+E)→(i*E+E)→(i*i+E)→(i*i+i)2E→(E)→(E*E)→(i*E)→(i*E+E)→(i*i+E)→(i*i+i)60E(E)E+EE*EiiiE(E)E*EE+Eiii612.41234622.4•if–S→ifCthenSelseS–S→ifCthenS–S→C→•–ifc1thenifc2thens1elses263SifCthenSelseSc1ifCthenSs2c2s1SifCthenSc1ifCthenSelseSc2s1s2641Chomsky–2––3ε4