《好东西,不解释》由会员分享，可在线阅读，更多相关《好东西,不解释（14页珍藏版）》请在金锄头文库上搜索。
1、14-5 解：上下文有关文法（1 型文法） ，产生的语言 L（G）=aibici | i1,i 为整数 4-6 解：3 型文法，L（G）=ai | i1,i 为奇数 4-7 解：2 型文法，L（G）=aibi | i1,i 为整数 4-8 解：1 型文法，L（G）=aibici | i1,i 为整数 4-9 解： 1. 最左推导最右推导S (A) (B) (SdB)S (A) (B) (SdB) (A)dB) (B)dB) (SdS) (Sda) (S)dB) (b)dB) (A)da (B)da) (b)dS) (b)da) (s)da (b)da) 2. 语法树4-10 解： 1. 因为存
2、在推导 S SbF SbP Sbc Fbc FaPbc 所以 FaPbc 是文法 G (S) 的一个句型。 2. 语法树4-11 解： 因为串 aaabaa 可有下列两棵不同的语法树2所以文法 G (S)是二义文法。9-2 解： （1）消除文法 G 的产生式直接左递归。ASeA | fA AdA | （2）消除间接左递归：按 S.A 排序（按书上 P116 页的算法 i=2,j=1 时）将 S 的产生式 代入有AAaeA | AbeA | ceA | fA （3）消除的直接左递归有AceAA“ | fAA“ A“aeAA“ | beAA“ | （4）对 S 的产生式提公因子有SAB | c B
3、| a | b （5）最后，文法 G 提取公因子，消除左递归后的产生式由, , , 和组成，无 多余的产生式。 （6）若按A.S 排序，得到的产生式组合是另外的形式，但它们是等价的文法，读者可以试 试。 9-3 解： 消除左递归后，得文法 G: S(L) | a LSL L, SL | 递归下降过程：Procedure match(t:token);beginif lookahead=t then lookahead=nexttokenelse errorendprocedure S;beginif lookahead=a then match(a)else if lookahead=(the
4、nbeginmatch(c);L;if lookahead=)then match()else error3endendprocudure L;begin S;L;endprocudure L;beginif lookahead=, then beginmatch(,)S;Lendend 9-6 解： （1）G（S）：SASSiAS | ABAA+BABbS* | a（2）FIRST 集和 FOLLOW 集FIRSTFOLLOWSb，a#，*Si，#，*Ab，a#，*，iA+，#，*，iBb，a#，*，i，+预测分析表ai+b*#SSASSASSSiASSSAABAABAAAA+BAAABBa
5、BbS*（3）因为预测分析表无多重定义入口，所以 G是 LL（1）文法。 9-7 解： 对习题 9-3 的文法 G 消除左递归后，得文法 G：S(L) | aLSLL,SL | 4FIRST 集和 FOLLOW 集FIRSTFOLLOWS(，a)， ，#L(，a)L ，)预测分析表（）a,#SS(L)SaLLSLLSLLL)L,SL因为预测分析表无多重定义入口，所以文法 G 是 LL（1）文法。10-1 解： （1）规范规范推导（最右推导）最右推导 SABASbAABbbBABb （2）语法树（推导树）（3）短语 bB, AB, ABb, bBABb直接短语 bB, AB句柄 bB最左素短语
6、bB 10-2 解： （1）因为存在推导 SSbFFbFFaPbFFaPbPFaPbc 所以 FaPbc 是文法 G 的一个句型。 （2）语法树（3）短语 FaP, c, FaPbc直接短语 FaP, c句柄 FaP最左素短语 FaP 10-3 解： 拓广文法 0.SS 1.SAS52.Sb 3.ASA 4.Aa LR（0）项目集规范族 I0=closureSS I1=GO(I0,S) I2=GO(I0,A) I3=GO(I0,b) I0:SS SS SAS Sb SAS ASA SAS GO(I1,a)=I4 Sb ASA Sb GO(I2,A)=I2 ASA Aa ASA GO(I2,b)
7、=I3 Aa SAS AaSb I4=GO(I0,a) I5=GO(I1,A) I6=GO(I1,S) I7=GO(I2,S) Aa ASA ASA SASSAS ASA ASASAS Ab ASASb SAS AaASA Sb SASAa SbGO(I1,b)=I3GO(I2,a)=I4 FOLLOW(S)=a, b, #FOLLOW(A)=a, b 状态 5 在输入 a 时有 S4和 r3的移进归约矛盾。状态 5 在输入 b 时有 S3和 r3的移进归约矛盾。状态 7 在输入 a 时有 S4和 r1的移进归约矛盾。状态 7 在输入 b 时有 S3和 r1的移进归约矛盾。 文法 G 既不是
8、LR（0）文法，也不是 SLR（1）文法。 10-4 解： （1）最左推导S(T)(T,S)(S,S)(a,S)(a,(T)(a,T,S)(a,(S,S)=(a,(a,S)(a,(a,a)最右推导S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a)最左推导S(T)(T,S)(S,S)(T),S)(S),S)(T,S),S)(T,S,S),S)(S,S,S),S)(T),S,S),S) (T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),S,S),S)(a,a),S),S)=(a,a)
9、,(T),S)(a,a),(S),S)(a,a),(a),S)=(a,a),(a),S)(a,a),(a),a) 最右推导 S(T)(T,S)(T,a) (S,a)(T),a)(T,S),a)6(T,(T),a)(T,(S),a)(T,(a),a)(T,S,(a),a)(T,(a),a)(S,(a),a)(T),(a),a)(T,S),(a),a)(T,a),(a),a)(S,a),(a),a)(a,a),(a),a) （2）对句子(a,(a,a)的移进归约栈的变迁如下：其中， （3） ， （4） ， （8） ， （9） ， （12） ， （13） ， （15） ， （16） ， （18）共进
10、行 9 次归约，最右 推导也是 9 次推导，正好是递过程。归约（3）的句柄是 a，语法树如图（1）所示。归约（4）的句柄是 S，语法树如图（2）所示。归约（8）的句柄是 a，语法树如图（3）所示。归约（9）的句柄是 S，语法树如图（4）所示。归约（12）的句柄是 S，语法树如图（5）所示。归约（13）的句柄是 T,S，语法树如图（6）所示。归约（15）的柄是(T)，语法树如图（7）所示。归约（16）的句柄是 T,S，语法树如图（8）所示。归约（18）的句柄是(T)，语法树如图（9）所示。图（9）即是完整的语法树。图中的下标是为了区分归约过程中同名文法符号和便于理解而添加的，实际是没有的， 对句
11、子(a,a),(a),a)的规约栈变迁如图(10)所示。7图(10)8规范推导（最右推导）一共进行 17 步推导，归约过程也进行了 17 次归约，语法树如图 (11)所示，其中的下标可表明其形成的先后。图(11)10-7 解：0.SSFOLLOW(S)=$1.SABFOLLOW(A)=b,c2.BcBdFOLLOW(B)=d,$3.Bcd4.AaAb5.AabI0=closureSSI0:SSI4=GO(I2,B)I9=GO(I5,d)SAB SAB BcdAaAbI5=GO(I2,c)I10=GO(I6,b)Aab BcBd AaAbI1=GO(I0,S) BcBdI11=GO(I8,d)S
12、S BcBd BcBdI2=GO(I0,A) BcdSABI6=GO(I3,A)BcBd AaAbBcd GO(I3,a)=I3I3=GO(I0,a)I7=GO(I3,b)AaAb AabAabI8=GO(I5,B)9AaAb BcBdAab GO(I5,c)=I5 上述状态集没有移进归约冲突， （a）是 SLR 文法，分析表如下：10abcd$SAB0S3121acc2S543S3S764r15S5S986S107r5r58S119r3r310r4r411r2r210-10 解： （1）FIRSTVT(P)=A,(LASTVT(P)=a,)FIRSTVT(F)=aLASTVT(F)=a （2
13、）优先关系表：习题 11 11-1 解：11-3 解：推导树如下：11（1）EiEVAL=B设四元式初始编号 ip=100 （2）EiEVAL= C （3）E-EEVAL=T1(101)(,c,-,T1) （4）EiEVAL=D （5）EE+EEVAL=T2(101)(+,T1,D,T2) （6）EE*EEVAL=T3(103)(*,B,T2,T3) （7）Si:=E(104)(:=,T3,-,A) 11-4 解： 结果为 333645211。 11-5 解： （1）E1CBE2F=103(102)(,A,B,104) （4）E1E*EE1VAL=T1(103)(j,-,-,0) （5）E2E
14、+EE2VAL=T2(104)(*,2,z.T1) （6）Ai:=E2Achain=0(105)(+,y,T1,T2) （7）SAS1chain=0(106)(:=,T2,-,x) （8）SWS1S1chain=103(107)(j,-,-,102) （9）Sif E1 thenS1Schain=101习题 12 12-1 解： （a）基本块程序流图 B1 (1)(3)B2 (4) B3 (5) B4 (6) B5 (7)(8)B6 (9) B7 (10)(11) B8 (12)(13) B9 (14)(15)回边74 91 10712B10 (16)(17) （b）必经结点 D(1)=1D(2)=1,2D(3)=1,3 D(4)=1,3,4D(5)=1,3,4,5D(6)=1,3,4,6 D(7)=1,3,4,7D(8)=1,3,4,7,8D(9)=1,3,4,7,8,9 D(1
