编译原理期末考试试题.doc

广东技术师范学院 2011-2012学年第（2）学期期末考试试卷 (参考答案及评分标准) 科目：编译原理 （A）卷 填空题：（每个空2分，共20分） （1）编译程序 就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。 （2）算符优先分析方法是在 最左素短语 来刻画可规约串的。 （3）若某NFAM确定化后为DFAM，则它们能够识别的语言是 相同的 。 （4）在规范规约中用 句柄 来刻画可规约串。 （5）算符优先分析法是一种简单且直观的自上而下分析方法，它特别适合于分析程序语言中的 各类表达式。 （6）语法制导翻译的方法就是为文法的每个产生式，配上一个翻译子程序，并在语法分析的同时 执行这些子程序。 （7）语法分析程序简单的说就是读单词程序，该程序利用高级语言编写的源程序，将原程序中由单词符号组成的字符串分解在 一个个单词 来。最终输出是源程序等价的单词符号序列。 （8）若给定算符优先文法G[E]:E→E+TT T→TFF F→（B）则FIRSTVT(T)={*，*，i} （第8题待定） （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分） 解：①确定化 I Ia Ib {X} ф {1} {1} {2，Y} ф {2，Y} ф {1} 新状态编号，则有， I Ia Ib 0 ф 1 1 2 ф ② ф 1 确定化后的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分） 解：文法G[S]的LR(0)分析表 状态 ACTION GOTO a b # S B 0 s3 s4 1 2 1 acc 2 s3 s4 5 3 s3 s4 6 4 r3 r3 r3 5 r1 r1 r1 6 r2 r2 r2 五、（共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）分析表如下， i*i的LR分析过程 状态 状态栈 符号栈 输入串 说明（可省略） 1 0 # i*i# 移进 2 05 #i *i# 规约 3 03 #F *i# 规约 4 02 #T *i# 移进 5 027 #T* i# 移进 6 0275