-
编译原理复习题及答案
一、
选
择题
1
．
一个正规语言只能对应
(
B
)
A
一个正规文法
B
一个最小有限状态自动机
2
．
文法<
/p>
G[A]
：
A→ε
A→aB
B→Ab
B→a
是
(
A
)
A
正规文法
B
二型文法
3
．
下面说法正确的是
(
A
)
A
一个
SLR
（
1
）文法一定也是
LALR
（
1
）文法
B
一个
LR
（
1
）文法一定也是
LALR
（
< br>1
）文法
4
．
一个上
下文无关文法消除了左递归，提取了左公共因子后是满足
LL
（
1
）文法的
(
A
必要条件
B
充分必要条件
5
．
下面说法正确的是
(
B
)
A
一个正规式只能对应一个确定的有限状态自动机
B
一个正规语言可能对应多个正规文法
6
．
算符优
先分析与规范归约相比的优点是
(
A
)
A
归约速度快
B
对文法限制少
7
．
一个<
/p>
LR
（
1
）文法
合并同心集后若不是
LALR
（
1
）文法
(
B
)
A
则可能存在移进
/
归约冲突
B
则可能存在归约
/
归约冲突
C
则可能存在移进
/
归约冲突和归约
/
归约冲突
8
．
下面说法正确的是
(
A
)
A
Lex
是一个词法分析器的生成器
B
Yacc
是一个语法分析器
9
．
下面说法正确的是
(
A
)
A
一个正规文法也一定是二型文法
B
一个二型文法也一定能有一个等价的正规文法
10
．
编译
原理是对
(C)
。
A
、机器语言的执行
B
、汇编语言的翻译
C
、高级语言的翻译
D
、高级语言程序的解释执行
11
．
用高级语言编写的程序经编译后产生的程序叫
(B)
A
)
A
．源程序
B
．目标程序
C
．连接程序
D
．解释程序
12
．
(C)
不是编译程序的组成部分。
A.
词法分析程序
B.
代码生成程序
C.
设备管理程序
D.
语法分析程序
13
．
通常
一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，
目标代码生成等六个部分，还应包括
(C)
。
< br>
A
．模拟执行器
B
．解释器
C
．表格处理和出错处理
D
．符号执行器
14
．
源程
序是句子的集合，
(B)
可以较好地反映句子的结构。
A.
线性表
B.
树
C.
完全图
D.
堆栈
15
．
词法
分析器的输出结果是
(D)
。
A
、单词自身值
B
、单词在符号表中的位置
D
、单词的种别编码和自身值
C
、单词的种别编码
16
．
词法分析器不能
(D)
A.
识别出数值常量
B.
过滤源程序中的注释
D.
发现括号不匹配
C.
扫描源程序并识别记号
17
．
文法
：
G
：
S
→<
/p>
xSx | y
所识别的语言是
(D)<
/p>
。
A
、
xyx
B
、
(xyx)*
C
、
x*yx*
D
、
x
n
yx
n
(n
≥
0)
18
．
如果
文法
G
是无二义的，则它的任何句子
α
(A)
A
．最左推导和最右推导对应
的语法树必定相同
B
．最左推导和最
右推导对应的语法树可能不同
C
．最左推导和最右推导必定相同
<
/p>
D
．可能存在两个不同的最左推导，但它们对应的语法树相同
19
．
正则文法
(A)
二义性的。
< br>
A.
可以是
B.
一定不是
C.
一定是
20
．
(B
)
这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。
A.
存在
B.
不存在
C.
无法判定是否存在
21
．
给定
文法
A
→
bA |
ca
，为该文法句子的是
(C)
A.
bba
B. cab
C. bca
D. cba
22
．
设有
文法
G[S]
：
S
?
S1|S0|Sa|Sc|a|b|c
，下列符号串中是
该文法的句子有
(D)
A. ab0
B.
a0c01
C. a0b0a
D. bc10
23
．
描述一个语言的文法是
(B)
A
．唯一的
B.
不唯一的
C.
可能唯一
24
．
一个文法所描述的语言是
(A)
A
．唯一的
B.
不唯一的
C.
可能唯一
25
．
采用
自上而下分析，必须
(A)
。
A
、消除回溯
B
、消除左递归
C
、消除右递归
D
、提取公共左因子
26
．
编译过程中，语法分析器的任务是
(A)
①
分析单词的构成
②
分析单词串如何构成语句
③
分析语句是如何构成程序
④
分析程序的结构
A.
②③
B.
④
C.
①②③④
D.
②③④
27
．
词法分析器的输入是
(
A)
。
A
．符号串
B
．源程序
C
．语法单位
D
．目标程序
28
．
两个
有穷自动机等价是指它们的
(C)
。
A
．状态数相等
C
．所识别的语言相等
B
．有向弧数相等
D
．状态数和有向弧数相等
29
．
若状
态
k
含有项目“
A
→
α·
”，且仅当输入符号
a
∈
FOLLOW(A)
< br>时，才用规则“
A
→
α”
归约的语法分析方法是
(D)
。
A
．
LALR
分析法
B
．
LR(0)
分析法
C
．
LR(
1)
分析法
D
．
SLR(1)
分析法
30
．
若<
/p>
a
为终结符，则
A→α · aβ
为
(B)
项目。
A
．归约
B
．移进
C
．接受
D
．待约
31
．
在使
用高级语言编程时
,
首先可通过编译程序发现源程序的全部和部
分
(A)
错误。
A.
语法
B.
语义
C.
语用
D.
运行
32
．
乔姆
斯基
(Chomsky)
把文法分为四种类型，即
0
型、
1
型、
2
型、
3
型。其中
3
型文法是
(B)
A.
非限制文法
B.
正则文法
C.
上下文有关文法
D.
上下文无关文法
33
．
一个
上下文无关文法
G
包括四个组成部分，它们是一组非终结符号，
一组终结符号，一个开
始符号，以及一组
(B)
A.
句子
B.
产生式
C.
单词
D.
句型
34
．
词法分析器用于识别
(C)
A.
句子
B.
产生式
C.
单词
D.
句型
35
．
编译程序是一种
(B)
A.
汇编程序
B.
翻译程序
C.
解释程序
D.
目标程序
36
．
按逻辑上划分，编译程序第三步工作是
(A)
A.
语义分析
B.
词法分析
C.
语法分析
D.
代码生成
37
．
在语
法分析处理中，
FIRST
集合、
FO
LLOW
集合均是
(B)
A.
非终结符集
B.
终结符集
C.
字母表
D.
状态集
38
．
编译
程序中语法分析器接收以
(A)
为单位的输入。
A.
单词
B.
表达式
C.
产生式
D.
句子
39
．
编译过程中，语法分析器的任务就是
(B)
A.
分析单词是怎样构成的
B.
分析单词串是如何构成语句和说明的
D.
分析程序的结构
C.
分析语句和说明是如何构成程序的
40
．
若一
个文法是递归的，则它所产生的语言的句子
(A)
。
A.
是无穷多个
B.
是有穷多个
C.
是可枚举的
D.
个数是常量
41
．
识别上下文无关语言的自动机是
(C)
A.
下推自动机
B. NFA
C. DFA
D.
图灵机
42
．
编译原理各阶段工作都涉及
(B)
A.
词法分析
B.
表格管理
C.
语法分析
D.
语义分析
43
．
正则
表达式
R1
和
R2
等价是指
(C)
A.
R1
和
R2
都是定义
在一个字母表上的正则表达式
B.
R1
和
R2
中
使用的运算符相同
C.
R1
和
R2
代表同一正
则集
D.
R1
和
R2
代表不同正则集
44
．
已知文法
G[S]:S
→
A1
，
A
→
A1|S0|0
。与
G
等价的正规式是
(C)
A.
0(0|1)*
B.
1*|0*1
C.
0(1|10)*1
D.
1(10|01)*0
45
．
与
(a|b)*(a|b)
等价的正规式是
(C)
。
A.a*| b*
B.(ab)*(a|b)
C. (a|b)(a|b)*
D.(a|b)*
46
．
(D
)
文法不是
LL(1)
的。
A.
递归
B.
右递归
C. 2
型
D.
含有公共左因子的
47
．
给定
文法
A
→
bA|cc
< br>，则符号串①
cc
②
bcbc
③
bcbcc
④
bccbcc
⑤
< br>bbbcc
中，是该文法句子的
是
(D)
A.
①
B.
③④⑤
C.
②④
D.
①⑤
48
．
LR(1)
文法都是
()
A.
无二义性且无左递归
C.
无二义性但可能是左递归
B.
可能有二义性但无左递归
D.
可以既有二义性又有左递归
49
．
文法
E
→
E+E|E*E|i
的句子
i*i+i*i
有
(
C)
棵不同的语法树。
A. 1
B. 3
C. 5
D.7
50
．
文法
S
→
aaS|abc
定义的语言是
(C)
。
A.{a2kbc|k>0}
B.{akbc|k>0}
C.{a2k-1bc|k>0}
D.{akakbc|k>0}
51
．
若<
/p>
B
为非终结符，则
A
→
.B
A.
移进项目
为
(D)
。
C.
接受项目
D.
待约项目
B.
归约项目
52
．
<
/p>
同心集合并可能会产生新的
(D)
冲突。
A.
二义
B.<
/p>
移进
/
移进
C.
移进
/
归约
D.
归约
/
归约
53
．
就文法的描述能力来说，有
(C)
A
．
SLR(1)
?
LR(0)
B
．
LR(1)
?
LR(0)
C
．
SLR(1)
?
LR(1)
D
．无二义文法
?
LR(1)
54
．
如图
所示自动机
M
，请问下列哪个字符串不是
M
所能识别的
(D)
。
A. bbaa
B. abba
C. abab
D.
aabb
55
．
有限状态自动机能识别
(C)
A.
上下文无关语言
B.
上下文有关语言
C.
正规语言
D.0
型文法定义的语言
56
．
已知
文法
G
是无二义的，则对
G
的任意句型α
(A)
A.
最左推导和最右推导对应的语法树必定相同
B.
最左推导和最右推导对应的语法树可能相同
C.
最左推导和最右推导必定相同
<
/p>
D.
可能存在两个不同的最左推导，但他们对应的语法树相同
57
．
(B)
不是
DFA
的
成分
A.
有穷字母表
B.
多个初始状态的集合
C.
多个终态的集合
D.
转换函数
58
．
与逆
波兰式
(
后缀表达式
)ab+c*d+
对应的中缀表达式是
(B)
A.
a+b+c*d
B.
(a+b)* c+d
C.
(a+b)* (c+d)
D.
a+b*c+d
59
．
后缀式
abc?+?d+
可用表达式
(B)
来表示。
A
．
(? (a+b)?c)+d
B
．
?
(a+(b?c))+d
C
．
?
(a?(b+c))+d
D
．
(a?(?b+c))+d
60
．
表达式
A*(B-C*(C/D))
的后缀式为
(B)
。
A
．
ABC-CD/**
B
．
ABCCD/*-*
C
．
ABC-*CD/*
D
．以上都不对
61
．
(D
)
不是
NFA
的成分。
A.
有穷字母表
B.
初始状态集合
C.
终止状态集合
D.
有限状态集合
二、
问
答题
1
．
将文法
G[S]
改写为等价的
G′[S]
，使
G′[S]
< br>不含左递归和左公共因子。
G[S]
：
S→bSAe | bA
A→Ab | d
答：
文法
G[S]
改写为等价的不含左递
归和左公共因子的
G'[S]
为：
S→bB
B→SAe | A
A→d A
'
A' →bA' | ε
2
．
将文法
G[S]
改写为等价的
G'[S]
，使
G'[S]
< br>不含左递归和左公共因子。
G[S]
：
S→SAe|Ae
A→dAbA|dA|d
答：
文法
G[S]
改写为等价的不含左递
归和左公共因子的
G'[S]
为：
S
→AeS'
S' →AeS'|ε
A →dA'
A' →AB|ε
B
→bA |ε
3
．
将文法
G[S]
改写为等价的
G'[S]
，使
G'[S]
< br>不含左递归和左公共因子。
G[S]
：
S→[A
A→B]|AS
B→aB|a
答：
文法
G[S]
改写为等价的不含左递
归和左公共因子的
G'[S]
为：
S
→[A
A →B]A′
A′→SA′|ε
B
→aB′
B′→B|ε
4
．
判断下面文法是否为
LL(1)
文法，若是
,
请构造相应的
LL(1)
分析表。
S→aH
H→aMd | d
M→Ab | ε
A→aM |
e
答：
首先计算文法的
FIRST
集和
FOLLOW
集如下表。
< br>
文法的
FIRST
集和
FOLLOW
集
非终结符
S
H
M
A
FIRST
集
{a}
.........
{a
，
d}
.....
{a
，
e
，
ε}
{a
，
e}
.....
FOLLOW
集
{# }
...
{# }
...
{d
，
b}
{b}
....
由于
predict
（
H→aMd
）
∩
predict
< br>（
H→d
）
={a}∩{d
}=
predict
（
M→Ab
）
∩
predict
（<
/p>
M→ε
）
={a
，
e}∩{d
，
b }=
predict
< br>（
A→aM
）
∩
predict
（
A→e
）<
/p>
={ a }∩{ e }=
所以该文法是
LL(1)
文法，
LL(1)
分析表如下表。
S
H
M
A
5
．
判断下
面文法是否为
LL(1)
文法，若是，请构造相应的
LL(1)
分析表。
S→aD
D→STe|ε
a
→aH
.
→aMd
→Ab
.
→aM
.
d
→d
.
→ε
b
→ε
e
→Ab
→e
.
#
T→bH|H
H→d|ε
答：
首先计算文法的
FIRST
集和
FOLLOW
集如下表。
< br>
非终结符
S
D
T
H
{a}
{a
，
ε}
{b
，
d
，<
/p>
ε}
{d
，
ε}
FIRST
集
FOLLOW
集
{#
，
b
，
d
，
e}
.
{#
，
b
，<
/p>
d
，
e }
{e}
{e}
由于
predict
（
D→STe
）
∩
predict
（
D→ε
）
={a}∩{#
，
b
，
d
，
e }=
predict
（
< br>T→bH
）
∩
predict<
/p>
（
T→H
）
={
b}∩{e }=
predict
（
H→d
）
∩
predict
（
< br>H→ε
）
={ d }∩{ e }=
< br>所以该文法是
LL(1)
文法，
LL(1)
分析表如下表：
S
D
T
H
6
．
判断下
面文法是否为
LL(1)
文法，若是，请构造相应的
LL(1)
分析表。
S→aD
a
→aD
.
→STe
e
→ε
→H
.
→ε
b
→ε
→bH
d
→ε
→H
.
→d
.
#
→ε
D→STe|ε
T→bM
M→bH
H→M|ε
答：
文法的
FIRST
集和
FOLLOW
集
非终结符
S
D
T
M
H
FIRST
集
{a}
.....
{a
，
ε}
{b}
.....
{b}
.....
{b
，
ε}
FOLLOW
集
{#
，
b}
{#
，
b}
{e}
....
{e}
....
{e}
....
由于
predict
（
D→STe
）
∩
predict
< br>（
D→ε
）
={a}∩{#
，
b}=
p
redict
（
H→M
）
∩
predict
（
H→ε
）
={ b }∩{ e }=
所以该文法是
LL(1)
文法，
LL(1)
分析表如下表：
S
D
T
M
H
7
．
某语言
的拓广文法
G′
为：
a
→aD
.
→ST
e
e
→ε
b
→ε
→bM
→bH
→M
.
#
→ε
(0
) S′→S
(1) S →
Db|B
(2) D → d|ε
(3) B → Ba|ε
证明
G
不是
LR(0
)
文法而是
SLR(1)
文法，请给出
SLR(1)
分析表。
答：
拓广文法
G'
，增加产生式
S'→S
在项目集
I
0
中：<
/p>
有移进项目
D →·d
归约项目
D
→·
和
B →·
存在移进
-
归约和归约
-
归约冲突，
所以
G
不是
LR(0)
文法。
若产生式排序为：
(0) S'→S
(1) S →
Db
(2) S → B
(3) D → d
(4) D
→ε
(5) B → Ba
(6) B →ε
G′
的
LR(0)
项目集族及识别活前缀的
DFA
如下图：
由产生式知
Follow(S)={#}
Follow(D)= {b}
Follow(B)= {a
,#}
在
I
0
中
:
Follow(D) ∩{d}={ b}
∩{d}=
Follow(B)
∩{d}= { a ,#}
∩{d}=
Follow(D) ∩ Follow(B)=
{b}∩
{a ,#}
=
在
I
3
中
:
Follow(S)
∩{a}={#}∩{a}=
所以在
I
0
，
I
3
中的移进
-
归约
和归约
-
归约冲突可以由
Follow
集解决
,
所以
G
是
SLR(1)
文法
,
构造的
SLR(1)<
/p>
分析表如下表：
ACTION
状态
b
0
1
2
3
4
r4
S5
r3
d
S4
a
r6
S6
#
r6
acc
r2
S
1
D
2
B
3
GOTO
5
6
r5
r1
r5
8
．
<
/p>
给出与正规式
R
＝（
ab
）
*
（
a|b*
）
ba
等价的
NFA
。
答：
与正规式
R
等价的
NFA
如下图
9
．
给出与
正规式
R
＝（
(ab)*|b
）
*
（
a|(ba)*
）
a
等价的
NFA
。
答：
与正规式
R
等价的
NFA
如下图
-
-
-
-
-
-
-
-
-
上一篇：英语词汇学复习题重点
下一篇：时间序列预测方法实例