廖力编译原理课件第3章

[e-mail]37932352••––•––1341–Chomsky3•–→|(|)–52–•63–AA={ai|i=1,2,……n},1.εΦa(i=1,2,……n)i2.αβα|βα•βα*β+3.12•1)“|”“”“+”“”“•”2)A={ai|i=1,2,……n}αL(α)3)74––8•b(ab)*=(ba)*b•L(b(ab)*)={b,bab,babab,……}L((ba)*b)={b,bab,babab,……}nb(ab)*=(ba)*b941•αβγ–1.α+β=β+α–2.α+(β+γ)=(α+β)+γα(βγ)=(αβ)γ–3.α(β+γ)=αβ+αγ(α+β)γ=αγ+βγ–4.εα=αε=α–5.(α*)*=α*–6.α*=αεααα*=α*α–7.(α+β)*=(α*+β*)*=(α*β*)*1052αβγAε∉L(γ)α=β|αγα=βγ*α=β|γαα=γ*β116–1.G–2.–3.SS=w,wVT*w12G1–S→aS|aB–B→bB|bA–A→cA|c1.–SaS|aB……1–BbB|bA……2–AcA|c……313•2.2•1SaS|aBS=a*aB=a+B……4•2BbB|bAB=b+A……5•3AcA|cA=c*c=c+……6•65B=b+c+……7•74S=a+b+c+……8•3.S=a+b+c+14(FiniteAutomation,FA)1••152abcde……162abcde……172abcde……182abcdz……192abcdz……20•(|)*•xtemp–122222xtemp122112q0q111000223DFA(DeterministicFA)•(1)M(S,Σ,f,s0,Z–S–Σ–fS×Σ→Sf(s,a)=s’–s0s0S–ZZ⊆S•fsas’233(2)–DFA–•12“→”()εDFA24•DFAM=({0,1,2,3},{a,b},f,0,{3})–f:f(0,a)=1f(0,b)=2f(1,a)3f(1,b)2–f(2,a)=1f(2,b)=3f(3,a)3f(3,b)3•333312231210ba1aa032babbab25•DFAM{a,b,c}abca01abbca2ccb3acb26DFA:M=({0,1,2,3,},{a,b,c},f,0,{1,2,3})–ff(0,a)=1f(0,b)=1–f(0,c)=1f(1,a)=1–f(1,b)=1f(1,c)=1–f(2,a)=3f(2,b)=2–f(2,c)=2f(3,b)=3–f(3,c)=3273(3)–“”–KK–*00–+11(4)DFA•α∈Σ*DFAM=(S,Σ,f,s0,Z)(s0,α)*(s,ε),sZ283(4)DFA•DFAMML(M)–(s0,α)*(s’,ε),s’∉Z–294NFA(Non-deterministicFA)(1)M=S,Σ,f,S0,Z–S–Σ–fS×Σ→2S(S)–S0S0S–ZZS1)2)DFANFA30NFAM({q0,q1},{0,1},f,{q0}{q1})fq0q111000q0q0q1q1q1q0q010314(2)–MM’(L(M)=L(M’))MM’–5NFA(1)NFAMDFAM’L(M)=L(M’)LNFADFAL325NFA(2)•NFAM=(S,Σ,f,S0,Z)DFAM’=(Q,Σ,δ,I0,F1.I0=S02.QIi={s0,s1,……sj},skS,0≤k≤j;Mf({s0,s1,……sj},a)=f(s0,a)f(s1,a)……f(sj,a)=Υ={s0,s1,……st}=ItItQItQjkkasf0),(=335NFA(2)3.2Q4.F={I|IQ,IZΦ}1)M2)ΣQI0Qδ345NFA(2)3)NFA(COVER)DFA4)35NFAM({q0,q1},{0,1},f,{q0}{q1})fq0q111000q0q0q1q1q1q0q01036•1.M’I0={q0}QI0•2.QI0={q0}Mf({q0},0)={q0}f({q0},1)={q1}=I1Q={I0,I1}•3.QI1={q1}Mf({q1},0)={q0,q1}=I2f({q1},1)={q0}=I0Q={I0,I1,I2}•4.QI2={q0,q1}Mf({q0,q1},0)={q0,q1}f({q0,q1},1)={q0,q1}=I2Q={I0,I1,I2}•5.F={I1,I2}37•NFA–DFAM’=({I0,I1,I2},{0,1},Σ,I0,{I1,I2}I2={q0,q1}I2={q0,q1}I2={q0,q1}I0={q0}I2={q0,q1}I1={q1}I1={q1}I0={q0}I0={q0}10ΣQ38I2I2I2I0I2I1I1I0I010δI0I111000I21396(1)(2)()——–1.DFAM–2.–3.406(3)DFAMs,t•s,t–(s,w)*(s1,ε)(t,w)*(t1,ε)s1,t1wVT*swtws,t•s,t–s,ts,t416(4)()1.S0{I01,I02}I01,I02ε2.kk{Ik0,Ik1……Ikm}.m–Iki={s1,s2,……sk},af(Iki,a)kIki–k426(4)()3.24.MM436(4)()1244•DFA3546aaaabbb012abbabab45•1.M–0{{0,1,2},{3,4,5,6}}•2.1f({0,1,2},a)={1,3}0{012}–1`{{1}{0,2}{3,4,5,6}}f({0,2},a)={1}1‘–f({0,2},b)={2,5}1‘{0,2}–1``{{1}{0}{2}{3,4,5,6}}462.2–f({3,4,5,6},a)={3,6}1“{3,4,5,6}–f({3,4,5,6},b)={4,5}1“{3,4,5,6}–{3,4,5,6}3.4–2{{1},{0},{2},{3,4,5,6}}4.3{3,4,5,6}456345647012aabb3aabbDFA481ΣNFAML(M)ΣΣNFAMαL(α)=L(M)ΣαDFAML(M)=L(α)αDFAML(M)L(α)492Mα1)2)Mx,yxεMMεyNFAM’L(M)=L(M’)3)3M’xyxyΣM50111113β2α|β2βα2αβα3αβ122αβ*51•DFAM111113200000xyεε52x0310|0101|1000|1100|11yεεx0yεε00|11(10|01)(00|11)*(01|10)xy((10|01)(00|11)*(01|10)|(00|11))*533αM1)αx,y2)3α3)2Σε4)NFAM(ε)DFAxyα5412α|β12βα2αβ112αβ1‘112β*2εε1‘β55(a|b)*(aa|bb)(a|b)*,DFAMxy(a|b)*(aa|bb)(a|b)*1y(a|b)*(a|b)*2x(aa|bb)bb1yε2xaa5εa|bε6εa|b1yε2xa5εbaε6εabb34ab563αMNFAMNFAMεεε(ε-closure)()DFANFA574εNFA(1)εεIε(ε-closure(I))(a)sIsε-closure(I)(b)sIsεs’ε-closure(I)584εNFA(2)–ε-closure(I){q0,q1,……qn}aε-closure(J)–ε-closure(J)•J=f(q0,a)f(q1,a)……f(qn,a)•Jεε-closure(J)594εNFA(3)εNFANFAM=(S,Σ,f,S0,Z)DFAM’=(Q,Σ,δ,I0,F(a)I0ε-closure(S0),I0Q(b)QIi={s0,s1,……sj},skS,0≤k≤j;It=ε-closure(f(Ii,a)),ItQItQ(c)2Q(d)F={I|IQ,IZΦ}601yε2xa5εbaε6εabb34abI5={5,1,4,6,y}I3={5,3,2,1,6,y}I6={5,3,1,6,y}I4={5,4,1,2,6,y}I6={5,3,1,6,y}I5={5,1,4,6,y}I4={5,4,1,2,6,y}I6={5,3,1,6,y}I4={5,4,1,2,6,y}I5={5,1,4,6,y}I3={5,3,2,1,6,y}I3={5,3,2,1,6,y}I4={5,4,1,2,6,y}I1={5,3,1}I2={5,4,1}I2={5,4,1}I3={5,3,2,1,6,y}I1={5,3,1}I2={5,4,1}I1={5,3,1}I0={x,5,1}baI61I5I3I6I4I6I5I4I6I4I5I3I3I4I1I2I2I3I1I2I1I0baIDFAI0I1I2I3I4I6I5abaaababbbbba621•G=(VN,VT,P,S)M=(Q,Σ,f,q0,Z)L(G)=L(M)•1)2)MGRGLL(M)=L(GR)=L(GL)632•G=(VN,VT,P,S)M=(Q,Σ,f,q0,Z)•1)VNTQ=VN{T};ΣVTq0S;PS→εZ={S,T}Z={T}6422)Pfa)PA1→aA2Mf(A1,a)=A2.b)PA1→aMf(A1,a)=T.c)Σaf(T,a)=Φ,65G=({S,A,B},{a,b,c},P,S)P–S→aS|aB–B→bB|bA–A→cA|cFAM=(Q,Σ,f,q0,Z)1)TQ={S,B,A,T}Σ{a,b,c}q0SZ={T}662)ff(S,a)=Sf(S,a)=Bf(B,b)=Bf(B,b)=Af(A,c)=Af(A,c)=TNFABTacASbabc673•M=(S,Σ,f,s0,Z),Rg=(VN,VT,P,s0),1)s0∉ZPa)Mf(Ai,a)=Aj,PAi→aAj;b)AjZ,PAi→aAi→a|aAj;2)s0Z,f(s0,ε)=s0,Ps0’→ε|s0s0’s068DFAM=({A,B,C,D},{0,1},f,A,{B})RgC01AD1010|1B0Rg=({A,B,C,D},{0,1},P,A)A→0B|1D|0B→1C|0DC→0B|1D|0D→0D|1DL(Rg)=L(M)=0(10)*694•G=(VN,VT,P,S)M=(Q,Σ,f,q0,Z)GM1)Q=VN{q0},q0MΣ=VTSMZPS→εZ={S,q0}Z={S}2)Pf:–a)PA1→A2aMf(A2,a)=A1.–b)PA1→aMf(q0,a)=A1.70•71•11)2)3)4)7221)2)733•FORTRAN“IF”–IF(5.EQ.M)GOTO50–IF=100–IF(100)=5741C––……–––.,;():752•()1)2)3)4)761.2.3.4.––77•=+•78LEXLEXLEXLEX79123NFA4DFA5εNFA6