发布时间 : 星期二 文章编译原理复习题-给学生(2014)更新完毕开始阅读
《编译原理》复习题
27．语法错误校正的目的是为了把错误改正过来。（ × ） 28．源程序和目标程序是等价关系。（ √ ）
29．编译程序中错误处理的任务是对检查出的错误进行修改。（ × ） 30．使用有限自动机可以实现单词的识别。（ √ ）
31．一个非确定的有限自动机NFA可以通过多条路径识别同一个符号串。（ √ ） 32．最小化的DFA所识别接受的正规集最小。（ × ） 33．一个语言（如C语言）的句子是有穷的。（ × ） 34．LL（1）方法又称为预测分析方法。（ √ ） 35．一个LL（1）文法是无二义和无回溯方法。（ √ ） 36．语法分析器可以检查出程序中的所有错误。（ × ） 37．LR分析法是自上而下的语法分析方法。（ × ） 三、多项选择题
1. 编译器的各个阶段的工作都涉及到（AE ）
A. 表格处理 B. 词法分析 C. 语法分析 D. 语义分析 E. 出错处理
2. 令?＝{a,b}，则?上的符号串的全体可用下面的正规式表示。（ABE ）
A. (a|b)* B. (a*|b*)* C. (a|b)+ D. (ab)* E. (a*b*)*
3. 自上而下的分析方法有：（AD ）
A. 递归下降分析法 B. LR（0）分析法 C. LALR（1）分析法 D. LL（1）分析法 E. SLR（1）分析法 4. 文法G：G[S]：S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 是（A ）。
A. 0型文法 B. 1型文法 C. 2型文法 D. 3型文法 E. 上下文有关文法
5. 对LR分析表的构造，有可能存在的动作冲突有：（AD ）
A. 移进/归约冲突 B. 移进/移进冲突 C. 归约冲突 D. 归约/归约冲突 E. 移进冲突
6. 一个编译器可能有的阶段为（ABCDE ）
A. 词法分析 B. 语法分析 C. 语义分析 D. 中间代码生成 E. 目标代码生成
7 令?＝{a,b}，则?上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB ）
A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b
9
《编译原理》复习题
E. b (a|b)*
8. 自下而上的分析方法有：（BCE ）
A. 递归下降分析法 B. LR（0）分析法 C. LALR（1）分析法 D. LL（1）分析法 E. SLR（1）分析法
9. 一般来说，编译器可分为前端和后端，下列编译阶段可被划分为编译的前端的有：（ABCDE ）
A. 词法分析 B. 语法分析
C. 语义分析 D. 中间代码生成 E. 中间代码优化
10．令?＝{a,b}，则?上的符号串的全体可用下面的正规式表示。（ABE ）
A. (a|b)* B. (a*|b*)*
C. (a|b)+ D. (ab)* E. (a*b*)*
11．下列符号串是符号集?＝{a,b}上的正规式的有：（ ABCDE）
A. ε B. a C. ab D. (ab｜a) (ab｜a) E. ab｜ab
12．正规式服从的代数规律有：（ABDE ）
A. “或”运算服从交换律 B. “或”运算服从结合律 C. “连接”运算服从交换律 D. “连接”运算服从结合律 E. “连接”运算可对“或”运算进行分配
13． 令?＝{a,b}，则?上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB ）
A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b E. b (a|b)* 14． 一个LR分析器包括：（ADE ）
A. 一个总控程序 B. 一个项目集 C. 一个活前缀 D. 一个分析栈 E. 一张分析表
15． LR分析器的核心部分是一张分析表，该表包括（DE ）等子表。
A. LL（1）分析表 B. LR（1）分析表 C. SLR（1）分析表 D. Action表 E. goto表
16． Action表中的每一项Action[S,a]所表示的动作可能为：（ABCD ）
A. 移进 B. 接受 C. 归约 D. 出错 E. 待约 五．简答题
1．构造正规表达式((a|b)*|aa)*b的NFA。 解：
3aX?1?a?2bY?a4b
10
《编译原理》复习题
2．设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f定义如下： f(x,a)={x,y} f{x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M′。
解：对照自动机的定义M=(S,Σ,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。 先画出NFA M相应的状态图，如下图所示。
aaXbbYb
用子集法构造状态转换矩阵，如下表所示。
I Ia Ib {x} {x,y} {y} {y} — {x,y} {x,y} {x,y} {x,y}
将转换矩阵中的所有子集重新命名，形成下表所示的状态转换矩阵，即得到
f 字符 状态 a b 0 2 1 1 — 2 2 2 2
M′=({0,1,2},{a,b},f,0,{1,2})， aM′状态转换图如下图所示。
02a, b bb
1
（注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。）
3．画出编译程序的总体结构图，简述各部分的主要功能。
解：编译程序的总体框图如下所示：
11
《编译原理》复习题
表词法分析器单词符号语法分析器语法单位语义分析与中间代码生成器出格错管四元式优化段四元式目标代码生成器目标代码处理理 （1）词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个单词符号，其输出结果是二元式(单词种别，单词自身的值)流。
（2）语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的句子。
（3）语义分析及中间代码生成器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。
（4）优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。 （5）目标代码生成器，把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。
（6）表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断和表格打交道。
（7）出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。
4．构造一个DFA，它接受Σ = {0, 1}上所有满足如下条件的字符串：每个1后面都有0直接跟在右边。 解：（1）0*(0|10)*0* 或者 (0|10)*
（2）
①NFA （2分）
0 X ε 0 ε 1 1 2 ②子集法确定化
I
0 ε 3 0 ε Y 0 I0 I1 12