西理工编译原理试题集1-7

01-普通作业一（第一章）

一、选择题（从备选项中选出一个或多个正确答案）。

1.编译程序的源程序是高级语言编写的程序，目标程序是编写的程序。

A.高级语言B.汇编语言C.机器语言D,汇编语言或机器语言

2.编译程序是对进行翻译。

A.高级语言B.汇编语言C.机器语言D.自然语言

3.如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段。

A.编译B.汇编C.运行D.预处理

4.编译的工作过程一般划分为词法分析、、语义分析、中间代码生成、代码优化

和目标代码生成若干阶段。

A.表格管理B.出错处理C.语法分析D.预处理

5.词法分析阶段的主要任务是识别。

A.表达式B.单词C.语句D,词组

二、判断题（对于下列陈述中正确的说法选择回答“对”，否则选择回答“错”）。

1.编译程序是一种常见的应用软件。

2.C语言的编译程序可以用C语言编写。

3.编译方式与解释方式的区别之一在于是否生成目标程序。

4.中间代码生成是编译程序不可或缺的部分。

5.含有优化的编译程序执行效率高。

三、解释下列术语：

（1）编译程序

（2）源程序

（3）目标程序

（4）编译程序的前端

（5）后端

（6）遍

四、一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程

序的总体结构图。

五、何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？

参考答案：

一、选择题

1.D2.A3.AC4.C5.B

二、判断题

1.错2.对3.对4.错5.错

三、

⑴把用高级程序设计语言书写的源程序，翻译成等价的计算机汇编语言或机器语言书写的

目标程序的翻译程序。

(2)源程序，是指未经编译的，按照一定的程序设计语言规范书写的，人类可读的文本文件。

⑶为源程序经编译可直接被计算机运行的机器码集合，在计算机文件上以.obj作扩展名。

⑷编译程序的前端通常指：词法分析、语法分析、语义分析等生成最终代码以前的一系列

步骤。

⑸后端包含代码优化和目标代码生成部分。

⑹对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

四、数据结构、分析部分、综合部分、结构。

五、

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

本章要点

1.程序语言的定义；

2.高级程序语言一般结构和主要共同特征；

3.正确理解上下文无关文法基本概念，包括：

文法的定义、推导、句型、句子、语言、语法树、二义性等；

4.Chomsky文法分类；

本章目标

掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述.

本章重点

1.语法，词法规则与语法规则；

2.语义和语义规则；

3.数据类型与操作；

4.推导，最左推导和最右推导；

5.语法分析树和二义性；

本章难点

1.二义性文法;

2.Chomsky各个文法类；

作业题

一、单项选择题：

(按照组卷方案，至少15道小题)

1.Chomsky把文法分成四种类型，。型、1型、2型和3型。3型文法也称为,2

型文法也称为。

a.上下文无关文法b.上下文相关文法c.正则文法d.短语文法

2.许多广为使用的语言，如Fortran、C、Pascal等，属于«

a.强制式语言b.应用式语言c.基于规则的语言d.面向对象的语言

设是一个文法，是开始符号。若则称是一个。

3.GSSn'a,ae(VTUVN),,a

a.句子b.句型c.推导d.语言

4.一个数据类型通常包括的三种要素中，没有下面的。

a.用于区别这种类型的数据对象的属性；b.这种类型的数据对象可以具有的值；

c.对这种类型的数据对象的内存分配；d.可以作用于这种类型的数据对象的操作；

5.Chomsky把文法分成四种类型，其中，也称正规文法

a.O型b.1型c.2型d.3型

6.语言的词法规则一般用Chomsky的____型文法来描述：

a.0b.1c.2d.3

7.文法

Sf(L)|a

LfL,S|S

中，下面—是该文法中的终结符号。

a.Sb.,c.Ld.|

8.文法G所描述的语言是的集合。

a.文法G的字母表Z中的所有符号组成的符号串；

b.文法G的字母表E的闭包£*中的所有符号串；

c.文法G的识别符号推出的所有符号串；

d.文法G的识别符号推出的所有终结符号串；

9.语言L={aca|ae（a|b广},该语言是语言»

a.3型语言，b.2型语言，c.l型语言，d.O型语言

10.设有文法G：

1-11|10|la|1c|a|b|c|

下面符号串中不是该文法的句子是：

a.abO,b.aOcOl,c.aaa,d.bclO

11.给定文法A-bA|cc,下面的符号串中，是该文法句子的是o

a.bcbc,b.bbbcc,c.bcbcc,d.bccbcc；

12.Chomsky定义的四种形式语言文法中，2型文法可由（G）识别。

a.图灵机；b.确定性有限自动机；c.下推自动机；d.非确定性有限自动机;

13.若文法G定义的语言是无限集，则文法必然是。

a.上下文无关的b.递归的c.二义性的d.无二义性的

14.文法S-aaS|abc定义的语言是。

a.{a2kbc|k>0}b.{akbc|k>0}

c.{a2klbc|k>0}d.{akakbc|k>0}

15.文法：G：S-xSx|y所识别的语言是（）。

a.xyxb.（xyx）*c.x*yx*d.xnyxn（n20）

—.答案:l.c.；2.a.；3.b；4.c；5.d；6.d；7.b；8,d；9.d；10.a；11.b；12.c；13.b；

14.c；15.d；

二、填空题：

（按照组卷方案，至少15道小题）

1.假设G是一个文法,a是由终结符和非终结符组成的串，s是文法的开始符号，如果s=>*a,

则称a是。

2.在赋值语句中，赋值号'：=’左右两边的变量名扮演着两种不同的角色，为了区分一个名

字的这两种特征，我们把一个名字所代表的称为该名的左值，把一个名字的称

为该名字的右值。

3.对于文法G,仅含终结符号的句型称为。

4.设有文法G⑸，其部分产生式：

E-E+T|T

T-T*F|F

F~(E)|a

贝

UVN={},VT={}»

5.由文法产生的集合是文法产生的语言。

6.Chomsky语法定义的3型文法又可以分为。

7.一个上下文文法G的四个组成部分分别是：。

8.已知语言：{aEWln,m20},其语法定义为：G=({a,b},{S,A,B},S,P),其中P

为：。

9.已知某语言的语法定义为：G=({a},{S}S,P),且P:S-aS|£,则该语言

为«

10.已知某语言为{wcwR|3e{a,b}*},其语法定义为G=({a,b,c},{S},S,P),其中P

为：。

11.所谓最右推导是指。

12.己知文法G(Z):

E-ET+|T

TfF*|F

F—FPt|P

PfE|i

试写出其识别的一个句子：。

13.文法G⑸：S-aA|a,A-aS为_____型文法，其确定的语言的为：。

14.在一棵语法树生长过程中的任何时刻，就是

一个句型。

15.我们说G=(VT,VN，S,P)是一个0型文法，如果它的每一个产生式a-p是这样一种结

构：。

二.答案：1.句型；2.单元的地址(或者：单元、存储单元的地址)，值(或者：单元的内

容)3.句子；4.VN={E,T,F},“={+,*,(,),a}；5.句子；6.右线性文法和左线性文法;

7.开始符号，产生式集合，终结符集合，非终结符集合；8.S玲AB；A^aAb|£；B-^aBb|£；

9.{an|n20}；10.S玲aSa|bSb|£；11.任何一步a=B都是对a中的最右非终结符进行替换。12.

个*2n+1所有那些没有后代的末端结点从左到右排列起来；

iii+；13.{a|n>0};14.15.

VT)'且至少含有一个非终结符，而(VN

ae(vNuBeUvT)\

三、判断题：

(按照组卷方案，至少15道小题)

1.一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。（）

2.可能有两个不同的文法G和G,期中一个是二义的而另一个是无二义的，但是却有L（G）

L（GZ）o（）

3.变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。（）

4.文法G:

SfbA

A-*aA|a

定义的语言是所有以b开头的后跟至少一个a的字符串的集合。（）

5.设有文法G：

S-S*S|S+S|（S）|a

该文法是二义的。（）

6.正则文法一定不是二义的。（）

7.上下文无关文法可以产生语言L={|i>=l,n>=l}»（）

8.不存在任何正规文法能产生语言L={anbn|n>=l}»（）

9.对于每一个左线性文法Gi，都存在一个右线性文法G2，使得L（GI）=L（G2）。（）

10.正规文法产生的语言都可以用上下文无关文法来描述。（）

11.上下文无关文法比正规文法有更强的描述能力。（）

12.文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存

在两个以上的文法来描述它。（）

13.二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切

地给出该文法是否二义的答案。（）

14.说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名

字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（）

15.C语言是一个允许子程序嵌套定义的语言。（）

三.答案：1.V；2.V；3.V；4.V；5.V；6.X；7.V；8.V；9.V；10.V；11.V；12.X；13.X；

14.V；15.X；

四、名词解释：

（按照组卷方案，至少3道小题）

1.二义性文法；2.推导和直接推导；3.句型，句子和语言；4.上下文无关文法;

5.语法；6.正规文法（左线性文法和右线性文法）；

四.答案：

1.如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。

2.设A-y是一个产生式，且a、pe（VTuVN）*,若aAB=>ayP，则称aA|3直接推出ayP；或者

说，a邓是aAp的一个直接推导。

如果ai=>a2=>......=>an,则称这个序列是从a1到an的一个推导。

3.设G是一个文法，s是它的开始符号。如果s=>*a,则称a是一个句型。

仅含终结符的句型叫句子。

文法G所产生的句子的全体叫文法G的语言，记为L（G）,L（G）={a|S=>*a,aev/lo

4.上下文无关文法G是一个四元式（VT，VN，S,P）,其中：

VT是一个非空有限集合，其中的每一个元素称为终结符；

VN是一个非空有限集合，其中的每一个元素称为非终结符，VNnvT=0；

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

P是一个产生式有限集合，每个产生式的形式是Pfa,其中PCVN，aG（V2VN）*。开始符号

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

5.若文法G=（V「VN，S,P）的任何产生式为A~aB或A-a,其中，aeVT*.A,B£VN,则

称G是右线性文法；

若文法G=（V「VN，S,P）的任何产生式为A-Ba或A-a,其中，aeV；,A,BSVN,则称G

是左线性文法；

左线性文法和右线性文法均为正规文法。

五、简答题：

（按照组卷方案，至少3道小题）

1.作为描述程序语言的上下文无关文法，对它有哪些限制？

答：

第一点：文法中不含任何下面形式的产生式：P-P;

第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对P

不存在永不终结的回路。

2.什么是二义性文法？从输入串abab来说明下面文法二义吗？

S->aSbS|bSaS|e

该文法产生的语言是什么？

答:

如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是二义的。

例如输入串abab,它有两棵语法树如下：

所以，该文法是二义的。

此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。

3.文法G⑸为：

S-Ac|aB

A-ab

B-be

该文法是否为二义的？为什么？

答：

对于串abe

⑴S二〉Ac二〉abc⑵S二〉aB二〉abc

即存在两不同的最右推导。所以，该文法是二义的。

或者：

对输入字符串abc,能构造两棵不同的语法树，所以它是二义的。

4已知文法G=({A,B,C},{a,b,c},P,A),P由以下产生式组成:

Afabc

A->aBbc

Bb->bB

Bc->Cbcc

bCfCb

aC->aaB

aC-*aa

此文法所表示的语言是什么？

答：

分析文法的规则：

每使用一次BcfCbcc,b、c的个数各增加一个；

每使用一次aCfaaB或aC-aa,a的个数就增加一个；

产生式BbfbB、bC-Cb起连接转换作用。

由于A是开始符号，由产生式A-abc推导得到终结符号串abc；由产生式A-aBbc推导得

到B后，每当使用产生式Bb-bB、Bc—Cbcc、bC—Cb、aCfaaB就会递归调用B一次，所

产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、…

所以文法描述的语言为{aW|n>0}.

5已知文法G[Z]:

Z-OU|1V

U-1Z|1

V—0Z|0

(1)请写出此文法描述的只含有4个符号的全部句子。

(2)G[Z]产生的语言是什么？

(3)该文法在Chomsky文法分类中属于几型文法？

答：

(1)0101,0110,1010,1001

(2)分析G⑵所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。

图1文法G[Z]可能的几种推导

由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或

Olo所以G⑵产生的语言L(G[Z])={x|x6(10|01)+}

(3)该文法属于3型文法。

七、应用题:

1.试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else（else

悬挂）文法的二义性：

stmt玲ifexprthenstmt\matched-stmt

matched-stmt^ifexprthenmatched-stmtelsestmt\other

expr->e

考虑句子ifethenifethenotherelseifethenotherelseother,试说明此文法仍然是二义性

的。

答：

1.考虑句子ifethenifethenotherelseifethenotherelseother

它具有如下所示的两种分析树

stmt

ifexprthenstmt

matched-stmt

ifexprthenmatched-stmteslestmt

othermatched-stmt

ifexprthenmatched-stmteslestmt

othermatched-stml

other

stmt

matched-stmt

other

则上面给出的if-then-else文法仍是二义性的。

2.考虑文法G[bexpr]：

bexpr^>bexprorbterm\bterm

bterm^>btermandbfactor|bfactor

bfactor^>r\otbfactor\(bexpr)|true|false

(a)请指出此文法的终结符号、非终结符号和开始符号。

(b)试对于句子1101：(什110032归6)构造-一棵分析树。

(C)试说明此文法所产生的语言是全体布尔表达式。

答：

(a)终结符号为:{or,and,not,(,),true,false}

非终结符号为：{bexpr,bterm,bfactor)

开始符号为：bexpr

(b)句子not(trueorfalse)的分析树为：

(c)用归纳法说明如下：

⑴不含运算的布尔表达式，常数true和false由此文法产

生：

bexpr=>bterm=>bfactor=>true

bexpr=>bterm=>bfactor=>false

(2)设结论对于少于n(n”)个运算的布尔表达式成立，即

若be1和be?是含有少于n个运算的布尔表达式，则有：

++

bexpr=>bei；bexpr=>be2o

⑶对于含有n个运算的布尔表达式，可表示成下面三种

形式：

(a)(be。or(be2)

(b)(be。and(be2)

(c)not(bej

对于(a)：bexpr=>bexprorbterm

=>btermorbterm=>bfactororbterm

=>(bexpr)orbterm=>+(beJorbterm

=>(bei)orbfactor=>(bejor(bexpr)

+

=>(bei)or(be2)

同理，有：

+

Bexpr=>(bejand(be2)

Bexpr=>+not(bej

综上所述，此文法所产生的语言是全体布尔表达式。

3.已知文法G[S],其产生式为:S->(S)|E

(a)L(G)是什么？

(b)对于⑶的结果，请给出证明。

答：

(a)解：L(G)={(n)n|n>0}

(b)证明：

首先证明L(G)q{(n)n|n20}

对推导次数进行归纳

1)：当推导次数为1时，使用产生式Sf£,此时左括号与右括号个数为0

2):假设推导次数为n时(a)成立，即：

S4(((...S...)))^(((……)))

n-1n-in-1n-1

则推导次数为n+1次时，多使用一次产生式S-⑸即：

S4(((...S...)))=>(((...S...)))=>(((……)))

n-1n-1nnnn

推导次数为n+1次时(a)成立。

根据⑴(2)可得：L(G)c{(n)n|n>0}

其次证明{(n)n|n?O}=L(G)

对n进行归纳

1):当n=0时，使用产生式S-*E即可；

2):假设当n=k时，结论成立，即「)keL(G),下面证n=k+l时结论成立。

由(k)keL(G),其推导过程如下：

S4(((...S...)))=>(((……)))

kkkk

当n=k+l时，推导过程如下：

S4(((...S...)))=>(((...S...)))=>(((……)))

kkk+1k+lk+1k+1

故(k+i)k+ieL(G)

nn

根据⑴⑵可得：{()|n>O}£L(G)

根据1,2可知：L(G)={(n)n|>0}

4.试构造生成下列语言的上下文无关文法：

(lXaVd|n>l,i>0}

(2){w|wW{a,b}+,且w中a的个数恰好比b多1}

(3){w|wG{a,b}*,且|a141b|421a|}

答：

(1)把a%"分成a%"和d两部分，分别由两个非终结符号生成，因此，生成此文法的产

生式为：

S玲AB

A玲aAb|ab

BBcB|e

(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产

生含相同个数的a和b的所有串，则产生式如下：

S->aE|Ea|bSS|SbS|SSb

E-»aEbE|bEaE|e

(3)设文法开始符号为S,产生的w中满足|a|S|b|S2|a|。因此,可想到S有如下的产生式(其

中B产生1到2个b)：

SfaSBS|BSaS|e

B-b|bb

5.已知文法G⑸：

S玲AB

A->aA|a

B玲bB|b

求该文法所定义的语言。

答：

从规则2可推出：a,aa,aaa,.......

从规则3可推出：b,bb,bbb,.......

再从规则1可推出句子：

ab,aab,aabb,aaab,abbb,......

即，从S出发可推出多个a后跟多个b的字符串，且a的个数与b的个数不尽相同。

故：L(G)={ambn|m,nel}

6.考虑下面上下文无关文法G[S]：

S—SS*|SS+|a

⑴对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。

(2)G⑶的语言是什么？

答：

⑴此文法生成串aa+a*的最右推导：

S=>ss*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

此文法生成串aa+a*的最左推导：

S=>SS*=>SS+S*=>*=>aS+S*=>aa+S*=>aa+a*

s

aa

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

7令文法G为

N-D|ND

D-0|1|2|3|4|5|6|7|8|9

⑴G的语言L(G)是什么？

(2)给出句子0127、34和568的最左推导和最右推导。

答：

(1)

NnNDnNDDnNDDDnNDDDD......nDD......D

:.L(G)={d(n+1)|nNO,de{0,1,9}}

允许以0开头的自然数(十进制无符号整数)；

(2)

0127最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=^0127

0127最右推导：N=ND=N7=ND7nN27=ND27nN127=Dl27noi27

8写一个文法，使其语言是奇数集，且每个奇数不以0开头。

答：(首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头,

也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、

3、5、7、9就满足要求，如果有多位，则要求第1位不能是0,而中间有多少位，每位是什

么数字(必须是数字)则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用

3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1一9之间的数，不包括

0；一个用来产生句子的结尾，为奇数：另一个则用来产生以非0整数开头后面跟任意多个

数字的数字串，进行分解之后，这个文法就很好写了。)

令S表示不以0开始的奇数集合。

S好〈奇数头〉〈整数〉〈奇数尾〉I〈奇数头〉〈奇数尾〉|〈奇数尾〉

〈奇数尾〉1|3|5|7|9

〈奇数头〉->2|4|6|8|〈奇数尾〉

〈整数〉->〈整数〉〈数字〉|〈数字〉

〈数字〉玲0|〈奇数头〉

9写一个上下文无关文法CFG,使其语言是能被5整除且不以0开头的无符号整数的集合。

（如｛5,10,15,…

答：

能被5整除的数从形式上看，是以。和5结尾的数字串。题目要求的不以0开头，并要

注意0不是该语言的句子。所求文法为：

G（S）：S—MFI5

Ff5I0

M-MDIN

DfNI0

N-*l|2l3l4l5l6l7l8l9

10证明下面的文法是二义的：

S->iSeSIiSIi

答：（根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该

句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程

序语言的了解，不难发现，这个文法应该是用来表示if….else….结构的（用“i”代表“if”

或语句集，“e”代表“else”）.因此我们就要到if….else…结构中去找二义性。我们知道，

程序语言一般都规定else部分是和它前面离它最近的没有被匹配的的if语句进行匹配。而

上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if

（如句子iiiei）,else和不同的if进行匹配时就会产生不同的语义。）

解答：

考虑句子iiiei,存在如下两个最右推导：

S=>iSeS=>iSei=>iiSei=>iiiei

S=>iS=>iiSeS=>iiSei=>iiiei

11某程序设计语言的表达式由运算符61、02s03.标识符、（、）组成，其中和82的优

先级相同，。3的优先级低于91、。2的优先级，优先级相同的运算符从右往左计算，可以用

括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？

设E为识别符号，终结符号集=｛也、①、仇、（、）、I｝，非终结符号集=｛E、T、F｝。

a.E玲T|E6iT|Ee2T

T-»F|T03F

F-»(E)|I

b.E^T|T01E|T02E

T^F|F03T

F玲(E)|l

c.E^T|E03T

T^F|TeiF|T62F

F玲(E)|l

d.E->T|T03E

T^F|F0IT|F02T

—(E)11

答：

(对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递

归的方向和推导(或规约)的先后，左递归表明左边的运算先处理，对应的运算符左结合;

右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出(或

先被规约)的，表明其运算先被处理，因此优先级高；反之，先推导出(或后被规约)的,

表明其运算后被处理，因此优先级低。)

题意要求：&和g的优先级相同，1的优先级低于也、外的优先级，因此力比仇、g先推

导出来，即应为图3所示的四种情形。

图3可能的文法推导顺序

因此a和b不成立。

又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4所示的情形。

⑴(2(3)

图4可能的文法递归结构

故c不成立，应为do

第三章词法分析

本章要点

1.词法分析器设计，

2.正规表达式与有限自动机，

3.词法分析器自动生成。

本章目标：

1.理解对词法分析器的任务，掌握词法分析器的设计；

2.掌握正规表达式与有限自动机；

3.掌握词法分析器的自动产生。

本章重占.

1.词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实

现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。

2.掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。

（1）非形式描述的语言0正规式

（2）正规式fNFA（非确定的有限自动机）

（3）NFA—DFA（确定的有限自动机）

（4）DFA-»最简DFA

本章难点

（1）非形式描述的语言-正规式

（2）正规式-NFA（非确定的有限自动机）

（3）NFA—DFA（确定的有限自动机）

（4）DFA.最简DFA

作业题

一、单项选择题

(按照组卷方案，至少15道)

1.程序语言下面的单词符号中，一般不需要超前搜索

a.关键字b.标识符c.常数d.算符和界符

2.在状态转换图的实现中，—一般对应一个循环语句

a.不含回路的分叉结点b,含回路的状态结点c.终态结点d.都不是

3.用了表示字母，d表示数字，Z={l,d},则定义标识符的正则表达式可以是：。

(a)ld*(b)ll'(c)l(l|d)*(d)H*|d*

4.正规表达式⑻a|W表示的集合是

(a){e,ab.ba,aa,bb}(b){ab,ba,aa>bb}

(c){a,b,ab,aa>ba,bb}(d){e,a,b,aa,bb,ab,ba}

有限状态自动机可用五元组T来描述，设有一有限状态自动机的

5.(V，Q,6,q0,Qf)M

定义如下：

T的定义为：

V={0,1},Q={q°，qi，q2}.Qf={q2}-6

6(qo，0)=qi6(q】，0)=q?

6(q2,1)=q26(q2,0)=q2

M所对应的状态转换图为—o

台旗+-谷利辩琴睡第

6.有限状态自动机可用五元组(g，Q,8,q0,Qf)来描述，设有一有限状态自动机M的

定义如下：

VT={0,1},Q={q°，q”q2}.Qf={q2}-6的定义为：

6(q(),0)=qi6(q00)=q2

6(q2,1)=q26(q2,0)=q2

M所能接受的语言可以用正则表达式表示为一。

①(0|1)*(2)00(011)*(3)(011)*00@0(011)*0

7.有限状态自动机可用五元组Q，8,q0,Qf)来描述，设有一有限状态自动机M的

定义如下：

VT={0,1},Q={q0，qi，q?}>Qf={q2}>6的定义为：

6(q0,0)=qi6(qi，0)=q2

6(q2，1)=q26(q2,0)=q2

M所能接受的语言为—o

①由0和1所组成的符号串的集合

②以0为头符号和尾符号、由0和1所组成的符号串的集合

③以两个0结束的，由0和1所组成的符号串的集合

④以两个0开始的，由0和I所组成的符号串的集合

8.从接受语言的能力上来说，非确定型有穷自动机和是等价的。

a.i.正规式；ii.上下文无关文法；iii.确定性有穷自动机；

b.i.左线性正规文法；ii.右线性正规文法；iii.确定性有穷自动机；

c.i.正规式；ii.上下文无关文法；iii.正规文法；

d.i.正规式；ii.确定性有穷自动机；iii.下推自动机；

9.下面四个选项中，关于编译过程中扫描器的任务的叙述，是较为完整且正确的。

①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输

出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表。

②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出：发现并定位词法

错误：建立符号表：输出状态转换图；把状态转换图自动转换成词法扫描程序。

③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输

出。

④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输

出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图

自动转换成词法扫描程序。

10.关于NFA的叙述中，下面是不正确的。

A,有一个有穷字母表B.有多个初始状态

C.有多个终止状态D.有多个有限状态

11.词法分析的理论基础是。

A.有穷自动机理论B.图灵机理论C.图论D.无穷自动机理论

12.设有两个状态S和T,如果从S出发能读出某个字w而停于终态，那么从T出发也能读

出同样的字而停于终态；反之，果从T出发能读出某个字w而停于终态，那么从S出发也

能读出同样的字而停于终态。则我们称状态S和状态T是。

A.可区分的；B.等价的；C.多余的；D.无用的。

13.词法分析器的输出结果是。

A、单词自身值B、单词在符号表中的位置

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

14.编译过程中扫描器的任务包括。

①组织源程序的输入

②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出

⑧删除注解

④删除空格及无用字符

⑤行计数、列计数

⑥发现并定位词法错误

⑦建立符号表

a.②③④⑦b.②③④⑥⑦c.①②③④⑥⑦d.①②③④⑤⑥⑦

15.下述正则表达式中与(a*+b)*(c+d)等价(即有相同符号串集)。(x+y亦可写作x|y)

①a*(c+d)+b(c+d)

②a*(c+d)*+b(c+d)*

③a*(c+d)+b(c+d)

④(a+b)*c+(a+b)*d

⑤(a*+b)*c+(a*+b)*d

a.①③b.③④⑤c.③d.④⑤

16、正则式的“*”读作。

a,并且L或者c.连接d.闭包

17.在状态转换图中，结点代表,用圆圈表示。

a.输入缓冲区b.向前搜索c.状态d.字符串

18.与(a|b)*(a|b)等价的正规式是。

A.a*|b*B.(ab)(a|b)*C.(a|b)(a|b)*D.(a|b)*

19.无符号常数的识别和拼数工作通常都在阶段完成。

A.词法分析B.语法分析C.语义分析D.代码生成

—.答案：1.b；2.b；3.c；4.d；5.②;6.②，7.@；8.b；9.①；10.B；11.A；

12.B；13.d；14.d：15.d；16.d；17.c；18.C；19.A

二、填空题：

(按照组卷方案，至少15道)

1.词法分析器对扫描缓冲区进行扫描时一般用两个指示器，一个

:另一个。

2.一个确定性有限自动机DFAM的化简是指：寻找一个状态数比M少的DFA使

得O

3.词法分析器所的输出常表示成如下形式的二元式：(,

)。

4.一个状态转换图只包含有限个状态，其中有一个被认为是,而且实际上至少有

一个。

5.把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个

程序段。

6.词法分析阶段的任务式从左到右扫描,从而逐个识别。

7.如果一个种别只含有一个单词符号，那么，对于这个单词符号，就可以完

全代表它自身了。

8.单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比

如，对于某个标识符，常将作为

其属性值。

9.单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比

如，对于常数，常将作为其属性

值。

10.如果一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以

外，还应给出有关.

11.如果,则认为这两个正规式等价。

12.对于2*中的任何符号串a,如果存在一条从初态结点到某一终态结点的通路，

且,则称a被该自动机所接受(识别)。

13.一个Lex源程序主要包括两部分，一部分是,另一部分是。

14.一个DFA可用一个矩阵表示，该矩阵的行表示,列表示,矩阵元素表

示。这个矩阵叫状态转换矩阵。

15.对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态i和当前所面临

的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为：

二.答案：1.指向当前正在识别的单词符号的开始位置，用于向前搜索以寻找单词符号的

终点；2.L(M)=L(M')；3.单词种别，单词符号的属性值；4.初态，终态；5.由while和if

语句构成的；6.源程序，单词；7.种别编码；8.存放它的有关信息的符号表项的指针；9.存

放它的常数表项的指针；10.单词符号的属性信息(属性值)；11.两个正规式所表示的正规

集相同；12.这条通路上所有弧的标记符号连接起来形成的符号串等于a；13.正规定义式，

识别规则；14.状态，输入字符，转换函数(或3(s,a))的值；15.将搜索器回退一个位置，

并令下一个状态图开始工作。

三、判断题：

(按照组卷方案，至少15道)

1.NFAM的非确定性表现在它有多个终态。()

2.有穷自动机接受的语言是正则语言。()

3.若“和「2是Z上的正规式，则3|「2也是。()

4.设M是一个NFA,并且L(M)={x,y,z},则M的状态数至少为4个。()

5.令Z={a,b},则E上所有以b为首的字符构成的正规集的正规式为b*(a|b)*。()

6.对任何一个NFAM,都存在一个DFAMl使得L(M')=L(M)。()

7.对一个右线性文法G,必存在•个左线性文法G',使得L(G)=L(G'),反之亦然。()

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

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

10.对任何正则表达式r,都存在一个NFAM,满足L(M)=L(r)。()

11.对任何正则表达式r,都存在一个DFAM,满足L(M)=L(r)。()

12.一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）

13.一个正规式只能对应一个有限状态自动机：（）

14.在词法分析的状态转换图中，有些结点是带星号的，这些结点肯定是终态结点。（）

15.适当设置扫描缓冲区的大小（比如容纳256个字符）可以保证单词符号不会被它的边界

所打断。（）

四.答案：1.X；2.4；3.44.X；5.X；6.J7.48.49.4；10.A/；117；12X；

13.X；14.4；15.X；

四、名词解释：

（按照组卷方案，至少5道）

1.状态转换图；

2.正规式（正规表达式、正则表达式）的形式化定义；

3.给出确定性有限状态自动机的形式化定义；

4.给出非确定性有限状态自动机的形式化定义；

5.DFA状态最小化。

四.答案

1.状态转换图是一张有限方向图，用于识别（或接受）一定的字符串。

在图中，结点代表状态，用圆圈表示；状态之间用箭弧连结；箭弧上的标记（字符）代

表在射出结点（即箭弧的始结点）状态下可能出现的字符或字符类。

一张状态转换图只包含有限个状态（即有限个结点），其中一个被认为是初态，而且实

际上至少要有一个终态（用双圈表示）。

2.正规式是采用递归方式来定义的。

（1）£和0都是正规式；

（2）任何aGZ，a是X上的一个正规式；

（3）假定।■和s都是Z上的正规式，则r|s、rs＞和r*也都是正规式。

3.一个确定有限自动机（DFA）M是一个五元式：M=（S,Z，8,s0,F）,其中：

（1）S是一个有限集合，它的每一个元素称为一个状态；

（2）Z是一个有限字母表，它的每一个元素称为一个输入字符；

（3）6是一个从SXZ到S的单值部分映射。5（s,a）=s',意思是:当前状态是s,输入

字符为a时，自动机将转入下一个状态s\s，称为s的后继状态；

（4）s0GS,是自动机的惟一初态；

（5）FcS,是一个终态集合。

一个非确定有限自动机（NFA）M是一个五元式：M=（S,Z，5,S0,F）,其中：

（1）S是一个有限集合，它的每一个元素称为一个状态；

（2）Z是一个有限字母表，它的每一个元素称为一个输入字符；

（3）6是一个从SX£到s的子