资源描述：
《编译原理习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、程序设计语言与编译——语言的设计与实现（第2版）习题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)Þ(B)Þ(SdB)Þ((A)dB)Þ((B)dB)Þ(SdS)Þ(Sda)Þ((S)dB)Þ((b)dB)Þ((A)daÞ((B)
6、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(*可有下列两棵不同的语法树习题9答案9-2解：（1）消除文法G的②产生式直接左递归。A→SeA'
7、fA'③A'→dA'
8、e④（2）消除间接左递归：按S.A排序，将S的①产生式代入③有A→AaeA'
9、AbeA'
10、ceA'
11、fA'
12、⑤（3）消除⑤的直接左递归有A→ceA'A"
13、fA'A"⑥A"→aeA'A"
14、beA'A"
15、e⑦（4）对S的①产生式提公因子有S→AB
16、c⑧B→
17、a
18、b⑨（5）最后，文法G提取公因子，消除左递归后的产生式由⑧,⑨,⑥,⑦和④组成，无多余的产生式。（6）若按A.S排序，得到的产生式组合是另外的形式，但它们是等价的文法，读者可以试试。9-3解：消除左递归后，得文法G':S→(L)
19、aL→SL'L'→,SL'
20、e递归下降过程：Procedurematch(t:token);beginiflookahead=tthenlookahea
21、d=nexttokenelseerrorendprocedureS;beginiflookahead='a'thenmatch('a')elseiflookahead='('thenbeginmatch('(');L;iflookahead=')'thenmatch(')')elseerrorendendprocudureL;beginS;L';endprocudureL';beginiflookahead=','thenbeginmatch(',')S;L'endend9-6解：（1）G'（S）：S→AS'S'→:AS'
22、e
23、A→BA'A'→+BA'
24、eB→bS*
25、a（2）FIRST集和FOLLOW集FIRSTFOLLOWSb，a#，*S':，e#，*Ab，a#，*，:A'+，e#，*，:Bb，a#，*，:，+预测分析表a:+b*#SS→AS'S→AS'S'S'→:AS'S'→eS'→eAA→BA'A→BA'A'A→eA→+BA'A→eA→eBB→aB→bS*（3）因为预测分析表无多重定义入口，所以G'是LL（1）文法。9-7解：对习题9-3的文法G消除左递归后，得文法G'：S→(L)
26、aL→SL'L'→,SL'
27、eFIRST集和FOLLOW集FI
28、RSTFOLLOWS(，a)，’，#L(，a)L'’，e)预测分析表（）a,#SS→(L)S→aLL→SL'L→SL'L'L'→eL'→,SL'因为预测分析表无多重定义入口，所以文法G是LL（1）文法。习题10答案10-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）语法
29、树（3）短语FaP,c,FaPbc直接短语FaP,c句柄FaP最左素短语FaP10-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)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(
30、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
