最新编译原理课后习题答案

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

2、时参与才能运行，其不产生可执行程序文 件，效率低，执行速度慢。精品文档尺N zzfe 弟早1 .乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？答：1) 0型文法、1型文法、2型文法、3型文法。2)2 .写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。答：Z SME|BS 1|2|3|4|5|6|7|8|9M |D|MDD 0|SB 2|4|6|8E 0|B3 .设文法G为：N D|NDD 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。答：N ND N3 ND3 N23 D23 123N ND N

3、DD DDD 1DD 12D 123N ND N1 ND1 N01D01 301N ND NDD DDD 3DD 30D 301N ND N1 ND1 N31 ND31 N431 ND431N5431D54317543175431N ND NDD NDDD NDDDD DDDDD 7DDDD 75DDD 754DD 7543D4 .证明文法 S iSeS|iS| i是二义性文法。答：对于句型iiSeS存在两个不同的最左推导:S iSeS iiSesS iS iiSeS所以该文法是二义性文法。5 .给出描述下面语言的上下文无关文法。(1) L1=anbnci |n>=1,i>=0 (

4、2) L2=aibjj>=i>=1(3) L3=anbmcmdn |m,n>=0答：(1) S ABA aAb | abB cB |(2) S ASb |ab精品文档A a |(3) S aSd | A |A bAc |6 .设计一个最简的 DFA M,使其能够识别所有的被 3整除的无符号十进制整数。 答：2|5|80|3|6|90|3|6|91|4|71|4|72|5|80|3|6|91|4|77 .设计一个DFA使其能够接受被4整除的二进制数。8 .写出表达下列各项的正则表达式。(1)二进制数且为 5的倍数。(2) 2 =a,b,c,第一个a位于第一个b之前的字符串。(3

5、) 2 =a,b,c,包含偶数个a的字符串。(4) 2=0, 1,不包含11子用的字符串。(D可以先画出相应的有限自动机：100101BDE1010添加新的开始状态S和终止状态T:1根据以上自动机，列出以下方程：S=A A=0A+1B+T B=0C+1D C=0E+1A D=0B+1C E=0D+1E解以上方程组： E=1*0D A=0*1B+6T代入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+yAf弋入上式

6、B=uB+vAB=u vA其中 u=(10) *(0|11)x v=(10)*(0|11)y将 B=iivA 代入 A=0*1u*vA+dTA=(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| )尺K*弟二早TOKEN同时检查源程1 .词法分析器的功能是什么?答：读源程序的字符序列，逐个拼出单词，

7、并构造相应的内部表示 序中的词法错误。2 .试分析分隔符(空格、跳格及回车等)对词法分析的影响。答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用 于错误定位，所以在删除回车符号前需要统计回车的个数。3 .给出识别C语言全部实型常数的自动机。答：(+|-1 )(1-90-9*|0)(.0-90-9*|) (E(+|-| )0-90-9*)4 .写出识别C语言中所有单词的 LEX程序。答：L=A-Z | a-zD=0-9D1=1-9%(LL)(L|D|_)* return ;D1D*return (2);+return (3);精品文档精品文档第四章1.设有如下文法G

8、S: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)=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,gLL文法。Predict(C )=g,b(2)由于Predict(A ASd) Predict(A ),所以该文法不

9、是2 .下列描述括号匹配的文法中，哪些是LL文法？(1) S (SS' |S' ) |(2) S (S)S |(3) S S(S)S |(4) S (S | S 'S' (S' ) |答：(1)不是，(2)是，(3)不是，(4)不是3 .已知文法 GE:E E+T | TT T*F | FF i | (E)请按递归下降法构造该文法的语法分析程序。答：求产生式的predict集合：predict(E E+T)=i,(predict(E T)=i,(predict" T*F)=i,(predict(T F)=i,(由于文法中非终极符号E 和 T 对

10、应的产生式的predict 集合的交集都不为空，法不满足自顶向下分析的条件，现对文法进行等价变换得到如下文法：E TEE +TE|T FTT *FT |FiF (E)求新文法的predict 集合：Predict(ETE )=(,iPredict(E+TE )=+Predict(E )=#,)Predict(TFT )=i,(Predict(T*FT )=*Predict(T )=+,),#Predict(F i)=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(token i,() F();T ();else Error();void T () if(token *) Matc h( * );F();T ();else if(token +,),#) ;else Error();void F() if(token i) Match( i );else if(token () Match( (

12、 );E();Match( ) ); else Error();4 .构造一个LL(1)文法G,它能识别语言L:L= | 为字母表上不包括两个相邻的1 的非空串，其中=0， 1。并证明你所构造的文法是LL(1)文法。答：A 0E | 1FB 0E | 1FC 0EE B IF C IPredict(A 0E)=0Predict(A 1F尸1Predict(B 0E)=0Predict(B 1F尸1Predict(E B尸0,1Predict(E )=#Predict(F C)=0Predict(F )=#对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文法。

13、5 .已知文法 GA为:A aABe|aB Bb | d(1)试给出与GA等价的LL文法G' A(2)构造G'简LL(1汾析表并给出输入串aade#的分析过程。答：所求G A的:AaA'(1)AABe(2)A(3)BdB'(4)B'bB'(5)B'(6)Predict(A aA' )=aPredict(A ABe)=aPredict(A ' )=#,dPredict(B dB' )=dPredict(B bB' )=bPredict(B ' )=e对任意非终极符号对应的产生式的predict集合的交

14、集都为空，所以该文法是LL(1)文法。(3)分析表如下:abde#A(1)A(2)(3)(3)精品文档B(4)B，(5)(6)aade#的分析过程如下分析栈输入流动作A#aade#替换aA' #aade#匹配A #ade#替换(2)ABe#ade#替换aABe#ade#匹配A Be#de#替换Be#de#替换(4)dB' e#de#匹配B' e#e#替换e#e#匹配#成功精品文档第五章(这章答案是错的)1 .设有下列文法：(1) S aAA AbA b(2) S aSSbS aSSSS c(3) S ASS bA SAA a(4) S cAS ccBB ccBB bA

15、cAA a构造上述文法的LR(0)归约活前缀状态机，并给出LR(0)分析表。答：(1)Ch05-1-(1)有移入、规约冲突(2)Ch05-1-(2)Zf .S (1)S .aSSb (2)S .aSSS (3)S7 .c(4)actiongotoabc#SS0s2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3有移入、规约冲突Ch05-1-(3)Zf S- cA (2)S- ccB (3)B- ccB (4)B- b (5) 2 cA (6) A a (7)actiongotoabc#ABSS0s12S1s3s54S21

16、AccS3R7R7R7R7S4 R6R6R6R6S5s3s9s876S6R3R3R3R3S7 1R2R2R2R2S8s3s107S9R5R5R5R5S10：s3s9s87r iiS11R4R4R4R42.设有下列文法:(1) S SaS | b(2) S bSb | cSc | b | c(3) S bSb | bSc | d(4) S aSb | bSa | ab(5) S Sab | bRR S | a(6) S SAB | BA B bA aA | B S AaAb | BbBaBA(8) A aABe | BaB dB |说明上述文法是否为SLR(1反法。若是，请构造SLR(1分析表；

17、若不是，请说明理由。答：(1)Ch05-2-(1)不是 SLR (1)(2)Ch05-2-(2)不是 slr (1)Follow(S)=#,b,c-bZf.SS7 .bSbS7.cScSf.bSf.crS b.Sb Sf b.Sf .bSbS7 .cScSf .bSf .cCh05-2-(3) 是 SLR (1)3_S 一 d.1d 2Sf b.SbSf b.ScS- .bSbS 一 .bScS 一 .d5 S- bSb.b4 Sf bS.b Sf bS.ccZf .S (1)S7 .bSb (2)S7 .bSc (3)S7 .d (4)actiongotobcd#SS0s2s31S1AccS

18、2s2s3Ch05-2-7 4S3r R4R4R4S4s5s6S5R2R2R2S6R3R3R36 S- bSc.Ch05-2-(4)不是 SLR( 1)Follow(S)=#,a,b-b-4S- aSb.(5)Ch05-2-(5)不是slr(i)Follow(R)=#,a(6)0Zf.S S .SAB Sf .BA Bf .b|b>Ch05-2-(6) 是SLR (1)SJ卡1Zf S.S S.ABZ .aAZ .B3一 a3S B.AZ .aA-B->Z .BBf .ba-5Af B.Bf .b-A-S1189S SA.BS SAB.IBBf .b5一 Z 2B4S- BA.Af

19、 a.AAf .aAAf .BBf .bAT7 A-aA.Z-S A SAB (2) A BA (3) A- aA (4) A- B (5) B- b (6)actiongotoab#ABSS01s231S1s6s2Acc85S2R6R6R6Ch05-2-7S31s6s245S4R3R3R3S5R5R5R5S61s6s275S7R4R4R4S8s29S9R2R2R2Ch05-2- 不是 SLR ( 1)Follow(A)=a,b Follow(B)=a,b0- ZSSf .AaAb Sf .BbBa 2.1-SZ Zf s.4TSf A.aAb-a-3Sf Aa.Ab A一.68Sf AaA.

20、bSf AaAb.ATBf.BTSf B.bBa-b->Sf Bb.Ba B 一.7-o9Sf BbB.aSf BbBa.BT(8)Ch05-2-(8)不是 SLR (1) Follow(B尸a,e3 .设有下列文法：S aAd | bBd | aBe | bAeA gB g说明该文法是 LR(1)文法，1不是LALR(1)文法。答：Ch05-3是LR文法0 ZfS Sf.aAd SfbBd Sf.aBe SfbAe#-a-5Sfa.Ad Sfa.Be Afg BfgZfS.3 Sfb.Bd Sfb.Ae Afg Bfg# # e d4SfaA.d#-At5SfaB.e#-Bt6A>

21、;g.db>g.e9SfbA.e#一At10S-bB.d #-Bf11 g A-g.B-g.7S-aAd.#-d-i8S-aBe.#一g12| SfbAe.#-e-d-J13 S-bBd.#Ch05-3不是LALR文法4 .设有下列文法：(1) E E+T | TT TF | TF (E) | F* | a | b(2) S Aa | bAc | dc | bda A d说明上述文法是否为SLR(1区法？是否为LALR(1戌法？并构造相应的分析表。答：Ch05-4-(1)不是 SLR文法Follow(T)=#,(,a,b,+,)F-(E).卜)Zf.E ef.e+t ef.t TfTF

22、TfTEt1 ZfE.efe.+tEfE+.T* T f .TFT f .T"T+-T-j3E-E+T.TfT.F TfT.F f(E) F f .F* Ff.a Ff.b -rr 8T-TF. F-F.*-a F-a.7Ffb.1110F-(E.)Le-efe.+tf-(.e) ef.e+t ef.t TfTF TfT-TEfT.TfT.F TfT. Ff(E) Ff.F* Ff.a Ff.b5- F f F*-F<J J-a<-6n1Z fe.efe.+t#+f,e0Zf.e ef.e+t ef.t TfTF Tf.T#+#+#+(ab#+(abCh05-4-(1)不

23、是LALR(1)文法2efe+.t#+(ab*)T一>.TF#+(abT一>.T#+(ab+9F-(E.) efe.+t#+(ab*)#+(ab*),10F-(E).#+(ab*)E3ef e+t.#+TfT.F#+(abT f T.#+(abFf(E)#+(ab* -F fF*#+(ab*F f.a#+(ab* 'F fb#+(ab*工18f-(.e)#+(ab*)ef.e+t#+(ab*)Ef.T#+(ab*)T f .TF#+(ab*)T f .T#+(ab*)5F-F*.#+(ab*J,*4T-TF.F -F.*#+(ab#+(ab*Ft6Fa.#+(ab*7F f

24、b.#+(ab*11e f t.#+(ab*)TfT.F#+(ab*)T f T.#+(ab*)F-.(E)#+(ab*)Ff.F*#+(ab*)Ff .a#+(ab*)Ff.b#+(ab*)-Tt(2)Ch05-4-(2)不是 SLR(1)文法 Follow(A)=a,cCh05-4-(2) 是 LALR(1)文法ZSr#TSr"0 zf .sr#SAa.r#-Ta4-At S-A.aSf.AaSf.bAcSf.dcSf.bdaA f.d# # # a6S-b.AcSfb.daAf.d9SfbA.cSfd.c Afd.7 S-bd.a A fd.S- bAc. #S dc.S-bd

25、a.Z. .S(1)Sf .Aa (2)Sf .bAc (3)Sf .dc(4)Sf .bda (5)Af.d(6)actiongotoabcd#ASS0s6s241S1AccS2R6s3S3R4S4s5S5R2S6s79S7s8R6S8R5S9s10S10R35 .设有下列文法：L MLb | aM说明上述文法是否为 LR(1)文法，若不是，请说明理由。答：Ch05-5 是 LR(1)文法精品文档精品文档第六章1. 试写出下列类型的内部表示：egerb.ARRAY1.5 of RECORDi:integer; b:boolean ENDc.ARRAY1.5 of RECORDa:A

26、RRAY1.10; r: RECORDi,j:integer END ENDd. RECORDr: RECORDx,y:real END;a: ARRAY1.10 of integer END2 .设当前层数为l,可用区距为101,且有下列程序段：CONST mm=333； nn=444；TYPE atype =ARRAY1.10 OF real;rtype = RECORDi,j:integer END;VAR a,b:atype;x,y:real试写出各标识符的内部表示。3 .设当前层数和区距分别为l和off,且有函数说明首部：FUNCTION f（ A： atype； VAR B： at

27、ype； VAR X： real） ： integer其中 atype 的定义见题5，试写出f 的内部表示。4 . 要求在下面括号中写上相应?（层数）和区距（off） 。（）（）PROCEDURE （g A： atype； （）（）VAR B： atype； （）（）VAR X： real （）（） （）（）.5 .给出下面C程序扫描到语句 c=a+b+x时相应的全局符号表（采用顺序表结构）。main（）int a=0;float c=1.0;float a=3.0;float x=1.3;float b=0.3;int b=10;c=a+b+x;）。6 .给出题1中程序扫描到语句 c=a+b

28、+x时相应的全局符号表（采用外拉链的散列表结构7 . 根据标识符的作用域规则，分别给出图6.5 的程序中，过程P、 Q、 R、 S 中有效的标识符。精品文档第七章1 .将算术表达式(a+b)*(c+d)-(a+b+c)翻译成四元式序列。2 .将下列语句翻译成四元式序列：a. IF x>0 THEN x:=0 ELSE x:=1b. WHILE x>0 DO x:=x-1c. IF x>0 THEN x:=x+1 ELSEIF x <0 THEN x:=x+1 ELSE x:=x+1d. WHILE x > 0 DOWHILE y > 0 DOBEGIN y:

29、=y-x; x:=x-1 END3 .给出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A: Array of 1.10of integer。a:=1;while a<=10 dobegin if a<>b thenAa:=Ab+2;else a:=a+1;b:=b+1; end4 .试将FOR语句翻译成四元式序列。5 .试将UNTIL语句翻译成四元式序列。6 .试将CASE语句翻译成四元式序列。7 .试给出4、5、6题中翻译过程的语法制导程序。精品文档精品文档第八章I .将下面的程序段划分为基本块并画出其程序流图。read(A);read(B);F:=1;C:

30、=A*A;D:=B*B;if C<D goto L1;E:=A*A;F:=F+1;E:=E+F;write(E);goto L3;II : E:=B*B;F:=F+2;write(E);if E>100 goto L2;goto L3;L2: F:=F-1;goto L1;L3: write(E);2 .假设有如下语句序列，写出常表达式优化前和优化后的四元式中间代码。(1) i:=1;(2) a:=20;j:=i*(i+1);b:=a*(a+10);k:=2*(i+j);c:=a*b;3 .假设有如下语句序列或表达式，写出公共表达式优化前和优化后的四元式中间代码。(1) x:=x*

31、y+z; y:=x*y+z; z:=x*y+z;(2) (a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)4 .写出如下循环语句不变式外提后的四元式中间代码。while i<=100 dobegin u:=A*B;m:=u*u;S:=S+m*m;i:=i+1;1.10。end5 .写出下面循环语句不变式外提后的四元式中间代码，其中数组各下标的类型为while i<=100 dobegin j:=1;while j<=100 do精品文档endbegin k:=1;while k<=100 doAijk:=0;end第九章1 .过程活动记录包含哪些信息？各信息的作用？何时填写它们？2 .下面是一个调用递归函数的 Pascal程序program PP(input,output)VAR k:integer;FUNCTION F(n:integer):integerbeginif n<=0 then F:=1else F:=n*F(n-1);end;begink:=F(10); end.当第二次(递归地)进入 F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？3 .对于下面的程序：procedure P