编译原理题库

1、第一章什么是编译器？编译程序的结构分为几个阶段，各阶段的任务是什么？遍、编译前端及编译后端的含义？编译程序的生成方式有哪些？第二章1. 写一文法，使其语言是偶正整数的集合。要求：（1）允许0打头（2）不允许0打头解：（1）允许0开头的偶正整数集合的文法EtNT|DTtNT|DNtD|1|3|5|7|9Dt0|2|4|6|8（2）不允许0开头的偶正整数集合的文法EtNT|DTtFT|GNtD|1|3|5|7|9Dt2|4|6|8FtN|0GtD|02. 证明下述文法G表达式是二义的。表达式：=a|（表达式）|表达式运算符表达式运算符：=+卜|*|/解：可为句子a+a*a构造两个不同的最右推导：最

2、右推导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)anbnambm|n,m>=0StAAAtaAb|e(2)1nOmlmOn|n,m>=041S0|A20A1|£第三章1、构造一个DFA它接收刀=a

3、,b上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。解：(b*abb*)*已知刀=a,b，根据题意得出相应的的正规式为:根据正规式画出相应的DFAM如下图所示用子集法将其确定化b*abb*IIaIbX,1,2,3,Y42,345,6,1,2,3,Y2,342,35,6,1,2,3,Y46,1,2,3,Y6,1,2,3,Y46,1,2,3,YIIaIb0121一3212314414由DFA得状态图顺序重新命名DFAM第四章练习1:文法GV:VtN|NEEtV|V+E是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。解:LL(1)文法的基本条件是不含左递归和回溯

4、(公共左因子)，而GV中含有回溯，所以先消V't£|E't£|+E除回溯得到文法GV:G'V:VtNVEtVE'ENti由LL(1)文法的充要条件可证GV是LL(1)文法练习2:有文法Gs:StbaAtBS|dBtaA|bS|c(1) 证明文法G是LL(1)文法。构造LL(1)分析表。A的任何两个不同产生式Ata|(3)写出句子adccd的分析过程解：(1)一个LL(1)文法的充要条件是：对每一个非终结符3，有下面的条件成立： FIRST(a)nFIRST(3)=; 若3*=£,则有FIRST(a)nFOLLOW(A)对于文法Gs:

5、StbaatBS|dBtaA|bS|c其FIRST集如下：FIRST(B)=a,b,c;FIRST(A)=a,b,c,d;FIRST(S)=a,b,c。其FOLLOW如下：首先，FOLLOW(S)=#;对StBA有：FIRST(A)£加入FOLLOW(B),即FOLLOW(B)=a,b,c,d;对AtBS有：FIRST(S)s加入FOLLOW(B),即FOLLOW(B)=a,b,c,d;对BtaA有：FOLLOW(B加入FOLLOW(A),即FOLLOW(A)=a,b,c,d;对BtbS有：FOLLOW(B加入FOLLOW(S),即FOLLOW(S)=#,a,b,c,d;由AtBS|

6、d得：FIRST(BS)nFIRST(d)=a,b,cnd=;由BtaA|bS|c得：FIRST(aA)nFIRST(bS)nFIRST(c)=anbnc=。由于文法Gs不存在形如3tS的产生式，故无需求解形如FIRST(a)nFOLLOW(A的值。也即，文法GS是一个LL(1)文法。(2) 由Gs:StBAAtBS|dBtaA|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#SStBAS

7、tBAStBAAAtBSAtBSAtBSAtdBBtaABtbSBtcSStBAStBAStBAAAtBSAtBSAtBSAtdBBtaABtbSBtc(3)在分析表的控制下，句子adccd的分析过程如下:栈当前输入符号输入串说明#Sadccd#Stba#ABadccd#BtaA#AAaadccd#AAdccd#ATd#Addccd#Accd#AtBS#SBccd#Btc#Scccd#Scd#StBA#ABcd#Btc#Accd#Ad#ATd#dd#分析成功第五章1已知文法GS为:Sta|A|(T)T,S|S(1) 计算GS的FIRSTVT和LASTVT(2) 构造GS的算符优先关系表并说明G

8、S是否为算符优先文法。(3) 给出输入串(a,(a,a)#的算符优先分析过程。解：文法：Sta|A|(T)TtT,S|S展开为：StaStASt(T)TtT,STts(1)FIRSTVT-LASTVT表非终结符FIRSTVT集LASTVT集SaA(aA)TaA(,aA),(2)算符优先关系表如下：表中无多重入口所以是算符优先(OPG文法。aA()5#a>>>>A><>>t<<<><<<>><<<>(3)输入串(a,(a,a)#的算符优先分析过程为:栈当前字符剩余输入串动

9、作#(a,(a,a)#Movein#(a,(a,a)#Movein#(aJ(a,a)#Reduce:Sta#(NJ(a,a)#Movein#(N,(a,a)#Movein#(N,(a,a)#Movein#(N,(aJa)#Reduce:Sta#(N,(NJa)#Movein#(N,(N,a)#Movein#(N,(N,a)#Reduce:Sta#(N,(N,N)#Reduce:TtT,S#(N,(N)#Movein#(N,(N)#Reduce:St(T)#(N,N)#Reduce:TtT,S#(N)#Movein#(N)#Reduce:St(T)#N#第八早例1有文法：St(L)|aLtL,S

10、|S(或者说为此文法写一个语法制导定义)，它输出配对括号输出是2。S'tS,设num为综合属性，代表值属性，则语法制导定给此文法配上语义动作子程序的个数。如对于句子(a,(a,a),解：加入新开始符号S'和产生式义如下:产生式语义规则S'tSprint(S.num)St(L)S.num:=L.num+1StaS.num:=0LtL1,SL.num:=L1.num+S.numLTSL.num:=S.num例2：构造属性文法，能对下面的文法，只利用综合属性获得类型信息。DtL,id|LLttidTtint|real解：属性文法(语法制导)定义：产生式语义规则DtL,idD.

11、type:=L.typeaddtype(id.entry,L.type)DtlD.type:=L.typeLttidL.type:=T.typeaddtype(id.entry,T.type)TtintT.type:=integerTtrealT.type:=real第七章例1:给出下面表达式的逆波兰表示(后缀式)：(1) a*(-b+c)(2) if(x+y)*z=Othens:=(a+b)*celses:=a*b*c解：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=¥(注：Y表示if-then-else运算)例2：请将表达式-(a+b)*(c+d)-(a+

12、b)分别表示成三元式、间接三元式和四元式序列。解：三元式间接三兀式(1)(+a,b)间接三兀式序列间接码表(2)(+c,d)(1)(+a,b)(1)(3)(*(1),(2)(+c,d)(2)(4)(-(3),/)(3)(*(1),(2)(3)(5)(+a,b)(-(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(A<B)doif(C>D)thenX:=Y+

13、Z翻译成四元式解：假定翻译的四元式序列从(100)开始：(100) ifA<Bgoto(102)(101) goto(107)(102) ifC>Dgoto(104)(103) goto(100)(104) T:=Y+Z(105) X:=T(106) goto(100)(107)例4：写出for语句的翻译方案解：产生式动作StforEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtemp“:=”E.init)E.final)S.curr:=newtempS.code:=gen(S.first|gen(S.lastgoto”S.nex

14、t)goto”S.next)|gen(“if”S.first“>”S.last|gen(S.curr“:=”S.first)|gen(S.begin“：”)|gen(“if”S.curr“>”S.Last|S1.code|gen(S.curr:=succ(S.curr)|gen(“goto”S.begin)Etv:=initialtofinalE.init:=initial.placeE.final:=final.place第八章例1:C语言中规定变量标识符的定义可分为extern,externstatic,auto,localstatic和register五种存储类：(1) 对五

15、种存储类所定义的每种变量，分别说明其作用域。(2) 试给出适合上述存储类变量的内存分配方式。(3) 符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解：(1) extern定义的变量，其作用域是整个C语言程序。externstatic定义的变量，其作用域是该定义所在的C程序文件。auto定义的变量，其作用域是该定义所在的例程。localstatic定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。register定义的变量，其作用域与auto定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2) 对extern变量，设置一

16、个全局的静态公共区进行分配。对externstatic变量，为每个C程序文件，分别设置一个局部静态公共区进行分配。对auto和register变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。对localstatic变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3) 实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。第九章例1:下面的程序执行时，输出的a分别是什么？若参数的传递办法分别为(1)传名；(2)传地址；(3)得结果；4)传值。programmain(input,output);procedurep(x,y,z

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

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

19、是一个Pascal程序programPP(input,output)varK:integer;functionF(N:integer):integerbeginifN<=0thenF:=1elseF:=N*F(N-1);end;beginK:=F(10);end;当第二次(递归地)进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么?解：运行橫布局：第十章例1何谓代码优化？进行优化所需要的基础是什么？解：而运对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同,行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。例

20、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)假设只有GL、M在基本块后面还要被引用。(2)假设只有L在基本块后面还要被引用。解：基本块对应的DAG如下：B:=3D:

21、=A+CE：=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM=L例1一个编译程序的代码生成要着重考虑些问题？解:代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。课后习题答案：P36-6(1)(GJ是组成的数字串(2)最左推导：N二ND=NDD二NDDD二DDDD二ODDD二01DD=012D=0127N=ND=DD=3D=34N=ND=NDD二DDD二5DD二56D=568最右推导：N二ND=N7=ND7=N27二ND27=N127二D127=0127N=ND二N4二D4=34N=ND=N

22、8=ND8=N68=D68=568P36-8文法：EtTE+T|ETTtFT*F|T/FF>(E)|i最左推导:E=ET=TT=FT二iT二iT*F二iF*F=ii*F二ii*iE=T=T*F=F*F=i*F=i*(E)二i*(ET)二i*(TT)二i*(FT)=i*(iT)=i*(iF)=i*(ii)最右推导:EETET*FET*iEF*iEi*iTi*iFi*i_ii*iE=T=F*T=F*F=F*(E)=F*(ET)=F*(EF)=F*(E-i)F*(Ti)二F*(Fi)=F*(ii)=i*(ii)语法树:E/E+T/IE+TFTFiFiii+i+iE/、E+TFFiiiEE-T/

23、IE-TFTFiFiii+i*iP36-9句子iiiei有两个语法树:S二iSeS二iSei二iiSei二iiieiS=iS二iiSeS二iiSei二iiieiP64-7(1)1(01)*101011确定化:01X01,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,4最小化：0,1,2,3,4,5,60,1,234,5。1,3,50,1,2,3,4,51二1,2,4,60,1,2,3,4,5,60,1,2,3,401,3,50,1,2,3,4,5,60,1,2,30二1,30,1,2,3a

24、=1,2,40,1,2,34,5,60,10=10,1厂1,22,30=32,31=40,1,2,3,4,5,60012P64-12确定化:ab00,110,10,11100000给状态编号:ab0121122033330,1,2,20,1a二10,1b二2,3a二0,32,3b二30,1,2,32b(b)最小化：0,1,2,3,4,50,1a=10,1b=2,42,3,4,5人1,3,0,52,3,4,5几二2,3,4,52,4a=1,02,4b=3,53,5a二3,53,5打二2,40,1,2,4,3,50,1a=12,4a=1,03,5a二3,50,1b二2,42,4b3,53,5打二2

25、,4P811(1)按照T,S的顺序消除左递归G(S)S>aF|仃)T>STTJ,ST|；递归子程序：procedureS;beginifsym='a'orsym='人'thenabvaneeelseifsym='('thenbeginadvance;T;ifsym=')'thenadvanee;elseerror;endelseerrorend;procedureT;beginS;Tend;procedureT;beginifsym=','thenbeginadvanee;S;Tendend;其中：sy

26、m:是输入串指针IP所指的符号advanee:是把IP调至下一个输入符号error:是出错诊察程序FIRST(S)=a,(FIRST(T)=af,(FIRST(T)=,;FOLLOW(S)=),#FOLLOW(T)=)FOLLOW)=)预测分析表aA()5#SStaStaSt(T)TTtSTTtstTtSTTJ,ST是LL(1)文法P81-2文法：E>TEEr:E|；T>FT'TT|;FPFF*F'|；P(E)|a|b|AFIRST(E)=(,a,bfFIRST(E')=+,£FIRST(T)=(,a,bFIRST(T')=(,a,b,A,

27、£FIRST(F)=(,a,b,AFIRST(F')=*,£FIRST(P)=(,a,bfFOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F')=(,a,b,A,+,),#FOLLOW(P)=*,(,a,b,A,+,),#考虑下列产生式：EE|；T>T|；F*F；P>(E)|A|a|bFIRST(+E)AFIRST(£)=+n£=$FIRST(+E)AFOLLOW(E')=+A

28、#,)=$FIRST(T)AFIRST(£)=(,a,b,AA£=$FIRST(T)AFOLLOW(T')=(,a,b,AA+,),#=$FIRST(*F')AFIRST(£)=*A£=$FIRST(*F')AFOLLOW(F')=*A(,a,b,A,+,),#=$FIRST(E)AFIRST(a)AFIRST(b)AFIRST(A)=$所以,该文法式LL(1)文法.+*()abA#EEtTE'EtTE'EtTE'EtTE'E'EEEJ£EJ壬TTtTtFTtFTtFTT&

29、#39;TJeTJTTJetTTJTTJTTJsFFtPF'FtPF'FtPF'FtPFhF'FJ&F't*FF"t名FJ名F"t名FJ名FJ名FJzPPT(E)PtaPtbPtaprocedureE;beginifsym='('orsym='a'orsym='b'orsym='人'thenbeginT;E'endelseerrorendprocedureE：beginifsym='+'thenbeginadvanee;Eendelseif

30、sym<>')'andsym<>'#'thenerrorendprocedureT;beginifsym='('orsym='a'orsym='b'orsym='人'thenbeginF;T'endelseerrorendprocedureT'beginifsym='('orsym='a'orsym='b'orsym='人'thenTelseifsym='*'thenerroren

31、dprocedureF;beginifsym='('orsym='a'orsym='b'orsym='人'thenbeginP;F'endelseerrorendprocedureF'beginifsym='*'thenbeginadvanee;F'endendprocedureP;beginifsym='a'orsym='b'orsym='A'thenadvaneeelseifsym='('thenbeginadvanee;E

32、;ifsym=')'thenadvaneeelseerrorendelseerrorend;P133-1E二ET=ET*F短语：E+T*F,T*F,直接短语：T*F句柄:T*FP133-2文法：S>afl(T)T>T,S|S(1)最左推导：S=(T)二(T,S)=(S,S)二(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)二(a,(a,a)S=(T,S)=(S,S)二(T),S)=(T,S),S)=(T,S,S),S)二(S,S,S),S)=(T),S,S),S)=(T,S),S,S),S)=(S,S),S,S),S)=(a,S),S,

33、S),S)=(a,a),S,S),S)=(a,a),A,S),S)=(a,a),A,(T),S)=(a,a),A,(S),S)=(a,a),A,(a),S)=(a,a)f,(a),a)最右推导:S二(T)=(T,S)=(T,(T)=(T,(T,S)二(T,(T,a)=(T,(S,a)二(T,(a,a)二(S,(a,a)二(a,(a,a)S二(T,S)二(T,a)二(S,a)二(T),a)二(T,S),a)二(T,(T),a)二(T,(S),a)二(T,(a),a)二(T,S,(a),a)二(T,(a),a)二(S,A,(a),a)二(T)f,(a),a)二(T,S)f,(a),a)二(T,a)

34、,(a),a)二(S,a),A,(a),a)二(a,a),A,(a),a)(a,a),A,(a),a)(S),A,(a),a)(T,ar,(a),a)(TS),A,(a),a)(IL,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)(d,a)(§,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

35、#(S,a),A,(a),a)#归6#(T,a),A,(a),a)#归7#(a),A,(a),a)#进8#(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#

36、(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#归P133-3(1)FIRSTVT(S)=a,(FIRSTVT(T)=,a】,(LASTVT(S)=af,)LASTVT(T)=,a,)aA()Ja>>A>>(<<<=<)>><<<>>G6是算符文法，并且是算符优先文法（3）优先函数aA()5f44244g55523(4)栈输入字符串动作#(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）#归# (t# (t)# sP164-1答：表达式4*7+1)*2的附注语法树如下图:归T.val=58digit.lexval=2F.val=29)T.val=1F.val=1F.val=4digit.lexval=7digit.lexv