计算机编译原理试卷

《计算机编译原理》试卷AI参考答案

一、单项选择题（每小题1分，共25分）

1、语言是A

A、句子的集合B、产生式的集合C、符号串的集合D、句型的集合

2、编译程序前三个阶段完成的工作是C

A、词法分析、语法分析和代码优化

B、代码生成、代码优化和词法分析

C、词法分析、语法分析、语义分析和中间代码生成

D、词法分析、语法分析和代码优化

3、一个句型中称为句柄的是该句型的最左______D

A、非终结符号B、通语C、句子D、直接短语

4、下推自动机识别的语言是C

A、0型语言B、1型语言C、2型语言D、3型语言

5、扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法

单位即B

A、字符B、单词C、句子D、句型

6、对应Chomsky四种文法的四种语言之间的关系足B

A、L0CL1UL2UL3B、LsuLjaLiuLoC、L3=L2<ZLICL（）D、L（）（ZLICL2=L3

7、词法分析的任务是A

A、识别单词B、分析句子的含义C、识别句子D、生成目标代码

8、常用的中间代码形式不含D

A、三元式B、四元式C、逆波兰式D、语法树

9、代码优化的目的是C

A、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价交换

10、代码生成阶段的主要任务是C

A、把高级语言翻译成汇编语言

B、把高级语言翻译成机器语言

C、把中间代码变换成依赖具体机器的目标代码

D、把汇编语言翻译成机器语言

11、一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符

号，以及一组Bo

A、字符串B、产生式C、数字符号D、文法

12、程序的基本块是指D。

A、一个子程序B、一个仅有一个入口和一个出口的语句

C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口

13、高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方

法。

A、自左向右B、自顶向下C、自底向上D、自右向左

14、在通常的语法分析方法中，A特别适用于表达式的分析。

A、算符优先分析法B、LR分析法

C、递归下降分析法D、LL（1）分析法

15、经过编译所得到的目标程序是Do

A、四元式序列B、间接三元式序列

C、二元式序列D、机器语言程序或汇编语言程序

16、一个文法所描述的语言是Ao

A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、无法确定

17、描述一个语言的文法是Co

A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、以上都不正确

18、设有文法G[I]：I-*Il|IO|Ia|Ic|a|b|c

下列符号串中是该文法句子的有Bo

①abO②aOcOl③aaa®bclO

可选项有：

A、①B、®®®C、③④D、®®®®

19、运行阶段的存储组织与管理的目的是_____C______o

①提高编译程序的运行速度②节省编译程序的存储空间

③提高FI标程序的运行速度④为运行阶段的存储分配做准备

可选项有：

A、①②B、②③C、③④D>@@

20、将编译程序分成若干个“遍”是为了Bo

A、提高程序的执行效率

B、使程序的结构更加清晰

C、利用有限的机器内存并提高机器的执行效率

D、利用有限的机器内存但降低了机器的执行效率

21、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标

代码生成等五个部分，还应包括C。

A、模拟执行器B、解释器C、表格处理和出错处理D、符号执行器

22、一个句型中的最左_____B称为该句型的句柄。

A、短语B、简单短语C、素短语D、终结符号

23、设G是一个给定的文法，S是文法的开始符号，如果(其中xWV*)，则称x是文法G

的一个Bo

A、候选式B、句型C、单词D、产生式

24、一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号,

一个开始符号，以及一组_____D。

A、句子B、句型C、单词D、产生式

25、文法G[E]：

E-*T|E+T

T-FIT*F

F-aI(E)

该文法句型E+F*(E+T)的简单短语是下列符号串中的B。

①(E+T)②E+T®F④F*(E+T)

可选项有：

A、①和③B、②和③C、③和④D、③

二、判断题(每小题1分，共1。分)

(J)26、对任意一个右线性文法G,都存在一个NFAM,满足L(G)=£M)。

(J)27、对任意一个右线性文法G,都存在一个DFAM,满足L(G)=L(M)。

(J)28、对任何正规表达式e,都存在一个NFAM,满足L(G尸L(e)。

（J）29、对任何正规表达式e,都存在一个DFAM,满足L（G）=L（e）。

（X）30、计算机高级语言翻译成低级语言只有解释一种方式。

（X）31、在编译中进行语法检查的目的是为了发现程序中所有错误。

（X）32、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统

功能完全相同。

（J）33、正则文法其产生式为Afa,AfBb,A,B£VN,a、b£V「

（X）34、每个文法都能改写为LL（1）文法。

（J）35、递归下降法允许任一非终极符是直接左递归的。

三、名词解释题（每小题4分，共8分）

36、归约

我们称a丫8直接归约出aAB,仅当A-丫是一个产生式，且a、pG（VNUVT）*o归约

过程就是从输入串开始,反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。

37、推导

我们称aAB直接推出a丫B,即aAB=a），B,仅兰A-Y是一个产生式，且a、BW

（VNUVT）*O如果aQUQ…=Qn，则我们称这个序列是从aI至a2的一个推导。若存在

一个从a।a”的推导，则称a।可推导出推导是归约的逆过程。

四、简答题（每小题4分，共8分）

38、试给出非确定自动机的定义。

答：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K,2,f,S,Z）。

其中：

（1）K是一个有穷集，它的每个元素称为一个状态：

（2）2是一个有穷字母表，它的每个元素称为一个输入符号，所以也称2为输入符号表；

（3）f是状态转换函数，是在KX二*-K的子集的映射，即，f:KX，*-2K；表明在某

状态下对于某输入符号可能有多个后继状态；

（4）S（K是一个非空初态集；

（5）Z（K是一个终态集（可空）。

39、编译程序的工作分为那几个阶段？

答：词法分析、语法分析和语义分析是对源程序进行的分析（称为编译程序的前端），而中间

代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合（称为编译程序的后端），

它们从源程序的中间表示建立起和源程序等价的目标程序。

五、应用题（每小题5分，共25分）

40、对于文法G[S]：S->AB,A-»Aa|bB,Bfa|Sb求句型baSb的全部短语、直接短语和句

柄？

句型baSb的语法树如下图所示。

答：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型

baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语

和句柄。

41、设有非确定的有自限动机NFAM=({A,B,C},{0,1},5,{A},{C}),其中：

5(A,0)={C)8(A,l)=；A,B)8(B,1)={C)8(C,1尸{C}。请画出状态转换距阵和状

态转换图。

答：状态转换距阵为：

状态转换图为:

42、文法G[S]：

S->aSPQ|abQ

QP—PQ

bP—>bb

bQ—>bc

cQ—>cc

(1)它是Chomsky哪一型文法？

(2)它生成的语言是什么？

答：

(1)由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部

的符号长度，所以文法G[S]是Chomskyl型文法，即上下文有关文法。

(2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到：

S=>abQ=>abc

S=>aSPQ=>aabQPQ=>aabPQQ=>aabbQQ=>aabbcQ=>aabbcc

S=aSPQ=aaSPQPQ=aaabQPQPQ=aaabPQQPQ=aaabPQPQQ=aaaPPQQQ=

aaabbPqqq=>aaabbQQQ=>aaabbbcQQ=>aaabbbccQ=>aaabbbccc

••••••

于是得到文法G[S]生成的语言L={anbncn|n>l}

43、下面文法G[S]是否为LL(1)文法？说明理由。

S-*AB|PQxA-*xyB-*bc

P—dP|eQ-*aQ|e

答：该文法不是LL(1)文法。

只有三个非终结符有两个选择。

(1)P的两个右部dP和£的开始符号肯定不相交。

(2)Q的两个右部aQ和£的开始符号肯定不相交。

(3)对S来说，由于xWFIRST(AB)，同时也有x匹FIRST(PQx)(因为P和Q都可能为空)。

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

44、设有文法G［法:

SfaA

A-*Ab

A-*b

求识别该文法所有活前缀的DFAO

答：

(1)首先拓广文法：

在G中加入产生式O.S'T,然后得到新的文法G':

O.S'-S

l.S-aA

2.AfAb

3.A-*b

⑵再求G'的识别全部活前缀的DFA：

六、综合题(每小题8分，共24分)

45、对给定正规式b*(d|ad)(b|ab)\构造其NFAM。

答：首先用A十二AA"改造正规式得：b\d|ad)(b|ab)(b|ab)fr；其次，构造该正规式的NFAM,如

下图所示。

46、将文法G[V]改造成为LL(1)的。

G[V]：V-*N|N[E]

E-*V|V+E

N-i

答：对文法G[V]提取公共左因子后得到文法:

G，V]：V-NA

A-*£||E]

E-VB

B-*F|+E

N-i

求出文法G[V]中每一个非终结符号的FIRST集：

FIRST(V)={i}FIRST(A)={L£)

FIRST(E)={i}FIRST(B)={+,e}

FIRST(N)={i}

求出文法G1V]中每一个非终结符号的FOLLOW集：

FOLLOW(V)={#}UFIRST(B)\{£}UFOLLOW(E)={#,+,]}

FOLLOW(A)=FOLLOW(V)={+„#}

rOLLOW(E)=FIRST(])\{s}UFOLLOW(B)=FIRST(])\{e}UFOLLOW(E)={]}

FOLLOW(B尸FOLLOW(E尸{]}

FOLLOW(N)=FIRST(A)\{£}UFOLLOW(V尸{[,],+,#}

可以看到，对文法G'[V]的产生式A-£|[E],有

FIRST([E])nFOLLOW(A)={[}A{+,],#}=0

对产生式B-£|+E,有

FIRST(+E)AFOLLOW(B)={+}Q[]}=0

而文法的其他产生式都只有一个不为&的右部，所以文法G'[V]是LL(1)文法。

47、对于文法G[S]：S->AS|bA->SA|a

(1)列出所有LR(0)项目

(2)列出构成文法LR(0)项目集规范族。

答：

首先将文法G拓广为G[S]

S'-S

S-*AS|b

A~SA|a

(1)文法G[S]的LR(0)项目是:

1、S'->・S5、S-*AS•9、A-*S•A

2、S'-S・6、S--b10、A-SA・

3、S一•AS7、S-b・11、A-*,a

4、S-A-S8、A-,SA12、A-*a•

(2)列出构成文法LR(0)项目集规范族。

用c-CLOSURE(闭包)办法构造文法G，的LR(0)项目集规范族如下:

Io：1、S'f・SI3：9、A-S・Ak：12、A—a•

3、S-*・AS8、Af・SAI7：7、S-*b・

8、A--SA3、S--AS

11、A-*,a6、S-**b

6、S--b11>A1•a

Ii：2、S'-*S・I4：1()、ATA・

9、AfS•A4、S-A-S

8、A-*•SA3、S-*・AS

11、A-**a6、S-・b

3、S--AS8、Af・SA

6、S--b11、A-*•a

I2：4、S-A・SI5：5、S-AS・

3、S—,AS9、AfS•A

6、S-**b8、Af・SA

8、A—・SA11、A-**a

11、A一•a3、S-*・AS

6、S-・b

h中的S，-S•和A--SA是由状态Io中的1和3读入一个S字符后得到的下一个项目,

而L中的A-SA和AfA•S则是由b中的9和3读入一个A字符后得到的下一个项目;

K中的S»AS•和A»S-A则足由L中的4和8读入一个S字符后得到的下一个项目。

状态全体构成了文法G，的LR(0)规范族。

《计算机编译原理》试卷A2参考答案

一、单项选择题(每小题I分，共25分)

1、构造编译程序应掌握D。

A、源程序B、目标语言C、编译方法D、以上三项都是

2、变量应当_____Co

A、持有左值B、持有右值

C、既持有左值乂持有右值D、既不持有左值也不持有右值

3、编译程序绝大多数时间花在D上。

A、出错处理B、词法分析C、目标代码生成D、管理表格

4、D不可能是目标代码。

A、汇编指令代码B、可重定位指令代码

C、绝对指令代码D、中间代码

5、使用A可以定义一个程序的意义。

A、语义规则B、词法规则C、产生规则D、词法规则

6、词法分析器的输入是Bo

A、单词符号串B、源程序C、语法单位D、目标程序

7、中间代码生成时所遵循的是Co

A、语法规则B、词法粉则C、语义规则D、等价变换规则

8、编译程序是对Do

A、汇编程序的翻译B、高级语言程序的解释执行

C、机器语言的执行D、高级语言的翻译

9、文法G：S—xSx|y所识别的语言是C。

A、xyxB>(xyx)*C、xnyxn(n>0)D、x*yx*

10、文法G描述的语言L(G)是指Ao

A、L(G)={a|S^a,aGVT*}B、L(G)={a|S=^a,aeVT*}

C、L(G)={a|S^a,ae(VTUVN*)}D、L(G)={a|S^a,ae(VTUVN*)}

11、有限状态自动机能识别Co

A、上下文无关文法B、上下文有关文法

C、正规文法D.短语文法

12、设G为算符优先文法，G的任意终结符对a、b有以下关系成立C

A、若f(a)>g(b),则a>bB、若f(a)vg(b),则avb

C、A~B都不一定成立D、A~B一定成立

13、如果文法G是无二义的，则它的任何句子aA。

A、最左推导和最右推导对应的语法树必定相同

B、最左推导和最右推导对应的语法树可能不同

C、最左推导和最右推导必定相同

D、可能存在两个不同的最左推导，但它们对应的语法树相同

14、由文法的开始符经0步或多步推导产生的文法符号序列足C

A、短语B、句柄C、句型D、句子

15、文法G：E—E+TIT

T—T*P|P

P-(E)|I

则句型P+T+i的句柄和最左素短语为Bo

A、P+T和iB、P和P+TC、i和P+T+iD、P和T

16、设文法为：S—SA|A

A—>a|b

则对句子aba,下面D是规范推导。

A、S=>SA=>SAA=>AAA=>aAA=>abA=>aba

B、S=>SA=>SAA=>AAA=>AAa=>Aba=>aba

C、SnSAnSAAnSAanSbanAbanaba

D、S=>SA=>Sa=>SAa=>Sba=>Aba=>aba

17、文法G：S->b|A(T)

T->T,S|S

则FIRSTVT(T)Co

A、{b,A,(}B、{b,A,»C、{b,八}D、［b,A,),，)

18、产生正规语言的文法为D。

A、0型B、1型C、2型D、3型

19、采用自上而下分析，必须C。

A、消除左递归B、消除右递归C、消除回溯D、提取公共左因子

20、在规范归约中，用B来刻画可归约串。

A、直接短语B、句柄C、最左素短语D、素短语

21、若一个文法是递归的，则它所产生的语言的句子Ao

A、是无穷多个B、是有穷多个C、是可枚举的D、个数是常量

22、词法分析器用于识别C。

A、句子B、句型C>单词D、产生式

23、在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是B

A、非终极符集B、终极符集C、字母表D、状态集

24、编译程序中语法分析器接收以A为单位的输入。

A、单词B、表达式C、产生式D、句子

25、在LR分析法中，分析栈中存放的状态是识别规范句型C的DFA状态。

A、句柄B、前缀C、活前缀D、LR(0)项目

二、判断题(每小题1分，共10分)

(J)26、文法S->aS|bR|£R—cS描述的语言是(a|bc)*

(X)27、在自下而上的语法分析中，语法树与分析树一定相同。

(X)28、二义文法不是上下文无关文法。

(X)29、语法分析时必须先消除文法中的左递归。

(X)30、规范归约和规范推导是互逆的两个过程。

(X)31、一个文法所有句型的集合形成该文法所能接受的语言。

(X)32、一个有限状态自动机中，有且仅有一个唯一终态。

(X)33、设r和s分别是正规式,则有L(r|s)=L(r)|L(s).

(X)34、自动机M和M'的状态数不同，则二者必不等价。

(J)35、确定的自动机以及不确定的自动机都能正确地识别正规集。

三、名词解释题(每小题4分，共8分)

36、短语

设G[Z]是给定文法，w=xuyev+,为该文法的句型，如果满足下面两个条件：

①Z二xUy；

②U当u：

则称句型xuy中的子串u是句型xuy的短语。

37、简单短语

设G[Z]是给定文法，w=xuyEV+,为该文法的句型，如果满足下面两个条件：

①Z二xUy；

②Unu；

则称句型xuy中的子串u是句型xuy的简单短语(或直接短语)。

四、简答题(每小题4分，共8分)

38、给出上下文无关文法的定义。

答：

一个上下文无关文法G是一个四元式(VT,VN,S,P),其中：

•VT是一个非空有限集，它的每个元素称为终结符号；

•VN是一个非空有限集，它的每个元素称为非终结符号，vTnvN=<i>；

•S是一个非终结符号，称为开始符号；

•P是一个产生式集合(有限)，每个产生式的形式是P-a,其中，P£VN，ae(VTUVN)*o

开始符号S至少必须在某个产生式的左部出现一次。

39、简述DFA与NFA有何区别？

答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个

开始状态。另一方面，DFA的映象M是从KXZ到K,而NFA的映象M是从KXZ到K

的子集，即映象M将产生一个状态集合(可能为空集)，而不是单个状态。

五、应用题(每小题5分，共25分)

40、已知文法G[E]为:

E-*T|E+T|E-T

T-F|T*F|T/F

Ff(E)|i

①该文法的开始符号(识别符号)是什么？

②请给出该文法的终结符号集合VT和非终结符号集合VN.

③找出句型T+T*F+i的所有短语、简单短语和句柄。

解：①该文法的开始符号(识别符号)是E。

②该文法的终结符号集合V产什、-、*、/、(、)、i｝。

非终结符号集合VN=｛E、T、F｝。

③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;

简单短语为i、T*F、第一个T;句柄为第一个T。

41、已知文法G[S]为：

S-*dAB

A»aA|a

B-*Bb|e

①G[S]产生的语言是什么？

②G凶能否改写为等价的正规文法？

解:①G[S]产生的语言是L(G[S]尸｛daW|n21,m20)。

②G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[S]为：

S'-dA

A-*aA|aB|a

B-*bB|b

42、按指定类型，给出语言的文法。

L=｛aHU>i2l｝的上下文无关文法。

答：

FhL=｛abiU>i21｝知，所求该语言对应的上下文无关文法首先应有S-aSb型产生式，以保

证b的个数不少于a的个数；其次，还需有S-Sb或S-bS型的产生式，用以保证b的个

数多于a的个数；也即所求上下文无关文法G[S]为：

G[S]：S-*aSb|Sb|b

43、有文法G：S-*aAcB|Bd

A-*AaB|c

B-*bScA|b

(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄：

(2)写出句子acabcbbdcc的最左推导过程.

答：

(1)分别画出对应两句型的语法树，如下图所示

句柄:AaBBd

(2)句子acabcbbdcc的最左推导如下：

S=>aAcB=>aAaBcB=>acaBcB=>acabcB=>acabcbScA=>acabcbBdcA

=>acabcbbdcA=>acabcbbdcc

44、考虑文法G[T]：

T-T*F|F

F-*FtP|P

P-(T)|i

证明T*Pt(T*F)是该文法的一个句型，并指出直接短语和句柄。

答：

首先构造T*Pt(T*F)的语法树如下图所示。

由上图可知，T*Pt(T*F)是文法G[T]的一个句型。

直接短语有两个，即P和T*F；句柄为匕

六、综合题(每小题8分，共24分)

45、构造下面文法的LL(1)分析表。

D—TL

T—►int|real

L—idR

R一，idR|£

答：求开始符号集合和后继符号集合：

FIRST(D)=FIRST(T)={int,real}FOLLOW(D)=FOLLOW(L)={#}

FIRST(L)={id}FOLLOW(T)={id}

FIRST(R)={,,£}FOLLOW(R)={#}

£是产生式Rf£右部的一个开始符号，而#在FOLLOW(R)中，所以Rf£填在输入符号#

的栏目中。

LL(1)分析表如下表所示

非终结符输入符号

intrealid9#

DD-*TLD-*TL

TT-intT—real

LL-idR

RR一,idRR-*E

46、己知文法：

G[AJ：A-*aAa|£

(1)该文法是LL(1)文法吗？为什么？

(2)若采用LL(1)方法进行语法分析，如何得到该文法的LL(1)分析表？

(3)若输入符号串“aaaa”，请给出语法分析过程。

答：(1)因为产生式A-aAa|£有空产生式右部，而

FOLLOW(A)={#}UFIRST(a)={a,#}

造成FIRST(A)nFOLLOW(A)={A,£}D{a,#}W0

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

(2)若采用LL(1)方法进行语法分析，必须修改该文法。

因该文法产生偶数(可以为0)个a,所以得到文法

G'[A1：A-*aaA|£

此时对产生式A-*aaA|*有FOLLOW(A)={#}UFOLLOW(A)={#},因而

FIRST(A)nFOLLOW(A)={a,£}H{#}=0

所以文法G[A]是LL(1)文法，按LL(1)分析表构造算法构造该文法的LL(1)分析表

如卜表所示。

文法G1A]的LL(1)分析表

A#

AA-*aaAA-*£

(3)若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如下表所示。

对符号串“aaaa”的分析过程

步骤分析栈输入串产生式/动作

1#Aaaaa#A-*aaA

2#Aaaaaaa#匹配

3#Aaaaa#匹配

4#Aaa#A—aaA

5#Aaaaa#匹配

6#Aaa#匹配

7#A#A—e

8##接受

47、设有文法G[法为:

S-*a|b|(A)

A-*SdA|S

(1)完成下列算符优先关系表，并判断G[S]是否为算符优先文法。

算符优先关系表

ab()d#

a>>

b>>

(<<<

)>>

d

#<<<立

(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语。

(3)给出输入串(adb)#的分析过程。

答：

(1)先求文法G[S]的FIRSTVT集和LASTVT集：

由Sfa|b|(A)得:FIRSTVT(S)={a,b,();

由A-*Sd…得:FIRSTVT(A)={d};

又由A-S…得：FIRSTVT(S)CFIRSTVT(A),即FIRSTVT(A尸{d,a,b,(};

由Sfa|b|(A)得;LASTVT(S)={a,b,}};

由A~…dA得：LASTVT(A)={d)

又由A-*S得：LASTVT(S)ULASTVT(A),即LASTVT[A尸

构造优先关系表方法如下：

①对P—・,ab…,或P-…aQb…,有a'b;

②对P-*•••aR…，WbGFIRSTVT(R),有a«b;

③对P-…Rb…，WaeFIRSTVT(R),有a»b。

由此得到：

①由S-(A)得：(工);

②由S-(A…得：(<FIRSTVT(A),即:(«d,(《a,(«b,(《(油A-…dA得：d<FIRSTVT(A)

即：d<d,d<a,d<b,d<(；

③由S-A)得，LASTVT(A)>),即:d»),a»),b>),A);由A-Sd…得：LASTVT(S)>d

即：a>d,b>d,)>d;

此外，由#S#得:#呻；

由#«FIRSTVT(S)得：#<a,#<b,#<(；脂由LASTVT(S)冲得：d>#,a>#,b>#,)>#o

最后得到算符优先关系表，如下表所示。

由上表可以看出，任何两个终结符之间至少只满足工、<、》三种优先关系之一，故G[S：为算

符优先文法。

(2)为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，

如下图所示。

由上图可得到：

短语：S,SdS,SdSdS,(SdSdS)

简单短语(即宜接短语)：S

句柄(即最左直接短语)：S

素短语：SdS,它同时也是该句型的最左素短语。

(3)输入串(adb)#的分析过程见下表:

符号栈输入串说明

#(adb)#移进

井(adb)#移进

#(adb)#用S—a归约

#(Sdb)#移进

#(Sdb)#移进

#(Sdb)#用S-b归约

#(SdS冲用ATS归约

#(SdA)#用A-SdA归约

#(A)#移进

#(A)#用S—(A)归约

#S#分析成功

《计算机编译原理》试卷B参考答案

一、单项选择题(每小题1分，共25分)

1、有文法G：E-E*T|T

T->T+i|i

句子1+2*8+6按该文法G归约，其值为B.

A、23B、42C、30D、17

2、规范归约指Bo

A、最左推导的逆过程B、最右推导的逆过程

C、规范推导D、最左归约的逆过程

3、词法分析所依据的是B。

A、语义规则B、构词规则C、语法规则D、等价变换规则

4、词法分析器的输出结果是Co

A、单词的种别编码B、单词在符号表中的位置

C、单词的种别编码和自身值D、单词自身值

5,正规式Mi和M2等价是指Cv

A、Mi和M2的状态数相等B、Mi和M2的有向弧条数相等

C、Mi和M?所识别的语言集相等D、Mi和M2状态数和有向弧条数相等

6、下面的状态转换图接受的字集为D。

A、以0开头的二进制数组成的集合B、以0结尾的二进制数组成的集合

C、含奇数个。的二进制数组成的集合D、含偶数个0的二进制数组成的集合

7、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，B-

_O

A、词法分析器应作为独立的一遍

B、词法分析器作为子程序较好

C、词法分析器分解为多个过程，由语法分析器选择使用

D、词法分析器并不作为一个独立的阶段

8、若a为终结符，则A-a-ap为B项目

A、归约B、移进C、接受D、待约

9、若项目集h含有A则在状态k时，仅当面临的输入符号aUPOLLOW(A)时，才采

取动作的一定是Do

A、LALR文法B、LR：0)文法C>LR(1)文法D、SLR(1)文法

10、就文法的描述能力来说，有Co

A、SLR(1)CLR(0)B、LR(1)CLR(0)

C、SLR(1)CLR(1)D、无二义文法ULR(1)

II、在LR(0)的ACTION子表中，如果某一行中存在标记“父的栏，则A。

A、该行必定填满弓B、该行未填满弓

C、其他行也有0D、goto子表中也有弓

12、一个C指明了在分析过程中的某时刻所能看到产生式多大一部分。

A、活前缀B、前缀C、项目D、项目集

13、中间代码生成所依据的是C。

A、语法规则B、词法规则C、语义规则D、等价变换规则

14、四元式之间的联系是通过_____B实现的。

A、指示器B、临时变量C、符号表D、程序变量

15、后缀式ab+cd+/可用表达式B来表示。

A、a+b/c+dB、(a+b)/(c+d)C、a+b/(c+d)D、a+b+c/d

16、表达式(iAVB)A(CVD)的逆波兰表示为______B0

A、-1ABVACDVB、A-|BVCDVA

C、ABV-ICDVAD、A-IBVACDV

17、四元式表示法的优点为C。

A、不便于优化处理，但便于表的更动B、不便于优化处理，但节省存储空间

C、便于优化处理，也便于表的更动D、便于表的更动，也节省存储空间

18、终结符具有D属性。

A、传递B、继承C、抽象D、综合

19、编译程序使用B区别标识符的作用域。

A、说明标识符的过程或函数名B、说明标识符的过程或函数的静态层次

C、说明标识符的过程或函数的动态层次D、标识符的行号

20、程序所需的数据空间在程序运行前可确定，称为C管理技术。

A、动态存储B、栈式存储C、静态存储D、堆式存储

21、优化可生成D的目标代码。

A、运行时间较短B、占用存储空间较小

C、运行时间短但占用内存空间大D、运行时间短且占用存储空间小

22、文法G[N]=({b},{N,B},N,{N-*b|bB,B-*bN)),该文法所描述的语言是

_C_____o

A、L(G[N])=[N|i^O}B.L(G[N])={b2i|i>0}

C、L(GlN])={b2i+l|i2()}D、L(GlN])=|b2i+,Ii^l}

23、乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文

法是Bo

A、短语文法B、正则文法C、上下文有关文法D、上下文无关文法

24、文法G所描述的语言是C的集合。

A、文法G的字母表V中所有符号组成的符号串

B、文法G的字母表V的闭包V“中的所有符号串

C、由文法的开始符号推出的所有终极符串

D、由文法的开始符号推出的所有符号串

25、按逻辑上划分，编译程序第二步工作是Co

A、语义分析B、词法分析C、语法分析D、代码优化

二、判断题(每小题1分，共10分)

(J)26、算符优先关系表不一定存在对应的优先函数。

(X)27、自底而上语法分析方法的主要问题是候选式的选择。

(义)28、LR法是自顶向下语法分析方法。

(X)29、简单优先文法允许任意两个产生式具有相同右部。

(X)30、若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。

(J)31、一个句型的句柄一定是文法某产生式的右部。

(J)32、数组元素的地址计算与数组的存储方式有关。

(X)33、在程序中标识符的出现仅为使用性的。

(X)34、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

(X)35、在程序中标识符的出现仅为使用性的。

三、名词解释题(每小题4分，共8分)

36、素短语

至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。

37、语法树

满足下面4个条件的树称之为文法G[S]的一棵语法树。

①每一终结均有一标记，此标记为VNUVT中的一个符号；

②树的根结点以文法G[S]的开始符S标记；

③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；

④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别

为Xi,X2,…,XK，则A-XI,X2,…,XK，必然是G的一个产生式。

四、简答题(每小题4分，共8分)

38、编译程序和高级语言有什么区别？

答：用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的

目标程序(这个过程即编译)，才能由计算机执行。执行转换过程的程序叫编译程序。汇编

程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。

编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语

言编写的程序，按照一-对应的关系，转换成用机器语言表示的程序。解释型编译程序将高

级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下

一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但

可以进行人和计算机的“对话”，随时可以修改高级语言的程序。BASIC语言就是解释型高级

语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且

过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。

39、简述自下而上的分析方法。

答：所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号;

或者说从语法树的末端开始，步步向上“归约”，直到根节点。

五、应用题(每小题5分，共25分)

40、证明下述文法G：

S^aSbS|aS|d

是二义性文法。

答：

一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文

法。

句子aadbd有两棵语法树.如下图：

由此可知，SfaSbS|aS|d定义的文法是二义性文法。

41、设有语言L(G)={adaR|a£(a,b).,aR为a之逆}，试构造产生此语言的上下文无关文法G。

解：根据题义，可知aR为a之逆的含义就是句子中的符号a、b以d为中心呈左右对称出现;

由于a七(a,b),所以a、b的个数可以为零。所以可构造产生此语言的上下文无关文法G[S]

为：S-aSa|bSb|d

42、为正规式(a|b)"a(a|b)构造一个等价的确定的有限自动机。

答：

a

a

2

b

43、给定下列自动机:

(1)把此自动机转换为确定自动机DFA。

(2)给出此DFA的正则表达式。

答：(1)：有状态矩阵如图：

(2)此DM的正则表达式为：(aa*b|b)(b|ab)*或a*b(b|ab)

44、对于文法G[S]：

Sf(L)|aS|aL^L,S|S

(1)画出句型(S,(a))的语法树。

(2)写出上述句型的所有短语、直接短语、句柄和素短语。

答：

(1)句型(S,(a))的语法树如下图所示

小

a

(2)由上图可知:

①短语:S、a、(a)、S,(a)、(S,(a))；

②直接短语：a、S；

③句柄：s；

④素短语：素短语可由上图中相邻终结符之间的优先关系求得，即

<(<e,<(<sav>)€>)C>#

因此素短语为a。

六、综合题(每小题8分，共24分)

45、设乂=({x,y),{a,b},f,x,{y})为一非确定的有限自动机，其中f定义如下：

f(x,a)={x,y}f(x,b)={y}

f(y,a)=6f(y,b)={x,y}

试构造相应的确定有限自动机M'。

答:对照自动机的定义M=(S,Z,f,So,Z),由f的定义可知f(x,a)、f(y,b)均为多值函数,所以是

一非确定有限自动机，先画出NFAM相应的状态图，如下图所示。

用子集法构造状态转换矩阵表如下所示。

ILIh

{X}{x,y}{y}

{y}—{x.y}

{x,y}{x,y}{x,y}

将转换矩阵中的所有子集重新命名而形成下表所示的状杰转换矩阵。

ab

021

1—2

222

即得到M三({0,1,2},{a,b},f,O,{1,2}),其状态转换图如下图所示。

将上图的DFAM，最小化。首先，将M，的状态分成终态组{1,2}与非终态组{0}；其次，考

察{1,2}。由于{l,2}a={l,2}b={2}U",2},所以不再将其划分了，也即整个划分只有两组(()),

{1,2}：令状态1代表{1,21即把原来到达2的弧都