编译原理复习题及答案
一、 选择题
1． 一个正规语言只能对应( B )
A 一个正规文法 B 一个最小有限状态自动机
2． 文法G[A]：A→ε A→aB B→Ab B→a是( A )
A 正规文法 B 二型文法
3． 下面说法正确的是( A )
A 一个SLR（1）文法一定也是LALR（1）文法
B 一个LR（1）文法一定也是LALR（1）文法
4． 一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A )
A 必要条件 B 充分必要条件
5． 下面说法正确的是( B )
A 一个正规式只能对应一个确定的有限状态自动机
B 一个正规语言可能对应多个正规文法
6． 算符优先分析与规范归约相比的优点是( A )
A 归约速度快 B 对文法限制少
7． 一个LR（1）文法合并同心集后若不是LALR（1）文法( B )
A 则可能存在移进/归约冲突
B 则可能存在归约/归约冲突
C 则可能存在移进/归约冲突和归约/归约冲突
8． 下面说法正确的是( A )
A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器
9． 下面说法正确的是( A )
A 一个正规文法也一定是二型文法
B 一个二型文法也一定能有一个等价的正规文法
10． 编译原理是对(C)。
A、机器语言的执行 B、汇编语言的翻译
C、高级语言的翻译 D、高级语言程序的解释执行
11． (A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL
12． 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。
A. 编译器 B. 汇编器 C. 解释器 D. 预处理器
13． 用高级语言编写的程序经编译后产生的程序叫(B)
A．源程序 B．目标程序 C．连接程序 D．解释程序
14． (C)不是编译程序的组成部分。
一、画图( 每题参考分值5分 )
1、设有布尔表达式文法G【B】： B→B or T | T
T→T and F | F
F→not F | （B） | true | false
给出句型 true and not false or F的语法树，以及所有直接短语、句柄。
正确答案：
直接短语：true
false
F
句 柄 ：true
2、设有基本块：
t1＝3*A
t2＝2*C
t3＝t1＋t2
t4＝t3十5
t5＝2*C
t6＝3*A
t7＝t6＋t5
M＝t7－1
N＝t4－M
1．画出DAG图；
2．假设只有M，N在基本块后面还要被引用，请写出优化后的代码序列。
正确答案：
答：
DAG：
优化后的代码
1． t1＝3*A
2． t2＝2*C
3． t3＝t1＋t2
4． t4＝t3＋5
5． M＝t3－1
6． N＝t4－M
3、设有布尔表达式文法G【B】： B→B or T | T
T→T and F | F
F→not F | （B） | true | false
给出句子 （ true or false）and not false的推导和语法树。
正确答案：
解：
B T T and F F and
F
（B）and
F
（B or T）and F
（T or T）and F （F or T）and F （true or T）and F
编译原理答疑题
1． 编译程序的结构是什么?
答：编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。
2． PL／0编译程序的结构是什么？
答：由PL／0的EBNF可知，PL／0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL／0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL／0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL／0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分
析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。当源程序编译正确时，PL／0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。
3．关系有哪些基本性质？
答：自反的 在集合X上的关系R，如对任意x∈X，均有(x，x) ∈R，则称关系R是自反的。
非自反的 在集合X上的关系R，如对任意x∈X，均有(x，x)R，则称关系R是非自反。
对称的 在集合X上的关系R，如果合(x，y) ∈R，便必有(y，x) ∈R，则称关系R是对
称的。
非对称的 在集合X上的关系R，如果有(x，y) ∈R丛x≠y，便必有(y，x)R，则称关系R是非对称的。
传递的 在集合X上的关系R，如果合(x，y) ∈R且(y，z) ∈R，必有(x，z) ∈R，则称关系R是传递的。
第3章 习题解答
1.构造正规式1(0|1)*101相应的DFA.
[答案]
先构造NFA
确定化 0 1
X A
A A AB
AB AC AB
AC A ABY
ABY AC AB
重新命名，令AB为B、AC为C、ABY为D
0 1
X A
A A B
B C B
C A D
D C B
转化成DFA：
==============================================================
2.将下图确定化：
[答案] 0 1
S VQ QU
VQ VZ QU
QU V QUZ
VZ Z Z
V Z
QUZ VZ QUZ
Z Z Z
重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。
0 1
S A B
A C B
B D E
C F F
D F
E C E
F F F
转化为DFA：
================================================================
3.把下图最小化：
[答案]
（1）初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5} 对非终态组进行审查： {1,2,3,4,5}a {0,1,3,5}
而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}
∵{4} a {0}，所以得新分划
（2）Π1：{0}，{4}，{1,2,3,5}
对{1,2,3,5}进行审查：
∵{1,5} b {4}
{2,3} b {1,2,3,5}，故得新分划
（3）Π2：{0}，{4}，{1, 5}，{2,3}
{1, 5} a {1, 5}
{2,3} a {1,3}，故状态2和状态3不等价，得新分划
