广东技术师范学院
2011-2012学年第（2）学期期末考试试卷
(参考答案及评分标准)
科目：编译原理（A）卷
一、填空题：（每个空2分，共20分）
（1）编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。
（2）算符优先分析方法是在最左素短语来刻画可规约串的。
（3）若某NFAM确定化后为DFAM，则它们能够识别的语言是相同的。
（4）在规范规约中用句柄来刻画可规约串。
（5）算符优先分析法是一种简单且直观的自上而下分析方法，它特别适合于分析程序语言中的各类表达式。
（6）语法制导翻译的方法就是为文法的每个产生式，配上一个翻译子程序，并在语法分析的同时执行这些子程序。
（7）语法分析程序简单的说就是读单词程序，该程序利用高级语言编写的源程序，将原程序中由单词符号组成的字符串分解在一个个单词来。最终输出是源程序等价的单词符号序列。
（8）若给定算符优先文法G[E]:E→E+T|T T→T*F|F F→（B）则FIRSTVT(T)={+，*，(} （9）采用LL（1）的分析方法时，需要消除左递归和***。
（10）在确定有限自动机DFAMd=（S,∑,*,*,Z）中，*是一个从S×∑到S的单值映射。
二、单项（共25分）
1.词法分析器的输出结果是C。
A单词的种别编码B单词在符号表中的位置
C单词的种别编码和自身值D单词自身值
2.凡圆点在最右端的项目，如A→*，成为一个“B”项目。
A移进B规约C接受D待约
3.给定文法G[S]:S→aBA A→cBA|* B→i
其中FOLLOW（B）={ C }
A a
B a,i
C c #
D i #
4.设有文法G[T]: T→T*F|F F→F↑P|P P→（T）|a
句型T*P↑（T*F）的句柄是符号串C
A (T*F):
B T*F:
C P:
D P↑（T*F）:
5.有一语法制导翻译如下所示：
S→xxW {print“1”}
S→y {print“2”}
W→Sz {print“3”}
若输入序列为“xxxxyzz”，且采用自上而下的分析方法，则输出序列是A
A 23131
B 11233
C 11231
D 33211
6.构造编译程序应掌握D
A源程序B目标语言C编译方法D以上三项都是
7.赋值语句x=a+b*c-d的逆波兰式应为B
A xab+c*d-=
B xabc*+d-=
C xabcd*+-=
D x=abc*+d-
8.表达式（﹁A∨B）∧（C∨D）的逆波兰表示为B
A ﹁AB∨∧CD∨
B A﹁B∨CD∨∧
C AB∨﹁CD∨∧
D A﹁B∨∧CD∨
三、求解问题（共22分）
（1）给定NFAM如图1，试用子集法确定化（不要求化简，要描述转换表并将结果画图,12分）
（2）化简图2所示DFAM（要求描述化简过程和最终DFAM图，10分）
解：①确定化
新状态编号，则有，
确定化后的DFAM图为
②化简：
由给定DFAM图2可知，终态集为I={2,3}
由Ia：2a=1,3a=1，所以1暂不可分。另一方面：Ib：2b=2,3b=3，最终{2,3}不可分解。
对于非终态集I={X，1}，Ia：Xa=1，1a=ф，故{X，1}需分解为{X}，{1}简化后的DFAM图为：
四、已知文法G[S]如下，
G[S]:S→BB B→aB|b
已给其拓广文法的项目集规范族如下,
G'[S']的DFA，试完成构造LR（0）分析表的未完成部分（共10分）
五、（共12分）给定文法G[E]
G[E]:(1)E→E+T
(2)E→T
(3)T→T*F
(4)T→F
(5)F→(E)
(6)F→i
及其SLR（1）分析表如下，
六、考查基本块：（11分）
（1）T=A-B
（2）W=A+B
（3）C=T/W
其中ABC为变量，TW为中间变量，
（1）试在给定表里面完成待用信息和活跃信息链填充和四元式序列标注。（2）若有寄存器R1和R2，按照目标程序生成算法转换成目标程序。
解：（1）给定四元式序列附加待用/活跃信息标记后为
（1）T(3)L=A(2)L - B(2)L
（2）W(3)L=A FL+B FL
FL FF FF
（2）目标程序
MOV R1,A
SUB R1,B
MOV R2,A
ADD R2,B
DIV R1,R2
MOV C,R1
