五套编译原理期末考试试卷及答案.doc
《五套编译原理期末考试试卷及答案.doc》由会员分享,可在线阅读,更多相关《五套编译原理期末考试试卷及答案.doc(39页珍藏版)》请在三一文库上搜索。
1、得分一 填空题(每空 2 分,共 20 分)1. 不同的编译程序关于数据空间的存储分配策略可能不同,但大部分编译中采用的方案有两种:静态存储分配方案和动态存储分配方案,而后者又分为(1) 和 (2) 。2. 规范规约是最(3)规约。3. 编译程序的工作过程一般划分为 5 个阶段:词法分析、(4) 、语义分析与中间代码生成,代码优化及(5) 。另外还有(6)和出错处理。4表达式 x+y*z/(a+b)的后缀式为 (7) 。5文法符号的属性有综合属性和 (8)。6假设二位数组按行存放,而且每个元素占用一个存储单元,则数组 a1.15,1.20某个元素 ai,j的地址计算公式为(9)。7局部优化是局
2、限于一个(10)范围内的一种优化。得分二 选择题(1-6 为单选题,7-8 为多选题,每问 2 分,共 20 分)1. 一个上下文无关文法 G 包括四个组成部分:一组终结符,一组非终结符,一个( ),以及一组( )。A 字符串B 产生式C 开始符号D 文法2.程序的基本块是指( )。A 一个子程序B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段D 一组顺序执行的程序段,仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于( )分析方法。A 自左向右B 自顶向下C 自底向上D 自右向左4在通常的语法分析方法中,( )特别适用于表达式的分析。A 算符优先
3、分析法B LR 分析法C 递归下降分析法D LL(1)分析法5经过编译所得到的目标程序是( )。A 四元式序列B 间接三元式序列C 二元式序列D 机器语言程序或汇编语言程序6 一个文法所描述的语言是( );描述一个语言的文法是( )。A 唯一的B 不唯一的C 可能唯一,也可能不唯一7 如果在文法 G 中存在一个句子,当其满足下列条件( )之一时,则称该文法是二义文法。A 其最左推导和最右推导相同 B 该句子有两个不同的最左推导C 该句子有两个不同的最右推导 D 该句子有两棵不同的语法树E 该句子对应的语法树唯一8 下面( )语法制导翻译中,采用拉链回填技术。A. 赋值语句B. 布尔表达式的计算
4、C. 条件语句D. 循环语句三 解答题(共 60 分)得分1 (共 15 分)已知文法 GE:EETE|(E)|iT*|+(1) 将文法 G 改造成 LL(1)文法;(5 分)(2) 构造文法 G 中每个非终结符的 FIRST 集合及 FOLLOW 集合;(5 分)(3) 构造 LL(1)分析表。(5 分)2 (共 12 分)给定文法 GS:SS(S)|(1) 给出句子()()()()的规范推导过程;(4 分)(2) 指出每步推导所得句型的句柄;(4 分)(3) 画出该句子的语法推导树。(4 分)3 (共 8 分)在一个移入-规约分析过程中采用以下的语法制导翻译模式,在按一个产生式规约时,立即
5、执行括号中的动作。AaBprint “0”;Acprint “1”;BAbprint “2”;(1) 当分析器的输入为 aacbb 时,打印的字符串是什么?(3 分)(2) 写出分析过程。(5 分)4 (10 分)翻译循环语句 while (ad) then x:=y+z 。要求:给出加注释的分析树及四元式序列。参考以下部分翻译模式:(1) Sif E then M S1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1 .nextlist)(2) Swhile M1 E do M2 S1 backpatch(S1.n
6、extlist,M1,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,M1 .quad)(3)SAS.nextlist:=makelist()(4)LSL.nextlist:=S.nextlist(5)MM.quad:=nextquad(6)Eid1 relop id2E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place ,id2.place,0);emit(j,-,-,0
7、)(7) SL:=Eemit(:=,E.place,-,L.place)(8) EE1+E2E.place:=newtemp;emit(+,E1.place,E2.place,E.place,)5 (共 15 分)设有表格构造文法 GS:Sa|(T)TT,S|S(1) 计算文法 GS的 FIRSTVT 集和 LASTVT 集。(5 分)(2) 构造 GS的优先关系表,并判断 GS是否为算符优先文法。(5 分)(3) 计算 GS的优先函数。(5 分)得分二单项选择题(每题 2 分,共 10 分)1. 设有文法 GI: II1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有()。 ab0
8、 a0c01 aaa bc10可选项有:A BCD2.程序的基本块是指()。A 一个子程序B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段D 一组顺序执行的程序段,仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于()分析方法。A 自左向右B 自顶向下C 自底向上D 自右向左4经过编译所得到的目标程序是()。A 四元式序列B 间接三元式序列C 二元式序列D 机器语言程序或汇编语言程序5 运行阶段的存储组织与管理的目的是()。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度 为运行阶段的存储分配做准备可选项有:A. B. C.
9、 D. 2.(10 分) 已知文法 GS:得分SaBc|bABAaAb|bBb|(4) 构造其 LL(1)分析表;(5) 判断符号串 baabbb 是否为该文法的句子(写出含有符号栈、输入串和规则的分析过程)。3. (10 分) 已知文法 G 为:EE+T|TTT*P|PPi(1) 构造该文法的优先关系表(不考虑语句括号#),并指出此文法是否为算符优先文法。(2) 构造文法 G 的优先函数表。4 (8 分)在一个移入-规约分析过程中采用以下的语法制导翻译模式,在按一个产生式规约时,立即执行括号中的动作。SbAbprint “1”A(Bprint “2”Aaprint “3”BAa)print
10、“4”(3) 当输入序列为 b(aa)a)a)b 时,打印的字符串是什么?(4) 写出移入-规约分析过程。5 (12 分)翻译循环语句 while (xy) do if (a=b) then x:=2*y+a 。要求:给出加注释的分析树、三地址码序列及相应的四元式序列。参考以下部分翻译模式:(1) Sif E then M S1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1 .nextlist)(2) Swhile M1 E do M2 S1 backpatch(S1.nextlist,M1,.quad);back
11、patch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,M1 .quad)(3)SAS.nextlist:=makelist()(4)LSL.nextlist:=S.nextlist(5)MM.quad:=nextquad(6)Eid1 relop id2E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place ,id2.place,0);emit(j,-,-,0)(7) SL:=Eemit(:=,E.pl
12、ace,-,L.place)(8) EE1+E2E.place:=newtemp;emit(+,E1.place,E2.place,E.place,)6. (8 分) Generate assembly code for the following sequence assuming that x,y and z are in memory locations(noticing only two registers R1 and R2).S=0I=0L1: if xy goto L2Z=s+aiI=i+1 Goto L1L2:7 (6 分) Give out the all basic blo
13、cks of the following program fragment and construct the relevant flow graph(DAG).read C A=0 B=1L4: A=A+Bif BC goto L2 B=B+1goto L4 L2: write A8. (8 分)Translate the assignment statement bi=b*c-b*d into(1) A syntax tree.(2) Three address instructions.答案:(1) 栈式动态存储分配(2) 堆式动态存储分配(3) 左(4) 语法分析(5) 目标代码生成(
14、6) 表格管理(7) xyz*ab+/+(8) 继承属性(9) a+(i-1)*20+j-1(10) 基本块一、选择题(每问 2 分,共 20 分)1.C B2.D3.B4.A5.D6.A,C7.BCD,选对一个得 1 分且不超过满分,选错一个扣一分,扣完为止。8.BCD,选对一个得 1 分且不超过满分,选错一个扣一分,扣完为止。二、解答题1(1)文法存在左递归,消除左递归后的文法为:E(E)E|i E(2 分)ETEE| (2 分)T*|+(1 分)(2)(5 分)没考虑#扣 0.5 分,其它错或少写一个扣 0.5 分FIRST(E)=(,iFIRST(E)=*,+, FIRST(T)=*,
15、+FOLLOW(E)=),*,+,#FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i(3)每错一个扣 0.5 分,全错或不写不得分,扣完为止,共 5 分()i*+#EE(E)EEiEEE ETEEETEEE E E TT*T+2(1)规范推导过程如下。写错推导符号扣 0.5 分,错写或少写一步推导扣 0.5 分,扣完为止,最左推导扣 2 分,共 4 分。S S(S) S(e ) S(S)() S(e )() S(S)()() S(S(S)()() S(S(e )()() S(S(S)()()() S(S(e )()()() S(e )()()() e ()()()()(2)(
16、1)中加下划线的部分是句柄,标识如(1)。每少写一个句柄扣 0.5 分,扣完为止,共 4 分。(3)每少写步扣 0.5 分,扣完为止,共 4 分。SS( S )S( S )S( S ) S( S )S( S ) 3(1)打印的字符串是:12020(错一个扣 0.5 分,共 3 分)(2)归约过程中错一步扣 0.5 分,扣完为止。(共 5 分)4(1)每少写一步扣 0.5 分,扣完为止,共 5 分。Swhile M1.q=100E1.t=102do M2.q=102S1E1.f=107adxE5.p=y+ E6.p=z(2)少写一个四元式扣 0.5 分,全错或不写不yz四元式序列为:100( j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 期末考试 试卷 答案
链接地址:https://www.31doc.com/p-11251895.html