编译原理题库

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开头的偶正整数集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|02.证明下述文法G表达式是二义的。表达式=a|(表达

2、式)|表达式运算符表达式运算符=+|-|*|/解：可为句子a+a*a构造两个不同的最右推导: 最右推导1 表达式Þ表达式运算符表达式Þ表达式运算符aÞ表达式* aÞ表达式运算符表达式* aÞ 表达式运算符a * aÞ表达式+ a * aÞ a + a * a最右推导2 表达式Þ表达式运算符表达式Þ表达式运算符表达式运算符表达式Þ表达式运算符表达式运算符 aÞ表达式运算符表达式 * aÞ 表达式运算符a * aÞ表达式+ a * aÞ a + a * a3.

3、 给出生成下述语言的上下文无关文法： （1） anbnambm| n，m>=0 （2） 1n0m1m0n| n，m>=0解： （1） anbnambm| n，m>=0 SAAAaAb| (2) 1n0m1m0n| n，m>=0S1S0|AA0A1|第三章1、构造一个DFA，它接收=a, b上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。解：已知=a, b，根据题意得出相应的的正规式为： (b*abb*)*根据正规式画出相应的DFA M，如下图所示用子集法将其确定化XY(b*abb*)*XYb*abb*1eeXYb123456bbaeeeeeeI

4、IaIbX,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,YIIaIb01213212314414由DFA得状态图 用最小化方法化简得：0，1，2，3,4，按顺序重新命名DFA M10243aaaabbbbb 0312aaabbb第四章练习1：文法GV： VN|NE EV|V+E Ni 是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而GV中含有回溯，所以先消除回溯得到文法GV： GV： VNV V|E EVE E|+E Ni由L

5、L(1)文法的充要条件可证GV是LL(1)文法练习2：有文法Gs: SBA ABS|d BaA|bS|c(1)证明文法G是LL(1)文法。(2)构造LL(1)分析表。(3)写出句子adccd的分析过程解：(1)一个LL(1)文法的充要条件是：对每一个非终结符A的任何两个不同产生式A|，有下面的条件成立： FIRST()FIRST()=; 若*Þ, 则有FIRST()FOLLOW(A)=对于文法Gs: SBA ABS|d BaA|bS|c其FIRST集如下： FIRST(B)=a, b, c; FIRST(A)=a, b, c, d; FIRST(S)=a, b, c。其FOLLOW集

6、如下：首先， FOLLOW(S)=#;对SBA有： FIRST(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)

7、FIRST(c) =a b c= 。由于文法Gs不存在形如 的产生式，故无需求解形如FIRST()FOLLOW(A)的值。也即，文法GS是一个LL(1)文法。(2) 由Gs:SBA ABS|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)预测分析表如下： abcd#SSBASBASBA  AABSABSABSAd B

8、BaABbSBc  SSBASBASBA  AABSABSABSAd BBaABbSBc  (3)在分析表的控制下，句子adccd的分析过程如下：第五章1 已知文法GS为：Sa|(T) TT,S|S (1) 计算GS的FIRSTVT和LASTVT。(2) 构造GS的算符优先关系表并说明GS是否为算符优先文法。(3) 给出输入串 (a,(a,a)#的算符优先分析过程。解：文法：Sa|(T) TT,S|S 展开为： SaSS(T) TT,S TS(1) FIRSTVT - LASTVT表 非终结符 FIRSTVT集 LASTVT

9、集 S a ( a ) T a ( , a ) , (2)算符优先关系表如下: 表中无多重入口所以是算符优先（OPG）文法。  a (),#a(),# (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 inMove inReduce: SaMove inMove

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

11、 S.num:=0 LL1,S L.num:=L1.num+S.num LS 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 real T.type:=real第七章例1：给

12、出下面表达式的逆波兰表示(后缀式)：(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), /) (

13、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<

14、;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 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) |gen(“if” S.first “

15、>” 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 final E.init := initial.place E.final := final.place第八章例1：C语言中规定变量标识符的定义可分为extern, extern static, auto, loc

16、al static和register五种存储类：(1) 对五种存储类所定义的每种变量，分别说明其作用域。(2) 试给出适合上述存储类变量的内存分配方式。(3) 符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解：(1) extern 定义的变量，其作用域是整个C 语言程序。 extern static 定义的变量，其作用域是该定义所在的C 程序文件。 auto 定义的变量，其作用域是该定义所在的例程。 local static 定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。 register 定义的变量，其作用域与auto 定义的变量一样。这种变量的值

17、，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2) 对extern 变量，设置一个全局的静态公共区进行分配。 对extern static 变量，为每个C 程序文件，分别设置一个局部静态公共区进行分配。 对auto 和register 变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。 对local static 变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3) 实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。第九章例1：下面的程序执行时，输出的a分别是什么？若参数的传递办法分别为(1)传名；(2)传地址

18、；(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 end. 解：(1) 参数的传递办法为“传名”时，a 为 9。(2) 参数的传递办法为“传地址”，a 为 8。(3) 参数的传递办法为“得结果”，a 为 7。(4) 参数的传递办法为“传值”，a 为 2。 例2：过程参数的传递方式有几种？简述“传地址”和“传值”的实现原理。解：参数的传递方式有下述几种：传值，传地址，传名，得结果“传值”方式，这是最简单的参数

19、传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。2.调用过程计算实参的值，并将它们的右值（r-value）放在为形式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。“传地址”方式，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。1.如实参是一个名字或是具有左值的表达式，则左值本身传递过去。2.如实参是一个表达式，比方a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址

20、传递过去。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;begin K:=F(10);.end;当第二次（递归地）进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？解：第十章例1：何谓代码优化？进行优化所需要的基础是什么？解：对代码进行等价变换，使得变换后的代码运行结果与变换前代码

21、运行结果相同，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。例2：编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？解：依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。最常用的代码优化技术有1. 删除多余运算2. 代码外提3. 强度削弱4. 变换循环控制条件5. 合并已知量与复写传播6. 删除无用赋值例3：试对以下基本块B2：B：=3 D：=A+CE：=A*C F：=D+EG：=B*F H：=A+CI：=A*C J：=H+IK：=B*5 L：=K+JM：=L应用DAG 对它们进行优化，并就以下两种情况分别写出优

22、化后的四元式序列：（1）假设只有G、L、M 在基本块后面还要被引用。（2）假设只有L 在基本块后面还要被引用。解：基本块对应的DAG 如下：B：=3 D：=A+CE：=A*C F：=D+EG：=B*F H：=A+CI：=A*C J：=H+IK：=B*5 L：=K+JM：=L例1 一个编译程序的代码生成要着重考虑哪些问题?解：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。课后习题答案：P36-6(1)是09组成的数字串(2)最左推导:最右推导:P36-8文法：最左推导:最右推导:语法树：/*P36-9句子iiiei有两个语法树：P64

23、7(1)XY X1234Y5 0 1 1 0 1 1确定化：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,4 0320 1 01 0 0 1 1 0654 0 1 0 1 1 1最小化： 002 1 1 0 0 1 0543 0 1 0 1 1 1P6412(a) a10 a,b a确定化：ab00,110,10,1110给状态编号：ab012112203333 a10 a a b b b32 b a最小化： a a210 b b a b(b)032 b b a a b a a b54

24、1 b a a a已经确定化了,进行最小化最小化：021 b b a a b aP811(1) 按照T,S的顺序消除左递归递归子程序：procedure S;beginif sym='a' or sym='' then abvanceelse if sym='(' then beginadvance;T;if sym=')' then advance;else error; endelse errorend;procedure T;beginS;end;procedure ;beginif sym=',' then

25、 beginadvance;S;endend;其中:sym:是输入串指针IP所指的符号 advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST()=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW()=)预测分析表a(),#ST是LL(1)文法P812文法：(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)=

26、#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F')=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考虑下列产生式: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

27、,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,该文法式LL(1)文法.(3)+*()ab#EE'TT'FF'P(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='' then begin T; E' end else errorendprocedure E'beginif sym='+' then begin advance; E end else if sym

28、<>')' and sym<>'#' then errorendprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='' then begin F; T' end else errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym='' then T else if

29、 sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='' then begin P; F' end else errorendprocedure F'beginif sym='*' then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='

30、' then advance else if sym='(' thenbeginadvance; E;if sym=')' then advance else errorendelse errorend;P1331短语: E+T*F, T*F,直接短语: T*F句柄: T*FP1332文法：(1)最左推导:最右推导:(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

31、),a)(T),a)(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,(

32、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#归P1333(1) FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2)a(),a>>>>

33、;(<<<=<)>>,<<<>>是算符文法，并且是算符优先文法(3)优先函数a(),f44244g55523 （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）#进# s#归P1641 答

34、：表达式（4*7+1）*2的附注语法树如下图：digit.lexval=2F.val=2E.val=58ndigit.lexval=4digit.lexval=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*LP1642答：(1)ab+(2)ab+P16511答：（1）Did LD.type:= L.type；addtype(id.type,L.type)L, id L1L.type:= L1.type；addtype(id

35、.type,L1.type)L : TL.type:= T.typeTinteger T.type := integerT real T.type := realP2171a*(-b+c)abc+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)abcd+*+A (C or not D)A not C Dnot 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 abcxy+z*0= ab+cabc ￥或 xy+z*0= P1 jez ab+c P2 jump abc P1 P2P2173-(a+b)*(c+d)-(a+b+c)的三元式序列:(1) +, a, b(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +