编译原理题库

1、第一章?什么就是编译器？?编译程序得结构分为几个阶段 , 各阶段得任务就是什么？?遍、编译前端及编译后端得含义？?编译程序得生成方式有哪些？第二章?1、 写一文法 , 使其语言就是偶正整数得集合。?要求 :(1) 允许 0 打头 (2) 不允许0 打头解:(1) 允许 0 开头得偶正整数集合得文法Et NT|DTt NT|DN tD|1|3|5|7|9Dt0|2|4|6|8(2) 不允许 0 开头得偶正整数集合得文法E t NT|DT t FT|GN t D|1|3|5|7|9D t 2|4|6|8F tN|0G tD|02、证明下述文法 G表达式就是二义得。表达式：=a|(表达式)| 表达式

2、运算符表达式运算符：=+|*|/解: 可为句子 a+a*a 构造两个不同得最右推导 :最右推导 1 表达式 表达式 运算符 表达式表达式 运算符 a表达式 * a表达式 运算符 表达式 * a表达式运算符 a * a表达式 + a * aa + a * a最右推导 2 表达式 表达式 运算符 表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符a表达式运算符表达式* a表达式运算符 a * a表达式+ a * aa + a * a3、给出生成下述语言得上下文无关文法 :(1) anbnambm| n,m>=0(2) 1n0m1m0n| n,m>=0解: (1) anbnam

3、bm| n,m>=0StAAAt aAb| e(2) 1nOm1m0n| n,m>=04 1S0|A at 0A1| £第三章1、构造一个DFA,它接收刀=a, b上所有满足下述条件得字符串 少一个b直接跟在其右边。解：已知刀=a, b,根据题意得出相应得得正规式为：(b*abb*)*根据正规式画出相应得用子集法将其确定化DFA M,如下图所示:字符串中得每个a都有至由DFA得状态图得:0,1,2,3,4,XXXa23(b*abb*)b*abb11b511b3aaabbblb6bIaIbrX,1,2,3,Y42,341_5,6,1,2,3,Y匚2,342,3L5,6,1,

4、2,3,Y46,1,2,3,Y6,1,2,3,Y46,1,2,3,Y用最小化方法化简 按顺序重新命名 DFA M第四章练习1:文法GV:V t N|NE Et V|V+E4IIaIb0121一3212314414就是否为LL(1)文法,如不就是，如何将其改造成LL(1)文法。解：LL(1)文法得基本条件就是不含左递归与回溯(公共左因子),而GV中含有回溯，所以先消除回溯得到文法G V:G ' V: V tNV V|EEtVE'E '|+ENt i由LL(1)文法得充要条件可证G V就是LL(1)文法练习2:有文法Gs:S t ba A t BS|d B t aA|bS|

5、c(1) 证明文法G就是LL(1)文法。 构造LL(1)分析表。(3) 写出句子adccd得分析过程解：(1) 一个LL(1)文法得充要条件就是：对每一个非终结符 A得任何两个不同产生式ATa |3,有下面得条件成立： FIRST( a ) A FIRST( 3 )=; 若 3 *s ,则有 FIRST( a ) A FOLLOW(A)对于文法Gs:St BAA t BS|d B t aA|bS|c其FIRST集如下：FIRST(B)=a, b, c; FIRST(A)=a, b, c, d; FIRST(S)=a, b, c。其FOLLOW!如下：首先，FOLLOW(S)=#;对 St BA

6、有：FIRST(A)s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;对 At BS有:FIRST(S) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;对 Bt aA 有:FOLLOW(B加入 FOLLOW(A),即 FOLLOW(A)=a, b, c, d ;对 Bt bS 有:FOLLOW(B加入 FOLLOW(S),即 FOLLOW(S)=#, a, b, c, d ;由 At BS|d 得：FIRST(BS)A FIRST(d) = a, b, c A d=;由 Bt aA|bS|c 得：FIRST(aA)A FIRST(bS

7、) A FIRST(c) =a A b A c=。由于文法Gs不存在形如3Ts得产生式，故无需求解形如 FIRST( a ) A FOLLOW(A得值。也即,文法GS就是一个LL(1)文法。(2) 由 Gs:S t baA t BS|d B t aA|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)预测分析表如下：abcd#SSt BASt BASt BAAAt BSAt BSat

8、 BSAt dBBt aABt bSBt cSSt BASt BASt BAAAt BSAt BSat BSAt dBBt aABt bSBt c(3)在分析表得控制下，句子adccd得分析过程如下栈当前输入符号输入串说明第五章Sadccd#St BA1已知文法GS为:adccd#Bt aA#AAa Al(T)Tt T,S|Sdccd#(1)#AB GS得 FIRSTVT与 LASTVTccd#ATd#构造GS得算符优先关系表并:说明GSCd#是否为算符优先文法。给？出输入、串(a,(a,§)#得算:符优先分析过程CAt BS解:ccd#Bf1#| A|(T) Tc t T,S|Sc

9、d#展开为Scd#St baRAS-5(T)d#Bf#Crst4sd#(1) F#RStVT 1 ASTVT dW#ATdJJ-u#dd#非终结符FIRSTVT 集LASTVT集分析诚功S a A ( a A)T a A ( , a A),(2)算符优先关系表如下：表中无多重入口所以就是算符优先(OPG)文法。aA()5#a>> >>A<<<>< >>fI<<<>><<<>>(3)输入串(a,(a,a)#得算符优先分析过程为栈当前字 符剩余输入串动作(a,(a,a)#M

10、ove in#(a,(a,a)#Move in#(a5(a,a)#Reduce: S t a#(N5(a,a)#Move in#(N,(a,a)#Move in#(N,(a,a)#Move in#(N,(a5a)#Reduce: S t a#(N,(N5a)#Move in#(N,(N,a)#Move in#(N,(N,a)#Reduce: S t a#(N,(N,N)#Reduce: T tT,S#(N,(N)#Move in#(N,(N)#Reduce: S t (T)#(N,N)#Reduce: T tT,S#(N)#Move inD t L,id | L L解：属性文法(语法制导)定义

11、： 产生式Dt L,id Daddtype(idDtLDLtt idLaddtype(idTtintTTtrealT第七章例1:给出下面表达式得逆波兰表示(后缀式):#(N)#Reduce: S t (T)#N#第八早例 1:有文法：S T (L)|a LTL,S|S给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义),它输出配对括号 得个数。如对于句子(a,(a,a), 输出就是2。解:加入新开始符号S'与产生式S' t S,设num为综合属性，代表值属性，则语法制导定义如下：产生式语义规则S'T Sprin t(S、num)ST (L)S、num:=L、n

12、um+1St aS、num:=OLt L1,SL、num:=L1、num+S numLT SL、num:=S、num例2:构造属性文法，能对下面得文法，只利用综合属性获得类型信息。t t id Tt int | real语义规则、type:=L、type、entry,L 、type)、type:=L、type、type:=T、type、entry,T、type)、type:=integer、type:=real(1) a*(b+c)(2) if(x+y)*z=O then s:=(a+b)*c else s:=a*b*c 解：(1) abc+*(2) xy+z*0=sab+c*:=sab*c*

13、:=¥(注：¥表示ifthenelse运算)例2:请将表达式(a+b)*(c+d)(a+b)分别表示成三元式、间接三元式与四元式序列。三元式(1) (+ a, b)(+ c, d)(1) (+ a, b)(3) (* (1), (2)(2) (+ c, d)(3), /)(3) (* (1), (2)(+ a, b)(3), /)(4), (5)(4), (1)四元式间接三元式间接三元式序列间接码表(1)(2)(3)(1) (+, a, b, t1)(2) (+, c, d, t2)(4) (, t3, /, t4) (6) (, t4, t5, t6)(3) (*, t1

14、, t2, t3)(5) (+, a, b, t5) 例 3: 请将下列语句 while (A<B) do if (C>D) then X:=Y+Z 翻译成四元式解: 假定翻译得四元式序列从 (100) (100) if A<B goto(102) (101) goto (107) (102) if C>D goto(104) (103) goto (100)(104) T : =Y+Z(105) X : =T(106) goto (100) (107)例 4: 写出 for 语句得翻译方案 解: 产生式S f for E do S1 S、SS开始:S|gen(S |g

15、en( |gen(S |gen(S |gen( |S1 |gen(S |gen(E f v:=initial to final第八章动作begin := newlabel 、 first := newtemp 、 last := newtemp 、 curr:= newtemp 、 code:=gen(S 、 first a ”、 last if ” S 、currfirsta ”、 beginif ” S、codea ?curr“:= ” E 、 init)E 、 final)“>” S 、last“goto ” S 、next)S 、 first) )>” S 、Last “g

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

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

18、auto 与 register 变量 , 设定它们在该例程得动态区中得相对区头得位移量。 而例程 动态区在运行时再做动态分配。对 local static 变量 , 为每个具有这类定义得例程 , 分别设置一个内部静态区进行分 配。(3) 实施标识符变量重复定义合法性检查 , 及引用变量得作用域范围得合法性检查。 第九章例 1: 下面得程序执行时 , 输出得 a 分别就是什么？若参数得传递办法分别为 (1) 传名 ;(2) 传 地址;(3) 得结果 ;4) 传值。program main (input,output); procedure p(x,y,z); beginy : =y+i;z :

19、=z+x;end;begina: =2;b: =3;p(a+b,a,a);print aend、 解:(1)参数得传递办法为“传名”时,a为9 。(2)参数得传递办法为“传地址”,a为8 。(3) 参数得传递办法为“得结果”,a为7 。(4) 参数得传递办法为“传值” ,a 为 2 。 例 2: 过程参数得传递方式有几种？简述“传地址”与“传值”得实现原理。 解:参数得传递方式有下述几种: 传值, 传地址 , 传名,得结果“传值”方式 , 这就是最简单得参数传递方法。 即将实参计算出它得值 ,然后把它传给被调过 程。具体来讲就是这样得 :1 、形式参数当作过程得局部变量处理 , 即在被调过程得

20、活动记录中开辟了形参得存储空 间, 这些存储位置即就是我们所说得实参或形式单元。2、调用过程计算实参得值 , 并将它们得右值 (rvalue) 放在为形式单元开辟得空间中。 3、被调用过程执行时 , 就像使用局部变量一样使用这些形式单元。“传地址”方式 , 也称作传地址 ,或引用调用。调用过程传给被调过程得就是指针 ,指向实参 存储位置得指针。1 、如实参就是一个名字或就是具有左值得表达式 , 则左值本身传递过去。2、如实参就是一个表达式，比方a+b或2,而没有左值，则表达式先求值，并存入某一位置， 然后该位置得地址传递过去。3、被调过程中对形式参数得任何引用与赋值都通过传递到被调过程得指针被

21、处理成间接 访问。例3:下面就是一个Pascal程序program PP(i nput,output)var K:in teger;fun cti on F(N:i nteger):i ntegerbeginif N< =0 then F:=1else F:=N * F(N1);en d;beginK:=F(10);、en d;当第二次(递归地)进入F后DISPLAY得内容就是什么？当时整个运行栈得内容就是什么? 解：运行妆祁局；例1：何谓代码优化？进行优化所需要得基础就是什么？解：对代码进行等价变换,使得变换后得代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或

22、两者都有。优化所需要得基础就是在中间代码生成之后或目标代码生成之后。例2:编译过程中可进行得优化如何分类？最常用得代码优化技术有哪些？ 解：依据优化所涉及得程序范围，可以分为：局部优化、循环优化与全局优化。 最常用得代码优化技术有1、删除多余运算2、代码外提3、强度削弱4、变换循环控制条件 5、合并已知量与复 写传播6、删除无用赋值例3:试对以下基本块B2:B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L应用DAG对它们进行优化，并就以下两种情况分别写出优化后得四元式序列(1)假设只有G L、M在基本块后面还要被引用。

23、(2)假设只有L在基本块后面还要被引用。解：基本块对应得DAG如下:B:=3 D:=A+CE:=A*C F:=D+EG:=B*F H:=A+CI:=A*C J:=H+IM:=L例1 一个编译程序得代码生成要着重考虑K:=B*5 L:=K+J些问题？解：,而衡量目标代码得质量主要从占代码生成器得设计要着重考虑目标代码得质量问题 用空间与执行效率两个方面综合考虑。课后习题答案：P366(1)就是09组成得数字串(2)最左推导：NNDNDDNDDDDDDD0DDD 01DD 012D0127NNDDD3D 34NNDNDDDDD5DD56D568最右推导:NNDN7ND7 N27ND27 N127D

24、1270127NNDN4D4 34NNDN8ND8 N68D68568P368文法：最左推导:E E TT TF T i T iT* Fi F* F ii *F i i*iE T T*F F *F i*F i*( E)i*( ET) i*(TT) i*( F T)i*(i T)i*( i F) i*(i i)最右推导:EE TE T* FE T*i E F *iE i*iT i* iF i*i i i*iE T F *T F * FF *( E )F*( ET) F*( E F) F*( E i)F*( T i)F *( Fi) F *( i i) i *(i i)语法树:/*/ E + /

25、Ei+i+iP369句子iiieiP64 - 7/EETFTFii+i*i有两个语法树：确定化：Jx丿弋1 LI2J 3J-0/ 1X0 V1,2,30001,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,400023004最小化:03P64- 12确定化：ab00,110,10,11100000给状态编号ab012112203333(b)bba20ba已经确定化了，进行最小化 最小化： 0,1, 2,3,4,5a1,0 3,5 2,4,11,03,52,4b3,5b 3,50,1b 2,4b 3,5b0

26、,1a 10,1b2,3,4,5a 1,3,0,5 2,4a3,5a 0,1,0,1a2,4a3,5a2,42,3,4,5b 2,3,4,53,52,4 2,43,52,4P81 1(1)按照T,S得顺序消除左递归递归子程序：procedure S;beginif sym='a' or sym='人'the n abva neeelse if sym='('the n begi nadvance;T;if sym=')' the n adva nee; else error;endelse erroren d;procedure

27、T;beginS;en d;procedure ;beginif sym=','the n begi nadvanee;S;enden d;其中：sym:就是输入串指针IP所指得符号 advanee:就是把IP调至下一个输入符号 error:就是出错诊察程序FIRST(S)=a,(FIRST(T)=af,(FIRST=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW=)预测分析表aA()5#ST就是LL(1)文法P81 - 2文法：(1)FIRST(E)=(,a,bf FIRST(E')=+,£ FIRST(T)=(,a,b FIRST(T

28、9;)=(,a,b,A,£ FIRST(F)=(,a,b,A FIRST(F')=*,£ FIRST(P)=(,a,bf FOLLOW(E)=#,) FOLLOW(E')=#,) FOLLOW(T)=+,),# FOLLOW(T')=+,),# FOLLOW(F)=(,a,b,A,+,),# FOLLOW(F')=(,a,b,A,+,),# FOLLOW(P)=*,(,a,b,A,+,),# 考虑下列产生式：FIRST(+E) A FIRST( £ )=+ n £ = $FIRST(+E) A FOLLOW(E')

29、=+ n #,)=$FIRST(T) A FIRST( £ )=(,a,b,AA £ = $FIRST(T) A FOLLOW(T')=(,a,b,A A +,),#=$FIRST(*F') A FIRST( £ )=* A £ = $FIRST(*F') A FOLLOW(F')=* A (,a,b,A,+,),#=$FIRST(E) A FIRST(a) A FIRST(b) A FIRST(A)= $ 所以,该文法式LL(1)文法、+*()abA#EE'TT'FF'Pprocedure E;b

30、eginif sym='(' or sym='a' or sym='b' or sym=' a' the n beg in T; E' end else errorendprocedure E'beginif sym='+'the n beg in adva nee; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or s

31、ym='a' or sym='b' or sym=' a' the n beg in F; T' end else errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym=' a' the n Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym=&#

32、39;b' or sym=' a'the n beg in P; F' endelse errorendprocedure F：beginif sym='*'the n beg in adva nee; F' endendprocedure P;beginif sym='a' or sym='b' or sym='A' the n adva nee else if sym='(' the n beginadvanee; E;if sym=')' the n a

33、dva nee else errorendelse erroren d;P133- 1短语：E+T*F, T*F, 直接短语：T*F 句柄:T*FP133-2文法：(1)最左推导：S (T)(T,S)S (T,S)(S,S)(T,S),S,S), S)(a,a),A ,S),S)(a,a),A ,(a), a)最右推导:S (T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(T),S)(T,S),S)(T,S,S),S)(S,S),S,S),S)(a,a),A ,(T), S)(T,(T)(T,(T,S)(a,S),S,S),S) (a,a),A ,(S),S)(a,(S,S)(

34、a,(a,S)(a,(a,a)(S,S,S),S)(T),S,S),S)(a,a),S,S),S)(a,a),A ,(a),S)(T,(T,a)(T,(S,a)(T,(a,a)(T,S),a)(T,(T), a)(S,a ,(a), a) (S,a),A ,(a),a)(T,(S),a)(T),a ,(a),a) (a,a),A ,(a),a)(S,(a,a)(a,(a,a)S (T,S)(T,a)(S,a)(T),a)(T,(a),a)(T,S,(a),a)(T,a ,(a), a)(T,S),a ,(a), a) (T,a),A ,(a),a)(a,a),A,(a),a)(S0,(a),a

35、) (T, a),A,(a),a) (LSV，(a),a) (TL，A，(a),a) (S，A，(a)，a) (T,A,(a),a) (TS，(a),a) (T,( a),a) (T,( S),a) (T,( T),a) (TS),a) (IL，a) (S，a) (TS) (T)_S“移进归约”过程步骤栈输入串动作0#(a,a),A,(a),a)#预备1#(a,a),A,(a),a)#进2#(a,a),A,(a),a)#进3#(a,a),A,(a),a)#进4#(a,a),A,(a),a)#进5#(S,a),A,(a),a)#归6#(T,a),A,(a),a)#归7#(T，a),A,(a),a

36、)#进8#(T，a),A,(a),a)#进9#(T，S),A,(a),a)#归10#(T),A,(a),a)#归11#(T),A,(a),a)#进12#(S,A,(a),a)#归13#(T,A,(a),a)#归14#(T，A,(a),a)#进15#(T，a,(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)#归23#(T，(T),a)#进24#(T,S),a)#归25#(T),a)#归26#(T),a)#进27#(S,a)#归28#(

37、T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T)#归33#(T)#进34#S#归P133-3(1) FIRSTVT(S)=a,(FIRSTVT(T)=,a】,(LASTVT(S)=af,)LASTVT(T)=,a,)栈动作#(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)#进aA()5a>>A>>(<<<=

38、<)>><<<>>就是算符文法，并且就是算符优先文法(3)优先函数aA()5f44244g55523#(t,(t,s)#归#(t,(t)#归#(t,(t)#进#(t,s)#归#(t)#归#(t )#进# s#归P164- 1T、val=58digit、lexval=2val=1F、val=29(T、val=1T、 val=4F、val=7答：表达式（4*7+1）*2得附注语法树如下图F、val=1F、val=4digit、lexval=7digit、lexval=1digit、lexval=4P164 - 2答：j realLLT、type;addtype(id1、type;addtype(id、type、type,L、type)、type,L 1、type)P217- 1a*(b+c)a+b*(c+d/e)a+b*(c