大学计算机编译原理期末复习试题(含有答案)Word文件下载.doc
《大学计算机编译原理期末复习试题(含有答案)Word文件下载.doc》由会员分享，可在线阅读，更多相关《大学计算机编译原理期末复习试题(含有答案)Word文件下载.doc（23页珍藏版）》请在冰点文库上搜索。
d．语义分析 e．词法分析
2、编译程序工作时，通常有阶段。
a．词法分析 b．语法分析 c．中间代码生成
d．语义检查 e．目标代码生成
1．b、c2.a、b、c、e
三、填空题
1、解释程序和编译程序的区别在于。
2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。
3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。
4、编译程序是指将程序翻译成程序的程序。
解答
是否生成目标程序2、词法分析中间代码生成3、源程序 目标代码生成 4、源程序目标语言
一、单项选择题
1、文法G：
S→xSx|y所识别的语言是。
a.xyx b.（xyx）* c.xnyxn（n≥0） d.x*yx*
2、文法G描述的语言L（G）是指。
a.L（G）={α|Sα,α∈VT*} b.L（G）={α|Sα,α∈VT*}
c.L（G）={α|Sα,α∈（VT∪VN*）} d.L（G）={α|Sα,α∈（VT∪VN*）}
3、有限状态自动机能识别。
a.上下文无关文法 b.上下文有关文法
c.正规文法 d.短语文法
4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。
a.若f（a）>
g（b），则a>
b b.若f（a）<
g（b），则a<
b
c.a~b都不一定成立 d.a~b一定成立
5、如果文法G是无二义的，则它的任何句子α。
a.最左推导和最右推导对应的语法树必定相同
b.最左推导和最右推导对应的语法树可能不同
c.最左推导和最右推导必定相同
d.可能存在两个不同的最左推导，但它们对应的语法树相同
6、由文法的开始符经0步或多步推导产生的文法符号序列是。
a.短语 b.句柄 c.句型 d.句子
7、文法G：
E→E+T|T
T→T*P|P
P→（E）|I
则句型P+T+i的句柄和最左素短语为。
a.P+T和i b.P和P+T c.i和P+T+i d.P和T
8、设文法为：
S→SA|A
A→a|b
则对句子aba，下面是规范推导。
a.SÞ
SAÞ
SAAÞ
AAAÞ
aAAÞ
abAÞ
aba
b.SÞ
AAaÞ
AbaÞ
c.SÞ
SAaÞ
SbaÞ
d.SÞ
SaÞ
9、文法G：
S→b|∧（T）
T→T,S|S
则FIRSTVT（T）。
a.{b,∧,（} b.{b,∧,）} c.{b,∧,（,，} d.{b,∧,）,，}
10、产生正规语言的文法为。
a.0型 b.1型 c.2型 d.3型
11、采用自上而下分析，必须。
a.消除左递归 b.消除右递归 c.消除回溯 d.提取公共左因子
12、在规范归约中，用来刻画可归约串。
a.直接短语 b.句柄 c.最左素短语 d.素短语
13、有文法G：
E→E*T|T
T→T+i|i
句子1+2*8+6按该文法G归约，其值为。
a.23B.42c.30d.17
14、规范归约指。
a.最左推导的逆过程 b.最右推导的逆过程
c.规范推导d.最左归约的逆过程
[解答]
1、选c。
2、选a。
3、选c。
4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。
所以，由f（a）>
g）（b）或f（a）<
g（b）并不能判定原来的a与b之间是否存在优先关系：
故选c。
5、如果文法G无二义性，则最左推导是先生长右边的枝叶：
对于d，如果有两个不同的是了左推导，则必然有二义性。
故选a。
6、选c。
7、由图2-8-1的语法树和优先关系可以看出应选b。
E
E+F
E+TP
Ti
P
#<
·
+·
>
+<
i·
#
图2-8-1句型P+T+I的语法及优先关系
8、规范推导是最左推导，故选d。
9、由T→T,…和T→（…得FIRSTVT（T））={（,，）}；
由T→S得FIRSTVT（S）⊂FIRSTVT（T），而FIRSTVT（S）={b,∧,（}；
即
FIRSTVT（T）={b,∧,（,，}；
因此选c。
10、d11、c12、b13、b14、b
1、下面哪些说法是错误的。
a.有向图是一个状态转换图 b.状态转换图是一个有向图
c.有向图是一个DFA d.DFA可以用状态转换图表示
2、对无二义性文法来说，一棵语法树往往代表了。
a.多种推导过程 b.多种最左推导过程 c.一种最左推导过程
d.仅一种推导过程 e.一种最左推导过程
3、如果文法G存在一个句子，满足下列条件之一时，则称该文法是二义文法。
a.该句子的最左推导与最右推导相同
b.该句子有两个不同的最左推导
c.该句子有两棵不同的最右推导
d.该句子有两棵不同的语法树
e.该句子的语法树只有一个
4、有一文法G：
S→AB
A→aAb|ε
B→cBd|ε
它不产生下面集合。
a.{anbmcndm|n,m≥0} b.{anbncmdm|n,m>
0}
c.{anbmcmdn|n,m≥0} d.{anbncmdm|n,m≥0}
e.{anbncndn|n≥0}
5、自下而上的语法分析中，应从开始分析。
a.句型 b.句子 c.以单词为单位的程序
d.文法的开始符 e.句柄
6、对正规文法描述的语言，以下有能力描述它。
a.0型文法 b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法
解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e
三、填空题
1、文法中的终结符和非终结符的交集是。
词法分析器交给语法分析器的文法符号一定是，它一定只出现在产生式的部。
2、最左推导是指每次都对句型中的非终结符进行扩展。
3、在语法分析中，最常见的两种方法一定是分析法，另一是分析法。
4、采用语法分析时，必须消除文法的左递归。
5、树代表推导过程，树代表归约过程。
6、自下而上分析法采用、归约、错误处理、等四种操作。
7、Chomsky把文法分为种类型，编译器构造中采用和文法，它们分别产生和语言，并分别用和自动机识别所产生的语言。
解答1、空集终结符右
2、最左
3、自上而上自下而上
4、自上而上
5、语法分析
6、移进接受
7、42型3型上下文无关语言正规语言下推自动机有限
四、判断题
1、文法S→aS|bR|ε描述的语言是（a|bc）* （）
R→cS
2、在自下而上的语法分析中，语法树与分析树一定相同。
（）
3、二义文法不是上下文无关文法。
（）
4、语法分析时必须先消除文法中的左递归。
（）
5、规范归约和规范推导是互逆的两个过程。
6、一个文法所有句型的集合形成该文法所能接受的语言。
（）
解答1、对2、错3、错4、错5、错6、错
五、简答题
1、句柄 2、素短语 3、语法树 4、归约 5、推导
1、句柄：
一个句型的最左直接短语称为该句型的句柄。
2、素短语：
至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。
3、语法树：
满足下面4个条件的树称之为文法G[S]的一棵语法树。
①每一终结均有一标记，此标记为VN∪VT中的一个符号；
②树的根结点以文法G[S]的开始符S标记；
③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；
④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,XK，则A→X1,X2,…,XK，必然是G的一个产生式。
4、归约：
我们称αγβ直接归约出αAβ，仅当A→γ是一个产生式，且α、β∈（VN∪VT）*。
归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。
5、推导：
我们称αAβ直接推出αγβ，即αAβÞ
αγβ，仅当A→γ是一个产生式，且α、β∈（VN∪VT）*。
如果α1Þ
α2Þ
…Þ
αn，则我们称这个序列是从α1至α2的一个推导。
若存在一个从α1αn的推导，则称α1可推导出αn。
推导是归约的逆过程。
六、问答题
1、给出上下文无关文法的定义。
一个上下文无关文法G是一个四元式（VT,VN,S,P），其中：
●VT是一个非空有限集，它的每个元素称为终结符号；
●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ；
●S是一个非终结符号，称为开始符号；
●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，
α∈（VT∪VN）*。
开始符号S至少必须在某个产生式的左部出现一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的语言是什么？
（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：
SÞ
abQÞ
abc
aSPQÞ
aabQPQÞ
aabPQQÞ
aabbQQÞ
aabbcQÞ
aabbcc
aaSPQPQÞ
aaabQPQPQÞ
aaabPQQPQÞ
aaabPQPQQÞ
aaaPPQQQÞ
aaabbPqqqÞ
aaabbQQQÞ
aaabbbcQQÞ
aaabbbccQÞ
aaabbbccc
……
于是得到文法G[S]生成的语言L={anbncn|n≥1}
3、按指定类型，给出语言的文法。
L={aibj|j＞i≥1}的上下文无关文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；
其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；
也即所求上下文无关文法G[S]为：
G[S]：
S→aSb|Sb|b
4、有文法G：
S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）写出句子acabcbbdcc的最左推导过程。
（1）分别画出对应两句型的语法树，如图2-8-2所示
句柄:
AaBBd
S
a
A
c
B
A
a
BbScA
Bdc
（a）
S
aAcB
BScA
Bd
c
（b）
图2-8-2语法树
（2）句子acabcbbdcc的最左推导如下：
SÞ
aAcBÞ
aAaBcBÞ
acaBcBÞ
acabcBÞ
acabcbScAÞ
acabcbBdcA
Þ
acabcbbdcAÞ
acabcbbdcc
5、对于文法G[S]：
S→（L）|aS|aL→L,S|S
（1）画出句型（S,（a））的语法树。
（2）写出上述句型的所有短语、直接短语、句柄和素短语。
（L）
L，S
S
（L）
S
a
图2-8-3句型（S,（a））的语法树
（1）句型（S,（a））的语法树如图2-8-3所示
（2）由图2-8-3可知：
①短语：
S、a、（a）、S,（a）、（S,（a））；
②直接短语：
a、S；
③句柄：
S；
④素短语：
素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
#·
（·
，
（
a·
）·
#
因此素短语为a。
6、考虑文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
T
T*F
F
↑
P
P（
T
）
图2-8-4句型T*P↑（T*F）的语法树
证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。
首先构造T*P↑（T*F）的语法树如图2-8-4所示。
由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。
直接短语有两个，即P和T*F；
句柄为P。
1、词法分析所依据的是。
a.语义规则 b.构词规则 c.语法规则 d.等价变换规则
2、词法分析器的输出结果是。
a.单词的种别编码 b.单词在符号表中的位置
c.单词的种别编码和自身值 d.单词自身值
3、正规式M1和M2等价是指。
a.M1和M2的状态数相等 b.M1和M2的有向弧条数相等
c.M1和M2所识别的语言集相等 d.M1和M2状态数和有向弧条数相等
4、状态转换图（见图3-6-1）接受的字集为。
0
1
0
图3-6-1
Y
X
a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合
c.含奇数个0的二进制数组成的集合d.含偶数个0的二进制数组成的集合
5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，。
a.词法分析器应作为独立的一遍b.词法分析器作为子程序较好
c.词法分析器分解为多个过程，由语法分析器选择使用d.词法分析器并不作为一个独立的阶段
解答1、b2、c3、c4、d5、b
1、在词法分析中，能识别出。
a.基本字 b.四元式 c.运算符
d.逆波兰式 e.常数
2、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为。
a.b（ab）* b.b（ab）+ c.（ba）*b
d.（ba）+b e.b（a|b）
解答1、a、c、e2、a、b、d
1、确定有限自动机DFA是的一个特例。
2、若二个正规式所表示的相同，则认为二者是等价的。
3、一个字集是正规的，当且仅当它可由所。
解答1、NFA2、正规集3、DFA（NFA）所识别
1、一个有限状态自动机中，有且仅有一个唯一终态。
（）
2、设r和s分别是正规式，则有L（r|s）=L（r）|L（s）。
3、自动机M和M′的状态数不同，则二者必不等价。
（）
4、确定的自动机以及不确定的自动机都能正确地识别正规集。
5、对任意一个右线性文法G，都存在一个NFAM，满足L（G）=L（M）。
（）
6、对任意一个右线性文法G，都存在一个DFAM，满足L（G）=L（M）。
7、对任何正规表达式e，都存在一个NFAM，满足L（G）=L（e）。
（）
8、对任何正规表达式e，都存在一个DFAM，满足L（G）=L（e）。
解答1、2、3、错4、5、6、7、8、正确
五、基本题
1、设M＝（{x,y},{a,b},f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。
解答：
对照自动机的定义M=（S,Σ,f,S0,Z），由f的定义可知f（x,a）、f（y,b）均为多值函数，所以是一非确定有限自动机，先画出NFAM相应的状态图，如图3-6-2所示。
aa
b
b
图3-6-2NFAM
用子集法构造状态转换矩阵表3-6-3所示。
I
Ia
Ib
{x}
{x,y}
{y}
—
将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。
表3-6-4状态转换矩阵
a
2
a
a,b
bb
图3-6-5DFAM′
即得到M′=（{0,1,2},{a,b},f,0,{1,2}），其状态转换图如图3-6-5所示。
a
a,b
b
图3-6-6化简后的DFAM′
将图3-6-5的DFAM′最小化。
首先，将M′的状态分成终态组{1，2}与非终态组{0}；
其次，考察{1,2}。
由于{1,2}a={1,2}b={2}⊂{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：
令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。
最后，得到如图3-6-6所示化简DFAM′。
2、对给定正规式b*（d|ad）（b|ab）+，构造其NFAM；
d
ε
b*
b*（d|ad）（b|ab）（b|ab）*
3
4
5
6
7
8
（d|ad）
（b|ab）
（b|ab）*
ad
ab
b|ab
图3-6-7的NFAM
首先用A+=AA*改造正规式得：
b*（d|ad）（b|ab）（b|ab）*；
其次，构造该正规式的NFAM，如图3-6-7所示。
1、构造下面文法的LL
（1）分析表。
D→TL
T→int|real
L→idR
R→
升级会员 