文档介绍：编译原理试卷及答案
秦皇岛分校东北大学
C、绝对机器指令代码D、中间代码3、一个控制流程图就是具有C的有向图
A、唯一入口结点B、唯一出口结点C、唯一首结点D、唯一尾结点4、设有文法 G[S]： S-b|bB
B-bS ,则该文法所描述的语言是C o
学号
课程名称：编译原理试卷：(B )答案考试形式：闭卷
授课专业：计算机科学与技术考试日期：年 月曰试卷：共2页
题号
—
*
四
得分
阅卷人
班级
姓名
装
订装
线
订线内不要答题
一、填空题(每空2分，共30分)
1、编译程序的整个过程可以从逻辑上划分为词法分析、、语义分析、中间代码生成、 代码优化和目标代码生成等几个阶段，另外还有两个重要的工作是理和出错处理。表 格管
2、规范规约中的可归约串是
3、语法分析方法主要可分为自顶向下和自底向上两大类。4、LR (0)文法的项目 集中不会出现移进-归约冲突和归约-归约冲突。5、数据空间的动态存储分配方式可 分为栈式和堆式两种。
6、 编译程序是指能将源语言程序翻译成目标语言程序的程序。
7、 确定有穷自动机DFA是NFA的一个特例。8、表达式(a+b)*c。
二、选择题(每题2分，共20分)
1、LR语法分析栈中存放的状态是识别的DFA状态。
A、前缀B、可归前缀C、项目D、句柄2、
A、汇编指令代码B、可重定位指令代码
A、L (G) ={bi|iN0} B、L (G) ={b2i|iN0} C、L (G) ={b2i+l | i>0} D、L (G) = (b2i+l|i>l}
5、把汇编语言程序翻译成机器可执行的目标程序的工作是由B完成的。
A、编译器B、汇编器C、解释器D、预处理器6、在目标代码生成阶段，符号表用于
D o
A、目标代码生成B、语义检查C、语法检查D、预处理器地址分配0
7、规范归约是指B。
A、最左推导的逆过程B、最右推导的逆过程C、规范推导D、最左归约逆过程8、使 用可以定义一个程序的意义。
A、语义规则B、词法规则C、语法规则D、左结合规则9、经过编译所得到的目标程 序是。
A、三元式序列B、四元式序列C、间接三元式D、机器语言程序或汇编语言程序10、 在一个基木块内进行的代码优化是
A、全局优化B、局部优化C、循环优化D、代码外提
M 简答题（3小题，共30分）1、已知文法G[S]： S-Ac|aB
A—ab B—be
证明该文法具有二义性（本题6分）
证明：因为该文法的句型abc存在如下两棵语法树：
-1 -
所以，该文法具有二义性
四、综合题（20分）
设有文法G[S]： S-BA
A-BS | d
B-*aA|bS|c
3、若有文法G[S]： S—bAb A-* （B | a B—Aa）。构造该文法的简单优先关系矩阵。
学号
班级
Lr®< R»< rNZ
一胃< _«<- s<s)
• <vs Ree他«£z«
p
y
V
L>
t
pa
q
s
H t
V
f
ca
，
S
<
m
。。1。) LHeLHETaHSULI u(sqxls》LJ u (v^hs&e
“e"一 sq-vetg
5XP) uflqdTrp msYE U (SOQMS YE“^p_sCQt<-ffl
栈
当前输入符号
输入串
#s
a
deed#
#AB
a
deed#
#AAa
a
deed#
#AA
D
ccd#
#Ad
d
ccd#
#A
c
cd#
#SB
c
cd#
#Sc
c
cd#
#S
c
d#
#AB
c
d#
#Ac
c
d#
#A
d
#
#d
d
#
#
#
S
b
A
B
a
)
s
b
<
<
A
—r
B
>
>
a
>
>
-T~
(
<
工
<
<
)
>
>
姓名
订线内不要答题
（10分）解：
4、构造正规表达式（a|b） * b的DFA并化简。（14分）解：先构造其NFA如下：
确定化为DFA：
将其最小化如下：
（1）证明文法G是LL