编译原理试卷与复习

《编译原理》期终考卷2010

学号：姓名：

说明:1、本考卷中大写字母CVN，其他符号CVT，

2、试卷中一、二两题请作在考卷上

一、填空题（20分）

1、一般说来编译系统的编译过程分五步，它们分别

为、、、、o

2、计算机三大系统软件分别、、。

3、自上而下分析法的典型算法是、两类。

二、判断题（10分。注：每答对一题得+2分；答错一题得-2分；不答者得。分）

1、设E为{a,b},则a,ba,{£},。都是Z上的正规式。（）

2、对于上下文无关文法G[S],若S=>aAB=aBy则A—'一定是一条产生式规则，

其中a,p,yG（VTWN）*（）

3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）

4、LR（0）分析法是--种规范归约法。（）

5、算符优先分析法只能用来分析算符优先文法。（）

三、（20分）

1、设E={a,b,c）,设计一个DFAM,它识别所有以b开头且只允许出现一个b的

字。

2、用程序实现DFAM的功能。

四、下列文法如果是LL⑴文法，请求其预测分析表；如果不是，请说明理由（本题20分）

A—AaBlB

B—BeFlF

F->f

六、（30分）有作控制用的布尔表达式文法G[E]及其语义动作如下:

文法G[E]：

⑴卜尸产。{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J<,ENTRY(i'7),ENTRY(i10,0);GEN(J,0)}

(2)E->AEW{E.FC:=EW.FC;E.TC:=MERGE(A.TC,EW.TC))

(3)A->BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC)

⑷B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY0);GEN(J,0)}

1、构造SLR（1）分析表（若不是SLR（l））的，则说明理由）

2、使用语法制导翻译法分析作控制用的布尔表达式a<bVc的四元式生成过程，并画

出最后的真假链表。

3、给出语句IFa<bVcTHENI:=m*nELSEI:=m+n的完整四元式序列。

《编译原理》软件工程2005级期终考卷

学号：姓名：

说明：1.本考卷中大写字母GVN，其他符号GVT，2、试卷中一、二两题请作在考卷上

一、概念题（15分）

1、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？

2、对下列状态转换图，写出状态0的处理过程:

字母

其中：状态2的过程为proc2.

3、文法G为：

S—aAB

A—a

B-、切，

则判断G为LL（1）文法的条件是：

二、判断题（10分。注：每答对一题得+2分；答错一题得-2分；不答者得0分）

1、设Z为{a,b},贝Ua,ba,{£},。都是E上的正规式。（）

2、对于上下文无关文法G[S],若S=aAB=apY则A->7一定是一条产生式规则，

其中a，B，yG（VTVVN）*（）

3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）

4、LR（0）分析法是一种规范归约法。（）

5、算符优先分析法只能用来分析算符优先文法。（）

三、（10分）设文法G3为：S—AaBc

A—Aala

B-*b

求句型AaBc的最左素语。

四、（20分）设文法G[S]为

S—aAcB问：1、该文法是否为算符文法，为什么？

A->Ab|b2、构造算符优先关系表。

B->d3、该文法是否可改造为LL（1）文法，为什么？

五、（本题20分）设文法G为：E—eAfleBg

A—aA|a

B—Bb|a

对于输入串eaaaf,采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。

六、（25分）有作控制用的布尔表达式文法G［E］及其语义动作如下：

1、构造SLR（1）分析表（若不是SLR（l））的，则说明理由）

2、分析布尔式aVb<c的四元式生成过程，并画出最后的真假链表。

3、给出语句IFaVb<cTHENI:=m*nELSEI:=m+n的完整四元式序列。

文法G［法:

⑴「严0⑵{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J〈,ENTRY(i™),ENTRY(i(2)),0);GEN(J,0)}

(2)E->AE(I){E.FC:=EW.FC;E.FC:=MERGE(A.TC,EW.TC)}

(3)A—BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}

(4)B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY(i),_,0);GEN(J,0)}

常见问题

自顶向下分析算法

带回溯的自顶向下分析

主旨：对任何输入串试图用一切可能的方法，从根节点（文法开始符号）出发，自上而下地

为输入串建立一棵语法树。其本质是一种试探法。

S——>cAd

例.A输入串0=

存在的问题：

1.若文法是左递归的（沏使P=pa）则分析会陷入死循环

2.存在回溯

3.效率低

自下向上分析基本问题

归约

我们所讨论的自下而上分析法是一种“移进-归约”法。这种方法的大意是，用一个寄

存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个侯

选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

例：假定文法G为：

(1)S-*aAcBe

(2)A-b

(3)A-Ab

(4)B-d

我们希望把输入串abbcde归约到S,则符号栈的变化情形如下：

步骤：12345678910

动作：进进归进归进进归进归

ab(2)b(3)cd(4)e(1)

e

dBB

bcccc

bAAAAAAA

aaaaaaaaaS

SLR分析表的构造

—.LR(0)存在的问题

LR(0)虽简单，但很少见，如叫不是LR(0)的。

解决办法

A->a»

若项目集4中有：CTa•3，分析所有含A和B的句型，考察所有可能直接跟在

A和B之后的终结符，如果它们不相交且都不含b,那么当状态I面临任何输入符号a时,

可采取如下移进一归约策略。

1.a=b时,移进

2,若"及亚的则用d•归约。

3,若ae7fos犷(也则用3Ta•归约。

4.其他，出错。

一般而言，如果某LR(0)项目集I中含有m个移进项目，

AT同时有0个归约项目&TG-,Ba。若

{.,-一-=,1«国皿。鹏)，….质龙〃溜(纥)两两不相交，则动作冲突可通过检查当前输入

符号a属于哪个集合而决定。

因为只看一个符号，所以称为SLR⑴方法(简单LR(1))

总结性习题一

第一章编译程序概述

1.1什么是编译程序

编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个

高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构

编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来

讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式

转换成另一种表示形式，各个阶段进行的操作在逻辑匕是紧密连接在一起的。■般一个编译

过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个

阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序

的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作:

表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种

不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格

管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的

地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被

编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。图1.1表示了编译

的各个阶段。

图1.1编译的各个阶段

1.3高级语言解释系统

为了实现在一个计算机上运行高级语言的程序，主要有两个途径：第一个途径是把该程

序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。第二个途径是编写

一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就

叫解释程序。从功能上说，一个解释程序能让计算机执行高级语言。它与编译程序的主要不

同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义,

执行相应的动作。

第二章：高级语言及其语法描述

问答第1题

写一文法，使其语言是偶正整数的集合。要求:

(1)允许0打头；

(2)不允许0打头。

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

E-*NT|D

T-NT|D

N-Dl1|3|5|7|9

Df0|2|4|6|8

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

E-NT|D

T-FT|G

N-*D|1|3|5|7|9

D-2|4|6|8

F-N|O

G-D|O

问答第2题

证明下述文法G［〈表达式〉］是二义的。

〈表达式〉：:=a|（〈表达式〉）|〈表达式〉

〈运算符〉〈表达式〉〈运算符〉：：=+IT*M

答：可为句子a+a*a构造两个不同的最右推导：

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

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

n〈表达式〉*:a

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

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

n〈表达式〉4a*a

na+a*a

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

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

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

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

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

n〈表达式〉」a*a

na+a*a

问答第3题

令文法G［E］为:

E—T|E+T|E-T

…F|T*F|T/F

Ff（E）|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

答：因为存在推导序列：E=E+T=E+n*F所以E+T*F是文法G[E]的一个句

句型E+T*F的

短语有:E+T*F,T*F

直接短语有：T*F

句柄为：T*F

问答第4题

给出生成下述语言的上下文无关文法:

(1){a"b"a°b°|n,m>=0}

(2){1"OB1°0"n,m>=0}

答：⑴S-AA

A-«-aAb|e

(2)

S-*1SO|A

A-OA1|e

问答第5题

给出生成下述语言的三型文法：

(1){anbm|n,m>=l}

(2){anbBckIn,m,k>=0}

答：⑴S-aA

AfaA|B

B->bB|b

(2)A-aA|B

B-*bB|C

C-*cC|£

问答第6题

给出下述文法所对应的正规式：

S-OA|1B

A-1S|1

B-OS0

答：R=(01|10)(01|10)”

第三章：词法分析

问答第1题

构造正规式1(01)*101相应的DFA.

答：先构造NFA：

用子集法将NFA确定化

01

XA

AAAB

ABACAB

ACAABY

ABYACAB

除X,A外，重新命名其他状态，令AB为B、AC为C、ABY为D,因为D含有Y(NFA的

终态)，所以D为终态。

01

XA

AAB

BCB

CAD

DCB

DFA的状态图：：

问答第2题

将下图确定化:

解：

用子集法将NFA确定化:

01

SVQQU

VQVZQU

QUVQUZ

VZZZ

VZ

QUZVZQUZ

ZZZ

重新命名状态子集，令VQ为A、QU为B、VZ为C、V为I）、QUZ为E、Z为F。

01

SAB

ACB

BDE

CFF

DF

ECE

FFF

no：终态组{0},非终态组{1,2,3,4,5}

对非终态组进行审查：

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

而{0,1,3,5}既不属于{0},也不属于{1,2,3,4,5}

•••{4}aU{0},所以得到新分划

ni：{0},⑷，{1,2,3,5}

对{1,2,3,5}进行审查：

V{1,5}bC{4}

{2,3}bu{l,2,3,5},故得到新分划

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

{115}aC{1,5}

{2,3}ac{l,3},故状态2和状态3不等价，得到新分划

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

这是最后分划了

最小DFA：

问答第4题

构造一个DFA,它接收£={0,1}上所

有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。

解：按题意相应的正规表达式是(0*10)*。*,或0*(010)*0*构造相应的DFA,首先构

造NFA为

用子集法确定化:

I1011

{X,0,1,3,Y)(0,1,3,Y){2}

(0.1.3.Y){0,1,3,Y){2}

{2}{1,3,Y}

{1.3.Y}{1,3,Y)⑵

重新命名状态集:

S01

123

223

34

443

DFA的状态图:

可将该DFA最小化：

终态组为（1,2,4},非终态组为{3},{1,2,4}0{1,2,4},

{1.2.4J1{3},所以1,2,4为等价状态，可合并。

第四章语法分析一自上而下分析

（一）

问答第1题

对于文法正,输入串GF+G的分析步骤如下:

步骤符号栈输入串动作

0#预备

1F+G#进

2#EF+G#归，用芭—

3#E*进

4#E*G+G#进

5#E*E+G#归，用E---->x

6#E+G#归，用石----

7#E+Q#进

8#E+Gn进

9#E+E#归，用芭----

10#E#归，用E

11ttE#接受

问答第2题

文法的另一种表示法

优点：便于消除左递归

I.用㈤

2.用㈤"表示口可重复0~17次

3,用时"用

4,用㈤：=£

用这种表示法，写出算术表达式文法的递归下降子程序

E->{*7}

T->用仔尸}

解：文法为尸T㈤W,递归子程序为：

PROCEDUREE;

BEGIN

T;

whilesym='+'do[advance;T]

END;

PROCEDURE?;

BEGIN

F;

whilesym='*'do[advance;F]

END;

PROCEDUREF;

BEIGN

ifsym='i'then

[advance;E;

ifsym=^)^thenladvance;return]

elseerror;]

elseerror;

END;

问答第3题

文法，

T->T*F|F

尸T(功i

有FIRST(+T)={+},FIRST(f)={(,i),FIRST(E)=FIRST(T)=FIRST(F)

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

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

问答第4题

文法有HRST(E)=HRST(T)=FIRST(F)={(,i),

E'+TE'|E

T

产-

FIRST(E')={+,£},FIRST(T')={*,£}

FOLLOE(E)={#,}},FOLLOE(E,)=FOLLOE(E),

FOLLOW(T,)=FOLLOE(T)=FIRST(E,)\{c}+FOLLOW(E,)={+,#,}),

FOLLOE(F)=FIRST(T,)\{£}+FOLLOE(T)={*,+,#,),}

问答第5题

S—>aAcBe

A-^Ab\b

文法B—d,试用LL(1)分析法分析输入串abbcde.

S—>aAcBe

A-^hA

解：①消除左递归得文法(无公共左因子)：3Td

②求必要的FIRST和FOLLOWo

FIRST(aAcBe)={a}

FIRST(bA')={b}

FIRST(£)={£}

FIRST(d)={d}

FOLLOW(A,)=FOLLOW(A)={c}

③构造LL⑴分析表

abcde#

SAA'BaAcBebA'£d

④分析

aabbbb0cdd,0

323232323221

第四章语法分析一自上而下分析(二)

问答第1题

对文法G[S]

S-a|Al(T)

T-T,S|S

(1)给出(a,(a,a))和(((a,a),八，(a)),a)的最左推导。

(2)对文法G,进行改写，然后对每个非终结符写出不带回溯的递归子程序。

(3)经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。

答：文法

S-a|Al(T)

T-T,S|S

(1)对(a,(a,a)的最左推导为：

sn(T)

N(T,s)

n(s,s)

n(a,s)

n(a,Cr))

n(a,(T,S))

(a,(S,S))

n(a,(a,S))

(a,(a,a))

对(((a,a),八，(a)),a)的最左推导为：

sn(T)

N(T,s)

n(s,s)

n((D,s)

N((T,s),s)

n((T,s,s),s)

n((s,s,s),s)

=>(((T),S,S),S)

n(((T,s),s,s),s)

n(((s,s),s,s),s)

=H((a,S),S,S),S)

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

n(((a,a),A,S),S)

n(((a,a),A,(T)),S)

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

=H((a,a),A,(a)),S)

n(((a,a),A,(a)),a)

(2)改写文法为：

0)S-a

1)S-A

2)S-(T)

3)T->SN

4)N-,SN

5)N-*e

非终结符FIRST集FOLLOW集

S{a,A,(){#,,,)}

T{a,A,(){)}....

N{,,e}.{)}....

对左部为N的产生式可知：

FIRST,SN)={,}

FIRSTe)={e}

FOLLOW(N)={)}

由于SELECT(NSN)ASELECT(N-e)={,}n{)}=0

所以文法是LL(1)的。

预测分析表(PredictingAnalysisTable)

aA()#

—►

s-a-A

(T)

fsfs

TfSN

NN

-A―►>

N

ESN

也可由预测分析表中无多重入口判定文法是LL(1)的。

(3)对输入串(a,a)井的分析过程为:

栈当前输入符剩余输入符所用产生式

(STACK)(CUR.CHAR)(IN0UT_STRING)(OPERATION)

#S(a,a)#...

#)T((a,a)#...S-(T)

#)Ta,a)#...

tt)NSa,a)#...T-SN

#)Naa,a)#...Sfa

tt)Na)#…•

#)NS,a)#...Nf,SN

tt)NSa)#...•

#)Naa)#...S-a

#)N)#...*

#))#・・.Nf£

##

可见输入串(a,a)#是文法的句子。

问答第2题

已知文法G[S]：

S-MH|a

H-LSo|E

KfdML|e

L-*eHf

MT|bLM

判断G是否是LL(D文法，如果是，构造LL(1)分析表。

答：文法：

S-MH|a

H-LSo|e

K-dML|e

L-eHf

MT|bLM

展开为：

0)S-MH

1)S—a

2)H-LSo

3)-e

4)K-*dML

5)"£

6)LfeHf

7)M-K

8)M-bLM

非终

FIRST集FOLLOW集

结符

{a,d,b,{#,。}......

S

£,e}

{d,{e,tt,o}.........

M

£,b}….

{£,e}・・・.{#,f.o}……

H

{e}..............{a,d,b,e,o,#

L

}

{d,{e,#,o).........

K

e)............

对相同左部的产生式可知:

SELECT(S-MII)ASELECT(S-a)={d,b,e,#,o}A{a}=0

SELECT(H-LSo)nSELECT(H-e)={e}n{#,f,o}=0

SELECT(K-dML)nSELECT(K-e)={d}C{e,#,o}=0

SELECT(M-K)nSELECT(M-bLM)={d,e,tt,o}n{b}=0

所以文法是LL(1)的。

预测分析表(PredictingAnalysisTable)

a0defbn

―►―►

S—MHTHfMH

aMHMH

-A

M-K-K-K一K

bLM

II―►-A--A

ELSo£e

―►

L

eHf

―►—►—►

K—e

£dMLe

由预测分析表中无多重入口也可判定文法是LL⑴的。

问答第3题

对于一•个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面

文法进行改写，并对改写后的文法进行判断。

(1)A-aABe|a

B-Bb|d

(3)S-Aa|b

AfSB

Bfab

答：(1)文法：

AfaABe|a

B-*Bb|d

提取左公共因子和消除左递归后文法变为：

0)A-aN

1)N-ABe

2)N-e

3)B-dN1

4)Nl-bN1

5)Nl-E

非终结FIRST

FOLLOW集

符集

A{a}...{#,d}

B{d}...{e}..

N{a,e}{#,d}

Nl{b,e}{e}・.

对相同左部的产生式可知：

SELECT(N-ABe)nSELECT(N-e)={a}n{礼d}=0

SELECT(Nl-bNl)nSELECT(Nl-c)={b}D{e}=0

所以文法是LL⑴的。

预测分析表(PredictingAnalysisTable)

aebd#

AfaN

—►d

B

N1

N一b

1eN1

—►

Nfe

ABee

也可由预测分析表中无多重入口判定文法是LL(D的。

(2)文法:

S-*Aa|b

A-SB

B-ab

第1种改写：

用A的产生式右部代替S的产生式右部的A得：

S-SBa|b

B—ab

消除左递归后文法变为：

0)S-bN

1)NTaN

2)N-e

3)B-ab

非终结FIRST

FOLLOW集

符集

s{b}・・.{«}

B{a}...{a}

N{e,a}{#}

对相同左部的产生式可知：

SELECT(N-BaN)nSELECT(N->e)={a}n(#}=0

所以文法是LL(1)的。

预测分析表(PredictingAnalysisTable)

也可由预测分析表中无多重入口判定文法是LL(1)的。

第2种改写：

用S的产生式右部代替A的产生式右部的S得：

S-Aa|b

A-AaB|bB

B-*ab

消除左递归后文法变为：

0)AAa

1)S->b

2)AiBN

3)N-aBN

4)N-e

5)Bfab

非终结FIRST

FOLLOW集

符集

s{b}...{#}

A{b}...{a}

B{a}...{a}

N{a,£}{a}

对相同左部的产生式可知：

SELECT(S-Aa)ASELECT(S-b)={b}n{b}={b}W0

SELECT(N-aBN)nSELECT(N->e)={a}n{a}={a}W0

所以文法不是LL(1)的。

预测分析表(PredictingAnalysisTable)

ab

sfAa..

fb....

AfbBN

fa

B

b..

NfaBN

-A

e...

也可由预测分析表中含有多重入口判定文法不是LL(1)的。

第五章语法分析一自下而上分析

问答第1题

已知文法G[S]为：

S-a|Al(T)

T-T,S|S

(1)计算G[S]的FIRSTVT和LASTVTo

(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。

(3)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

答：文法：

S--a|A|(T)

T-T,S|S

展开为：

Sfa

S-A

SfCD

T-*T,S

T-S

(1)FIRSTVT—LASTVT表

非终结

FIRSTVT集LASTVT集

符

{aA(a

s

()..A)}..

{aA(a

T

(,}A),}

(2)算符优先关系表(OPERATERPRIORITYRELATIONTABLE)

aA()>#

>>>

A<<<>>>

(■<

)<<<

<<<>>>

>>

—

表中无多重人口所以是算符优先(OPG)文法。

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

当前输

栈剩余输入串动作

入字符

(STACK)(INPUT_STRING)(ACTION)

(CHAR)

a,a)#...Movein

,3.).Movein

#(

a)#...Reduce:S

#(a

a)#...-*a

#(a

)#,・.Movein

#(N

#.•.Movein

«(N,a

Reduce:S

#(N,a)

a

#(N,N)

Reduce:T

#(N)

-T,S

#(N)#

Movein

#N#

Reduce:S

f⑴