2021年编译原理题库

第一章什么是编译器？编译程序构造分为几种阶段，各阶段任务是什么？遍、编译前端及编译后端含义？编译程序生成方式有哪些？第二章1.写一文法，使其语言是偶正整数集合。规定：（1）容许0打头（2）

不容许0打头解：（1）容许0开头偶正整数集合文法E→NT|DT→NT|DN→D|1|3|5|7|9D→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*aÞa+a*a最右推导2〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉aÞ〈表达式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+a*aÞa+a*a3.给出生成下述语言上下文无关文法：（1）{anbnambm|n，m>=0}（2）{1n0m1m0n|n，m>=0}解：（1）{anbnambm|n，m>=0}S→AAA→aAb|ε(2){1n0m1m0n|n，m>=0}S→1S0|AA→0A1|ε第三章1、构造一种DFA，它接受∑={a，b}上所有满足下述条件字符串：字符串中每个a均有至少一种b直接跟在其右边。解：已知∑={a，b}，依照题意得出相应正规式为：(b*abb*)*依照正规式画出相应DFAM，如下图所示用子集法将其拟定化XY(b*abb*)*XY(b*abb*)*XYb*abb*1XYb123456bbaIIaIb{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}IIaIb0121—3212314414由DFA得状态图用最小化办法化简得：{0}，{1}，{2}，{3,4}，按顺序重新命名DFAM’10210243aaaabbbbb0312aaabbb第四章练习1：文法G[V]：V→N|N[E]E→V|V+EN→i与否为LL(1)文法，如不是，如何将其改导致LL(1)文法。解：LL(1)文法基本条件是不含左递归和回溯（公共左因子），而G[V]中具有回溯，因此先消除回溯得到文法G’[V]：G’[V]：V→NV’V’→ε|[E]E→VE’E’→ε|+EN→i由LL(1)文法充要条件可证G’[V]是LL(1)文法练习2：有文法G[s]: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)=Φ对于文法G[s]：S→BAA→BS|dB→aA|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)={a}∩{b}∩{c}=Φ。由于文法G[s]不存在形如β→ε产生式，故无需求解形如FIRST(α)∩FOLLOW(A)值。也即，文法G[S]是一种LL(1)文法。(2)由G[s]:S→BAA→BS|dB→aA|bS|cFIRST(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→BA

AA→BSA→BSA→BSA→d

BB→aAB→bSB→c

SS→BAS→BAS→BA

AA→BSA→BSA→BSA→d

BB→aAB→bSB→c

(3)在分析表控制下，句子adccd分析过程如下：第五章1已知文法G[S]为：

S→a|∧|(T)T→T,S|S(1)计算G[S]FIRSTVT和LASTVT。(2)构造G[S]算符优先关系表并阐明G[S]与否为算符优先文法。(3)给出输入串(a,(a,a))#算符优先分析过程。解：文法：

S→a|∧|(T)T→T,S|S展开为：

S→aS→∧S→(T)

T→T,ST→S(1)FIRSTVT--LASTVT表非终结符FIRSTVT集LASTVT集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))#))#

)#

)#

)#

#

#

#Movein

Movein

Reduce：S→a

Movein

Movein

Movein

Reduce：S→a

Movein

Movein

Reduce：S→a

Reduce：T→T,S

Movein

Reduce：S→(T)

Reduce：T→T,S

Movein

Reduce：S→(T)第六章例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→TidT→int|real解：属性文法（语法制导）定义：产生式语义规则D→L,idD.type:=L.typeaddtype(id.entry,L.type)D→LD.type:=L.typeL→TidL.type:=T.typeaddtype(id.entry,T.type)T→intT.type:=integerT→realT.type:=real第七章例1：给出下面表达式逆波兰表达(后缀式)：(1)a*(-b+c)(2)if(x+y)*z=0thens:=(a+b)*celses:=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)doif(C>D)thenX:=Y+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语句翻译方案解：产生式动作S→forEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)||gen(S.last“:=”E.final)||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:=initialtofinalE.init:=initial.placeE.final:=final.place第八章例1：C语言中规定变量标记符定义可分为extern，externstatic，auto，localstatic和register五种存储类：(1)对五种存储类所定义每种变量，分别阐明其作用域。(2)试给出适合上述存储类变量内存分派方式。(3)符号表中登记存储类属性，在编译过程中支持什么样语义检查。解：(1)extern定义变量，其作用域是整个C语言程序。externstatic定义变量，其作用域是该定义所在C程序文献。auto定义变量，其作用域是该定义所在例程。localstatic定义变量，其作用域是该定义所在例程。且在退出该例程时，该变量值仍保存。register定义变量，其作用域与auto定义变量同样。这种变量值，在寄存器有条件时，可存储在寄存器中，以提高运营效率。(2)对extern变量，设立一种全局静态公共区进行分派。对externstatic变量，为每个C程序文献，分别设立一种局部静态公共区进行分派。对auto和register变量，设定它们在该例程动态区中相对区头位移量。而例程动态区在运营时再做动态分派。对localstatic变量，为每个具备此类定义例程，分别设立一种内部静态区进行分派。(3)实行标记符变量重复定义合法性检查，及引用变量作用域范畴合法性检查。第九章例1：下面程序执行时，输出a分别是什么？若参数传递办法分别为(1)传名；(2)传地址；(3)得成果；4)传值。

programmain(input,output);

procedurep(x,y,z)；

begin

y∶=y+1；

z∶=z+x;

end；

begin

a∶=2；

b∶=3；

p(a+b,a,a)；

printa

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程序

programPP(input,output)

varK:integer;

functionF(N:integer):integer

begin

ifN<=0thenF:=1

elseF:=N*F(N-1);

end;

begin

K:=F(10);

...

end;

当第二次（递归地）进入F后，DISPLAY内容是什么？当时整个运营栈内容是什么？解：第十章例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)是0~9构成数字串(2)最左推导:最右推导:P36-8文法：最左推导:最右推导:语法树：/********************************P36-9句子iiiei有两个语法树：P64–7(1)XYXYX1X1234Y511011拟定化：01{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}0320103201001101654016540111最小化：002102100101543015430111P64–12(a)a10a,b10a拟定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ给状态编号：ab012112203333a10a10abbb3232ba最小化：aa210bb210ab(b)032bba032abaab541ba541aa已经拟定化了,进行最小化最小化：021bba021abaP81–1(1)按照T,S顺序消除左递归递归子程序：procedureS;begin ifsym='a'orsym='^' thenabvance elseifsym='(' thenbegin advance;T; ifsym=')'thenadvance; elseerror; end elseerrorend;procedureT;begin S;end;procedure;begin ifsym=',' thenbegin advance; S; endend;其中:sym:是输入串指针IP所指符号advance:是把IP调至下一种输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}预测分析表a^(),#ST是LL(1)文法 P81–2文法：(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)考虑下列产生式: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)+*()ab^#EE'TT'FF'P(4)procedureE;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT；E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance；Eend elseifsym<>')'andsym<>'#'thenerrorendprocedureT;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF；T'end elseerrorend procedureT';begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP；F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance；F'endendprocedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance；E; ifsym=')'thenadvance elseerror end elseerrorend;P133–1短语：E+T*F，T*F,直接短语：T*F句柄：T*FP133–2文法：(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),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 ,(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 # 归P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)a^(),a>>^>>(<<<=<)>>,<<<>>是算符文法，并且是算符优先文法(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 # 归P164–1答：表达式（4*7+1）*2附注语法树如下图：digit.lexval=2F.val=2Edigit.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*L答：(1)aab+(2)aab+P165–11答：（1）D→idL {D.type:=L.type；addtype(id.type,L.type)}L→，idL1 {L.type:=L1.type；addtype(id.type,L1.type)}L→：T {L.type:=T.type}T→integer {T.type:=integer}T→real {T.type:=real}P217–1a*(-b+c) HYPERLINKmailto:ab@c+*ab@c+*a+b*(c+d/e) abcde/+*+-a+b*(-c+d) HYPERLINKmailto:a@bc@d+*+a@bc@d+*+A(CornotD) AnotCD not ornot or (AandB)or(notCorD) ABandCnotDoror(AorB)and(CornotDandE) ABorCDnotEandorand if(x+y)*z=0then(a+b)↑celsea↑b↑c xy+z*0=ab+c↑abc↑↑￥ 或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P2P217–3-(a+b)*(c+d)-(a+b+c)三元式序列:+，a，b@，(1)，-+，c，d*，(2)，(3)+，a，b+，(5)，c-，(4)，(6)间接三元式序列:三元式表：+，a，b@，(1)，-+，c，d*，(2)，(3)+，(1)，c-，(4)，(5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式