编译原理小测验(有答案).doc

一、选择题
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.是否生成目标代码

6. 一个上下文无关文法G包含四个组成部分，依次为：一组 （　G　　），一组（H　　），一个（　E　　）和一组（　C　　）。
　A．字符串　　　　　B. 字母数字串 C.产生式 D.结束符号 E.开始符号 F.文法 G.非终结符 H.终结符

7. 一个语言的文法是（ ）。
A．唯一的 B. 不唯一的 C.数量有限的

8. 编译程序中的语法分析器接受以（ ）为单位的输入，并产生有关信息供以后各阶段使用。
A.表达式 B.产生式 C.单词 D.语句

9. 文法的二义性和语法的二义性是两个（ ）的概念。
A.不同 B.相同 C.无法判断
10、如果L(M)=L(M'），则M与M'（ ）
A．等价 B．M与M'都是二义的
C．M与M'都是无二义的 D．他们的状态数相等

11、如果文法G是无二义的，则它的任何句子α（ ）
A．最左推导和最右推导对应的语法树必定相同
B．最左推导和最右推导对应的语法树可能不同
C．最左推导和最右推导必定相同
D．可能存在两个不同的最左推导，但它们对应的语法树相同

12、给定文法, A-> bA | cc, 下面哪些符号串可由其推导出（ ）。
① cc ② b*cc ③ b*cbcc ④ bccbcc ⑤ bbbcc
可选项有：
a.① b.①③④⑤ c.①⑤ d.①②⑤ e①②③④⑤

13. 若一个文法是递归的，则它所产生语言的句子个数（ ）。
a.必定是无穷的 b.是有限个的 c.根据具体情况而定

14. Chmosky的3型语言是这样一种语言，其产生式限制为____。
a.A-> π b. A->a A->aB
c.α->β d. αAβ->απβ

15. 词法分析器的输出结果是（ ）。
A、单词自身值 B、单词在符号表中的位置
C、单词的种别编码 D、单词的种别编码和自身值

16、文法：G：S→xSx | y所识别的语言是（ ）。
Axyx B、（xyx）* C、x+yx+ D、{xnyxn |（n≥0）}

二、判断题
设有文法G[I]:
   I->I1/I0/Ia/Ic/a/b/c
   判断下面符号串中哪些是该文法的句子.
   (1) ab0
    (2)a0c01
   (3)aaa
    (4)bc10
   (5)aabc
   (6)bbca
答：(1)错误
   (2)正确
   (3)正确
   (4)正确
   (5)错误
   (6)错误

三、问答题
1. 什么是正规式，正规式的递归定义是什么？
答正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。
下面是正规式和它所表示的正规集的递归定义。
     设字母表为∑，辅助字母表为∑'={Ф，ε，|，·，*，(，)}
   (1). ε和Ф都是∑上的正规式，它们所表示的正规集分别为{ε}和Ф
   (2). 任意a∈∑，a是∑上的一个正规式， 它所表示的正规集为{a}
   (3). 若e1，e2都是∑上的一个正规式， 它们所表示的正规集分别为L(e1)和L(e2)，那么e1|e2，e1·e2和，( e1)也都是正规式, 它们所表示的正规集分别为L(e1)∪L(e2), L(e1) ·L(e2)和，L(e1)
   (4). 仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上正规集。

2. 何谓二义性文法？试举一例说明。
答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。

3. 什么是有穷自动机？什么是确定的有穷自动机？
答：有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。
     有穷自动机分为两类确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。
确定的有穷自动机（DFA）
一个确定的有穷自动机（DFA）是一个五元组：M=（K，∑，f，S，Z），其中
  (1) K是一个有穷集，它的每个元素称为一个状态；
  (2) ∑是一个有穷字母表，它的每个元素称为一个输入字符，所以也称∑为输入符号字母表；
  (3) f是转换函数，是在K×∑→K上映像，即，如f（ ，a）=（∈K，∈K），就意味着，当前状态为，输入字符为a时，将转换到下一状态，我们把称作的一个后继状态；
  (4) S∈K是唯一的一个初态；
  (5)   ，是终态集，终态也称可接受状态或结束状态。

四、综合题
E
T
F
(
E
)
E
+
T
F
i
T
T
*
F
1. 对于文法G(E):
E®T|E+T
T®F|T*F
F®(E)|i
1. 写出句型(T*F+i)的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语、句柄。
答：
1.
EÞTÞFÞ(E) Þ(E+T) Þ(E+F)
Þ(E+i) Þ(T+i) Þ(T*F+i)

2.
短语：(T*F+i), T*F+i, T*F, i
直接短语：T*F, i
句柄：T*F
2. 设S={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
答：
构造相应的正规式：(0|1)*1(0|1)
NFA:
1 1

1
0
4
3
2
e e e e 1

0 0
确定化：
I

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

0
1
4
3
2
1
0
0 1 0 0

0 1

1 1
3. 设为一非确定的有限自动机，其中定义如下：

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

Y
a
b
b
Þ
a
b

根据子集构造法可以得出以下表格：
I
Ia
Ib
{x} 0
{x,y} 1
{y} 2
{x,y} 1
{x,y} 1
{x,y} 1
{y} 2

{x,y} 1

根据该表可以得到以下的DFA
0

2
a,
a
b
b
b
Þ

1