北方工业大学16编译原理期末复习题答案.doc_第1页
北方工业大学16编译原理期末复习题答案.doc_第2页
北方工业大学16编译原理期末复习题答案.doc_第3页
北方工业大学16编译原理期末复习题答案.doc_第4页
北方工业大学16编译原理期末复习题答案.doc_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

序号北方工业大学编译原理课程期末复习题(答案)A卷2016年春季学期订线装开课学院考试方式:闭卷考试时间:120 分钟班级 姓名 学号 题 号一二三四五六七八九十总 分得 分阅卷人一判断题(每个小题1分,共10分)1. 程序语言主要由语法和语义两方面定义。 ( )2. 自上而下分析方法会遇到的主要问题有左递归和回溯。 ( )3. 已知文法G:Ei | EAE,A+|* ,其中的终结符号集包括i,+。( )4. 编译程序是将高级语言程序翻译成机器语言程序。 ( )5. 只含有综合属性的属性文法称为S-属性文法。 ( )6. LL(1)文法中第一个L的含义是从左到右扫描输入串。 ( )7. 在编译中进行语法检查的目的是为了发现程序中所有错误。 ( ) 8. 一个语义子程序描述了一个文法所对应的翻译工作。 ( ) 9. 一个句型的直接短语是唯一的。 ( ) 10. 确定的自动机以及不确定的自动机都能正确地识别正规集。 ( ) 解:1. 2. 3. 4. 5. 6. 7. 8. 9. 10.二、选择题(每个小题1分,共20分)1. 文法分为四种类型,即0型、1型、2型、3型。其中3型文法是_。 A. 短语文法 B. 正规文法 C. 上下文有关文法 D. 上下文无关文法2. 不可能是目标代码。 A. 汇编指令代码 B. 可重定位指令代码 C. 绝对指令代码 D. 中间代码3. 将编译程序分成若干个“遍”是为了 。 A. 提高程序的执行效率 B. 利用有限的机器内存并提高机器的执行效率 C. 使程序的结构更加清晰 D. 利用有限机器内存但降低了机器的执行效率 4. 后缀式ab+cd+/可用表达式 来表示。 A. a+b/c+d B. (a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 5. 文法G:SxSx|y所识别的语言是 。A. xyxB. (xyx)*C. xnyxn(n0) D. x*yx*6. 文法GE: EE+T|T TT*P|P P(E)|i则句型P+T+i的句柄和最左素短语为 。A. P+T和iB. P和P+T C. i和P+T+i D. P和T7. 设有文法GE: EE*T|T TT+i|i句子1+2*8+6按该文法G归约,其值为 。 A. 42 B. 23 C. 30 D. 178. 规范归约指 。 A. 最右推导的逆过程 B. 最左推导的逆过程 C. 规范推导 D. 最左归约的逆过程9. 词法分析所依据的是 。 A. 语义规则B. 构词规则C. 语法规则D. 等价变换规则10. 状态转换图(见下图)接受的集合为 。 0 1 0YX A. 以 0开头的二进制数组成的集合 B. 以0结尾的二进制数组成的集合 C. 含奇数个0的二进制数组成的集合 D. 含偶数个0的二进制数组成的集合11. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此, 。 A. 词法分析器作为子程序较好 B. 词法分析器并不作为一个独立的阶段 C. 词法分析器分解为多个过程,由语法分析器选择使用 D. 词法分析器应作为独立的一遍12. 若a为终结符,则Aa为 项目。 A. 移进B. 归约C. 接受D. 待约13. 中间代码生成所依据的是 。 A. 语法规则B. 词法规则C. 语义规则D. 等价变换规则14. 终结符具有 属性。 A. 传递B. 继承C. 抽象D. 综合15. 下推自动机识别的语言是 。 A. 0型语言 B. 1型语言 C. 2型语言 D. 3型语言16. 常用的中间代码形式不含 。 A. 三元式 B. 四元式 C. 逆波兰表达式 D. 语法树17. 算符文法是指 的文法。 A. 没有形如U.VW.的产生式(U、V、WVN) B. VT中任意两个符号之间至多存在一种算符优先关系 C. 没有相同右部的产生式 D. 没有形如U的产生式 18. 下述语句类中,_在编译阶段通常不产生可执行代码。 A. 变量说明语句 B. 流程控制语句 C. 输入输出语句 D. 赋值语句 19. 文法所描述的语言是 的集合。 A. 文法的字母表中符号组成的符号串 B. 文法的字母表中终结符号组成的符号串 C. 由文法开始符号推导的符号串 D. 由文法开始符号推导的终结符号串 20. 符号串ab1b2是文法GA:AaB, BbB|b的句子,该句子的句柄是_。 A. b1 B. b2 C. a D. b1b2 解:1. B 2.D 3. C 4. B 5. C 6. B 7. A 8. A 9. B 10. D 11. A 12. A 13. C 14. D 15. C 16. D 17. A 18. A 19. D 20. B 三、已知文法G的产生式为:ET|E+T|E-TTF|T*F (2-1)F (E)|i试求:(1)消除该文法的左递归;(5分)(2)利用(1)得到的文法G(2-1),求(i+i*i)的最左推导和语法分析树。(5分)解:(1)ETEE+TE|-TE |TFT|T*FT| (2-1)F(E)|i(2)ETEFTE(E)TE(E)(TE)(FTE)(iTE)(iE)(i+TE)(i+FTE)(i+iTE)(i+i*FTE)(i+i*iTE)(i+i*i) (i+i*i)EE(根)Ti()Fi+TTEi*四、已知文法G的产生式:ETEE+TE|-TE |TFT|T*FT| (2-1)F(E)|i试求:(1)每个非终结符的FIRST集合;(5分)(2)每个非终结符的FOLLOW集合。(5分)答:FIRST(E)=(,iFOLLOW(E)=),#FIRST(E)=-,+, FOLLOW(E)=),#FIRST(T)=(, iFOLLOW(T)=-,+, ), #FIRST(T)=*, FOLLOW(T)=-,+,),#FIRST(F)=(, iFOLLOW(F)=*,-,+, ), #五、已知文法G3:Sa|(T);TT,S|S其中:S、T是非终结符,a、 、, 、 ( 和 )是终结符,S为开始符合,试求:(1)计算非终结符的FISTVT和LASTVT;(2)给出终结符的算符优先关系表;(3)给出(a,(a,a)的算符优先分析过程,指出每次规约的素短语。(共30分,每小题10分)解:(1)FIRSTVT和LASTVT如下:FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2) 构造优先关系表如下:a(),#a(=,#= (3) 输入串(a,(a,a)的算符优先分析过程如下:栈输入字符串动作#(a,(a,a)#预备#(a,(a,a)#进#(a,(a,a)#进#(s,(a,a)#归#(t,(a,a)#归#(t,(a,a)#进#(t,(a,a)#进#(t,(a,a)#进#(t,(s,a)#归#(t,(t,a)#归#(t,(t,a)#进#(t,(t,a)#进#(t,(t,s)#归#(t,(t)#归#(t,(t)#进#(t,s)#归#(t)#归#(t)#进#s#归六、已知文法G 的产生式为:ET|E+T|E-TTF|T*F (2-1)F (E)|i试给出表达式i1*i2+i3的规范式规约过程。用下面的格式描述该过程。(10分)步骤 符号栈 输入串 所用产生式答:输入串i1*i2+i3的分析步骤:步骤 符号栈 输入串 所用产生式0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归,用Fi3#T*i2+i3#归,用TF4#T*i2+i3#进5#T*i2+i3#进6#T*F+i3#归,用Fi7#T+i3#归,用FE*F8#E+i3#归,用FT9#E+i3#进10#E+i3#进11 #E+F# 归,用Ei 12 #E+T# 归,用TF13#E#归,用EE+T14#E#接受七、属性文法如表5-1所示,试求表达式a+4+c的抽象语法树,并描述建立抽象语法树过程。(10分)表6-1 属性文法产生式语义规则EE1+T E.nptr := mknode( + , E1.nptr , T.nptr )EE1-T E.nptr := mknode( - , E1.nptr , T.nptr )ETE.nptr := T.nptrT(E)T.nptr := E.nptrTid T.nptr := mklear( id , id.entry )Tnum T.nptr := mklear( num , num.val )答:(1)p1 := mkleaf( id , entrya );(2)p2 := mkleaf( num , 4 );(3)p3 := mknode( + , p1 , p2 );(4)p4 := mkleaf( id , entryc );(5)p5 := mknode( + , p3 , p4 );八、已知翻译模式如下:产生式语义规则EE1 or E2EE1 and E2Eid1 relop id2E.place := newtemp; emit( E.place := E1.place or E2.place ) E.place := newtemp; emit( E.place := E1.place and E2.place ) E.place := newtemp; emit( if id1.place relop.op id2.place goto nextstat+3); emit( E.place := 0); emit(goto nextstat + 2); emit( E.place := 1) 试给出布尔表达式ab and cd or ef的三地址代码(10分)。107:t2 := 1108:if e f goto 111109:t3 := 0110:goto 112111:t3 := 1112:t4 := t1 and t2113:t5 := t3 or t4100:if a b goto 103101:t1 := 0102:goto 104103:t1 := 1104:if c d goto 107105:t2 := 0106:goto 108答:九、已知翻译规则产生式语义规则S if E then S1S if E then S1 else S2E.true := newlabel;E.false := S.next;S1.next := S.next;S.code := E.code | gen( E.true: ) | S1.codeE.true := newlabel;E.false := newlabel;S1.next := S.next;S2.next := S.next;S.code := E.code | gen( E.true : ) | S1.code | gen( goto S.next ) | gen( E.false : ) | S2.codeSwhile E do S1S.begin := newlabel;E.true := newlabel; E.false := S.next;S1.next := S.begin;S.code := gen( S.bgein : ) | E.code | gen( E.true : ) | S1.code | gen( goto S.begin )试把下面的语句翻译成三地址代码While AC and BD DoIf A=1 then C:=C+1 elseWhile A=D Do A:=A+2108:goto S.next 113109:if A=D goto 111110:goto S.next 113 111:T2=A+2112:A:=T2113:goto 109 114:goto 100100:if AC goto 102101:goto L.false 115102:if BD goto 104103:goto L.false 115104:goto 106105:goto L.false 109106:T1=C+1107:C:=T1答:十、已知翻译规则(见第九题),试把下面的原程序翻译成三地址代码。while a b doif c d thenx := y + zelsex := y - z答: L1:if a b goto L2goto LnextL2:if c d goto L3goto L4L3:t1 := y + zx := t1goto L1(goto L5) L4:t2 := y - zx := t2L5goto L1 Lnext: goto L1十一、对以下四元式程序,试求:(1)它的流图(5分),(2)对其中的循环进行循环优化(10分)。I:=1Read J,KL: A:=K*IB:=J*IC:=A*BWrite CI:=I+1If I100 goto L2A:=K*IB:=J*IC:=A*BWrite CI:=I+1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论