2022年期末考试编译原理试卷及答案 .pdf

《2022年期末考试编译原理试卷及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年期末考试编译原理试卷及答案 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 该句子有两棵不同的语法树得分得分精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -

4、- -第 1 页，共 12 页E 该句子对应的语法树唯一8 下面（）语法制导翻译中，采用拉链回填技术。A. 赋值语句 B. 布尔表达式的计算 C. 条件语句 D. 循环语句三解答题 （共 60 分）1 （共 15 分）已知文法GE: E ETE|（E）|i T*|+ （1）将文法 G改造成 LL（1）文法；（5 分）（2）构造文法G中每个非终结符的FIRST 集合及 FOLLOW 集合； （ 5 分）（3）构造 LL（ 1）分析表。（5 分）2 （共 12 分）给定文法GS：SS(S)| （1） 给出句子 ()()()()的规范推导过程； （4 分）（2） 指出每步推导所得句型的句柄；（4 分

5、）（3） 画出该句子的语法推导树。（4 分）3 （共 8 分）在一个移入- 规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。 AaB print “0”； Ac print “1”； BAb print “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.ne

6、xtlist:=merge(E.falselist,S1 .nextlist) (2) Swhile M1 E do M2 S1 backpatch(S1.nextlist,M1,.quad); backpatch(E.truelist,M2,.quad); S.nextlist:=E.falselist emit ( j,-,-, M1 .quad) (3) SA S.nextlist:=makelist() (4) LS L.nextlist:=S.nextlist 得分精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页(5)

7、 MM.quad:=nextquad (6) Eid1 relop id2 E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); emit( j relop.op, id1.place , id2.place , 0); emit(j,-,-,0) (7) SL:=E emit(:=,E.place,-,L.place) (8) EE1+E2 E.place:=newtemp; emit(+,E1.place,E2.place,E.place,) 5 （共 15 分）设有表格构造文法GS：Sa| |(T) T T,

8、S|S (1)计算文法GS的 FIRSTVT集和 LASTVT集。 （5 分）(2)构造 GS 的优先关系表，并判断GS 是否为算符优先文法。 （5 分）(3)计算 GS 的优先函数。 （5 分）二单项选择题 （每题 2 分，共 10 分）1. 设有文法GI ： I I1|I0|Ia|Ic|a|b|c 下列符号串中是该文法句子的有（） 。 ab0 a0c01 aaa bc10 可选项有：A B C D2. 程序的基本块是指（） 。A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法

9、中，递归下降分析法属于（）分析方法。A 自左向右 B 自顶向下 C 自底向上 D 自右向左4经过编译所得到的目标程序是（） 。得分精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序5运行阶段的存储组织与管理的目的是（） 。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度 为运行阶段的存储分配做准备可选项有：A. B. C. D. 2. （10 分） 已知文法GS: SaBc|bAB AaAb|b Bb| （4）构造其 LL（1）

10、分析表；（5）判断符号串baabbb 是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。3. (10分) 已知文法G为：EE+T|T TT*P|P Pi （1） 构造该文法的优先关系表（不考虑语句括号#） ，并指出此文法是否为算符优先文法。（2） 构造文法G的优先函数表。4 （8 分）在一个移入- 规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。 SbAb print “1” A(B print “2” Aa print “3” BAa) print “4” （3）当输入序列为b(aa)a)a)b时，打印的字符串是什么？（4）写出移入 - 规约

11、分析过程。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); 得分精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4

12、 页，共 12 页 backpatch(E.truelist,M2,.quad); S.nextlist:=E.falselist emit ( j,-,-, M1 .quad) (3) SA S.nextlist:=makelist() (4) LS L.nextlist:=S.nextlist (5) MM.quad:=nextquad (6) Eid1 relop id2 E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); emit( j relop.op, id1.place , id2.place ,

13、0); emit(j,-,-,0) (7) SL:=E emit(:=,E.place,-,L.place) (8) EE1+E2 E.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=0 I=0 L1: if xy goto L2 Z=s+ai I=

14、i+1 Goto L1 L2: 7 (6分) Give out the all basic blocks of the following program fragment and construct the relevant flow graph(DAG). read C A=0 B=1 L4: A=A+B if BC goto L2 B=B+1 goto L4 L2: write A 8.(8 分)Translate the assignment statement bi=b*c-b*d into 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第

15、 5 页，共 12 页(1)A syntax tree. (2)Three address instructions. 答案：(1) 栈式动态存储分配(2) 堆式动态存储分配(3) 左(4) 语法分析(5) 目标代码生成(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）文法存在左递归，消除左递归后

16、的文法为：E(E)E |i E （2 分）E TEE | （2 分）T*|+ （1 分）（2）(5 分)没考虑 #扣 0.5 分，其它错或少写一个扣0.5 分FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWLLOW(E )= ),*,+,# FOLLOW(T)=(,i （3）每错一个扣0.5 分，全错或不写不得分，扣完为止，共5 分( ) i * + # E E(E)E EiEEEE TEE E E TEE E E T T* T+ 2 （1）规范推导过程如下。写错推导符号扣0.5 分, 错写或少写一步推导扣0.5 分，扣

17、完为止，最左推导扣2分，共 4 分。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页()()()()()()()()()()()()()()()()()()()()()()()()()()()(SSSSSSSSSSSSSSSSSSSS（2） （1）中加下划线的部分是句柄，标识如（1） 。每少写一个句柄扣0.5 分，扣完为止，共4 分。（3）每少写步扣0.5 分，扣完为止，共4 分。3 （1）打印的字符串是：12020（错一个扣0.5 分， 共 3 分）（2）归约过程中错一步扣0.5 分，扣完为止。 （共 5 分）4 （1）每少写

18、一步扣0.5 分，扣完为止，共5 分。（2）少写一个四元式扣0.5 分，全错或不写不得分，回填错误扣0.5 分，共 5 分。while M1.q=100 E1.t=102 do M2.q=102 S1 E1.f=107 (E3.t=102) L.p=x := E4.p=T1 (E3.f=103)cd x E5.p=y + E6.p=z y z S a0S1=00S11=000111 ，共 3 分， = 写成 - 扣 1 分（3） 共 3 分，错处扣0.5 分，扣完为止2. （1）空白表格也可以填写“错误”字样, 共 4 分，错一个扣0.5 分，扣完为止a b c $(#) S SaBc SbA

19、B A AaAb Ab B Bb BB （2）共 6 分，其中判断“baabbb 是该文法句子”为2 分，其他错一个扣0.5 分，扣完为止符号栈输入串规则$S $BAb $BA $BbAa $BbA $BbbAa $BbbA $Bbbb $Bbb $Bb $b $ baabbb$ baabbb$ aabbb$ aabbb$ abbb$ abbb$ bbb$ bbb$ bb$ b$ $ $ SbAB AaAb AaAb Ab Bsuccess 3.(1)共 6 分，其中判断“该文法为算符优先文法”为2 分，其他错一个扣0.5 分，扣完为止+ * i + (2) 共 4 分，错一个扣0.5 分，扣

20、完为止+ * i f 2 4 4 g 1 3 5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页4 （1）34242421 ，共 4 分，错一个扣0.5 分（2）共 4分 ，错一个扣0.5 分，扣完为止stack Input string action $ $b $b( $b( $b( $b(a $b(A $b(Aa $ b(Aa) $ b(B $b(A $b(Aa $b(Aa) $b（ （B $b(A $b(Aa $b(Aa) $b(B $bA $bAb $S $s$ b(aa)a)a)b$ (aa)a)a)b$ (aa)a

21、)a)b$abbb$ (aa)a)a)b$bbb$ aa)a)a)b$bb$ a)a)a)b$ a)a)a)b$ )a)a)b$ a)a)b$ a)a)b$ a)a)b$ )a)b$ a)b$ a)b$ a)b$ )b$ b$ b$ b$ $ $ shift shift shift shift shift reduce, A a shift shift reduce, B Aa）reduce, A (B shift shift reduce, B Aa）reduce, A (B shift shift reduce, B Aa）reduce, A (B shift reduce, S bAb

22、accept 5 共 12 分，其中带注释的分析树、三地址码序列和四元式序列分别为4 分，错一个序列扣0.5 分，而错某点（某项）少于或等于5 个扣 0.5 分带注释语法树( 略) 三地址码序列四元式序列M1: if (xy) goto M2 100 (j, x,y,102) goto M4 101 (j,-,-,108) M2: if (a=b) goto M3 102 (j=,a,b,104) goto M1 103 (j,-,-,100) M3: t1=2*y 104 (*,2,y,t1) t2=t1+a 105 (+,t1,a,t2) x=t2 106 (=,t2,-,x) goto

23、M1 107 (j,-,-,100) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页M4: 108 (-,-,-,-) 6共 8 分，错一个扣0.5 分，扣完为止LD R1,0 ST S,R1 ST I,R1 L1: LD R1,X SUB R1,R1,Y (OR SUB R1,Y) BGTZ R1,L2 LD R2,a(R1) ADD R2,R2,S (OR ADD R2,S) ST Z,R2 LD R1,I (从这开始，下面的语句中的R1也可以全部变成R2) ADD R1,R1,1 (OR INC R1) ST I,R1

24、 BR L1 L2: 7 共 6 分，基本块划分和流图各为3 分，错一处扣 1 分，扣完为止8. （1）共 4 分，错一项扣1 分，扣完为止（2）共 4 分，错一项扣1 分，扣完为止t1=b*c t2=b*d t3=t1-t2 t4=i+1 (or t4=i) bt4=t3 B4 B3 B2 B1 read c A=0 B=1 L4: A=A+B If BC goto L2 (OR B4) B=B+1 Goto L4 (OR B2) L2: write A 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页