编译原理试卷及答案
课程名称：
编译原理
试卷：(B )答案
考试形式： 闭卷
授课专业： 计算机科学与技术 考试日期: 年 月曰 试卷：共_2_页
一、 填空题(每空2分，共30分)
1、 编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、
中间代码生成、
代码优化
和目标代码生成等几个阶段，另外还有两个重要的工
作是 理 和出错处理。表格管
2、 规范规约中的可归约串是
句柄 ，算符优先分析中的可归约串是 最左素短语 3、 语法分析方法主要可分为
自顶向下 和 自底向上
两大类。
4、 LR (0)文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。
5、 数据空间的动态存储分配方式可分为
栈式 和 堆式 两种。
6、 编译程序是指能将 源语言程序翻译成
目标语言程序的程序。
7、 确定有穷自动机 DFA 是 NFA 的一个特例。 &表达式 (a+b)*c 的逆波兰表示为 ab+c* 。
二、 选择题(每题2分，共20分)
1、 LR 语法分析栈中存放的状态是识别
B 的DFA 状态。
A 、前缀
B 、可归前缀
C 、项目
D 、句柄
2、 D ___ 不可能是目标代码。
A 、汇编指令代码
B 、可重定位指令代码 3、 一个控制流程图就是具有
C
的有向图
A 、唯一入口结点
B 、唯一出口结点
C 、唯一首结点
D 、唯一尾结点 4、 设有文法 G[S] : S T b|bB
B 宀bS ，则该文法所描述的语言是
C 。
A 、L (G ) ={b i |i > 0}
B 、L (G ) ={b 2i |i > 0}
C 、L (G ) ={b 2i+1|i > 0}
D 、L (G ) ={b 2i+1 |i > 1}
5、 把汇编语言程序翻译成机器可执行的目标程序的工作是由
B 完成的。
A 、编译器
B 、汇编器
C 、解释器
D 、预处理器
6、 在目标代码生成阶段，符号表用于
D 。
A 、目标代码生成
B 、语义检查
C 、语法检查
D 、预处理器地址分配 0
7、 规范归约是指
B
。
A 、最左推导的逆过程
B 、最右推导的逆过程
C 、规范推导
D 、最左归约逆过程
8、 使用 A 可以定义一个程序的意义。
A 、语义规则
B 、词法规则
C 、语法规则
D 、左结合规则
9、 经过编译所得到的目标程序是
D 。
A 、三元式序列
B 、四元式序列
C 、间接三元式
D 、机器语言程序或汇编语言程序 10、 在一个基本块内进行的代码优化是 _______ B ______ 。
A 、全局优化
B 、局部优化
C 、循环优化
D 、代码外提
三、简答题(3小题，共30 分) 1、已知文法 G[S] : S T Ac|aB
A T ab
B T bc
证明该文法具有二义性
(本题6 分)
证明：因为该文法的句型 abc 存在如下两棵语法树:
东北大学秦皇岛分校
C 、绝对机器指令代码
D 、中间代码 题号
-一一
-二二
四
总分
得分
阅卷人
装 订 线 内 不
所以，该文法具有二义性
四、综合题（20分）
装订线内不3、若有文法G[S] : S T bAb A（B|a B Aa）。构造该文法的简单优先关系矩阵。
（10 分）
解:
3b A B a(
S
b<0
A F
B>
a>>X
(<=1c
)
4、构造正规表达式（a|b）* b的DFA并化简。（14分）
解：先构造其NFA如下:
确定化为DFA :
i L U
|S,A.B| (J IA.B1 1(A-H-Zi 2
lA.e} i机旬】l&B 対i
1A.BJI 1仇別1JA.BZJ ‘2
设有文法G[S]:S T BA A T BS|d B T aA|bS|c
（1
）
证明文法G是LL （1）文法。
（2
）
构造LL （1）分析表。
（3
）
写出句子adccd的分析过程。
解:( 1)
由A-ES|d^；
F[KST H -aA|bS|c 得： FJRST(tA)nFiiiSTXbs)nnitST(cp=(a}n |b} n . 可 见，文法G是是LL( 1)文法。 ' ~ r- a b c d s S—HA S—BA S-RA A A -RS A—BS A—RS A-d B B 一aA B *t$RY (3)当H黑入符号输入串1 色deed# HAB a deed# ttA心n deed# AAA D evd# #Ad d #A c c矿 c c K W 祐L 斗AB c IfAc c d# #d d 备注：学生不得在试题纸上答题（含填空题、选择题等客观题 填空题（每空1分，共20分） 1 ?编译过程一般分为 _________________ 、_______________ 、中间代码生成、和目标代码生成五个阶段。 2 ?语法分析最常用的两类方法是______________________ 和___________________ 分析法。 3 ?确定的有穷自动机是一个___________ ，通常表示为_________________________________ 。 4 ?所谓最右推导是指________________________________________________________________ 。 5 ?语法分析器的任务是______________________________________________________________ 。 6 .如果一个文法的任何产生式的右部都不含有—的非终结符，则这种文法称为 __________ 文法。 7 ?进行确定的自上而下语法分析要求语言的文法是无________________ 和 的。 8 ? LR分析法是一种____________________________________________ 的语法分析方法。 9 ?根据优化对象所涉及的程序范围，代码优化分为_______________________ 、_______________ 和— 等。 是非题（下列各题，你认为正确的，请在题后的括号内打“ V”，错的打“X 6 ?一个LL（ I）文法一定是无二义的。............................................. （ 7 ?在规范规约中用最左素短语来刻划可归约串。.................................. （） 8 ?目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。............. （） 9 ?编译程序是对汇编程序的翻译。............................. （ 10 ?逆波兰法表示的表达式亦称前缀式。.................................... （ 三、简答题（每题5分，共15分） 1、简述栈式存储管理策略； 2、何谓DAG ; 3、何谓文法的二义性; 四、给岀下述文法对应的正规式（7分） S T 0A| 1B A T 1S | 1 B T 0S | 0 五、已知文法G（E）: E T T | E+T | E -T T T F | T*F | T/F F T（E） | i 证明E+T*F是该文法的一个句型，并指岀该句型的所有短语、直接短语和句柄。 每题2分，共20分） 1 ?正规文法产生的语言都可以用上下文无关文法来描述。 ............... （） 2 ?仅考虑一个基本块，不能确定一个赋值是否真是无用的。.......................... （） 3 ?如果一个文法是递归的，则其产生的语言的句子是无穷个。（） 4 ?四元式之间的联系是通过符号表实现的。......................................... （）5?文法的二义性和语言的二义性是两个不同的概念。 （ ）六、设有文法G[S]: S aBc|bAB A aAb|b B b| ￡ 10.常用的优化技术包括: _______________ 、强度削弱、复写传播、 （8 分） .（10 构造其L L（1）分析表，并分析符号串baabbb是否是该文法的句子 分） 七、设有文法G[E]: 1、x 2、V 3、V 4、X 5、V 6、“7、X 8、V 9、X 10、X E （E） | ￡ 试判断该文法是否为SLR（1）文法，若不是，请说明理由；若是请构造SLR（1）分析表。（10 分） 八、假设可用寄存器为R0和R1，试写岀下列四元式序列对应的目标代码。（10 分） T仁B-C T2=A*T1 T3=D+1 T4=E-F T5=T3*T4 参考答案 、填空题（1X20=20分） 1.词法分析、语法分析、代码优化 2.自上而下、自下而上 3.五元组、DFA=(K , E, M, S, Z) 4. 任何一步都是对中最右非终结符进行替换 5. 分析一个文法的句子结构 6. 相邻、算符 7. 左递归、公共左因子 8. 自下而上 9. 局部优化、循环优化、局部优化 10 . 删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除 无用赋值（任选3个） 、是非题（2X10=20分） 三、简答题（见书中相应部分） 四、解：首先得正规式方程组： (5X3=15 分) (8分) S=0A+1B A=1S+1 B=0S+0 求解该方程组得： S=(01|10)(01|10)* 五、解（2分） 是文法G[S]的句型。 短语：E+T*F, T*F （2分） 直接短语：T*F （2分） 句柄：T*F （2分） 六、解： 、因为FOLLOW(B)=FIRST(c) U FOLLOW(S)={c,#}(2 分),所以构造文法G[S]的LL （1）分析表（5 ）如下： a B c # S aBc bAB A aAb b B b ￡￡ 符号串baabbb 是该文法的句子（3分）（分析过程略）。 七（2分） 所以该文法为SLR（1）文法。‘其分析表如下：（8分） 状态ACTION GOTO ( ) # E 七、设有文法G[E]: 1、x 2、V 3、V 4、X 5、V 6、“7、X 8、V 9、X 10、X 0 S2 r2 r2 1 1 acc 2 S2 r2 3 S4 4 r1 八、目标代码为：（10 分） LD RO,B SUB RO,C LD R1,A MUL R1,R0 LD RO,D ADD R0,1 ST R1,M LD R1,E SUB RO,F MUL R0,R1 LD R1,M DIVR1,R0 ST R1,W