完整版编译原理课后习题答案

1、第一章1典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、 中间代码优化、目标代码生成、错误处理、表格管理。2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方 式？答：编译法、解释法。4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执 行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不

2、产生可执行程序文 件，效率低，执行速度慢。17第早1. 乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？答：1)0型文法、1型文法、2型文法、3型文法。2)0为前导。2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以答：SME | B 1|2|3|4|5|6|7|8|9| D | MD0|S2|4|6|80|B3. 设文法G为：N D|NDD 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。答：N ND N3 ND3 N23D23123N ND NDD DDD 1DD 12D123N ND N1 ND1

3、N01D01301N ND NDD DDD 3DD 30D301N ND N1 ND1 N31 ND31 N431ND431N5431D54317543175431N ND NDD NDDD NDDDD DDDDD 7DDDD 75DDD 754DD7543D4. 证明文法 S iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导:S iSeS iiSesS iS iiSeS所以该文法是二义性文法。5. 给出描述下面语言的上下文无关文法。（1） L1=anbnci | n=1,i=0 （2）L2=abj|j=i=1（3）L3=anbmcmdn |m,n=0 答：（1

4、）S ABA aAb | abB cB |（2）S ASb |abA a |(3) S aSd | A |A bAc |6. 设计一个最简的 DFA M,使其能够识别所有的被3整除的无符号十进制整数。答：7. 设计一个DFA使其能够接受被4整除的二进制数。答：08. 写出表达下列各项的正则表达式。(1) 二进制数且为 5的倍数。(2) 2 =a,b,c,第一个a位于第一个b之前的字符串。(3) 2 =a,b,c,包含偶数个a的字符串。(4) 2 =0 , 1,不包含11子串的字符串。答：(1)可以先画出相应的有限自动机1根据以上自动机，列出以下方程： S=A A=0A+1B+T B=0C+1D

5、 C=0E+1A D=0B+1C E=0D+1E解以上方程组：E=1*0DA=0*1B+0T代入C=01*0D+1A代入C=01*00B+01*01C+1AC=xB+yA其中 x=(01 01) 01 00 y=(01 01) 1代入B=0C+10B+11CB=(0|11)C+10BB=(10) *(0|11)C将C=xB+yA弋入上式B=uB+vAB=u vA其中 u=(10) *(0|11)x v=(10)*(0|11)y将 B=UvA 代入 A=0*1u*vA+0T* * * *A=(0 1uv) 0T将 A代入S=(0*1u*v)*0*T串(0*1u*v)*0*即为所求。(2) 该题目

6、理解为：至少有一个 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| )AVV*第二早1词法分析器的功能是什么？答：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示TOKEN同时检查源程序中的词法错误。2. 试分析分隔符(空格、跳格及回车等)对词法分析的影响。答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用于错误定位，所以在删除回车符号前需要统计回车的个数。3. 给出识别C语言全部实型常数的自动机

7、。答：(+卜1 )(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|_)* return (1);D1D*return (2);+return (3);第四章1. 设有如下文法GS:S aABbcd |A ASd |B SAh|eC|C Sf | Cg |(1) 求每个产生式的Predict集。(2) 该文法是否为 LL(1)文法？为什么？答：Predict(S aABbcd)=aPredict(S)=#,d,f,a,h Predict(A ASd)

8、=a,dPredict(A)=h,a,d,b,ePredict(B SAh)=a,d,hPredict(B eC)=ePredict(B )=bPredict(C Sf)=a,fPredict(C Cg)=a,f,gPredict(C )=g,bLL（1）文 法。(2)由于Predict(A ASd) Predict(A )，所以该文法不是2. 下列描述括号匹配的文法中，哪些是LL(1)文法？(1) S (SS |S ) | S (S)S |(3) S S(S)S | S (S | SS (S)|答:（1）不是，（2）是，（3）不是，（4）不是3.已知文法GE:E E+T | TT T*F |

9、 FF i | (E)请按递归下降法构造该文法的语法分析程序。答:求产生式的predict 集合：predict(EE+T)=i,(predict(ET)=i,(predict(TT*F)=i,(predict(TF)=i,(由于文法中非终极符号E和T对应的产生式的predict集合的交集都不为空,法不满足自顶向下分析的条件，现对文法进行等价变换得到如下文法：E TEE +TE |T FTT *FT |FiF (E)求新文法的 predict 集合：Predict(ETE )=(,iPredict(E+TE )=+Predict(E)=#,)Predict(TFT )=i,(Predict(T

10、*FT )=*Predict(T)=+,),#Predict(F i)=iPredict(F (E)=(Void E() if(token (,i) T();Eelse Error();void E () if(token +) Match( else if(token #,) ; else Error();void T() if(token i,() F();Telse Error();void T () if(token *) Match(else if(token +,),#) ; else Error();void F() if(token i) Match( else if(toke

11、n () Match();+ );T();E ();();* );F();T ();i );();E();Match( ) );所以该文所以满足由于以上文法中任意非终极符号对应的产生式的 predict 集合的交集都为空， 自顶向下分析的条件，所以可以写出如下的递归下降语法分析伪代码：else Error();4.构造一个LL(1)文法G,它能识别语言L:L= | 为字母表 上不包括两个相邻的 1 的非空串 ，其中 =0， 1。 并证明你所构造的文法是LL(1)文法。答：A 0E|1FB 0E | 1FC 0EE B |F C |Predict(A 0E)=0Predict(A 1F)=1Pr

12、edict(B 0E)=0Predict(B 1F)=1Predict(E B)=0,1Predict(E )=#Predict(F C)=0Predict(F )=#对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文法。5. 已知文法 GA为：A aABe|aB Bb | d(1) 试给出与GA等价的LL文法G A(2) 构造G A的 LL(1)分析表并给出输入串aade#的分析过程。(1)所求G A为:A aA(1)A ABe(2)A(3)B dB(4)B bB(5)B(6)Predict(AaA )=aPredict(AABe)=aPredict(A)

13、=#,dPredict(BdB )=dPredict(BbB )=bPredict(B)=e对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文法。(3)分析表如下:abde#A(1)A(2)(3)(3)BBaade#的分析过程如下分析栈输入流动作A#aade#替换(1)aA #aade#匹配A #ade#替换ABe#ade#替换(1)aA Be#ade#匹配A Be#de#替换Be#de#替换dB e#de#匹配B e#e#替换e#e#匹配#成功第五章(这章答案是错的)1.设有下列文法：(1)SaAAAbAbSaSSbSaSSSScSASSbASAAaScA

14、SccBBccBBbAcAAa构造上述文法的LR(O)归约活前缀状态机，并给出LR(O )分析表。答：(1)Ch05-1-(1)有移入、规约冲突5 門 Af Ab.Ch05-1-(2)Z .S(1)S .aSSb (2)S .aSSS S .c (4)actio ngotoabc#SSOs2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3Ch05-1-(3)有移入、规约冲突ZS S cA S ccB B ccB B b (5) A cA A a (7)acti ongotoabc#ABSS0s12S1s3s54S2：Ac

15、cS3R7R7R7R7S4 :R6R6R6R6S5s3s9s876S6R3R3R3R3S7 :R2R2R2R2S8s3s107S9R5R5R5R5S10：s3s9s87r 11S11R4R4R4R4(1)SSaS | bSbSb|cSc|b | cSbSb|bSc|dSaSb | bSa | abSSab | bRRS | aSSAB | BABbAaA | BSAaAb | BbBa2.设有下列文法:B(8) A aABe | BaB dB |说明上述文法是否为SLR(1文法。若是，请构造 SLR(1分析表；若不是，请说明理由。答：(1)Ch05-2-(1)不是 SLR( 1)Follow(

16、S)=#,a34aS Sa.SS .SaSS .b-STEaS SaS.S S.aSbCh05-2-(2)不是 slr (1)Follow(S)=#,b,c0Z.S-bS .bSbSf .cScS .bS .c1S b.SbS b.S .bSbS .cScS .bS .c03Z .S-d5S d.S .bSb1S .bSc2S .dS b.SbSS b.Sc*1S .bSb1Z S.bS .bScS .d(1)Ch05-2-(3)是 SLR5S bSb.hb4OS bS.bSS bS.cc6S bSc.Z .S (1)S .bSb S .bSc S .d (4)actio ngotobcd#S

17、S0s2s31S1AccS2s2s3Ch05-2-7 4S3P R4R4R4S4s5s6S5R2R2R2S6R3R3R3Ch05-2-不是 SLR ( 1)Follow(S)=#,a,bCh05-2-(5)不是 SLR (1)Follow(R)=#,aS4 SAB 4 BA At aA At B (5)Bt b (6)actiongotoab#ABSS0s231S1s6s2Acc85S2R6R6R6-C105-2-/S3 :s6s245S4R3R3R3S5R5R5R5S6s6s275S7R4R4R4S8s29S9R2R2R2Ch05-2- 不是 SLR ( 1)Follow(A)=a,b Fo

18、llow(B)=a,bSt .AaAb4St BbBa-AT2St Aa Ab68o. dudciAt .St a.aAb-a-iAt .-ATSt AaA b-bJSt AaAb.-BTBt .5St B.bBa970 Zt .SSt Bb.BaBt .BTSt BbB.a-e St BbBa.(8)Ch05-2-(8) 不是 SLR (1) Follow(B)=a,e3.设有下列文法：S aAd | bBd | aBe | bAeA gB g说明该文法是 LR(1)文法，但不是LALR(1)文法。答：19Ch05-3是LR文法0Z t .s St .aAd St .bBdSt .aBe S

19、t .bAe#%sZ t s.#aT2St a.Ad#St a.Be#A t .gdB t .ge-B-3St b.Bd#St b.Ae#A t .geB t .gdA2St a.Ad#St a.Be#0A t .gdZt .S#-a-B t .geSt .aAd#St .bBd#St .aBe#St .bAe#-bp3Ch05-3不是LALR文法-BT# e dSt b.Bd St b.Ae A t .gBt .gS1 Zt s.St aA.d6Atg.dB t g.e5St aB.e #7St aAd.#-d-i8St aBe.#912St bA.e#诵| St bAe.#10dT11 A

20、 tg.eB t g.dSt bB.d I#4St aA.d#|-A彳5St aB.e#StaBe. I #6A t g. B t g.d, ee, dg.9-AT13St bBd.#7St aAd.#812St bAe.#1 101 13St bB.d#St bBd.#St bA.e#-BT294. 设有下列文法：(1) E E+T | TT TF | TF (E) | F* | a | b(2) S Aa | bAc | dc | bdaA d说明上述文法是否为 SLR(1)文法？是否为LALR(1)文法？并构造相应的分析表。答: (1)Ch05-4-(1)不是 SLR(1)文法 Foll

21、ow(T)=#,(,a,b,+,)Z .EE.E+TE.TT .TFT .T1 ZE.E E.+TE E+.T申 T .TFT .TT+T-j3 E E+T. TT.F TT. F .(E) F .F* F .a F .b4TTF.FF.*F b.11Ch05-4-(1)5 F F*.(*-r3F (.E)E .E+TE .T T .TF T .T100-9F (E).F(E.) E E.+TE不是LALR(1)文法Z E.E E.+T#+ -Z .E E .E+T E .TT.TF T.T# #+#+ #+(ab #+(ab2EE+.T T.TF T.T#+(ab*)#+(ab#+(ab7

22、LF (E.) E E.+T-TET.TT.F TT.F.(E)F.F*F.aF.b4 -0 THEN x:=0 ELSE x:=1b. WHILE x0 DO x:=x-1c. IF x0 THEN x:=x+1 ELSEIF x 0 DOWHILE y 0 DOBEGIN y:=y-x; x:=x-1 END3. 给出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A: Array of 1.10of integer。a:=1;while a=10 dobegi n if ab the nAa:=Ab+2;else a:=a+1;b:=b+1;end4. 试将FOR语句翻译成四元式序列。5. 试将UNTIL语句翻译成四元式序列。6. 试将CASE语句翻译成四元式序列。7. 试给出4、5、6题中翻译过程的语法制导程序。第八章1. 将下面的程序段划分为基本块并画出其程序流图。read(A);read(B);F:=1;C:=A*A;D:=B*B;if C100 goto L2;goto L3;L2: F:=F-1;goto L1;L