《编译原理》复习题

一、单项选择题 为 。 C

1．构造编译程序应掌握 。D a. 10 b. 34 c. 14 d.54

a. 源程序 b. 目标语言 c. 编译方法d. 以上三项都是 2．编译程序绝大多数时间花在 上。D

a. 出错处理 b. 词法分析 c. 目标代码生成d. 表格管理

3．DFA M(见图1-1)接受的字集为 。D

a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合

不同

c. 最左推导和最右推导必定相同 0XY1d. 可能存在两个不同的最左推导，但它们09．如果文法G是无二义的，则它的任何句子α 。 A

a. 最左推导和最右推导对应的语法树必定

相同

b. 最左推导和最右推导对应的语法树可能

c. 含奇数个0的二进制数组成的集合 对应的语法树相同

图1-1 d. 含偶数个0的二进制数组成的集合 4． -a-(b*c/(c-d)+(-b)*a)的逆波兰表示是 。(@代表后缀式中的求负运算符) C

a. abc*cd-b@a*+/-@ b. a@bc*cd-b@a*+/- c. a@bc*cd-/b@a*+- d. a@bc*/cd-b@a*+- 5．在规范归约中，用 来刻画可归约串。 B

a. 直接短语b. 句柄

c. 最左素短语d. 素短语

10．下列动作中，不是自下而上分析动作的是： 。B

a. 移进 b. 展开 c. 接受d. 报错

11．编译程序是对 。D

a. 汇编程序的翻译 b. 高级语言程序的

解释执行

c. 机器语言的执行d. 高级语言的翻译 12．词法分析器的输出结果是 。C 的位置

c. 单词的种别编码和自身值 d. 单词自身值

13．正规式M1和M2等价是指 。C

a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 B

d. M1和M2状态数和有向边条数相等 14．在规范归约中，用 来刻画可归约串。 B

1

6．若B为非终结符，则A→α·Bβ为 项目。D

a. 归约 b. 移进

c. 接受 d. 待约

7．中间代码生成时所依据的是 。C

a. 语法规则 b. 词法规则 c. 语义规则d. 等价变换规则

8．有文法G及其语法制导翻译如下所示（语义规则中的*和+分别是常规意义下的算术运算符）：

E→E ∧ T {E.val = E.val * T.val} E→T {E.val = T.val}

T→T# n {T.val = T.val + n.val } T→ n {T.val = n.val} 则分析句子1 ∧ 2 ∧ 3 # 4其值

(1)

(1)

(1)

(1)

a. 单词的种别编码 b. 单词在符号表中

a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语

15．若a为终结符，则A→α·aβ为 项目。《编译原理》复习题

a. 归约b. 移进 c. 接受d. 待约

a. 语法规则 b. 词法规则 c. 语义规则 d. 等价变换规则

B

22．在规范归约中，用 来刻画可归约串。

16．语法分析时所依据的是 。A

素短语

23．若B为非终结符，则A→α· 为 项目。A

a. 归约 b. 移进 c. 接受d. 待约 a. 直接短语 b. 句柄 c. 最左素短语d.

17．文法G：S→xSx|y所识别的语言是 。C

a. xyx b. (xyx)* c. xnyxn (n≥0) d. x*yx*

A

24．文法G：S→xSx| xS|y所识别的语言是 。

18．如果文法G是无二义的，则它的任何句子α 。 A

定相同

能不同

c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们b. 最左推导和最右推导对应的语法树可a. 最左推导和最右推导对应的语法树必

d. x*yx*

a. xmyxn(m≥n≥0) b. (xyx)* c. xnyxn(n≥0)

25．有文法G及其语法制导翻译如下所示（语义规则中的*和+分别是常规意义下的算术运算符）：

E→E ∧ T {E.val = E.val * T.val} E→T {E.val = T.val}

T→T# n {T.val = T.val + n.val } T→ n {T.val = n.val}

则分析句子2 ∧ 3 # 4其值为 。 C

a. 10 b. 21 c. 14 d. 24

26．间接三元式表示法的优点为 。 A a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 27．下列动作中，不是自上而下分析动作的是： 。C

a@bc*cd-/b@a*+-

d.

a. 匹配b. 展开c. 接受d. 报错

(1)

(1)

(1)

(1)

对应的语法树相同

19．下列动作中，不是自上而下分析动作的是： 。C

a. 匹配 b. 展开c. 移进 d. 报错

20．词法分析器的输出结果是 。C 的位置

c. 单词的种别编码和自身值 d. 单词自身值

21． -a-(b*c/(c-d)+(-b)*a)的逆波兰表示是 。(@代表后缀式中的求负运算符) C

a.

abc*cd-b@a*+/-@

b.

a. 单词的种别编码 b. 单词在符号表中

a@bc*cd-b@a*+/-

c.

28．同正规式（a|b）+等价的正规式是______B___________。

2

a@bc*/cd-b@a*+-

《编译原理》复习题

A．（a|b）* B．（a|b）（a|b）* C．（ab）*（ab）D．（a|b）|（a|b）*

29．称有限自动机A1和A2等价是指_______D________。

A．A1和A2都是定义在一个字母表上的有限自动机

B．A1和A2状态数和有向边数相等 C．A1和A2状态数或有向边数相等 D．A1和A2所能识别的字符串集合相等 30．由文法的开始符号出发经过若干步（包括0步）推导产生的文法符号序列称为_B。

A．语言 B．句型 C．句子 D．句柄

31．在自上而下的语法分析中，应从 C 开始分析。

A．句型B．句子 C．文法开始符号 D．句柄 32．一个文法G，若C ，则称它是LL（1）文法。

A．G中不含左递归 B．G无二义性 C．G的LL（1）分析表中不含多重定义的条目 D．G中产生式不含左公因子

33．在规范归约中，用______B______来刻画可归约串。

A．直接短语 B．句柄 C．素短语 D．短语 34．若a为终结符，则A→α·aβ为_______B______项目。

A．归约 B．移进 C．接受 D．待约

产生式 义动作

S’ → S print(S.num)

语

S → (L) S.num = L.num +1

S → a

S.num = 0 L →L(1), S

L.num = L(1).num + S.num

L →S

L.num =

S.num

若输入为(a,(a))，且采用自底向上的分析方法，则输出为 C 。

A．0 B．1 C．2

D．4

37．四元式之间的联系是通过 _______B____________实现的。

A．指示器 B．临时变量 C．符号表 D．程序变量

38.将编译程序分成若干“遍”，是为了（ B ）。 A.提高程序的执行效率 B.使程序的结构更为清晰

C.利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率

39.一个编译程序在编译时，大多数时间花在

35．中间代码生成时所依据的是 （ D ）上。 C 。

A．词法规则 B．语法规则 C．语义规则 D．等价变换规则

36．文法G[S]及其语法制导翻译定义如下：

3

A.出错处理 B.词法分析 C.目标代码生成 D.表格管理及处理

40. 下列符号串不可以由符号集?＝{a,b}上的正闭包运算产生的是：（A ）

《编译原理》复习题

A. ε B. a C. aa D. ab 41.词法分析器的输出是：（ C ） A.单词在符号表中的位置 B.单词的自身值 C.单词的自身值和单词的种类码 D.单词的种类码

42. 两个DFA等价是指：（ D ） A. 这两个DFA的状态数相同

B. 这两个DFA的状态数和有向弧条数都相等 C. 这两个DFA的有向弧条数相等 D. 这两个DFA接受的语言相同

43．生成中间代码时所依据的是（ C ）。

A．语法规则 B．词法规则 C．语义规则 D．等价变换规则

44．表达式（┐a∨b）∧（c∨d）的逆波兰表示为（B ）。

A．┐ab∨∧cd∨ B．a┐b∨cd∨∧ C．ab∨┐cd∨∧ D．a┐b∨∧cd∨

45.有文法G及其语法制导翻译如下所示（语义规则中的*和+分别是常规意义下的算术运算符）： E→E(1) ∧ T {E.val = E(1).val * T.val} E→T { E.val = T.val}

T→T(1)# n {T.val = T(1).val + n.val } T→ n {T.val = n.val}

则分析句子2 ∧ 3 # 4其值为（ C ）。 A. 10 B. 21 C. 14 D. 24

46．表达式a+b+c+d的逆波兰表示为（ B ）。

A．a+bc+d+ B．ab+c+d+ C．ab+cd++ D．abc+d++

47. 文法G[S]及其语法制导翻译定义如下： 产生式 语义动作

S’ → S print(S.num) S → (L) S.num = L.num +1

S → a

S.num = 0

L →L(1), S L.num = L(1).num + S.num

L →S L.num =

S.num

4

若输入为(a,(a))，且采用自底向上的分析方法，则输出为（ C ）。

A．0 B．1 C．2 D．4

48.若a为终结符，则A→α. aβ为（ B ）。 A.归约项目 B.移进项目 C.待约项目 D.接受项目

49.若B为非终结符，则A→α. Bβ为（ C ）。 A.归约项目 B.移进项目 C.待约项目 D.接受项目

50. 项目A→α. 为（ A ）。

A.归约项目 B.移进项目 C.待约项目 D.接受项目 51. 语法分析器的输入是：（ A ）

A. Token序列 B. 源程序 C. 目标程序 D. 符号表

52. 在LR（0）的Action表中，如果某行中存在标记为“rj”的栏，则：（ A ）

A. 该行必定填满“rj” B. 该行未必填满“rj” C. 其他行可能也有“rj” D. goto表中也可能有“rj” 53. LR分析过程中栈内存储的是（ A ）。 A. 活前缀 B. 前缀 C. 归约活前缀 D. 项目 54.文法G：S → x xS | y 所识别的语言是（ D ）。 A．xxy* B．(xxy)* C．xx*yx D．(xx)*y 55.若状态k含有项目“A→α.”，对任意非终结符a，都用规则“A →α”归约的语法分析方法是（ B ）。

A．LALR分析法 B．LR(0)分析法 C．LR(1)分析法 D．SLR(1)分析法

56.在编译过程中，如果遇到错误应该( C )。 A. 把错误理解成局部的错误

B. 对错误在局部范围内进行纠正，继续向下分析 C. 当发现错误时，跳过错误所在的语法单位继续分析下去

D. 当发现错误时立即停止编译，待用户改正错误后再继续编译

57.将编译程序分成若干“遍”，是为了（ B ） A.提高程序的执行效率 B.使程序的结构更为清晰 C.利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 58.下列符号串不可以由符号集?＝{a,b}上的正闭包运算产生的是：（ A ） A. ε B. a C. aa D. ab

59.表达式（┐a∨b）∧（e∨f）的逆波兰表示为（ B ）。

A．┐ab∨∧ef∨ B．a┐b∨ef∨∧ C．ab∨┐ef∨∧ D．a┐b∨∧ef∨

60.有文法G及其语法制导翻译如下所示（语义规