(完整word版)编译原理题库(word文档良心出品).pdf-淘文阁

资源描述

《(完整word版)编译原理题库(word文档良心出品).pdf》由会员分享，可在线阅读，更多相关《(完整word版)编译原理题库(word文档良心出品).pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Tianges reference 1 第一章什么是编译器？编译程序的结构分为几个阶段，各阶段的任务是什么？遍、编译前端及编译后端的含义？编译程序的生成方式有哪些？第二章1.写一文法，使其语言是偶正整数的集合。要求：（1）允许 0 打头（2）不允许 0 打头解：（1）允许 0 开头的偶正整数集合的文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8（2）不允许0 开头的偶正整数集合的文法 E NT|D TFT|G N D|1|3|5|7|9 D 2|4|6|8 FN|0 G D|0 2.证明下述文法G 表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+

3、0n|n，m=0 S 1S0|A A 0A1|第三章1、构造一个DFA，它接收=a,b 上所有满足下述条件的字符串：字符串中的每个a 都有至少一个b 直接跟在其右边。解：已知=a,b，根据题意得出相应的的正规式为：(b*abb*)*根据正规式画出相应的DFA M，如下图所示用子集法将其确定化I Ia Ib X,1,2,3,Y 4 2,3 4 5,6,1,2,3,Y 2,3 4 2,3 5,6,1,2,3,Y 4 6,1,2,3,Y 6,1,2,3,Y 4 6,1,2,3,Y 由 DFA得状态图用最小化方法化简得：0，1，2，3,4，按顺序重新命名DFA M 第四章练习 1：文法 GV：VN|N

4、E EV|V+E N i 是否为 LL(1)文法，如不是，如何将其改造成LL(1)文法。解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而GV中含有回溯，所以先消I Ia Ib 0 1 2 1 3 2 1 2 3 1 4 4 1 4 X Y(b*abb*)*X Y b*abb*1 X Y b 1 2 3 4 5 6 b b a 1 0 2 4 3 a a a a b b b b b 0 3 1 2 a a a b b b Tianges reference 3 除回溯得到文法G V：G V：VNV V|E EVE E|+E N i 由 LL(1)文法的充要条件可证G V 是 LL

6、ST(A)加入 FOLLOW(B),即 FOLLOW(B)=a,b,c,d;对 ABS有：FIRST(S)加入 FOLLOW(B),即 FOLLOW(B)=a,b,c,d;对 BaA 有：FOLLOW(B)加入 FOLLOW(A),即 FOLLOW(A)=a,b,c,d;对 BbS 有：FOLLOW(B)加入 FOLLOW(S),即 FOLLOW(S)=#,a,b,c,d;由 ABS|d 得：FIRST(BS)FIRST(d)=a,b,c d=;由 BaA|bS|c得：FIRST(aA)FIRST(bS)FIRST(c)=a b c=。由于文法Gs 不存在形如的产生式，故无需求解形如FIRST

7、()FOLLOW(A)的值。也即，文法GS 是一个 LL(1)文法。(2)由 Gs:S BA A BS|d BaA|bS|c 的FIRST(B)=a,b,c;FOLLOW(B)=a,b,c,d;FIRST(A)=a,b,c,d;FOLLOW(A)=a,b,c,d;FIRST(S)=a,b,c。FOLLOW(S)=#,a,b,c,d 可构造 LL(1)预测分析表如下：a b c d#S SBA SBA SBA A ABS ABS ABS Ad B BaA BbS Bc S SBA SBA SBA A ABS ABS ABS Ad B BaA BbS Bc Tianges reference 4(

8、3)在分析表的控制下，句子adccd 的分析过程如下：第五章1 已知文法GS 为：Sa|(T)TT,S|S (1)计算 GS的 FIRSTVT和 LASTVT。(2)构造 GS的算符优先关系表并说明GS 是否为算符优先文法。(3)给出输入串 (a,(a,a)#的算符优先分析过程。解：文法：Sa|(T)T T,S|S 展开为：Sa SS(T)TT,S TS(1)FIRSTVT-LASTVT表非终结符FIRSTVT集LASTVT集S a (a )T a (,a ),(2)算符优先关系表如下:表中无多重入口所以是算符优先（OPG）文法。a(),#a(),#栈当前输入符号输入串说明#Sadccd#SB

9、A#ABadccd#BaA#AAaadccd#AAdccd#Ad#Addccd#Accd#ABS#SBccd#Bc#Scccd#Scd#SBA#ABcd#Bc#Accd#Ad#Ad#dd#分析成功Tianges reference 5(3)输入串（a,(a,a)）#的算符优先分析过程为：栈当前字符剩余输入串动作#(#(a#(N#(N,#(N,(#(N,(a#(N,(N#(N,(N,#(N,(N,a#(N,(N,N#(N,(N#(N,(N)#(N,N#(N#(N)#N(a,(a,a)#a,(a,a)#,(a,a)#(a,a)#(a,a)#a,a)#,a)#a)#a)#)#)#)#)#Move

10、 in Move in Reduce:S a Move in Move in Move in Reduce:S a Move in Move in Reduce:S a Reduce:T T,S Move in Reduce:S(T)Reduce:T T,S Move in Reduce:S(T)第六章例 1：有文法：S(L)|a LL,S|S 给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子(a,(a,a)，输出是2。解：加入新开始符号S 和产生式S S，设 num 为综合属性，代表值属性，则语法制导定义如下：产生式语义规则 SS print(

11、S.num)S(L)S.num:=L.num+1 S a S.num:=0 L L1,S L.num:=L1.num+S.num L S L.num:=S.num 例 2：构造属性文法，能对下面的文法，只利用综合属性获得类型信息。D L,id|L L T id T int|real 解：属性文法（语法制导）定义：产生式语义规则 D L,id D.type:=L.type addtype(id.entry,L.type)D L D.type:=L.type L T id L.type:=T.type addtype(id.entry,T.type)T int T.type:=integer T

12、real T.type:=real Tianges reference 6 第七章例 1：给出下面表达式的逆波兰表示(后缀式)：(1)a*(-b+c)(2)if(x+y)*z=0 then s:=(a+b)*c else s:=a*b*c 解：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else 运算）例 2：请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。解：三元式间接三元式 (1)(+a,b)间接三元式序列间接码表 (2)(+c,d)(1)(+a,b)(1)(3)(*(1),(2)(2)(+c,

13、d)(2)(4)(-(3),/)(3)(*(1),(2)(3)(5)(+a,b)(4)(-(3),/)(4)(6)(-(4),(5)(5)(-(4),(1)(1)(5)四元式 (1)(+,a,b,t1)(2)(+,c,d,t2)(3)(*,t1,t2,t3)(4)(-,t3,/,t4)(5)(+,a,b,t5)(6)(-,t4,t5,t6)例 3：请将下列语句 while(AD)then X:=Y+Z 翻译成四元式解：假定翻译的四元式序列从（100）开始：（100）if AD goto（104）（103）goto（100）（104）T=Y+Z（105）X=T（106）goto（100）（107

14、）例 4：写出 for 语句的翻译方案解：产生式动作S for E do S1 S.begin:=newlabel S.first:=newtemp S.last:=newtemp S.curr:=newtemp S.code:=gen(S.first“:=”E.init)|gen(S.last“:=”E.final)Tianges reference 7|gen(“if”S.first“”S.last“goto”S.next)|gen(S.curr“:=”S.first)|gen(S.begin“:”)|gen(“if”S.curr“”S.Last“goto”S.next)|S1.code|

15、gen(S.curr:=succ(S.curr)|gen(“goto”S.begin)E v:=initial to final E.init:=initial.place E.final:=final.place 第八章例 1：C语言中规定变量标识符的定义可分为extern,extern static,auto,local static和 register五种存储类：(1)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的内存分配方式。(3)符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解：(1)extern 定义的变量，其作用域是整个C 语言程序

16、。extern static 定义的变量，其作用域是该定义所在的C 程序文件。auto 定义的变量，其作用域是该定义所在的例程。local static 定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。register 定义的变量，其作用域与auto 定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2)对 extern 变量，设置一个全局的静态公共区进行分配。对 extern static 变量，为每个C 程序文件，分别设置一个局部静态公共区进行分配。对 auto 和 register 变量，设定它们在该例程的动态区中的相对区头的

17、位移量。而例程动态区在运行时再做动态分配。对 local static 变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3)实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。第九章例 1：下面的程序执行时，输出的a 分别是什么？若参数的传递办法分别为(1)传名；(2)传地址；(3)得结果；4)传值。program main(input,output);procedure p(x,y,z);begin y=y+1;z=z+x;end;begin a=2;b=3;p(a+b,a,a);print a Tianges reference 8 end.解：(1)参

18、数的传递办法为“传名”时，a 为 9。(2)参数的传递办法为“传地址”，a 为 8。(3)参数的传递办法为“得结果”，a 为 7。(4)参数的传递办法为“传值”，a 为 2。例 2：过程参数的传递方式有几种？简述“传地址”和“传值”的实现原理。解：参数的传递方式有下述几种：传值，传地址，传名，得结果“传值”方式，这是最简单的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。2.调用过程计算实参的值，并将它们的右值（r-value）放在为形式单元开

19、辟的空间中。3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。“传地址”方式，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。1.如实参是一个名字或是具有左值的表达式，则左值本身传递过去。2.如实参是一个表达式，比方a+b 或 2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。例 3：下面是一个Pascal 程序program PP(input,output)var K:integer;function F(N:integer):integer

20、begin if N=0 then F:=1 else F:=N*F(N-1);end;begin K:=F(10);.end;当第二次（递归地）进入F 后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？解：Tianges reference 9 第十章例 1：何谓代码优化？进行优化所需要的基础是什么？解：对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。例 2：编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？解：依据优化所涉及的程序范围，可以分为：局

21、部优化、循环优化和全局优化。最常用的代码优化技术有1.删除多余运算2.代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播 6.删除无用赋值例 3：试对以下基本块B2：B：=3 D：=A+C E：=A*C F：=D+E G：=B*F H：=A+C I：=A*C J：=H+I K：=B*5 L：=K+J M：=L 应用 DAG 对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G、L、M 在基本块后面还要被引用。（2）假设只有L 在基本块后面还要被引用。解：基本块对应的DAG 如下：B：=3 D：=A+C E：=A*C F：=D+E G：=B*F H：=A+C

22、 I：=A*C J：=H+I K：=B*5 L：=K+J M：=L 例 1 一个编译程序的代码生成要着重考虑哪些问题?解：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。课后习题答案：P36-6(1)L G()1是 09 组成的数字串(2)最左推导:Tianges reference 10 NNDNDDNDDDDDDDDDDDDDNNDDDDNNDNDDDDDDDD0010120127334556568最右推导:NNDNNDNNDNDNNDNDNNDNNDND77272712712701274434886868568P36-8 文法：

23、ET ET ETTF TF TFFE i|*|/()|最左推导:EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii*()*()*()*()*()*()*()最右推导:EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii*()*()*()*()*()*()*()*()语法树：/*EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*iP36-9 句子 iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeii

24、iieiP647(1)1 01 101(|)*X Y Tianges reference 11 0 1 1 0 1 1 确定化：0 1 X 1,2,3 1,2,3 2,3 2,3,4 2,3 2,3 2,3,4 2,3,4 2,3,5 2,3,4 2,3,5 2,3 2,3,4,Y 2,3,4,Y 2,3,5 2,3,4 0 1 0 0 0 1 1 0 0 1 0 1 1 1 最小化：,012 3 4 56012 3 4 5135012 34 512 4 6012 3 456012 3 41 35012 3456012 31010030 12 31 2 4012 3456011011 22 3

25、32 34012345610101,0 1 0 0 1 0 0 1 0 1 1 1 X 1 2 3 4 Y 5 6 0 1 2 3 5 4 5 0 1 2 4 3 Tianges reference 12 P6412(a)a a,b a 确定化：a b 0 0,1 1 0,1 0,1 1 1 0 给状态编号：a b 0 1 2 1 1 2 2 0 3 3 3 3 a a a b b b b a 最小化：,012 30110122 30 32 330123abab a a b b a b 0 1 2 3 0 1 2 0 1 Tianges reference 13(b)b b a a b a a

26、 b b a a a 已经确定化了,进行最小化最小化：,0 12 3 4 50 110 12 42 3 4 51 3 0 52 3 4 52 3 4 52 41 02 43 53 53 53 52 40 12 43 50 110 12 42 4,abababababa,1 02 43 53 53 53 52 4bab b b a a b a P811(1)按照 T,S 的顺序消除左递归|,)(|)(TSTTSTTaSSG递归子程序：procedure S;begin if sym=a or sym=then abvance else if sym=(then begin advance;T;i

27、f sym=)then advance;else error;end else error 0 2 3 1 4 5 0 1 2 Tianges reference 14 end;procedure T;begin S;Tend;procedure T;begin if sym=,then begin advance;S;Tend end;其中:sym:是输入串指针IP 所指的符号advance:是把 IP 调至下一个输入符号error:是出错诊察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST(T)=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(T)=)预

28、测分析表a (),#S SaSST()T TSTTSTTSTTTTST,是 LL(1)文法P812 文法：|)(|*|baEPFFFPFTTTFTEEETETianges reference 15(1)FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=(,a,b,+,),#FOLL

29、OW(P)=*,(,a,b,+,),#(2)考虑下列产生式:EETTFFPEa b|*|()|FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a)FIRST(b)FIRST()=所以,该文法式LL(1)文法.(3)+*()a b#E ETE ETE ETE ETE E EEEET TFTTFTTFTTFTT TTTTTTTT

30、TTTF FPFFPFFPFFPFF FFF*FFFFFFP PE()PaPbP(4)procedure E;begin Tianges reference 16 if sym=(or sym=a or sym=b or sym=then begin T;E end else error end procedure E;begin if sym=+then begin advance;E end else if sym)and sym#then error end procedure T;begin if sym=(or sym=a or sym=b or sym=then begin F;T

31、 end else error end procedure T;begin if sym=(or sym=a or sym=b or sym=then T else if sym=*then error end procedure F;begin if sym=(or sym=a or sym=b or sym=then begin P;F end else error end procedure F;begin if sym=*then begin advance;F end end procedure P;begin if sym=a or sym=b or sym=then advanc

32、e else if sym=(then Tianges reference 17 begin advance;E;if sym=)then advance else error end else error end;P1331 EETETF*短语:E+T*F,T*F,直接短语:T*F 句柄:T*F P1332 文法：SaTTT S S|(),|(1)最左推导:STT SS Sa SaTaT SaS Saa Saa aST SS STST S ST S S SS S S STS S ST S S SSS S S S Sa S()(,)(,)(,)(,()(,(,)(,(,)(,(,)(,(,)(

33、,)(,)(),)(,),)(,),)(,),)(),),)(,),),)(,),),)(,),),)(,),),)(,),),)(,),(),)(,),(),)(,),(),)(,),(),)S SSa aS S Sa aSSa aTSa aSSa aaSa aaa最右推导:STT STTTT STT aTS aTa aS a aaa aST ST aS aTaT S aTTaTSaTaaT S aaTaa()(,)(,()(,(,)(,(,)(,(,)(,(,)(,(,)(,(,)(,)(,)(,)(),)(,),)(,(),)(,(),)(,(),)(,(),)(,(),)(,(),)(

34、),(),)(,),(),)(,),(),)(,),(),)(,),(),)SaaTaaT SaaT aaaS aaaa aaa(2)(a,a),(a),a)(S,a),(a),a)(T,a),(a),a)(T,S),(a),a)(T),(a),a)(S,(a),a)(T,(a),a)(T,S,(a),a)(T,(a),a)(T,(S),a)(T,(T),a)(T,S),a)(T),a)Tianges reference 18(S,a)(T,S)(T)S“移进-归约”过程：步骤栈输入串动作0#(a,a),(a),a)#预备1#(a,a),(a),a)#进2#(a,a),(a),a)#进3#(a

35、,a),(a),a)#进4#(a,a),(a),a)#进5#(S,a),(a),a)#归6#(T,a),(a),a)#归7#(T,a),(a),a)#进8#(T,a ),(a),a)#进9#(T,S ),(a),a)#归10#(T),(a),a)#归11#(T),(a),a)#进12#(S,(a),a)#归13#(T,(a),a)#归14#(T,(a),a)#进15#(T,(a),a)#进16#(T,S,(a),a)#归17#(T,(a),a)#归18#(T,(a),a)#进19#(T,(a),a)#进20#(T,(a ),a)#进21#(T,(S ),a)#归22#(T,(T ),a)#归2

36、3#(T,(T),a)#进24#(T,S),a)#归25#(T),a)#归26#(T),a)#进27#(S ,a)#归28#(T ,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T )#归33#(T)#进34#S#归Tianges reference 19 P1333(1)FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2)a (),a (=,6G是算符文法，并且是算符优先文法(3)优先函数a (),f 4 4 2 4 4 g 5 5 5 2 3 faff(f)f,gagg(g)g,（4）栈输入字符

37、串动作#（a,(a,a)）#预备#(a,(a,a)#进#(a ,(a,a)#进#(s ,(a,a)#归#(t ,(a,a)#归#（t,(a,a)）#进#（t,（a,a）#进#（t,（a,a）#进#（t,（s,a）#归#（t,（t,a）#归#（t,（t,a）#进#（t,（t,a）#进#（t,（t,s）#归#（t,（t）#归#（t,（t）#进#（t,s）#归Tianges reference 20#（t）#归#（t）#进#s#归P1641 答：表达式（4*7+1）*2 的附注语法树如下图：digit.lexval=2F.val=2E.val=58ndigit.lexval=4digit.lexva

38、l=7digit.lexval=1F.val=4F.val=7F.val=1T.val=4*T.val=28E.val=28+T.val=1E.val=1E.val=29()F.val=29T.val=29T.val=58*LTianges reference 21 P1642 答：(1)(2)P16511 答：（1）D id L D.type:=L.type；addtype(id.type,L.type)L,id L1L.type:=L1.type；addtype(id.type,L1.type)L :T L.type:=T.type T integer T.type:=integer T

39、real T.type:=real P2171 a*(-b+c)abc+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)abcd+*+A (C or not D)A not C D not or not or(A and B)or(not C or D)A B and C not D or or (A or B)and(C or not D and E)A B or C D not E and or and if (x+y)*z=0 then (a+b)c else ab c xy+z*0=ab+c abc￥或 xy+z*0=P1 jez ab+c P2 jump abc P1

40、 P2 P2173-(a+b)*(c+d)-(a+b+c)的三元式序列:(1)+,a,b(2),(1),-(3)+,c,d(4)*,(2),(3)(5)+,a,b(6)+,(5),c(7)-,(4),(6)a b+a b+Tianges reference 22 间接三元式序列:三元式表：(1)+,a,b(2),(1),-(3)+,c,d(4)*,(2),(3)(5)+,(1),c(6)-,(4),(5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1)+,a,b,1T(2),1T,-,2T(3)+,c,d,3T(4)*,2T,3T,4T(5)+,a,b,5T(6)+,5T

41、,c,6T(7)-,4T,6T,7TP2187 100.(j,A,C,102)101.(j,-,-,0)102.(j,B,D,104)103.(j,-,-,101)104.(j=,A,1,106)105.(j,-,-,109)106.(+,C,1,T1)107.(:=,T1,-,C)108.(j,-,-,100)109.(j,A,D,111)110.(j,-,-,100)111.(+,A,2,T2)112.(:=,T2,-,A)113.(j,-,-,109)114.(j,-,-100)P2709(1)9 (2)8 (3)7 (4)2 Tianges reference 23 P 3061:re

42、ad C A:=0 B1 B1 B:=1-L1:A:=A+B if B C goto L2 B2-B2 B:=B+1 goto L1 B3-L2:write A halt B4 B3基本块为B1、B2、B3、B4程序流图如右：B4P 3062:read A,B F:=1 C:=A*A B1 D:=B*B if C100 goto L2-halt B4-L2:F:=F-1 goto L1 B5BBBBBread C A:=0 B:=1 L1:A:=A+B if B C goto L2B:=B+1 goto L1L2:write A halt Tianges reference 24-基本块为B1、B2、B3、B4、B5程序流图如右：P307-4 B1 B2 B3 B2构成一个循环。进行循环优化后，得到：B1 B2B2 B3 I:=1 read J,K L:C:=A*B write C A:=A+K B:=B+J if AR goto L halt A:=K*I B:=J*I R:=K*100 I:=1 read J,K L:A:=K*I B:=J*I C:=A*B write C I:=I+1 if I100 goto L halt

展开阅读全文