编译原理复习题

编译原理复习题

一、

选择题

B、汇编语言的翻译

D、高级语言程序的解释执行

1、 编译原理是对(C)。

A、机器语言的执行 C、高级语言的翻译

2、 (A)是一种典型的解释型语言。

A．BASIC

B．C

C．FORTRAN

D．PASCAL

3、 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器

B. 汇编器

C. 解释器

D. 预处理器

4、 用高级语言编写的程序经编译后产生的程序叫(B)

A．源程序

B．目标程序

C．连接程序

D．解释程序

5、 (C)不是编译程序的组成部分。

A.词法分析程序

B.代码生成程序

C.设备管理程序

D.语法分析程序

6、 通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器

B．解释器

C．表格处理和出错处理 D．符号执行器

7、 编译程序绝大多数时间花在(D)上。

A．出错处理

B．词法分析

C．目标代码生成

D．表格管理

8、 源程序是句子的集合，(B)可以较好地反映句子的结构。

A. 线性表

B. 树

C. 完全图

D. 堆栈

9、 词法分析器的输出结果是(D)。

A、单词自身值

B、单词在符号表中的位置 D、单词的种别编码和自身值

C、单词的种别编码 10、 词法分析器不能(D)

A. 识别出数值常量

B. 过滤源程序中的注释 D. 发现括号不匹配

C. 扫描源程序并识别记号

11、 文法：G：S→xSx | y所识别的语言是(D)。

A、xyx

B、(xyx)*

C、x*yx*

D、xnyxn (n≥0)

12、 如果文法G是无二义的，则它的任何句子α(A)

A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同

D．可能存在两个不同的最左推导，但它们对应的语法树相同

13、 正则文法(A)二义性的。

A. 可以是

B. 一定不是

C. 一定是

14、 (B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。

A. 存在

B. 不存在

C. 无法判定是否存在

15、 给定文法A→bA | ca，为该文法句子的是(C)

A. bba

B. cab

C. bca

D. cba

16、 设有文法G[S]：S?S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D)

A. ab0

B. a0c01

C. a0b0a

D. bc10

17、 文法G产生的(D)的全体是该文法描述的语言。

A．句型

B. 终结符集

C. 非终结符集

D.句子

18、 若文法G定义的语言是无限集，则文法必然是(A)

A．递归的

B. 上下文无关的

C. 二义性的

D. 无二义性的

19、 描述一个语言的文法是(B)

A．唯一的

B. 不唯一的

C. 可能唯一

20、 一个文法所描述的语言是(A)

A．唯一的

B. 不唯一的

C. 可能唯一

21、 采用自上而下分析，必须(A)。

A、消除回溯

B、消除左递归 D、提取公共左因子

C、消除右递归

22、 编译过程中，语法分析器的任务是(A)

① 分析单词的构成 ② 分析单词串如何构成语句 ③ 分析语句是如何构成程序 ④ 分析程序的结构 A. ②③

B. ④

C. ①②③④

D. ②③④

23、 词法分析器的输入是( A)。

A．符号串

B．源程序

C．语法单位

D．目标程序

24、 两个有穷自动机等价是指它们的(C)。

A．状态数相等 C．所识别的语言相等

B．有向弧数相等

D．状态数和有向弧数相等

25、 若状态k含有项目“A→α· ”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的

语法分析方法是(D)。

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

26、 若a为终结符，则A→α · aβ为(B)项目。

A．归约

B．移进

C．接受

D．待约

27、 在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分(A)错误。

A. 语法

B. 语义

C. 语用

D. 运行

28、 乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是(B)

A. 非限制文法

B. 正则文法

C. 上下文有关文法

D. 上下文无关文法

29、 一个句型中的(A)称为该句型的句柄。

A. 最左直接短语

B. 最右直接短语

C. 终结符

D. 非终结符

30、 在自底向上的语法分析方法中，分析的关键是(D)

A. 寻找句柄

B. 寻找句型

C. 消除递归

D. 选择候选式

31、 在自顶向下的语法分析方法中，分析的关键是(C)

A. 寻找句柄

B. 寻找句型

C. 消除递归

D. 选择候选式

32、 在LR分析法中，分析栈中存放的状态是识别规范句型(C)的DFA状态。

A.句柄

B. 前缀

C. 活前缀

D. LR(0)项目

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集合、FOLLOW集合均是(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，则符号串①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc中，是该文法句子的是(D)

A. ①

B. ③④⑤

C. ②④

D. ①⑤

48、 LR(1)文法都是()

A. 无二义性且无左递归

B. 可能有二义性但无左递归 D. 可以既有二义性又有左递归

C. 无二义性但可能是左递归

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、 若B为非终结符，则 A→?.B? 为(D)。

A.移进项目

B.归约项目

C.接受项目

D.待约项目

52、 同心集合并可能会产生新的(D)冲突。

A.二义

B.移进/移进

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.最左推导和最右推导必定相同

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/** 61、 (D)不是NFA的成分。

A. 有穷字母表 62、

二、 简答题

1、 编译程序

将高级语言的源程序翻译成低级语言的程序称作编译程序。 2、 编译程序和解释程序有哪些区别？

解释程序是源程序的一个执行系统，而编译程序是源程序的一个转换系统；解释器直接由源程序得到运行结果，而编译器是生成等价于源程序的某种目标机程序。

3、 词法分析

从左到右地一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，识别出

B. 初始状态集合

C. 终止状态集合

D. 有限状态集合

B．ABCCD/*-*

C．ABC-*CD/*

D．以上都不对

现给出一个NFA:M=(Σ,Q,0,{9},f) 其中Σ={羊，空，菜，狼} Q={0,1,2,3,4,5,6,7,8,9}

转换函数

f(0,羊)=1, f(1,空)=2, f(2,菜)=3, f(2,狼)=5, f(3,羊)=4 f(5,羊)=6, f(4,狼)=7, f(6,菜)=7, f(7,空)=8, f(8,羊)=9

37、 简单描述由下面的产生式对应的文法生成的语言： S→aA A→bS S→?

Answer： S?aA?abS?abaA?ababS 由此可得， L(G)={(ab)n：n≥0}

38、 在∑={a，b}上构造接受下面语言的DFA： L={ w：|w| mod 3 = 0}

Answer：

使用标记为|w| mod 3的状态，则解是：

39、 在∑={0，1}上，构造接受下列语言的DFA：

每个00后面都紧跟着1的符号串。如101，0010，0010011001都属于这种语言，而0001和00100不属于。

Answer： 对连续的0的个数进行计数，从而得到DFA的主要部分：

然后加入其他转换以处理连续的0，并为不可能接受的符号串设置陷井(trap)。

40、 找到一个DFA，识别所有前缀为ab，定义在∑={a，b}上的符号串。

这里需要考虑的只有符号串的前两个符号；读入这两个符号后，符号串余下的部分就不必理会了。因此，我们设计一个四状态的自动机来解决这个问题。这四个状态分别是：初态、两个识别ab并最终进入终态的状态，和一个非终态的陷井状态。

如果第一个符号是a，第二个符号是b，那么自动进入终态。而且，不管剩下的输入是什么，它都会停留在这个状态中。另外，如果第一个符号不是a，或者第二个符号不是b，那么自动进入非终态的陷井状态中。

41、 给出句型F+T*F的短语、直接短语和句柄

Answer：

短语：F，T*F，F+T*F 直接短语：F，T*F 句柄：F

42、 给出句型E+T*i的短语，直接短语和句柄

Answer：

短语：i，T*i，E+T*i 直接短语：i 句柄：i

43、 已知文法： S?aAB A?bBb B?A|?

给出符号串abbbb的最左推导和最右推导。 最左推导是：

S?aAB?abBbB?abAbB?abbBbbB?abbbbB?abbbb 最右推导是：

S?aAB?aA?abBb?abAb?abbBbb?abbbb

44、 文法G[S]为： S?Ac|aB A?ab B?bc

该文法是否为二义的？为什么？ [答案]

对于串abc

(1) S=>Ac=>abc (2) S=>aB=>abc

即存在两不同的最右推导，所以该文法是二义的。

45、 文法G[S]为： S?Ac|aB A?ab B?bc

写出L(G[S])的全部元素。 [答案]

S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc}

46、 设计一个接受语言L((a|b)*b(a|bb)*)的NFA

47、 已知Σ={a，b，c}，构造L的正则表达式： L={w：|w| mod 3 = 0}

产生所有长度为3的符号串并重复。解为： ((a|b|c)(a|b|c)(a|b|c))*

48、 包含偶数个0的0、1串。

产生两个0，中间填入一些1，然后重复。但要记住，一个0都没有的情况。解为： (1*01*01*)*|1*

49、

三、 分析题

1、 证明下面文法：

S?AaAb|BbBa A?? B??

是LL(1)文法，但不是SLR(1)文法。

Answer：

(1) 因为仅非终结符S有两个不同的选择，只考虑S的两个右部，由于

First(AaAb) = {a} First(BbBa) = {b}

First(AaAb) ∩ First(BbBa) = φ 所以该文法为LL(1)文法。 (2) 由于

Follow(AaAb) = {a，b} Follow(BbBa) = {a，b}

First(AaAb) ∩ First(BbBa) ≠ φ

对任何句子，在面临第一个符号时的空规则中，不知道应该将?规约为A还是B，存在归约-归约冲突，因而不是SLR(1)文法。

2、 设有正规式r=1(0|1)*101，试给出：

(a) 识别该正规集的NFA；

(b) 识别该正规集的DFA并最简化(要有计算过程)；

3、 已知正规式R=l(l|d)*，求最小DFA

分裂法子集法解：步骤：

1o 求NFA

l(l|d)*

x

2o 求DFA

子集法：构造确定化的矩阵

分割法R=>NFA=>DFA=>最小DFAl x l 1 ε 2 ε d y 分裂： y l A l B l d C d

3o 最小化DFA

分割法：首先将DFA分解成两个子集： π =({A},{B,C})

0分解{B,C}： 对l：

对d：

∴B,C等价：去掉C 最小化DFA：

l A l B d 非l 非d Z

注：实现时，扩充为：

l A l B d

且规定：字符串的长度为n,

4、 试写出在∑={a,b}上且不以a开头，但以aa结尾的字符串集合的正规式，并构造与之等价且状态最少的DFA。

根据状态矩阵得到状态图DFA M1 b 1

b 3 a b

a b a

b

0 2 4 a

最后，最小化。 先将状态分为非终结状态集{0,1,2,3}和终态集(4)。由状态矩阵（也可按最小化划分的方法求得）可知1和3状态在输入a或b所对应的下一个状态是对应相同的，故最后的划分为：{0},{1,3},{2},{4}。重新命名状态组{0}=0,{1,3}=1,{2}=2,{4}=3,则可得化简后的转换矩阵和最小化的DFA M:

5、 已知文法G[S]为： S→aAd|；Bd|aB↑|；A↑ A→a B→a ① 试判断G[S]是否为LALR(1)文法 ② 当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。

6、 将文法G改写成等价的LL(1)文法，并构造预测分析表。 G：S→S*aT|aT|*aT T→+aT|+a

解：消除左递归后的文法G’: S→aTS’|*aTS’

S’→*aTS’|ε T→+aT|+a

提取左公因子得文法G’’:S→aTS’|*aTS’

S’→*aTS’|ε T→+aT’ T’→T|ε

Select(S→aTS’)={a} Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}

Select(T’→T)=First(T) ={+}

Select(T’→ ε)=Follow(T’)={*,#} Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a S S’Ta, N S’ S’Ta, N T T’ ε, P a #

7、 已知文法G[S]：

T’a, N T, P TS’T, N ε, N # ε, P ε, P OK S→ UTa | Tb T→ S | Sc | d U→ US | e

(1) 试判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。 (2) 构造相应的分析表。

解：

(1) 首先拓广文法为G'，增加产生式S'→S

(0) S'→S (1) S→UTa (2) S→Tb (3) T→S (4) T→Sc (5) T→d (6) U→US (7) U →e G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

（2）在I1中：

S' →S.为接受项目，T →S. 为归约项目，T →S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR(0)文法。 在I1中：

Follow(S') ∩ Follow(T)= { #} ∩{a ，b}=

Follow(T) ∩{ c}= { a ，b} ∩{c}= 在I8中：

Follow(U) ∩ Follow(T) ∩{ c}={d,e}∩{ a ，b} ∩{c}=

所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下： 状态(State) 0 1 2 3 4 5 6 7 8 9 10 8、 文法G及其LR分析表如下，请给出对串dada#的分析过程。

G: S → VdB ①

V → e ② V → ε ③ B → a ④ B → Bda ⑤ B → ε ⑥ 状态 0 1 2 3 4 5 6 7 8 ACTION d S4 r2 r6 r4 S7 r5 e a S5 S8 # acc r6 r4 r1 r5 S 1 r3 S3 GOTO B 6 V 2 Action a b c d e # S5 S4 r3 r3 S6 Acc S5 S4 S9.................. r7 r7 r5 r5........................ r4 r4......................... S10 S9......................... r3 r3. S6 r6 r6...... r2 r2. r2 r2 r2 r2 r1 r1. r1 r1 r1 r1 Goto S U T 1 2 3 . 8 2 7 解：对输入串dada#的分析过程 步骤 状态栈 1 0 符号栈 # 剩余输入符号 动作 dada# 用V →ε归约 2 3 4 5 6 7 8 9 02 024 0245 0246 02467 024678 0246 01 #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S dada# ada# da# da# a# # # # 移进 移进 用B →a归约 移进 移进 用B →Bda 归约 用S →VdB 归约 接受 9、 设有文法G[S]: S ? LaR|R L ? bR|c R ? L

判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR分析表。

LR(1)状态机如下：

因为状态机中没有冲突，所以是LR(1)文法。 LR(1)分析表如下： (1) S? LaR (2) S? R (3) L? bR (4) L? c

(5) R? L

1 2 3 4 5 6 7 8 9 10 11 12 13 14 a R4 S7 R5 R3 b S6 S6 S12 S12 c S4 S4 S13 S13 # Acc R2 R4 R5 R5 R3 R1 R5 R4 R3 S 2 L 5 8 11 11 14 R 3 9 10

10、 证明下面文法是SLR(1)文法，并构造其SLR分析表。

E?E + T | T T?T F | F F?F* | a | b

11、 证明下面文法是SLR(1)文法, 并构造其SLR分析表. E ? E + T (1) E ?T (2) T ? T F (3) T ?F (4) F ? F* (5) F ? a (6) F ? b (7)

本文来源：https://www.bwwdw.com/article/bocg.html