编译原理习题答案(部分).docx

本书习题可分为思考题和必做题，这里仅给出必做题的参考答案。习题11-1至1-11均为思考题。习题22-1至2-14均为思考题。习题33-1至3-13均为思考题。习题44-1至4-4均为思考题。4-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. 因为存在推导S SbF SbP Sbc Fbc FaPbc所以FaPbc是文法G (S) 的一个句型。2. 语法树4-11解：因为串aaabaa可有下列两棵不同的语法树所以文法G (S)是二义文法。4-12解：因为串i (*可有下列两棵不同的语法树4-13解：假定所设计的语言面向的机器为一般通用机。按照题目给出的问题，如果不考虑输入和输出语句，那么所要设计的语言仅包含字符串数据类型和赋值语句。语言设计如下：begin；end|；string说明：string是变量的类型，表示变量为字符串。|一切可由键盘输入的字符|，；|：=|说明：符号“”为字符串连接运算符，例如字符串abc和字符串xyz经过连接运算的结果为abcxyz。|a|b|x|y|z0|1|2|3|4|5|6|7|8|9说明：本语言未设置任何控制语句，若要进行较为复杂的程序设计，必须增加控制语句，本语言的程序只能完全顺序执行。例：将字符串abc和xyz连接成字符串abcxyz。beginstring A1, A2, A3, A4；string B1, B2 B3, B4；A1:=a；A2:=b；A3:=c；B1:=x；B2:=g;B3:=z;A4:=A1A2；A4:=A4A3；B4:=B1B2；B4:=B4B3；B4:=A4B4end要求的结果字符串在B4中。习题55-1至5-19均为思考题。习题66-1至6-4均为思考题。习题77-1至7-5均为思考题。7-6解：设x, y, z对应的形式单元为J1（和J1），J2（和J2），J3（和J3）。1. 引用调用A:=2B:=3T:=A+B（T的值为5）J1:=T的地址J2:=A的地址J3:=A的地址J2:=J2+1（A的值为3）J3:=J3+J1（A的值为3+5=8）打印A的值为8。2. 传值A:=2B:=3T:=A+B（T的值为5）J1:=T（J1的值为5）J2:=A（J2的值为2）J3:=A（J3的值为2）J2:=J2+1（J2的值为3）J3:=J3+J1（J3的值为7）打印A的值为2。3. 结果调用形式单元J1, J2, J3无初始化值，计算是不确定的，打印A的值仍为2。4. 传值得结果A:=2B:=3T:=A+B（T的值为5）J1:=T（J1的值为5）J1:=T的地址J2:=A（J2的值为2）J2:=A的地址J3:=A（J3的值为2）J3:=A的地址J2:=J2+1（J2的值为3）J3:=J3+J1（J3的值为7）J3:=J1（T的值为5，未变）J2:=J2（A的值为3）J3:=J3（A的值为7）打印A的值为7。5. 名调用计算时用实参原文替换形参A:=2B:=3B:=A+1（A替换y, A的值为3）A:=A+A+B（A的值为9）打印A的值为9。习题88-1为实验题。8-2为实验题。8-3为实验题。8-4为实验题。8-5为思考题。8-6为思考题。习题99-1为思考题。9-2解：（1）消除文法G的产生式直接左递归。ASeA | fAAdA | e（2）消除间接左递归：按S.A排序（按书上P116页的算法i=2,j=1时）将S的产生式代入有AAaeA | AbeA | ceA | fA（3）消除的直接左递归有AceAA | fAAAaeAA | beAA | e（4）对S的产生式提公因子有SAB | cB| a | b（5）最后，文法G提取公因子，消除左递归后的产生式由, , , 和组成，无多余的产生式。（6）若按A.S排序，得到的产生式组合是另外的形式，但它们是等价的文法，读者可以试试。9-3解：消除左递归后，得文法G:S(L) | aLSLL, SL | e递归下降过程：Procedure match(t:token);beginif lookahead=t then lookahead=nexttoken else errorendprocedure S;beginif lookahead=a then match(a) else if lookahead=( then begin match(c); L; if lookahead=) then match() else error endendprocudure L;begin S;L;endprocudure L;beginif lookahead=, then begin match(,) S; L endend9-4解：这里只给出消除直接右递归的一般形式。G：有产生式Aa1A | a 2A | | a nA | b消除直接右递归时得产生式AAbAAa1 | Aa2 | | Aan | e9-5为思考题。9-6解：（1）G（S）：SAS SiAS | e ABA A+BAe AbS* | a（2）FIRST集和FOLLOW集FIRSTFOLLOWSb，a#，*Si，e#，*Ab，a#，*，iA+，e#，*，iBb，a#，*，i，+预测分析表ai+b*#SSASSASSSiASSeSeAABAABAAAeA+BAAeAeBBaBbS*（3）因为预测分析表无多重定义入口，所以G是LL（1）文法。9-7解：对习题9-3的文法G消除左递归后，得文法G：S(L) | aLSLL,SL | eFIRST集和FOLLOW集FIRSTFOLLOWS(，a)，#L(，a)L，e)预测分析表（）a,#SS(L)SaLLSLLSLLL)L,SL因为预测分析表无多重定义入口，所以文法G是LL（1）文法。习题1010-1解：（1）规范规范推导（最右推导）最右推导SABASbAABbbBABb（2）语法树（推导树）（3）短语 bB, AB, Abb, bBABb直接短语 bB, AB句柄 bB最左素短语 bB10-2解：（1）因为存在推导SSbFFbFFaPbFFaPbPFaPbc所以FaPbc是文法G的一个句型。（2）语法树（3）短语 FaP, c, FaPbc直接短语 FaP, c句柄 FaP最左素短语 FaPbc10-3解：拓广文法0.SS1.SAS2.Sb3.ASA4.AaLR（0）项目集规范族I0=closureSS I1=GO(I0,S) I2=GO(I0,A) I3=GO(I0,b)I0:SSSS SAS SbSASASA SAS GO(I1,a)=I4SbASA Sb GO(I2,A)=I2ASAAa ASA GO(I2,b)=I3AaSAS Aa SbI4=GO(I0,a)I5=GO(I1,A) I6=GO(I1,S) I7=GO(I2,S)AaASA ASA SAS SAS ASA ASA SAS Ab ASA Sb SAS Aa ASA Sb SAS Aa Sb GO(I1,b)=I3 GO(I2,a)=I4FOLLOW(S)=a, b, #FOLLOW(A)=a, b 状态5在输入a时有S4和r3的移进归约矛盾。 状态5在输入b时有S3和r3的移进归约矛盾。 状态7在输入a时有S4和r1的移进归约矛盾。 状态7在输入b时有S3和r1的移进归约矛盾。 文法G既不是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),(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)(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）共进行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）即是完整的语法树。图中的下标是为了区分归约过程中同名文法符号和便于理解而添加的，实际是没有的，对句子(a,a),(a),a)的规约栈变迁如图(10)所示。图(10)规范推导（最右推导）一共进行17步推导，归约过程也进行了17次归约，语法树如图(11)所示，其中的下标可表明其形成的先后。图(11)10-5解：算符优先关系表构造如下：该文法的产生式没有两个非终结符相邻，没有e产生式，它是算符文法，在其算符优先关系表中，任何两个终结符之间至多只存在一种优先关系，故它是算符优先文法。10-6解：FIRSTVT(B)=,乛,(,iLASTVT(B)=,乛,),i在规则BBB中，FIRSTVT(B),又在规则BBB中，LASTVT(B),因此，在与之间存在两种优先关系，故G不是算符优先文法。若令，为右结合，则有，优先级由低到高为乛, , ，则有乛, 乛, ，构造优先关系表如下：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)SS 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)AaAb BcBdAab GO(I5,c)=I5上述状态集没有移进归约冲突，（a）是SLR文法，分析表如下：abcd$SAB0S3121acc2S543S3S764r15S5S986S107r5r58S119r3r310r4r411r2r210-8解：拓广文法0.SSFOLLOW(S)=a,b,$I1=GO(I0,S)1.SbAFOLLOW(A)=a,b,$ SS2.SaBFOLLOW(B)=a,b,$I2=GO(I0,b)3.ASaI0=closureSS SbA4.AaI0:SS ASa5.BSb SbA Aa6.Bb SaB SbA SaBI3=GO(I0,a)I5=GO(I2,S)I7=GO(I3,B)I10=GO(I5,a)SaB ASa SaB ASaBSbI6=GO(I2,a)I8=GO(I3,S) GO(I6,B)=I7Bb Aa BSb GO(I6,S)=I8SbA SaBI9=GO(I3,b) GO(I6,b)=I9SaB BSb Bb G