《编译原理课后习题答案》由会员分享，可在线阅读，更多相关《编译原理课后习题答案（28页珍藏版）》请在金锄头文库上搜索。
1、1第一章1典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程
2、序文件，效率低，执行速度慢。2第二章1. 乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0 型文法、1 型文法、2 型文法、3 型文法。2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以 0 为前导。答：ZSME | BS1|2|3|4|5|6|7|8|9M | D | MDD0|SB2|4|6|8E0|B3. 设文法 G 为：N D|NDD 0|1|2|3|4|5|6|7|8|9请给出句子 123、301 和 75431 的最右推导和最左推导。答：NND N3ND3N23D23123NNDNDDDDD1DD12D123NNDN1ND1N0
3、1D01301NNDNDDDDD3DD30D301NNDN1ND1N31ND31N431ND431N5431D543175431NNDNDDNDDDNDDDDDDDDD7DDDD75DDD754DD7543D754314. 证明文法 SiSeS|iS| i 是二义性文法。答：对于句型 iiSeS 存在两个不同的最左推导：SiSeSiiSesSiSiiSeS所以该文法是二义性文法。5. 给出描述下面语言的上下文无关文法。（1 ） L1=anbnci |n=1,i=0 （2 ） L2=aibj|j=i=1（3 ） L3=anbmcmdn |m,n=0答：（1 ） SABAaAb | abBcB |
4、 （2 ） SASb |ab3Aa | （3 ） SaSd | A | AbAc | 6. 设计一个最简的 DFA M,使其能够识别所有的被 3 整除的无符号十进制整数。答：1 200 | 3 | 6 | 91 | 4 | 72 | 5 | 80 | 3 | 6 | 91 | 4 | 72 | 5 | 80 | 3 | 6 | 92 | 5 | 81 | 4 | 77. 设计一个 DFA,使其能够接受被 4 整除的二进制数。答：1 2 3001 0101018. 写出表达下列各项的正则表达式。（1 ）二进制数且为 5 的倍数。（2 ） =a,b,c,第一个 a 位于第一个 b 之前的字符串。（
5、3 ） =a,b,c,包含偶数个 a 的字符串。（4）=0，1,不包含 11 子串的字符串。答：（1）可以先画出相应的有限自动机:A B C D E0101100101添加新的开始状态 S 和终止状态 T:4A B C D E0101100101ST根据以上自动机，列出以下方程： S=A A=0A+1B+T B=0C+1D C=0E+1A D=0B+1C E=0D+1E解以上方程组： E=1 *0D A=0 *1B+0*T代入 C=01*0D+1A代入 C=01*00B+01*01C+1A C=xB+yA 其中 x=(01*01)*01*00 y=(01*01)*1代入 B=0C+10B+11
6、C B=(0|11)C+10B B=(10)*(0|11)C将 C=xB+yA 代入上式 B=uB+vA B=u*vA其中 u=(10)*(0|11)x v=(10)*(0|11)y将 B=u*vA 代入 A=0 *1u*vA+0*T A=(0*1u*v)*0*T将 A 代入 S=(0 *1u*v)*0*T串(0 *1u*v)*0*即为所求。（2）该题目理解为：至少有一个 a 和一个 b，且 a 出现在 b 的前面（可以有间隔），则答案为：c*a(a|c)*b(a|b|c)*（3）(b|c)*a(b|c)*a)*(b|c)* (a(b|c)*a | b | c)*（4）(0|10)*(1|)5
7、第三章1. 词法分析器的功能是什么？答：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示 TOKEN；同时检查源程序中的词法错误。2. 试分析分隔符（空格、跳格及回车等）对词法分析的影响。答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用于错误定位，所以在删除回车符号前需要统计回车的个数。3. 给出识别 C 语言全部实型常数的自动机。答：(+|-| )(1-90-9*|0)(.0-90-9*|) (E(+|-|)0-90-9*)4. 写出识别 C 语言中所有单词的 LEX 程序。答：L=A-Z | a-zD=0-9D1=1-9%(L|_)(L|D|_)* re
8、turn (1);D1D* return (2);+ return (3);6第四章1. 设有如下文法 GS:SaABbcd | AASd | BSAh | eC | CSf | Cg | (1) 求每个产生式的 Predict 集。(2) 该文法是否为 LL(1)文法？为什么？答：(1)Predict(SaABbcd)=aPredict(S )=#,d,f,a,h Predict(AASd)=a,dPredict(A )=h,a,d,b,ePredict(BSAh)=a,d,hPredict(B eC)=ePredict(B )=bPredict(CSf)=a,fPredict(C Cg)=
9、a,f,gPredict(C )=g,b(2)由于 Predict(AASd) Predict(A )，所以该文法不是 LL(1)文法。2. 下列描述括号匹配的文法中，哪些是 LL(1)文法？(1) S(SS | S ) | (2) S(S)S | (3) SS(S)S | (4) S(S | SS(S) | 答：(1)不是， (2)是，(3)不是，(4)不是3. 已知文法 GE:EE+T | TTT*F | FFi | (E)请按递归下降法构造该文法的语法分析程序。答：求产生式的 predict 集合：predict(EE+T)=i,(predict(ET)=i,(predict(TT*F)
10、=i,(predict(TF)=i,(7由于文法中非终极符号 E 和 T 对应的产生式的 predict 集合的交集都不为空，所以该文法不满足自顶向下分析的条件，现对文法进行等价变换得到如下文法：ETEE+TE | TFTT*FT | FiF(E)求新文法的 predict 集合：Predict(ETE)=(,iPredict(E+TE)=+Predict(E)=#,)Predict(TFT)=i,(Predict(T*FT)=*Predict(T)=+,),#Predict(Fi)=iPredict(F(E)=(由于以上文法中任意非终极符号对应的产生式的 predict 集合的交集都为空，所
11、以满足自顶向下分析的条件，所以可以写出如下的递归下降语法分析伪代码：Void E() if(token(,i) T();E();else Error();void E() if(token+) Match(+);T();E();else if(token#,) ;else Error();void T() if(tokeni,() F();T();else Error();void T() if(token*) Match(*);F();T();else if(token+,),#) ;else Error();void F() if(tokeni) Match(i);else if(toke
12、n() Match();E();Match();else Error();4. 构造一个 LL(1)文法 G，它能识别语言 L:L= | 为字母表 上不包括两个相邻的 1 的非空串 ，其中=0，1。并证明你所构造的文法是 LL(1)文法。8答：A0E | 1FB0E | 1FC0EEB | FC | Predict(A0E)=0Predict(A1F)=1Predict(B0E)=0Predict(B1F)=1Predict(EB)=0,1Predict(E)=#Predict(FC)=0Predict(F)=#对任意非终极符号对应的产生式的 predict 集合的交集都为空，所以该文法是 L
13、L(1)文法。5. 已知文法 GA为：AaABe | aBBb | d(1) 试给出与 GA等价的 LL(1)文法 GA。(2) 构造 GA的 LL(1)分析表并给出输入串 aade#的分析过程。答：(1)所求 GA为：AaA (1)AABe (2)A (3)BdB (4)BbB (5)B (6)Predict(AaA)=aPredict(AABe)=aPredict(A)=#,dPredict(BdB)=dPredict(BbB)=bPredict(B)=e对任意非终极符号对应的产生式的 predict 集合的交集都为空，所以该文法是 LL(1)文法。(3) 分析表如下：a b d e #A
14、 (1)A (2) (3) (3)9B (4)B (5) (6)aade#的分析过程如下分析栈 输入流 动作A# aade# 替换(1)aA # aade# 匹配A # ade# 替换(2)ABe# ade# 替换(1)aABe# ade# 匹配ABe# de# 替换(3)Be# de# 替换(4)dBe# de# 匹配Be# e# 替换e# e# 匹配# # 成功10第五章（这章答案是错的）1. 设有下列文法：(1) SaAAAbAb(2) SaSSbSaSSSSc(3) SASSbASAAa(4) ScASccBBccBBbAcAAa构造上述文法的 LR(0)归约活前缀状态机，并给出 LR(0)分析表。答：(1)Z . SS . a AA . A bA . bSZ S .0 1S a . AA . A bA . ba2A b .3bAS a A .A A . b4bA A b .5C h 0 5 - 1 - ( 1 )有移入 、 规约冲突(2)11C h 0 5 - 1 - ( 2 )Z . SS . a S S bS . a S S SS . caS a . S S bS a . S S SS . cS . a S S bS . a
