上海大学编译原理试卷-2014春(附答案)演示教学.doc

上海大学编译原理试卷2013-2014春(附答案)精品文档试卷序号： 第 1 页 ( 共 8 页 )上海大学 2013 2014 学年春 季学期试卷A课程名： 编译原理 课程号： 08305013 学分： 5 参考答案题号一（10）二(10)三(10)四(15)五(12)六(15)七(12)八(16)得分 一、判断题（本大题共10 小题，每小题1 分，共10 分）判断下列各题正误，正确者在括号内打“”，错误者在括号内打“”。 1. 对中间代码的优化不依赖于具体的计算机。 （ ）2. 程序流图中的每条回边对应于一个循环。 （ ）3. 自底向上语法分析时必须先消除文法中的左公共因子。 （ ）4. 使用逆波兰式描述表达式时无须使用括号。 （ ）5. 编译程序是对高级语言程序的解释执行。 （ ）6. 符号表内容的一个重要作用是作为上下文语义合法性检查的依据。 （ ） 7. 状态中含有冲突的文法有可能是一个SLR(1)文法。 （ ） 8. 语义处理中“拉链”的作用是使“回填”更为有效。 （ ）9. 算符优先分析法是一种自下而上的语法分析方法。 （ ）10. 编译程序能找出源程序中所有错误。 （ ） 成绩得分阅卷人二、选择题（本大题共10 小题，每小题1 分，共10 分）在每小题列出的备选项中只有一个是符合题目要求的，请将其代码填写在题中的空格内。错选、多选或未选均无分。1 以下优化技术除 b 外，都是针对循环优化进行的。a) 强度削弱 b) 删除多余运算 c) 变换控制条件 d) 代码外提2下列 d 工作不属于编译阶段的前端。 a) 语法分析 b) 词法分析 c) 中间代码生成 d) 目标代码生成3 表达式 (a + b)*c / d对应的逆波兰式是 a 。 a) ab+c*d/ b) abc+/*d c) ab*c+/d d) abc*/d+4一个句型中称为句柄的是该句型中最左的 d 。 a) 非终结符 b) 句子 c) 短语 d)直接短语5以下 c 函数是PL/0编译程序中的词法分析器。a) term b) expression c) getsym d) factor6PL/0编译程序的语法分析采用的是 b 。a) LR分析法 b) 递归子程序法 c) 算符优先分析法 d) 预测分析法7程序所需的数据空间在程序运行前就可确定，称为 d 方法。 a) 动态分配 b) 堆式分配 c)栈式分配 d)静态分配8下列语句中， c 语句不是基本块的入口语句。 a) 程序的首条 b) 被转向的目标 c) 停止 d) 条件转移的下一条9给定文法AbAa | a | b，下列符号串中语法正确的是 a 。a) bbaaa b) babba c) abaab d) aabab10 c 和代码优化部分不是每个编译程序都必需的。 a) 目标代码生成 b) 词法分析 c) 中间代码生成 d) 语法分析 第 2 页( 共 8 页 ) 第 3 页( 共 8 页 )三、设计题（本大题共2小题，每小题5分，共10分）1定义一个上下文无关文法GS，生成下述语言L： L= an dm bn | n,m1 答GA：AaAb | aBbBdB | d2证明下列文法GA是一个二义文法：AB+B | BBB*B | A | a答： 对于句子a+a*a 存在两个不同的最左推导：1: A=B+B=a+B=a+B*B=a+a*B=a+a*a2: A=B=B*B=A*B=B+B*B=a+B*B=a+a*B=a+a*a GA是一个二义文法 四、设计题（本大题共3小题，每小题5分，共15分） 设有正规式 r = (a |ab) (a|b)* b 1 构造一个NFA M，接受L(r)。 2. 把上述NFA M转化为等价的DFA M。 3给出DFA M所对应的正规文法。GS：SaA AaB | bCBaB | bC CaB | bC | 五、设计题（本大题共2小题，第1题7分，第2题5分，共12分） 对下列基本块B应用DAG进行优化，设只有S、W在基本块后面还要继续引用。 B: T1 := a+b T2 := 3.14 S := T1*T2 T3 := a+b T4 := 2.56 T5 := T2+T4 W := T5*T1 S := T5*T3 1基本块B的DAG 答：2优化后的基本块B 答： T1:=a+b T5:=5.70 W:=T5*T1 S:=W 第 4 页( 共 8 页 ) 第 5 页( 共 8 页 )六、分析题（本大题共2小题，第1题5分，第2题10分，共15分）1对下列属性文法中的语义处理功能作简略说明：Eid1 rop id2 E.true:=nextstat; E.false:=nextstat+1;E.Codebegin:=nextstat; emit(if id1.place rop id2.place goto); emit(goto-) 答：E.true：E的真出口链E. false：E的假出口链E.Codebegin: E的代码开始地址 Nextstat：下一条代码地址emit： 生成一条四元式2 在下划线处填写正确内容，完成下列源语句通过语法制导翻译后生成的四元式序列。源语句： while (s100) and(a b) or (a=b) dobegina:=a+1;if (ab) then s:= s+a; end; 四元式序列： 1) if s100 goto(3) 2) goto (14) 3) if ab goto (7) 4) goto (5) 5) if a=b goto(7) 6) goto (14) 7) t1:=a+1 8) a:=t1 9 ) if ab goto (11) 10) goto (1) 11) t2:=s+a12) s:=t2 13 ) goto (1) 14) 七、 证明题（本大题共3小题，每题4分，共12分） 设有文法GS： SB A AAB | Aa | a Bba | bB 1) 证明GS是一个非LL(1)文法。答： A含左递归（以及A、B含公共左因子） GS非LL(1)文法。 2) 把 GS等价改写为LL(1)文法G1S。答：G1S:SB A AaA ABA| a A | BbBBa | B 3) 证明G1S为LL(1)文法。答：对于S,A,B:仅有一个候选，选择唯一；对于A：Select(ABA) = bSelect(AaA) = aSelect(A ) = #a b = 且 a # = 且 b # = 选择唯一对于B：Select (Ba) = aSelect (BB) = bab = 选择唯一 G1S为LL(1)文法。第 6 页( 共 8 页 )八、综合题（本大题共3小题，第1题6分，第2，3题各5分共16分） 设有文法GS: (0) SE(1) EE+T(2) ET(3) Tn (4) Tr 1. 证明GS是SLR(1)文法,构造GS的SLR(1)分析表。答：LR(0)项目集规范族： 状态I1含有移进-归约冲突 GS是非LR(0)文法 follow(S)=# += GS是SLR(1)文法SLR(1)分析表：状态ACTION GOTO+ n r #E T01 2 3456 s3 s4s5 accr2 r2r3 r3r4 r4 s3 s4r1 r11 2 6 第 7 页( 共 8页 )第 8页( 共 8页 )2. 对输入串 n+r+n# 给出分析过程： 步骤状态 符号 输入串动作12.3.4.5.6.7.8.9.10.11.12.0 #03 #n02 #T01 #E015 #E+0154 #E+r0156 #E+T01 #E015 #E+0153 #E+n0156 #E+T01 #En+r+n#+r+n#+r+n#+r+n#r+n#+n#+n#+n#n# # #s3r3r2s5s4r4r1s5s3r3r1acc3将文法GS扩充为属性文法: (0) SE (1) EE+T print(“+”) (2) ET (3) Tn print(“n”) (4) Tr print(“r”) 写出对输入串 n+r+n# 进行语法制导翻译分析后，输出的符号串。答：输出的符号串: nr+n+ 收集于网络，如有侵权请联系管理员删除