《2004编译原理a》由会员分享，可在线阅读，更多相关《2004编译原理a（6页珍藏版）》请在金锄头文库上搜索。
1、莆田学院 2004-2005 学年第一学期计应、计教专业（本科）编译原理课程期末试卷 A班级_姓名_学号_题号一 (10%)二 (30%)三 (8%)四 (10%)五 (12%)六 (15%)七 (15%)总分得分阅卷教 师签名一、是非题(下列各题，你认为正确的，请在题干的括号内打“ ” ，错的打 “” 。每题 1 分，共 10 分) 1. 编译过程的多个阶段可以合成一遍完成。( ) 2. 多遍扫描的编译程序优于单遍扫描的编译程序。( ) 3. 一个句型对应的一棵语法树包括了该句型的所有推导。( ) 4. 文法的二义性与语言的二义性是两个不同的概念。( ) 5. 每个文法都能改写为 LL(1)
2、文法。( ) 6. 算符优先关系表不一定存在对应的优先函数。( ) 7. 对任何一个编译程序来说，产生中间代码是不可缺少的。( ) 8. 符号表的内容在词法分析阶段填进并在以后各阶段得到使用。( ) 9. 动态存储分配是指在编译阶段对源程序中的量进行分配，以使目标代 码在运行时加快运行速度。( ) 10. 一个基本块的出口和入口可以不唯一。( ) 二、填空题（每空 2 分,共 30 分） 1. 编译方式与解释方式的根本区别在于 。 2. 对于文法 G，仅含终结符号的句型称为_。 3. 设有文法 GT:T-T*F|F F-FP|P P-(T)|a 则该文法句型 T*P(T*F)的句柄是_。 4.
3、 编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一 个个具有独立含义的最小语法单位-_。 5. 语言集合 L(G)=an|n0相应的正规表达式为_。 6. 自顶向下语法分析方法的基本思想是：从识别符号出发，不断建立 _，试图构造一个推导序列，最终由它推导出与输入符 号串相同的符号串。 7.算符优先分析法每次都是对_进行归约。8. LR(0)中分析法的名字中， “R”的含义是_。 9. 有简单优先文法 G(S): SbAb A(B|a BAa),则存在0 and b0 then begini:=i+1;if i100 then a:=a-1else b:=b-1;end; 翻译成四元
4、式序列。 四、对以下基本块T1:=6 T2:=A*B T3:=A-B T4:=T1/3 X:=T2*T4 Y:=T2*T4 T5:=A*B T6:=T3+T5 Y:=T6 (1) 画出 DAG 图 (2) 假设只有 X，Y 在基本块出口后还被引用，写出优化后的四元式序 列。 五、设有以下文法GS:SaAbDe|d ABSD|e BSAc|cD| DSe| (1) 求出该文法的每一个非终结符的 FOLLOW 集。 (2) 该文法是 LL（1）文法吗？（说明原因） 六、设有文法S（A）AABB|BBb|c (1) 构造识别该文法活前缀的 DFA (2) 构造该文法的 SLR 分析表。 七、已知有穷
5、自动机如下图所示：（1）写出表示该状态转换图所表示的语言的正规式 （2）构造识别该语言的 DFA （3）写出表示该语言的正规文法0,10,111ABC2004-05编译原理A 参考答案 一、 二、 1用汇编语言或机器语言写的 2.句子 3.P 4. 单词 5.aa* 6.直接推导 7.最左素短语 8.最右推导 9b,a,0,102)101(j,-,-,113) 102(j,b,0,104) 103(j,-,-,113) 104(+,i,1,T1) 105(:=,T1,-,i) 106(j,i,100,108) 107(j,-,-,111) 108(-,a,1,T2) 109(:=,T2,a)
6、110(j,-,-,113)111(-,b,1,T3) 112(:=,T3,-,b) 113 四、T2:=A*B T3:=A-B X:=T2*2 Y=T3+T2五、(1) FOLLOW(S)=a,b,c,d,e,# FOLLOW(A)=b,c FOLLOW(B)=a,d FOLLOW(D)=a,b,c,d,e (2) 该文法不是 LL（1）文法。 因为产生式 BSAc|cD| 中FIRST(SAc)FOLLOW()=a,d 六、I9I8I7I6I4I3I2I1I0cccbbSS S（A ）SSBbS(A) AABB AB Bb BcABBcS（A） S（A ） AABB Bb BcAABBAA
7、BB Bb BcBBBSA） （bI5FOLLOW(S)=# FOLLOW(A)=b,c,） FOLLOW(B)=b,c,）ACTIONGOTO状态 bc()#SAB0S211acc2S5S6343S5S6S784r3r3r35r4r4r46r5r5r57r18S5S699r2r2r2七、 （1） （0|1）*11（0|1）* （2）确定化I 改名01A AA AA,B BA,B BA AA,B,C CA,B,C CA,C DA,B,C CA,C DA,C DA,B,C C最小化 可分为三个等价集A,B,C,D(3) 正规文法GA:A0A|1BB-0A|1C|1C-0C|1C|0|100011011ABCD00,1011ABC
