《2022年期末考试编译原理试卷及答案.docx》由会员分享，可在线阅读，更多相关《2022年期末考试编译原理试卷及答案.docx（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 得分 一填空题 （每空 2 分,共 20 分 ）1. 不同的编译程序关于数据空间的储备安排策略可能不同,但大部分编译中采纳的方案有两种：静态储备安排方案和动态储备安排方案,而后者又分为（1） 和 （2） ；2. 规范规约是最（3）规约；3. 编译程序的工作过程一般划分为 5 个阶段： 词法分析、（ 4） 、语义分析与中间代码生成,代码优化及 （5） ；另外仍有（ 6）和出错处理；4表达式 x+y*z/a+b的后缀式为（7） ；a1.15,1.20某个元素ai ,j 的地址5文法符号的属性有综合属性和（ 8）；6假设二位数组按行存放,而且每个元素
2、占用一个储备单元,就数组运算公式为（ 9）；7局部优化是局限于一个（10）范畴内的一种优化；得分二挑选题 （1-6 为单项题, 7-8 为多项题,每问2 分,共 20 分）；第 1 页,共 12 页1. 一个上下文无关文法G包括四个组成部分：一组终结符,一组非终结符,一个（）,以及一组（A 字符串 B 产生式 C 开头符号 D文法2. 程序的基本块是指（）；A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组次序执行的程序段,仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于（）分析方法；A 自左向右 B 自顶向下 C 自底向
3、上 D 自右向左4在通常的语法分析方法中,（ ）特殊适用于表达式的分析；A 算符优先分析法 B LR 分析法C 递归下降分析法 D LL （1）分析法5经过编译所得到的目标程序是（）；A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序6 一个文法所描述的语言是（）；描述一个语言的文法是（）；A 唯独的 B 不唯独的 C 可能唯独,也可能不唯独7 假如在文法G中存在一个句子,当其满意以下条件（）之一时,就称该文法是二义文法；A 其最左推导和最右推导相同 B 该句子有两个不同的最左推导C 该句子有两个不同的最右推导 D 该句子有两棵不同的语法树名师归纳总结 - - -
4、 - - - -精选学习资料 - - - - - - - - - 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 ：SSS| （1） 给出句子 的规范推导过程； （4 分）（2） 指出每步推
5、导所得句型的句柄；（4 分）（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 backpatchE.truel
6、ist,M.quad; 1 .nextlist S.nextlist:=mergeE.falselist,S2 Swhile M1 E do M2 S 1 backpatchS1.nextlist,M1,.quad; backpatchE.truelist,M2, .quad; S.nextlist:=E.falselist 名师归纳总结 3 Semit j,-,-,M1 .quad 第 2 页,共 12 页A S.nextlist:=makelist 4 LS L.nextlist:=S.nextlist - - - - - - -精选学习资料 - - - - - - - - - 5 MM.
7、quad:=nextquad 6 Eid 1 relop id2 E.truelist:=makelistnextquad; e.falselist:=makelistnextquad+1; emitj relop.op, id 1.place , id 2.place , 0; emitj,-,-,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,S|S 1 运算文法 GS 的 FIRST
8、VT集和 LASTVT集；（5 分）2 构造 GS 的优先关系表,并判定 GS 是否为算符优先文法； （5 分）3 运算 GS 的优先函数； （5 分）得分二单项挑选题 （每题 2 分,共 10 分）1. 设有文法 GI ： I I1|I0|Ia|Ic|a|b|c 以下符号串中是该文法句子的有（）； aaa bc10 ab0 a0c01 可选项有：A B C D第 3 页,共 12 页2. 程序的基本块是指（）；A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组次序执行的程序段,仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中,递归下降分析法
9、属于（）分析方法；A 自左向右 B 自顶向下 C 自底向上 D 自右向左4经过编译所得到的目标程序是（）；名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序5运行阶段的储备组织与治理的目的是（）； 提高编译程序的运行速度 节约编译程序的储备空间 提高目标程序的运行速度 为运行阶段的储备安排做预备可选项有：A. B. C. GS: D. 得分2. （10 分） 已知文法SaBc|bAB AaAb|b Bb| （4） 构造其 LL（1）分析表；（5） 判定符号串 baabbb 是
10、否为该文法的句子（写出含有符号栈、输入串和规章的分析过程）；3. 10 分 已知文法 G为：EE+T|T TT*P|P Pi （1） 构造该文法的优先关系表（不考虑语句括号（2） 构造文法 G的优先函数表；#）,并指出此文法是否为算符优先文法；4 （ 8 分）在一个移入- 规约分析过程中采纳以下的语法制导翻译模式,在按一个产生式规约时,立刻执行括号中的动作； SbAb print “ 1” AB print “ 2” Aa print “ 3” BAa print “ 4” （3） 当输入序列为 baaaab 时,打印的字符串是什么？（4）写出移入 - 规约分析过程；5 （ 12 分）翻译循环
11、语句 while xy do if a=b then x:=2*y+a ；要求：给出加注释的分析树、三地址码序列及相应的四元式序列；参考以下部分翻译模式：名师归纳总结 1 Sif E then M S1 backpatchE.truelist,M.quad; 1 .nextlist 第 4 页,共 12 页S.nextlist:=mergeE.falselist,S2 Swhile M1 E do M2 S 1 backpatchS1.nextlist,M1,.quad; - - - - - - -精选学习资料 - - - - - - - - - backpatchE.truelist,M 2
12、, .quad; S.nextlist:=E.falselist emit j,-,-,M1 .quad 3 SA S.nextlist:=makelist 4 LS L.nextlist:=S.nextlist 5 M M.quad:=nextquad 6 Eid1 relop id 2 E.truelist:=makelistnextquad; e.falselist:=makelistnextquad+1; emitj relop.op, id1.place , id2.place , 0; emitj,-,-,0 7 SL:=E emit:=,E.place,-,L.place 8 E
13、E1+E2 E.place:=newtemp; emit+,E 1.place,E 2.place,E.place, 6. 8 分 Generate assembly code for the following sequence assuming that x,y and z are in memory locationsnoticing only two registers R1 and R2. S=0 I=0 L1: if xy goto L2 Z=s+ai I=i+1 Goto L1 L2: 7 6分 Give out the all basic blocks of the follo
14、wing program fragment and construct the relevant flow graphDAG. 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 第 5 页,共 12 页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 1 A syntax tree. 2 Three address instructions. 答案：1 栈式动态储备
15、安排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）文法存在左递归,排除左递归后的文法为：EEE |i E （ 2 分）E TEE| （2 分）T*|+ （1 分）（2）5 分没考虑 #扣 0.5 分,其它错或少写一个扣 0.5 分FIRSTE=,i FIRSTE=*,
16、+, FIRSTT=*,+ FOLLOWE=,*,+,# FOWLLOWE = ,*,+,# FOLLOWT=,i （3）每错一个扣0.5 分,全错或不写不得分,扣完为止,共5 分# 2 i * + E EEE EiE EEE E TEEE TEEEE0.5 分,扣完为止,最左推导扣T T* T+ 2（1）规范推导过程如下；写错推导符号扣0.5 分, 错写或少写一步推导扣分,共 4 分；名师归纳总结 - - - - - - -第 6 页,共 12 页精选学习资料 - - - - - - - - - SS S S S S S S S S S S S S S S S （2）（1）S S S 0.5
17、 分,扣完为止,共4 分；中加下划线的部分是句柄,标识如（1）；每少写一个句柄扣（3）每少写步扣0.5 分,扣完为止,共4 分；S S S S S S S S S S S 3（1）打印的字符串是：12022（错一个扣 0.5 分, 共 3 分）（2）归约过程中错一步扣 0.5 分,扣完为止； （共 5 分）4（1）每少写一步扣 0.5 分,扣完为止,共 5 分；S while M1.q=100 E1.t=102 do M2.q=102 S1 E1.f=107 ad x E5.p=y + E6.p=z 0.5 分,全错或不写不得分,回填错误扣0.5 分,共 5 分；y z 名师归纳总结 - -
18、- - - - -第 7 页,共 12 页精选学习资料 - - - - - - - - - 四元式序列为：100j,a,b,1021 分,全错或不写不得分,共5 分；101 j,_,_, 107102j,c ,d, 104103j,_,_, 106104,y,z,T1 105:,T,1_,x106j,_,_, 1005（1）少写一个扣FIRSTVTS=a, , FIRSTVTT=, a, LASTVTS= a, , LASTVTT= a, , .、.、三种关系中的一种,2 优先表如下；每错一个扣0.5 分,全错或不写不得分,扣完为止,共3 分文法 GS 没有两个非终结符相邻的情形,且其优先表中
19、任一对终结符之间最多满意因此是 GS 算符优先文法； （2 分）可以不考虑终结符“#” ； , # a A . . ., .# .或者（3）优先函数；可以不考虑终结符“#” ；每错一个扣0.5 分,全错或不写不得分,扣完为止,共5 分；a , # f 6 6 2 6 6 2 g 7 7 7 2 5 2 或者a , f 4 4 2 4 4 g 5 5 5 2 3 三、填空题（每空 2 分,共 20 分）1 目标程序 （target code）语法分析（syntax analyzer ）代码优化器（code optimizer ）代码产生器（ code generator ）符号表治理（ symb
20、ol table manager）2 继承属性（ inherited attribute）名师归纳总结 第 8 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - 3 局部优化（ local optimization）4 四元式（ quatriple）5 E + * id 四、单项挑选题（每题 2 分,共 10 分）1.B 2.D 3.B 4.D 5.C五、解答题（共 70 分）1（1） LG=0 m1 m|M1 共 2 分,写成扣 1 分（2） S=0S1=00S11=000111,共 3 分, = 写成 - 扣 1 分（3） 共 3 分,错处扣0.5
21、 分,扣完为止第 9 页,共 12 页2. （1）空白表格也可以填写“ 错误” 字样, 共 4 分,错一个扣0.5 分,扣完为止a b c $# S SaBc SbAB A AaAb Ab B Bb BB （2）共 6 分,其中判定“baabbb 是该文法句子” 为2 分,其他错一个扣0.5 分,扣完为止符号栈输入串规章$S baabbb$ $BAb baabbb$ SbAB $BA aabbb$ $BbAa aabbb$ AaAb $BbA abbb$ $BbbAa abbb$ AaAb $BbbA bbb$ $Bbbb bbb$ Ab $Bbb bb$ $Bb b$ $b $ B$ $ s
22、uccess 3.1共 6 分,其中判定“ 该文法为算符优先文法” 为2 分,其他错一个扣0.5 分,扣完为止+ * i + 2 共 4 分,错一个扣0.5 分,扣完为止+ * i f 2 4 4 g 1 3 5 名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 4（1）34242421 ,共 4 分,错一个扣0.5 分action 0.5 分,而错某点（2）共 4 分 ,错一个扣0.5 分,扣完为止stack Input string $ baaaab$ shift $b aaaab$ $b aaaab$abbb$ shift $b aaaab$bbb
23、$ shift $b aaaab$bb$ shift $ba aaab$ shift $bA aaab$ reduce, A a $bAa aab$ shift $ bAa aab$ shift $ bB aab$ reduce, B Aa）$bA aab$ reduce, A B $bAa ab$ shift $bAa ab$ shift $b（B ab$ reduce, B Aa）$bA ab$ reduce, A B $bAa b$ shift $bAa b$ shift $bB b$ reduce, B Aa）$bA b$ reduce, A B $bAb $ shift $S $ r
24、educe, S bAb $s$ accept 5 共 12 分,其中带注释的分析树、三地址码序列和四元式序列分别为4 分,错一个序列扣（某项）少于或等于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 M1 107 j,-,
25、-,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,aR1 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 BR L1 L2: 7 共 6 分,基本块划分和流图各为3 分,错一处扣 1 分,扣完为止read c B1 A=0 B=1 L4: A=A+B B2 If BC goto L2 OR B4 B=B+1 B3 Goto L4 OR B2 B4 L2: write A 8. （1）共 4 分,错一项扣 1 分,扣完为止（2）共 4 分,错一项扣 1 分,扣完为止 t1=b*c t2=b*d t3=t1-t2 t4=i+1 or t4=i bt4=t3 名师归纳总结 - - - - - - -第 11 页,共 12 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 12 页