编译原理习题答案

本书习题可分为思考题和必做题，这里仅给出必做题的参考答案。习题11-1至1-11均为思考题。习题22-1至2-14均为思考题。习题33-1至3-13均为思考题。习题44-1至4-4均为思考题。4-5解：上下文有关文法（1型文法），产生的语言L（G）{=aibici|i≥1,i为整数}4-6解：3型文法，L（G）={ai|i≥1,i为奇数}4-7解：2型文法，L（G）={aibi|i≥1,i为整数}4-8解：1型文法，L（G）={aibici|i≥1,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|z数字→0|1|2|3|4|5|6|7|8|9说明：本语言未设置任何控制语句，若要进行较为复杂的程序设计，必须增加控制语句，本语言的程序只能完全顺序执行。例：将字符串abc和xyz连接成字符串abcxyz。beginstringA1,A2,A3,A4；stringB1,B2B3,B4；A1:=a；A2:=b；A3:=c；B1:=x；B2:=g;B3:=z;A4:=A1‖A2；A4:=A4‖A3；B4:=B1‖B2；B4:=B4‖B3；B4:=A4‖B4end要求的结果字符串在B4中。习题55-1至5-19均为思考题。习题66-1至6-4均为思考题。习题77-1至7-5均为思考题。7-6解：设x,y,z对应的形式单元为J1（和J'1），J2（和J'2），J3（和J'3）。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）J'1:=T的地址J2:=A（J2的值为2）J'2:=A的地址J3:=A（J3的值为2）J'3:=A的地址J2:=J2+1（J2的值为3）J3:=J3+J1（J3的值为7）J'3↑:=J1（T的值为5，未变）J'2↑:=J2（A的值为3）J'3↑:=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的②产生式直接左递归。A→SeA'|fA'③A'→dA'|④（2）消除间接左递归：按S.A排序（按书上P116页的算法i=2,j=1时）将S的①产生式代入③有A→AaeA'|AbeA'|ceA'|fA'⑤（3）消除⑤的直接左递归有A→ceA'A|fA'A⑥A→aeA'A|beA'A|⑦（4）对S的①产生式提公因子有S→AB|c⑧B→|a|b⑨（5）最后，文法G提取公因子，消除左递归后的产生式由⑧,⑨,⑥,⑦和④组成，无多余的产生式。（6）若按A.S排序，得到的产生式组合是另外的形式，但它们是等价的文法，读者可以试试。9-3解：消除左递归后，得文法G':S→(L)|aL→SL'L'→,SL'|递归下降过程：Procedurematch(t:token);beginiflookahead=tthenlookahead=nexttokenelseerrorendprocedureS;beginiflookahead='a'thenmatch('a')elseiflookahead='('thenbeginmatch('c');L;iflookahead=')'thenmatch(')')elseerrorendendprocudureL;beginS;L';endprocudureL';beginiflookahead=','thenbeginmatch(',')S;L'endend9-4解：这里只给出消除直接右递归的一般形式。G：有产生式A→1A|2A|…|nA|消除直接右递归时得产生式A→A'A'→A'1|A'2|…|A'n|9-5为思考题。9-6解：（1）G'（S）：S→AS'S'→iAS'|A→BA'A'→+BA'A→bS*|a（2）FIRST集和FOLLOW集FIRSTFOLLOWSb，a#，*S'i，#，*Ab，a#，*，iA'+，#，*，iBb，a#，*，i，+预测分析表ai+b*#SS→AS'S→AS'S'S'→iAS'S'→S'→AA→BA'A→BA'A'A→A→+BA'A→A→BB→aB→bS*（3）因为预测分析表无多重定义入口，所以G'是LL（1）文法。9-7解：对习题9-3的文法G消除左递归后，得文法G'：S→(L)|aL→SL'L'→,SL'|FIRST集和FOLLOW集FIRSTFOLLOWS(，a)，’，#L(，a)L'’，)预测分析表（）a,#SS→(L)S→aLL→SL'L→SL'L'L'→)L'→,SL'因为预测分析表无多重定义入口，所以文法G是LL（1）文法。习题1010-1解：（1）规范规范推导（最右推导）最右推导SABASbAABbbBABb（2）语法树（推导树）（3）短语bB,AB,Abb,bBABb直接短语bB,AB句柄bB最左素短语bB10-2解：（1）因为存在推导SSbFFbFFaPbFFaPbPFaPbc所以FaPbc是文法G的一个句型。（2）语法树（3）短语FaP,c,FaPbc直接短语FaP,c句柄FaP最左素短语FaPbc10-3解：拓广文法0.S'→S1.S→AS2.S→b3.A→SA4.A→aLR（0）项目集规范族I0=closure{S'→·S}I1=GO(I0,S)I2=GO(I0,A)I3=GO(I0,b)I0:S'→·SS'→S·S→A·SS→b·S→·ASA→S·AS→·ASGO(I1,a)=I4S→·bA→SAS→·bGO(I2,A)=I2A→·SAA→·aA→·SAGO(I2,b)=I3A→·aS→·ASA→·aS→·bI4=GO(I0,a)I5=GO(I1,A)I6=GO(I1,S)I7=GO(I2,S)A→a·A→SA·A→S·AS→AS·S→A·SA→·SAA→S·AS→·ASA→·bA→·SAS→·bS→·ASA→·aA→·SAS→·bS→·ASA→·aS→·bGO(I1,b)=I3GO(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解：算符优先关系表构造如下：该文法的产生式没有两个非终结符相邻，没有产生式，它是算符文法，在其算符优先关系表中，任何两个终结符之间至多只存在一种优先关系，故它是算符优先文法。10-6解：FIRSTVT(B)={∧,∨,乛,(,i}LASTVT(B)={∨,∧,乛,),i}在规则B→B∨B中，∨＜FIRSTVT(B),∴∨＜∧又在规则B→B∨B中，LASTVT(B)＞∨,∴∨＞∨因此，在∨与∧之间存在两种优先关系，故G不是算符优先文法。若令∨，∧为右结合，则有∨＜∨，∧＜∧，优先级由低到高