编译原理填空_选择

一、填空题:

1-01.编译程序的工作过程一般可以划分为 词法分析,语法分析,语义分析，中间代码生成,代

码优化 等几个基本阶段,同时还会伴有 表格处理 和 出错处理 .

1-02.若源程序是用高级语言编写的,目标程序是 机器语言程序或汇编程序 ,则其翻译程序称

为编译程序.

1-03.编译方式与解释方式的根本区别在于 是否生成目标代码 .

1-04.翻译程序是这样一种程序,它能够将 用甲语言书写的程序 转换成与其等价的 用乙语言

书写的程序 .

1-05.对编译程序而言,输入数据是 源程序 ,输出结果是 目标程序 .

1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶

段 和 运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个

阶段: 编译阶段 , 汇编阶段 和 运行阶段 .

2-01.所谓最右推导是指： 任何一步αÞβ都是对α中最右非终结符进行替换的 。

2-02.一个上下文无关文法所含四个组成部分是 一组终结符号、一组非终结符号、一个开始

符号、一组产生式 。

2-03.产生式是用于定义 语法成分 的一种书写规则。

2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S ＝>x，x

∈Vt*} 。

2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文

法的一个句型 。

2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法

的一个句子。

3-01.扫描器的任务是从源程序中识别出一个个 单词符号 。

4-01.语法分析最常用的两类方法是 自上而下 和 自下而上 分析法。

4-05.递归下降分析法是 自顶向下 分析方法。

4-06.自顶向下的语法分析方法的基本思想是：从文法的 开始符号 开始，根据给定的输入串

并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的 句子 ，使之与给定

的输入串匹配。

4-07.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一

步一步的向上进行直接归约，试图归约到文法的 开始符号 。

5-04.在LR（0）分析法的名称中，L的含义是 自左向右的扫描输入串 ，R的含义是 最左归

约 ，0 的含义是 向后查看0个输入符号 。

二、单选题:

1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代

码生成等五个部分，还应包括 (1)c .其中, (2)b 和代码优化部分不是每个编译程序都必需的.

词法分析器用于识别 (3)c ,语法分析器则可以发现源程序中的 (4)d .

(1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器

(2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成

(3) a.字符串 b.语句 c.单词 d.标识符

(4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误

1-11.程序语言的语言处理程序是一种 (1)a . (2)b 是两类程序语言处理程序,他们的主要区

别在于 (3)d .

(1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统

(2) a.高级语言程序和低级语言程序 b.解释程序和编译程序

c.编译程序和操作系统 d.系统程序和应用程序

(3) a.单用户与多用户的差别 b.对用户程序的查错能力

c.机器执行效率 d.是否生成目标代码

1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .

a.汇编语言程序 b.机器语言程序 c.高级语言程序

d. a 或者 b e. a 或者 c f. b 或者 c

1-13.下面关于解释程序的描述正确的是 b .

(1) 解释程序的特点是处理程序时不产生目标代码

(2) 解释程序适用于COBOL 和 FORTRAN 语言

(3) 解释程序是为打开编译程序技术的僵局而开发的

a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)

1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释

程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后阶段产生的目标代码更为高效.

与编译系统相比，解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法. (4)a 就

是一种典型的解释型语言.

(1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化

(2): a.比较简单,可移植性好,执行速度快

b.比较复杂,可移植性好,执行速度快

c.比较简单,可移植性差,执行速度慢

d.比较简单,可移植性好,执行速度慢

(3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为中间代码,再解释执行

c.先将源程序解释转化为目标程序,在执行 d.以上方法都可以

(4) : a. BASIC b. C c. FORTRAN d. PASCAL

1-15.用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 b 后,

可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .

a. 源程序 b. 目标程序 c. 函数 d. 过程

e. 机器指令代码 f. 模块 g. 连接程序 h.程序库

1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内

容: c , d , f .

a. 汇编语言 b. 高级语言 c. 源语言 d. 目标语言

e. 程序设计方法 f. 编译方法 g. 测试方法 h. 机器语言

1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成 (1)d ,

诸阶段的工作往往是 (2)d 进行的.

(1) a. 过程 b. 程序 c. 批量 d.遍

(2) a. 顺序 b. 并行 c. 成批 d.穿插

1-18.编译程序与具体的机器 a , 与具体的语言 a .

a. 有关 b.无关

1-19.使用解释程序时,在程序未执行完的情况下， a 重新执行已执行过的部分.

a. 也能 b.不可能

1-20.编译过程中,语法分析器的任务就是 b .

(1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的

(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构

a. (2)(3) b. (2)(3)(4) c. (1)(2)(3) d.(1)(2)(3)(4)

1-21.编译程序是一种常用的 b 软件.

a. 应用 b. 系统

1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步.

(1) 编辑 (2) 编译 (3) 连接 (4) 运行

a. (1)(2)(3)(4) b. (1)(2)(3) c. (1)(3) d.(1)(4)

1-23.编译程序必须完成的工作有 a .

(1) 词法分析 (2) 语法分析 (3) 语义分析

(4) 代码生成 (5) 中间代码生成 (6) 代码优化

a. (1)(2)(3)(4) b. (1)(2)(3)(4)(5) c. (1)(2)(3)(4)(5)(6)

d. (1)(2)(3)(4)(6) e. (1)(2)(3)(5)(6)

1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说

法 a .

a. 不正确 b.正确

1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由 b 完成的.

a. 编译器 b. 汇编器 c. 解释器 d. 预处理器

1-26.编译程序生成的目标程序 b 是机器语言的程序.

a. 一定 b. 不一定

1-27.编译程序生成的目标程序 b 是可执行的程序.

a. 一定 b. 不一定

1-28．编译程序是一种 B 。

A. 汇编程序 B. 翻译程序 C. 解释程序 D. 目标程序

1-29．按逻辑上划分，编译程序第二步工作是 C 。

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

2-07．文法G所描述的语言是 C 的集合。

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

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

C.由文法的开始符号推出的所有终结符串

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

2-08．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文

法是 B 。

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

2-10．一个句型中的最左 B 称为该句型的句柄。

可选项有：

A. 短语 B. 简单短语 （直接短语） C. 素短语 D. 终结符号

2-11．设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V*),则称x是文法

G的一个 B 。

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

2-12．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符

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

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

2-13.文法G[E]：

E→T∣E＋T

T→F∣T＊F

F→a∣（E）

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

①（E＋T） ②E＋T ③F ④ F＊(E＋T)

可选项有：

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

2-14．若一个文法是递归的，则它所产生的语言的句子 A 。

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

3-02．词法分析器用于识别 C 。

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

4-07.在法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 B 。

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

4-08.编译程序中语法分析器接收以 A 为单位的输入。

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

5-06．在自底向上的语法分析方法中，分析的关键是 D 。

A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式

5-07. 在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。

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

1．对于文法G[S]：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄？

句型baSb的语法树如图五(2)所示。

S

A

B

b

B S b

a

图五(2) 句型baSb的的语法树

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

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

柄。

某语言的文法G为： E → aTd|ε

T → Eb|a

证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。

问答第4题

解： 拓广文法G'，增加产生式S'→E

在项目集I

0

中：

有移进项目E →·aTd

和归约项目E→·

存在移进-归约冲突，所以G不是LR(0)文法。

若产生式排序为：

(0) S′→E

(1) E → aTd

(2) E →ε

.

(3) T → Eb

(4) T → a

G′的LR(0)项目集族及识别活前缀的DFA如下图：

由产生式知：

Follow(E)={# ，b}

Follow(T)= {d}

在I

0

，I

2

中:

Follow(E) ∩{a}={# ，b} ∩{a}=

在I

5

中:

Follow(E) ∩{a}={# ，b} ∩{a}=

Follow(T) ∩{a}= {d} ∩{a}=

Follow(T) ∩ Follow(E) = {d} ∩{# ，b}=

所以在I

0

， I

2

， I

5

中的移进-归约和归约-归约冲突可以由Follow集解决,所以G′是SL

R(1)文法。

构造的SLR(1)分析表如下表。

SLR(1)分析表

Name

0

1

2

3

4

5

6

7

ACTION

a

S2

S5

S5

b

r2

r2

S7

r2

r1

GOTO

#

r2

acc

r2

r2

r1

E

1

4

4

T

3

3

d

S6

r4

r3

一、单项选择题(共10小题，每小题2分，共20分)

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．L

0

L

1

L

2

L

3

B．L

3

L

2

L

1

L

0

C．L

3

=L

2

L

1

L

0

D．L

0

L

1

L

2

=L

3

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

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

9． 代码优化的目的是 C

A．节省时间 B．节省空间

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

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

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

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

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

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

二、填空题（本大题共5小题，每小题2分，共10分）

1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。

2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。

3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序

的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。

4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态

存储分配)方案和(动态存储分配)方案。

5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

选择题（每空2分，共20分）

1. 下面说法正确的是：B

A 一个正规式只能对应一个确定的有限状态自动机；

B 一个正规语言可能对应多个正规文法；

2. 表达式E*(F-C*(C/D))的逆波兰表示为（ B ）

A. EFC-CD/** B. EFCCD/*-* C. EFC-*CD/* D. 前三个选项都不对

3.下面说法正确的是：A

A Lex是一个词法分析器的生成器

6． 一个文法所描述的语言是（ A ）；描述一个语言的文法是（ B ）。

A 惟一的 B 不惟一的

7. Chomsky定义的四种形式语言文法中，0型文法又称为（A ）文法；1型文法又称为（C ）

文法；2型文法可由（ G ）识别。

A 短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正则文法

E 图灵机 F 有限自动机 G 下推自动机

1． 编译程序按功能分为哪几个阶段？各个阶段的主要功能？

六个阶段:

词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生

成。

各阶段的主要功能：

词法分析:

检查词法错误并把源程序中的单词转换成一种内部形式(数据形式);

语法分析:

检查源程序的语法错误,当发现错误时输出一些信息,并尽可能的继续检

查；

中间代码生成:

生成源程序的一种便于优化和便于产生目标代码的内部表示；

中间代码优化:

进行不依赖于目标机的优化,以产生高质量目标代码；

目标代码生成:

根据目标机特点从中间代码产生高质量目标代码。