编译原理题库

第一章什么是编译器？编译程序的结构分为几个阶段，各阶段的任务是什么？遍、编译前端及编译后端的含义？编译程序的生成方式有哪些？第二章1. 写一文法，使其语言是偶正整数的集合。要求：（ 1）允许 0 打头（ 2）不允许 0 打头解：（ 1）允许 0 开头的偶正整数集合的文法E NT|D T NT|DN D|1|3|5|7|9 D 0|2|4|6|8（ 2）不允许 0 开头的偶正整数集合的文法E NT|DT FT|GN D|1|3|5|7|9D 2|4|6|8F N|0G D|02. 证明下述文法 G表达式是二义的。表达式 =a|( 表达式 )| 表达式运算符表达式运算符 =+|-|*|/解：可为句子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） anbnambm| n ，m>=0S AAA aAb| 精品文库(2) 1n0m1m0n| n， m>=0S 1S0|AA 0A1| 第三章1、构造一个DFA，它接收 =a,b 上所有满足下述条件的字符串：字符串中的每个a 都有至少一个b 直接跟在其右边。解：已知 =a, b，根据题意得出相应的的正规式为：(b*abb*)*根据正规式画出相应的DFA M，如下图所示用子集法将其确定化XX(b*abb*)*1YYIIaIbX,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,Y由 DFA得状态图顺序重新命名 DFA MbX23ab*abb*1465bYbIIaIb01213212314414用最小化方法化简得：0 ， 1 ， 2 ， 3,4 ，按1baa30aaa1babb24bb第四章练习 1：文法 GV ：0a3b2bV N|NEEV|V+EN i是否为 LL(1) 文法，如不是，如何将其改造成LL(1) 文法。解：LL(1) 文法的基本条件是不含左递归和回溯（公共左因子），而GV 中含有回溯，所以先消欢迎下载2精品文库除回溯得到文法GV ：G V ：V NVV |EE VEE |+EN i由 LL(1) 文法的充要条件可证G V 是 LL(1) 文法练习 2：有文法Gs:S BAA BS|dB aA|bS|c(1) 证明文法 G是 LL(1) 文法。(2) 构造 LL(1) 分析表。(3) 写出句子 adccd 的分析过程解： (1) 一个 LL(1) 文法的充要条件是：对每一个非终结符A 的任何两个不同产生式A |，有下面的条件成立： FIRST( ) FIRST( )= ; 若 *,则有 FIRST( ) FOLLOW(A)=对于文法 Gs:SBAA BS|dBaA|bS|c其 FIRST 集如下：FIRST(B)=a, b, c;FIRST(A)=a, b, c, d;FIRST(S)=a, b, c。其 FOLLOW集如下：首先， FOLLOW(S)=#;对 S BA 有： FIRST(A) 加入 FOLLOW(B), 即 FOLLOW(B)=a, b, c, d ;对 A BS 有： FIRST(S) 加入 FOLLOW(B), 即 FOLLOW(B)=a, b, c, d ;对 B aA 有： FOLLOW(B)加入 FOLLOW(A), 即 FOLLOW(A)=a, b, c, d ;对 B bS 有： FOLLOW(B)加入 FOLLOW(S), 即 FOLLOW(S)=#, a, b, c, d ;由 A BS|d 得：FIRST(BS) FIRST(d) = a, b, c d = ;由 B aA|bS|c 得：FIRST(aA) FIRST(bS)FIRST(c) =ab c= 。由于文法Gs 不存在形如 的产生式，故无需求解形如FIRST( ) FOLLOW(A)的值。也即，文法GS 是一个 LL(1) 文法。(2) 由 Gs:S BA A BS|d B 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#SS BAS BAS BAAA BSA BSA BSAdBB aAB bSB cSS BAS BAS BAAA BSA BSA BSAdBB aAB bSB c欢迎下载3精品文库(3) 在分析表的控制下，句子 adccd 的分析过程如下：栈当前输入符号输入串说明#Sadccd#SBA#ABadccd#BaA#AAaadccd#AAdccd#Ad#Addccd#Accd#ABS#SBccd#Bc#Scccd#Scd#SBA#ABcd#Bc#Accd#Ad#Ad#dd#分析成功第五章1 已知文法 GS 为：S a| |(T)T T,S|S(1) 计算 GS 的 FIRSTVT和 LASTVT。(2)构造 GS 的算符优先关系表并说明GS 是否为算符优先文法。(3) 给出输入串 (a,(a,a)# 的算符优先分析过程。解：文法：S a| |(T)T T,S|S展开为：S aSS (T)T T,ST S(1) FIRSTVT - LASTVT表非终结符FIRSTVT 集LASTVT集S a ( a ) T a ( , a ) , (2) 算符优先关系表如下 : 表中无多重入口所以是算符优先（OPG）文法。a(),#a (),#欢迎下载4精品文库(3) 输入串（ a,(a,a) ） # 的算符优先分析过程为：当 前 字栈剩余输入串动作符#(a,(a,a)#Move in#(a,(a,a)#Move in#(a,(a,a)#Reduce: S a#(N,(a,a)#Move in#(N,(a,a)#Move in#(N,(a,a)#Move in#(N,(a,a)#Reduce: S a#(N,(N,a)#Move in#(N,(N,a)#Move in#(N,(N,a)#Reduce: S a#(N,(N,N)#Reduce: T T,S#(N,(N)#Move in#(N,(N)#Reduce: S (T)#(N,N)#Reduce: T T,S#(N)#Move in#(N)#Reduce: S (T)#N#第六章例 1：有文法：S (L)|aL L,S|S给此文法配上语义动作子程序( 或者说为此文法写一个语法制导定义) ，它输出配对括号的个数。如对于句子(a,(a,a)，输出是2。解：加入新开始符号S' 和产生式S' S，设 num 为综合属性，代表值属性，则语法制导定义如下：产生式语义规则S' Sprint(S.num)S (L)S.num:=L.num+1S aS.num:=0L L1,SL.num:=L1.num+S.numL SL.num:=S.num例 2：构造属性文法，能对下面的文法，只利用综合属性获得类型信息。D L,id | LL T idT int | real解：属性文法（语法制导）定义：产生式语义规则D L,idD.type:=L.typeaddtype(id.entry,L.type)D LD.type:=L.typeL T idL.type:=T.typeaddtype(id.entry,T.type)T intT.type:=integerT realT.type:=real欢迎下载5精品文库第七章例 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,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 (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 for E do S1S.begin := newlabelS.first := newtempS.last := newtempS.curr:= newtempS.code:=gen(S.first“ := ” E.init)|gen(S.last“ := ” E.final)欢迎下载6精品文库|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|gen(S.curr := succ(S.curr)|gen(“ goto ” S.begin)E v:=initial to finalE.init := initial.placeE.final := final.place第八章例 1： C 语言中规定变量标识符的定义可分为extern,externstatic,auto,localstatic和 register 五种存储类：(1) 对五种存储类所定义的每种变量，分别说明其作用域。(2) 试给出适合上述存储类变量的内存分配方式。(3) 符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解：(1) extern定义的变量，其作用域是整个C 语言程序。extern static定义的变量，其作用域是该定义所在的C 程序文件。auto定义的变量，其作用域是该定义所在的例程。local static定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。register定义的变量，其作用域与auto定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2) 对 extern 变量，设置一个全局的静态公共区进行分配。对 extern static 变量，为每个 C 程序文件，分别设置一个局部静态公共区进行分配。对 auto 和 register 变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。对 local static 变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3) 实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。第九章例 1：下面的程序执行时，输出的 a 分别是什么？若参数的传递办法分别为 (1) 传名； (2) 传地址； (3) 得结果； 4) 传值。program main (input,output);procedure p(x,y,z);beginy =y+1;z =z+x;end;begina =2;b =3;p(a+b,a,a);print a欢迎下载7精品文库end.解：(1)参数的传递办法为“传名”时，a 为 9 。(2)参数的传递办法为“传地址”，a 为 8 。(3)参数的传递办法为“得结果”，a 为 7 。(4)参数的传递办法为“传值”，a 为 2 。例 2：过程参数的传递方式有几种？简述“传地址”和“传值”的实现原理。解：参数的传递方式有下述几种：传值，传地址，传名，得结果“传值”方式， 这是最简单的参数传递方法。 即将实参计算出它的值， 然后把它传给被调过程。具体来讲是这样的：1. 形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。2. 调用过程计算实参的值，并将它们的右值（r-value ）放在为形式单元开辟的空间中。3. 被调用过程执行时，就像使用局部变量一样使用这些形式单元。“传地址”方式，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。1. 如实参是一个名字或是具有左值的表达式，则左值本身传递过去。2. 如实参是一个表达式，比方 a+b 或 2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。3. 被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。例 3：下面是一个 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的内容是什么？当时整个运行栈的内容是什么？解：欢迎下载8精品文库第十章例 1：何谓代码优化？进行优化所需要的基础是什么？解：对代码进行等价变换， 使得变换后的代码运行结果与变换前代码运行结果相同， 而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。例 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 在基本块后面还要被引用。（ 2）假设只有 L 在基本块后面还要被引用。解：基本块对应的DAG 如下：B： =3D： =A+CE： =A*CF： =D+EG： =B*FH： =A+CI ： =A*CJ： =H+IK： =B*5L： =K+JM： =L例 1 一个编译程序的代码生成要着重考虑哪些问题 ?解：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。课后习题答案：P36-6(1)L ( G1) 是 09 组成的数字串(2) 最左推导 :欢迎下载9精品文库NNDNDDNDDDDDDD0DDD01DD012D 0127NNDDD3D34NNDNDDDDD5DD56D568最右推导 :NNDN 7ND7N 27ND 27N 127D1270127NNDN 4D434NNDN 8ND 8N 68D 68568P36-8文法：ET|ET|ETT F|T*F|T/F F ( E)|i最左推导 :EE TT TF T i Ti T * Fi F * Fi i * Fi i * iETT * FF * Fi * Fi *( E )i *( E T )i *( T T ) i *( F T)i *( iT )i *( iF )i *( ii )最右推导 :EE TE T*FE T * iEF * iE i * iT i * iF i * ii i * iETF * TF * FF*( E)F*(E T)F*(E F)F *( E i )F*( Ti )F*(Fi )F *( ii )i *( ii )语法树： /*EEEE+TE+TE-TE+TFTT*FE-TFTFiFFiTFiFiiiFiiii+i+ii-i-ii+i*iP36-9句子 iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP647(1)1(01|) * 101XY欢迎下载10精品文库01101X12345Y1确定化：01X1,2,31,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,4010230001101014560111最小化： 0,1,2,3,4,5,6 0,1,2,3,4,5 01,3,5 0,1,2,3,4,5 11,2,4,6 0,1,2,3,4, 5, 6 0,1,2,3,4 01,3,5 0,1,2,3, 4, 5,6 0,1,2,3 0 1,3 0,12,3 11,2,4 0,1, 2,3 4, 5, 6 0,1 0 1 0,1 11,2 2,3 0 3 2,3 1 4 0, 1, 2,3, 4, 5, 6 010200100113450111欢迎下载11精品文库P6412(a)aa,b01a确定化：ab00,110,10,1110给状态编号：ab012112203333aa01abbbb23a最小化： 0,1,2,3 0,1 a1 0,1 b 2 2,3 a0,3 2,3 b 3 0,1,2,3aabb012ab欢迎下载12精品文库(b)bba023abaabba5a1a4已经确定化了 , 进行最小化最小化： 0,1, 2, 3, 4, 5 0 ,1 a 1 0, 1 b2,4 2 , 3 , 4 ,5 a 1, 3, 0 ,5 2 , 3 , 4 , 5 b 2 ,3,4 ,5 2 , 4 a1,0 2 , 4 b 3,5 3 ,5 a 3,5 3 , 5 b 2,4 0 , 1,2, 4,3,5 0 ,1 a 1 0, 1 b2,4 2 , 4 a1,0 2 , 4 b 3,5 3 ,5 a 3,5 3 , 5 b 2,4bba012abaP811(1) 按照 T,S 的顺序消除左递归G (S)Sa | | (T )TSTT,ST |递归子程序：procedure S;beginif sym='a' or sym=''then abvanceelse if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse error欢迎下载13精品文库end;procedure T;beginS; Tend;procedureT ;beginif sym=','then beginadvance;S; Tendend;其中 :sym: 是输入串指针IP 所指的符号advance: 是把 IP 调至下一个输入符号error:是出错诊察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST( T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(T )=)预测分析表a(),#SSaSS( T )TTSTTSTTSTTTT,ST是 LL(1) 文法P812文法：ETEEE|TFTTT|FPFF*F|P( E )| a | b |欢迎下载14精品文库(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,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考虑下列产生式:EE|TT|F* F |P( E)| a|bFIRST(+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)+*()ab#EETE 'ETE' ETE' ETE 'E'EEEETTFTTFTTFTTFTT'TTT TTT TT TT TFFPFFPFFPFFPFF'FF* FFFFFFFPP (E)P aP bP (4)procedure E;begin欢迎下载15精品文库if sym='(' or sym='a' or sym='b' or sym=''then begin T; E' endelse errorendprocedure E'beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then errorendprocedure T;beginif sym='(' or sym='a' or sym='b' or sym=''then begin F; T' endelse errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym=''then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym=''then begin P; F' endelse errorendprocedure F'beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym=''then advanceelse if sym='(' then欢迎下载16精品文库beginadvance; E;if sym=')' then advanceelse errorendelse errorend;P1331EETET*F短语 : E+T*F, T*F,直接短语 : T*F句柄 : T*FP1332文法：S a|( 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, S), S)( a, a), S,S), S)( a, a), ,S), S)( a, a ), ,( T), S)( a, a), ,( S), S)( a ,a ), ,( a ), S)( a, a), ,( 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 )( T ), ,( a), a)( T , S), ,( a ), a)( T , a ), ,( a ), a)( S,a ), ,( a ), a )( a, a ), ,( a ), a)(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)欢迎下载17精品文库( S,a)(T,S)(T)S“移进 - 归约”过程：步骤栈输入串动作0#(a,a),(a),a)#预备1#(a,a),(a),a)#进2#( a,a),(a),a)#进3#(a,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)#归23#(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#归欢迎下载18精品文库P1333(1) FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2)a(),a>>>>(<<<=<)>>,<<<>>G6 是算符文法，并且是算符优先文法(3) 优先函数a(),f44244g55523fffffa(),ggggga(),（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）#归欢迎下载19精品文库#（ t）#归#（ t）#进# s#归P1641答：表达式（ 4*7+1 ） *2 的附注语法树如下图：LE.val=58nT.val=58T.val=29*F.val=2F.val=29digit.lexval=2