编译原理题库

第A-A-一早

■什么就是编译器？

■编译程序得结构分为几个阶段,各阶段得任务就是什么?

■遍、编译前端及编译后端得含义？

■编译程序得生成方式有哪些？

第一早

-1、写一文法，使其语言就是偶正整数得集合。

■要求：(1)允许0打头(2)不允许0打头

解：(1)允许0开头得偶正整数集合得文法

E-NT|D

T-NT|D

NfD1113|5|719

D-*0|2|4|6|8

(2)不允许0开头得偶正整数集合得文法

E-NT|D

T—FT|G

N^D1113151719

D-2|4⑹8

F-N|0

G-D|0

2、证明下述文法G［〈表达式〉］就是二义得。

〈表达式〉：：=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉

〈运算符〉：：=+||*|/

解:可为句子a+a*a构造两个不同得最右推导：

最右推导1〈表达式〉n〈表达式〉〈运算符〉〈表达式〉

=＞〈表达式〉〈运算符〉a

=＞〈表达式〉*a

n〈表达式〉〈运算符〉〈表达式〉*a

n〈表达式〉〈运算符〉a*a

=＞〈表达式〉+a*a

=a+a*a

最右推导2〈表达式〉n〈表达式〉〈运算符〉〈表达式〉

n〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉

n〈表达式〉〈运算符〉〈表达式〉〈运算符〉a

n〈表达式〉〈运算符〉〈表达式〉*a

n〈表达式〉〈运算符〉a*a

=＞〈表达式〉+a*a

=a+a*a

3、给出生成下述语言得上下文无关文法：

(1){anbnambm|n,m＞=0}

(2){InOmlmOnln,m＞=0}

解：(1){anbnambm|n,m＞=0}

S-AA

A-aAb|£

(2){InOmlmOnn,m>=0}

S-*1SO|A

A—OA1|e

弟二早

1、构造一个DFA,它接收E={a,b}上所有满足下述条件得字符串：字符串中得每个a都有至

少一个b直接跟在其右边。

解：

已知£={a,b},根据题意得出相应得得正规式为：(b*abb*)*

根据正规式画出相应得DFAM,如下图所示

用子集法将其确定化

Ilalb

{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)

由DFA得状态图

得：{0},{1},{2},{3,4},按顺序重新命名DFAM'

第四章

练习1:文法G[V]:

V-N[N[E]E-V|V+EN-i

就是否为LL(1)文法,如不就是,如何将其改造成LL(1)文法。

解：

LL⑴文法得基本条件就是不含左递归与回溯(公共左因子)，而G[V]中含有回溯,所以先消

除回溯得到文法G[V]:

G'[V]:V-NV'V'-e|[E]

E-VE'E'-e|+E

N-i

由LL(1)文法得充要条件可证G'[V]就是LL⑴文法

练习2:有文法G[s]:

S-BAA-BS|dB-aA|bS|c

⑴证明文法G就是LL⑴文法。

(2)构造LL⑴分析表。

⑶写出句子adccd得分析过程

解：(1)一个LL⑴文法得充要条件就是:对每一个非终结符A得任何两个不同产生式A-a

8,有下面得条件成立：

①FIRST(a)nFIRST(g)=0;

②若B*=>e,贝IJ有FIRST(a)CF0LL0W(A)=<5

对于文法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)有e}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};

对A-BS有：FIRST(S)\{e}加入FOLLOW(B),即FOLLOW⑻={a,b,c,d};

对BfaA有:FOLLOW(B)加入FOLLOW(A),即FOLLOW(A)={a,b,c,d};

对BfbS有:FOLLOW(B)加入FOLLOW(S),即FOLLOW(S)={和a,b,c,d};

由A-BS|d得：

FIRST(BS)nFIRST(d)={a,b,c}C{d}=中；

由B-*aA|bS|c得：

FIRST(aA)nFIRST(bS)nFIRST(c)={a}n{b}A{c}=中。

由于文法G[s]不存在形如B-e得产生式,故无需求解形如FIRST(a)AFOLLOW(A)得值。

也即，文法G[S]就是一个LL(1)文法。

(2)由G[s]:S-BAA-BS|dBfaA|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-BA

AA-BSA-BSA-BSA-d

BBfaAB-bSB一c

SS-BAS-BAS-BA

AA-BSA-BSA-BSA-d

BB—aAB-bSBfc

(3)在分析表得控制下,句子adccd得分析过程如下:

栈当前输入符号输入串说明

adeed#S-BA

1E,轴文冲妗］为:adeed#B->aA

SAAa|(T)ff-*T,S|Sdeed#

(1)睇算G闻得FIRSdvr与LAsfrVToccd#A-d

⑵物建G［S］得算符优先关系表并说明GSC薪是否为算符优先文法。

(3)解出输入串(a.缸a))#得壹符优先分稠曲早。A-BS

解:击圈:ccd#B—c

共必力八(T)CT—T,cd#

展方峪cd#S-BA

出一、LNS-&(T)d#B—c

T-£Qd#

TAQTvM主#Afd

(1)?4RSTVIi

ffudff

非终第i符FIRSTVT篥LAST里集分前成功

S{aA()(aA)}

T{aA(,){aA),)

(2)算符优先关系表如下：表中无多重入口所以就是算符优先(OPG)文法。

(3)输入串(a,(a,a))#得算符优先分析过程为:

当前字

栈剩余输入串动作

符

#(a,(a,a))#Movein

#(a,(a,a))#Movein

#(a(a,a))#Reduce:S^a

#(N(a,a))#Movein

#(N,(a,a))#Movein

#(N,(a,a))#Movein

#(N,(aa))#Reduce:S^a

#(N,(Na))#Movein

#(N,(N,a))#Movein

#(N,(N,a))#Reduce:S^a

#(N,(N,N))#Reduce:T—T,S

#(N,(N))#Movein

#(N,(N))#Reduce:S—(T)

#(N,N)#Reduce:T—T,S

#(N)#Movein

#(N)#Reduce:S—(T)

#N#

第八早

例1：有文法：S-(L)|aL-*L,S|S

给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号

得个数。如对于句子(a,(a,a)),输出就是2。

解:加入新开始符号S'与产生式S'-S,设num为综合属性,代表值属性,则语法制导定义如

下：

产生式语义规则

S'—Sprint(S>num)

Sf(L)S、num:=L>num+1

S-aS、num:=0

L-Ll,SL、num:=LI、num+S>num

LfSL、num:=S>num

例2:构造属性文法,能对下面得文法,只利用综合属性获得类型信息。

D-L,idLL-aTidTfintreal

解:属性文法(语法制导)定义：

产生式语义规则

D一L,idD、type:二L、type

addtype(id>entry,L>type)

D一LD>type:=L>type

L一TidL、type:=T>type

addtype(id>entry,T>type)

T一intT、type:二integer

T一realT>type:=real

第七章

例1:给出下面表达式得逆波兰表示(后缀式):

(1)a*(b+c)

(2)if(x+y)*z=0thens:=(a+b)*celses:=a*b*c

解：

(1)abc+*

(2)xy+z*0=sab+c*:=sab*c*:=¥

(注：¥表示ifthenelse运算)

例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,tl)(2)(+,C,d,t2)

(3)(*,tl,t2,t3)(4)(,t3,/,t4)

(5)(+,a,b,t5)(6)(,t4,t5,t6)

例3:请将下列语句

while(A<B)doif(OD)thenX:=Y+2

翻译成四元式

解：

假定翻译得四元式序列从(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:=newlabel

S、first:=newtemp

S、last:=newtemp

S、curr:=newtemp

S、code:=gen(S、firstE、init)

|gen(S>lastE、final)

||gen("if"S、first"〉"S、last"goto"S^next)

|gen(S>currS、first)

|gen(S>begin":")

|gen("if"S、curr"〉"S、Last"goto"S、next)

||SI、code

||gen(S、curr:=succ(S、curr))

|gen("goto"S、begin)

Efv:=initialtofinalE、init:=initial、place

E、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+i;

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、调用过程计算实参得值,并将它们得右值(rvalue)放在为形式单元开辟得空间中。

3、被调用过程执行时,就像使用局部变量一样使用这些形式单元。

“传地址”方式，也称作传地址,或引用调用。调用过程传给被调过程得就是指针，指向实参

存储位置得指针。

1、如实参就是一个名字或就是具有左值得表达式,则左值本身传递过去。

2、如实参就是一个表达式，比方a+b或2,而没有左值,则表达式先求值,并存入某一位置,

然后该位置得地址传递过去。

3、被调过程中对形式参数得任何引用与赋值都通过传递到被调过程得指针被处理成间接

访问。

例3:下面就是一个Pascal程序

programPP(input,output)

varK:integer;

functionF(N:integer):integer

begin

ifN<=0thenF:=l

elseF:=N*F(Nl);

end;

begin

K:二F(10);

end;

当第二次(递归地)进入F后,DISPLAY得内容就是什么？当时整个运行栈得内容就是什么?

解：

第十章

例1：何谓代码优化？进行优化所需要得基础就是什么？

解：

对代码进行等价变换，使得变换后得代码运行结果与变换前代码运行结果相同，而运

行速度加快或占用存储空间减少,或两者都有。

优化所需要得基础就是在中间代码生成之后或目标代码生成之后。

例2:编译过程中可进行得优化如何分类？最常用得代码优化技术有哪些？

解：

依据优化所涉及得程序范围,可以分为:局部优化、循环优化与全局优化。

最常用得代码优化技术有

1、删除多余运算2、代码外提3、强度削弱4、变换循环控制条件5、合并已知量与复

写传播6、删除无用赋值

例3:试对以下基本块B2:

B=3D=A+C

E二A*CF=D+E

G=B*FH=A+C

I=A*CJ=H+I

K=B*5L=K+J

M:=L

应用DAG对它们进行优化,并就以下两种情况分别写出优化后得四元式序列:

(1)假设只有G、L、M在基本块后面还要被引用。

(2)假设只有L在基本块后面还要被引用。

解：

基本块对应得DAG如下：

B:=3D:=A+C

E:=A*CF:=D+E

G:=B*FH:=A+C

I:=A*CJ:=H+I

K:=B*5L:=K+J

M:=L

例1一个编译程序得代码生成要着重考虑

些问题？

解：

代码生成器得设计要着重考虑目标代码得质量问题,而衡量目标代码得质量主要从占

用空间与执行效率两个方面综合考虑。

课后习题答案：

P366

(1)

就是0~9组成得数字串

(2)最左推导:

NnNDnNDDoNDDDnDDDDnODDDnQ1DD=>012Dn0127

NnNDnDDn3Dn34

N=ND=NDD=DDD=5DD=56D=568

最右推导：

NnNDn=ND7nN27nND21=>N127nDI27n0127

NnNDnN4no4n34

NnNDnN8nND8nN68nD68n568

P368

文法:

最左推导：

EnTnT*FnF*Fni*P=，*(E)=，*(E+T)=，*(T+T)=，*(P+T)

ni*(i+T)ni*(i+尸)=>，*(，+，)

最右推导：

E^>E+T^E+T*F^E+T*i^>E+F*i^>E+i*i^T+i*i^F+i*i^i+i*i

EnTnF*TnF*F>F*(E)=F*(E+T)nF*(E+F)nF*(E+i)

=>F*(T+i)=>F*(F+i)=>F*(i+i)=>i*(i+i)

:/********************************

EEE

P369

句子iiiei有两个语法树:

P64-7

确定化:

4o)1V/1

{X}{1,2,3)

巾巾巾

{1,2,3}{213}{2,3,4}

{213}{213}(2,3,4)

⑵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}

5

最小化:

P64-12

(a)

a

确定化:

ab

{0}{011}{1}

{0,1}{o,1}{1}

{1}{0}巾

6巾6

给状态编号:

ab

012

112

203

333

最小化:

(b)

a

ab

b

已经确定化了，进行最小化

最小化:

{{0,1},{2,3,4,5}}

{0,l}a={1}{0,1.={2,4}

{2,3,4,5}“={1,3,0,5}{2,3,4,5}〃={2,3,4,5}

{2,4}“={1,0}{2,4}〃={3,。

{3,5%={3,5}{3,5},={2,4}

{{0,1},{2,4},{3,5})

{0,1}“={1}{0,l}fc={2,4}

{2,4}“={1,0}{2,4卜={3,5}

{3,5}〃={3,5}{3,5}〃={2,4}

P81-1

(1)按照T,S得顺序消除左递归

递归子程序：

procedureS;

begin

ifsym=，a'orsym=''

thenabvance

elseifsym=，('

thenbegin

advance;T;

ifsym=')'thenadvance;

elseerror;

end

elseerror

end;

procedureT;

begin

S;

end;

procedure;

begin

ifsym=,

thenbegin

advance;

S;

end

end;

其中：

sym:就是输入串指针IP所指得符号

advance:就是把IP调至下一个输入符号

error:就是出错诊察程序

(2)

FIRST(S)={a/，(}

FIRST(T)={a/，(}

FIRST={,,}

FOLLOW(S)={),,,#}

FOLLOW(T)={)}

FOLLOW={)}

预测分析表

a()#

s

T

就是LL(1)文法

P81-2

文法：

(i)

FIRST(E)={(,a,b,1

FIRST(E))={+,e}

FIRST(T)={(,a,b,

FIRST(r)={(,a,b,\e}

FIRST(F)={(,a,b,4

FIRST(F')={*,«}

FIRST(P)={(,a,b,"}

FOLLOW(E)={#,)}

FOLLOW(E')={#,)}

FOLLOW(T)={+,),#}

FOLLOW。)=[+,),#}

FOLLOW(F)={(,a,b,',+,),#}

FOLLOWS)={(,a,b,',+,),#}

FOLLOW(P)={*,(,a,b,\+,),#}

(2)

考虑下列产生式：

FIRST(+E)AFIRST(e)={+}C{e}=6

FIRST(+E)AFOLLOW(E，)={+}G{#,)}二@

FIRST(T)AFIRST(£)={(,a,b,1G{&}二巾

FIRST(T)AFOLLOW(T)={(,a,b,1A什,)，#}二@

FIRST(*F5)AFIRST(£)={*}A{£}二巾

FIRST(*F')「FOLLOW(F')={*}Cl{(,a,b,\+,),#}=4)

FIRST((E))AFIRST(a)AFIRST(b)AFIRSTO=4

所以，该文法式LL⑴文法、

(3)

+*()ab-#

E

E'

T

T'

F

F'

p

(4)

procedureE;

begin

ifsym=，Corsym='a'orsym=，b'orsym=，

thenbeginT;E'end

elseerror

end

procedureE’;

begin

ifsym='+'

thenbeginadvance;Eend

elseifsym<>，)andsym<>，#'thenerror

end

procedureT;

begin

ifsym=，('orsym=，a'orsym=，b'orsym=，

thenbeginF;T'end

elseerror

end

procedureT';

begin

ifsym='('orsym='a'orsym=，b'orsym=，

thenT

elseifsym='*'thenerror

end

procedureF;

begin

ifsym='Corsym='a'orsym=，b'orsym=，

thenbeginP;F'end

elseerror

end

procedureF，;

begin

ifsym='*'

thenbeginadvance;F'end

end

procedureP;

begin

ifsym=，a'orsym=，b'orsym=，'

thenadvance

elseifsym=，('then

begin

advance;E;

ifsym=')'thenadvance

elseerror

end

elseerror

end;

P133-1

短语：E+T*F,T*F,

直接短语：T*F

句柄：T*F

P133-2

文法：

(D最左推导：

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)n(S,S)n((T),S)=>((T,S),S)=>((T,S,S),S)n((S,S,S),S)n((⑺,S,S),S)

n(((7,S),S,S)),S)n(((S,S),S,S),S)n(((a,S),S,S),S)n(((a,a),S,S),S)

一(((a,a),3S),S)n(((4,a),A,(T)),S)=>(((a,a)「,(S)),S)=(((a,a)J,(a)),S)

二>(((a,a),A,(a)),a)

最右推导：

Sn(T)n(T,S)n(T,(T))n(T,(T,S))n(T,(T,a))n(T,(S,a))n(T,(a,a))

=(S,(a,a))n(a,(a,a))

Sn(T,S)=>(T,d)n(S,a)n((T),a)=>((T,S),a)n((T,(T)),a)n((T,(S)),a)

=>((T,(a)),a)=((T,S,(a)),a)n((T,3(a)),a)=>((SJ,(a)),a)n(((T),3(a)),a)

=>(((T,S),A,(a)),a)(((T,a),A,(a)),a)=>(((S,a),A,(a)),a)=>(((a,a),A,(a)),a)

(2)

(((a,a),",(a)),a)

(((s,a),(a)),a)

(((T.a)/,(a)),a)

(((US)/.(a)),a)

((0)./,(a)),a)

((S/,(a)),a)

((T「，(a)),a)

((L_S,(a)),a)

((T,(a)),a)

((T,(S)),a)

((T,①),a)

((L_S)，a)

(组,a)

⑤a)

(LS)

(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)={,,…,)}

(2)

a()

a>>

八>>

(<<<=<

)>>

<<<>>

就是算符文法,并且就是算符优先文法

⑶优先函数

-

a()

f44244

g55523

(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得附注语法树如下图:

T、val=58

T、val=29*F、val=2

T、val=l

F、val=l

digit>lexval=7

F、val=4

digit>lexval=1

digit>lexval=4

P164-2

答：

(1)

+

L、type;addtype(id>t