编译原理习题分解.ppt

习题 第2章2-2试分别构造产生下列语言的文法 (2){anbmcp∣n,m,p≥0} 解一: S →ABC A →aA ∣ε B →bB ∣ε C →cC ∣ε 解二: S →aS∣ X X →bX ∣Y Y →cY∣ ε (3){an#bn∣n≥0} ∪{cn#dn∣n≥0} 错解: S →aSb ∣cSd ∣# 解: S →X∣ Y X →aXb ∣# Y →cYd∣# (6)偶数个0和偶数个1组成的符号串的集合 解: S →1A ∣0B ∣ε A →1S∣0C B →0S ∣1C C →0A∣1B (考察0开头的0011,0101,0110) 2-3试描述由下列文法所产生的语言的特点 (1){(10) n a b m a 0 n∣n,m≥0} (4)S =* baSndc(n≥0) (5){a2n-1∣n≥1} 2-6句子L: L: begin d; d; s; s; end的语法树 2-11 (1) S →AB S →c A →bA A →a B →aSb B →c bbaacb 解:最右推导(下划线为各步直接推导所得句型的句柄) S=AB=AaSb =Aacb=bAacb =bbAacb=bbaacb 2-11 (2) S →(AS) S →(b) A →(SaA) A →(a) (((b)a(a))(b)) 解:最右推导(下划线为各步直接推导所得句型的句柄) S= (AS) = (A (b) ) = ( (SaA) (b) ) = ( (Sa (a) ) (b) ) = ( ( (b) a (a) ) (b) ) 2-13化简文法 (1)解:执行算法2.1 因为C →c,所以Vn1={C} 又有A →cCC,所以Vn1={C,A} 同理S →bCACd,所以Vn1={C,A,S} 至此Vn1不再增大,于是得到文法G1为 G1=({S,A,C}, {b,c,d}, P1, S) 其中P1由如下产生式组成 S →bCACd, A →cSA ∣cCC, C →cS ∣c 再执行算法2.2 Vn2={S} 因为S →bCACd, A →cSA ∣cCC, C →cS ∣c 所以Vn2={S,A,C} Vt2= {b,c,d} 至此Vn2,Vt2不再增大,于是得到化简后的文法G2为 G2=({S,A,C}, {b,c,d}, P2, S) 其中P2由如下产生式组成 S →bCACd, A →cSA ∣cCC, C →cS ∣c 2-13化简文法 (3)解:执行算法2.1 因为S →ac, C →d,所以Vn1={S,C} 至此Vn1不再增大,于是得到文法G1为 G1=({S,C}, {a,b,c,d}, P1, S) 其中P1由如下产生式组成 S →ac, C →bc ∣d 再执行算法2.2 Vn2={S} 因为S →ac 所以Vn2={S} Vt2= {a,c} 至此Vn2,Vt2不再增大,于是得到化简后的文法G2为 G2=({S}, {a,c}, P2, S) 其中P2由如下产生式组成 S →ac 2-14消去ε-产生式 (2)解:执行算法2.3可得W={A} 可判定ε不属于L(G) 执行算法2.4 改写产生式集为 S →aAA∣aA∣a A →bAc∣bc∣dAe ∣de 2-15消去无用产生式和单产生式 (2)解:没有无用产生式 执行算法2.6可得W(S)={S,A,B} W(A)={A,B} W(B)={B} P’={S →SA, S →SB, S →(S), S →( ), S →[S], S →[ ]} ∪{A →(S), A →( ), A →[S], A →[ ]} ∪{B →[S], B →[ ]} (3)解:没有无用产生式 执行算法2.6可得W(E)={E,T,F,P} W(T)={T,F,P} W(F)={F,P} W(P)={P} P’={E →E+T∣T*F ∣P↑F ∣(E) ∣i} ∪{T →T*F ∣P↑F ∣(E) ∣i} ∪{F →P↑F ∣(E) ∣i} ∪{P → (E) ∣i} 第3章3-9对应状态矩阵画出状态图,写出相应3型文法,描述输入串特征 (ⅰ)解: S →bS ∣aA A →aA ∣bB