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

广东技术师范学院2011-2012学年第（2）学期期末考试试卷(参考答案及评分标准)科目：编译原理 （A）卷一、 填空题：（每个空2分，共20分）（1）编译程序 就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。（2）算符优先分析方法是在 最左素短语 来刻画可规约串的。（3）若某NFAM确定化后为DFAM，则它们能够识别的语言是 相同的 。（4）在规范规约中用 句柄 来刻画可规约串。（5）算符优先分析法是一种简单且直观的自上而下分析方法，它特别适合于分析程序语言中的 各类表达式。（6）语法制导翻译的方法就是为文法的每个产生式，配上一个翻译子程序，并在语法分析的同时 执行这些子程序。（7）语法分析程序简单的说就是读单词程序，该程序利用高级语言编写的源程序，将原程序中由单词符号组成的字符串分解在 一个个单词 来。最终输出是源程序等价的单词符号序列。（8）若给定算符优先文法GE:EE+TT TTFF 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.给定文法GS:SaBA AcBA|* Bi 其中FOLLOW（B）= C A a B a,i C c # D i #4.设有文法GT: TT*F|F FFP|P P（T）|a句型T*P（T*F）的句柄是符号串 CA (T*F): B T*F: C P: D P（T*F）:5.有一语法制导翻译如下所示：SxxW print“1”Sy print“2”WSz print“3”若输入序列为“xxxxyzz”，且采用自上而下的分析方法，则输出序列是AA 23131 B 11233 C 11231 D 332116.构造编译程序应掌握 DA源程序 B目标语言 C编译方法 D以上三项都是7.赋值语句x=a+b*c-d的逆波兰式应为BA xab+c*d-= B xabc*+d-= C xabcd*+-= D x=abc*+d-8.表达式（AB）（CD）的逆波兰表示为BA ABCD B ABCD C ABCD D ABCD三、求解问题（共22分）（1）给定NFAM如图1，试用子集法确定化（不要求化简，要描述转换表并将结果画图,12分）（2）化简图2所示DFAM（要求描述化简过程和最终DFAM图，10分）解：确定化IIaIbX112，Y2，Y1新状态编号，则有，IIaIb01121确定化后的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图为：四、已知文法GS如下，GS:SBB BaB|b已给其拓广文法的项目集规范族如下,GS的DFA，试完成构造LR（0）分析表的未完成部分（共10分）解：文法GS的LR(0)分析表状态ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2五、（共12分）给定文法GEGE:(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi及其SLR（1）分析表如下，i*i的LR分析过程状态状态栈符号栈输入串说明（可省略）10#i*i#移进205#i*i#规约303#F*i#规约402#T*i#移进5027#T*i#移进60275#T*i#规约702710#T*F#规约802#T#规约901#E#acc六、考查基本块：（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=AFL+BFL（3） CFL=TFF/WFF变量名代用信息活跃信息初值待用信息链初值活跃信息T