资源描述：
《编译原理习题答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、本书习题可分为思考题和必做题，这里仅给出必做题的参考答案。习题11-1至1-11均为思考题。习题22-1至2-14均为思考题。习题33-1至3-13均为思考题。习题44-1至4-4均为思考题。4-5解：上下文有关文法（1型文法），产生的语言L（G）{=aibici
2、i≥1,i为整数}4-6解：3型文法，L（G）={ai
3、i≥1,i为奇数}4-7解：2型文法，L（G）={aibi
4、i≥1,i为整数}4-8解：1型文法，L（G）={aibici
5、i≥1,i为整数}4-9解：1.最左推导最右推导SÞ(A)Þ(B)Þ(SdB)SÞ(A
6、)Þ(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解：假定所设计的语言面向的机器为一般通用机。按照题目给出的
7、问题，如果不考虑输入和输出语句，那么所要设计的语言仅包含字符串数据类型和赋值语句。语言设计如下：<程序>→<分程序><分程序>→begin<语句说明表>；<执行语句>end<说明语句表>→<说明语句>
8、<说明语句表>；<说明语句><说明语句>→<变量说明><变量说明>→string<变量表>说明：string是变量的类型，表示变量为字符串。<字符串>→<字符>
9、<字符串><字符><字符>→一切可由键盘输入的字符<变量表>→<变量>
10、<变量表>，<变量><执行语句表>→<执行语句表>；<执行语句>
11、<执行语句><执行语句>→<赋
12、值语句><赋值语句>→<变量>：=<表达式><表达式>→<变量>
13、<表达式>‖<变量>说明：符号“‖”为字符串连接运算符，例如字符串abc和字符串xyz经过连接运算的结果为abcxyz。<变量>→<标识符><标识符>→<字母>
14、<标识符><字母>
15、<标识符><数字><字母>→a
16、b
17、…
18、x
19、y
20、z<数字>→0
21、1
22、2
23、3
24、4
25、5
26、6
27、7
28、8
29、9说明：本语言未设置任何控制语句，若要进行较为复杂的程序设计，必须增加控制语句，本语言的程序只能完全顺序执行。例：将字符串abc和xyz连接成字符串abcxyz。beginstringA1
30、,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的地址
31、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
32、'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的②产生式直
33、接左递归。A→SeA'
34、fA'③A'→dA'
35、e④（2）消除间接左递归：按S.A排序（按书上P116页的算法i=2,j=1时）将S的①产生式代入③有A→AaeA'
36、AbeA'
37、ceA'
38、fA'⑤（3）消除⑤的直接左递归有A→ceA'A"
39、fA'A"⑥A"→aeA'A"
40、beA
