《河南科技大学期末考试编译原理试卷及答案》由会员分享，可在线阅读，更多相关《河南科技大学期末考试编译原理试卷及答案（12页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 12 页河南科技大学电信科卷河南科技大学电信科卷 A A一一填空题填空题（每空 2 分，共 20 分）1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。2. 规范规约是最（3）规约。3. 编译程序的工作过程一般划分为 5 个阶段：词法分析、 （4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。4表达式 x+y*z/(a+b)的后缀式为 （7） 。5文法符号的属性有综合属性和 （8） 。6假设二位数组按行存放，而且每个元素占用一个存储单元，则数组
2、 a1.15,1.20某个元素 ai，j的地址 计算公式为（9） 。7局部优化是局限于一个（10）范围内的一种优化。二二选择题选择题（1-6 为单选题，7-8 为多选题，每问 2 分，共 20 分）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 一个文法所描述的语言是（ ） ；描述一个语言的文法是（ ） 。得 分得分第 2 页 共 12 页A 唯一的B 不唯一的C 可能唯一，也可能不唯一7 如果在文法 G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。A 其最左推导和最右推导相同B 该句子有两个不同的最左推导C 该句子有两个不同的最右推导D 该句子
4、有两棵不同的语法树E 该句子对应的语法树唯一8 下面（ ）语法制导翻译中，采用拉链回填技术。A.赋值语句B. 布尔表达式的计算C.条件语句D. 循环语句三三解答题解答题（共 60 分）1 （共 15 分）已知文法 GE:E EETE|ETE|（E E）|i|iT T*|+*|+（1） 将文法 G 改造成 LL（1）文法； （5 分）（2） 构造文法 G 中每个非终结符的 FIRST 集合及 FOLLOW 集合； （5 分）（3） 构造 LL（1）分析表。 （5 分）2 （共 12 分）给定文法 GS：S SS(S)|S(S)|（1） 给出句子()()()()的规范推导过程； （4 分）（2）
5、指出每步推导所得句型的句柄； （4 分）（3） 画出该句子的语法推导树。 （4 分）3 （共 8 分）在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行 括号中的动作。AaBaBprintprint “0 0”； A Ac cprintprint “1 1”； BAbAbprintprint “2 2”； （1） 当分析器的输入为 aacbb 时，打印的字符串是什么？（3 分）（2）写出分析过程。 （5 分）4 （10 分）翻译循环语句 while (ad) then x:=y+z 。要求：给出加注释的分析树及四元式序 列。参考以下部分翻译模式：(1)Sif
6、E then M S1backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)(2)Swhile M1E do M2S1backpatch(S1.nextlist,M1,.quad);backpatch(E.truelist,M2,.quad);得分第 3 页 共 12 页S.nextlist:=E.falselistemit (j,-,-,M1.quad)(3)SAS.nextlist:=makelist()(4)LSL.nextlist:=S.nextlist(5)MM.quad:=nextquad(6)
7、Eid1relop id2E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place ,id2.place,0);emit(j,-,-,0)(7)SL:=Eemit(:=,E.place,-,L.place)(8)EE1+E2E.place:=newtemp;emit(+,E1.place,E2.place,E.place,)5 （共 15 分）设有表格构造文法 GS：S Sa|a|(T)|(T)T TT,S|ST,S|S(1)计算文法 GS的 FIRSTVT 集和 LAST
8、VT 集。 （5 分）(2)构造 GS的优先关系表，并判断 GS是否为算符优先文法。 （5 分）(3)计算 GS的优先函数。 （5 分）二二单项选择题单项选择题（每题 2 分，共 10 分）1. 设有文法 GI： I II1|I0|Ia|Ic|a|b|cI1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（） 。 ab0 a0c01 aaa bc10可选项有：A BCD2.程序的基本块是指（） 。A 一个子程序B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段D 一组顺序执行的程序段，仅有一个入口和一个出口得分第 4 页 共 12 页3. 高级语言编译程序常用的语法分析方法
9、中，递归下降分析法属于（）分析方法。A 自左向右B 自顶向下C 自底向上D 自右向左4经过编译所得到的目标程序是（） 。A 四元式序列B 间接三元式序列C 二元式序列D 机器语言程序或汇编语言程序5运行阶段的存储组织与管理的目的是（） 。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度 为运行阶段的存储分配做准备可选项有：A. B. C. D.2.（10 分） 已知文法 GS:SaBc|bABAaAb|bBb|（4） 构造其 LL（1）分析表；（5） 判断符号串 baabbbbaabbb 是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程） 。3. (10 分)
10、 已知文法 G 为：EE+T|TTT*P|PPi（1） 构造该文法的优先关系表（不考虑语句括号#） ，并指出此文法是否为算符优先文法。（2） 构造文法 G 的优先函数表。4 （8 分）在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括 号中的动作。SbAbbAbprintprint “1 1” A A(B(Bprintprint “2 2” Aa aprintprint “3 3” BAa)Aa)printprint “4 4” （3） 当输入序列为 b(aa)a)a)b 时，打印的字符串是什么？（4）写出移入-规约分析过程。5 （12 分）翻译循环语句 w
11、hile (xy) do if (a=b) then x:=2*y+a 。要求：给出加注释的分析树、三地址 码序列及相应的四元式序列。得分第 5 页 共 12 页参考以下部分翻译模式：(1)Sif E then M S1backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)(2)Swhile M1E do M2S1backpatch(S1.nextlist,M1,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,
12、M1.quad)(3)SAS.nextlist:=makelist()(4)LSL.nextlist:=S.nextlist(5)MM.quad:=nextquad(6)Eid1relop id2E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place ,id2.place,0);emit(j,-,-,0)(7)SL:=Eemit(:=,E.place,-,L.place)(8)EE1+E2E.place:=newtemp;emit(+,E1.place,E2.place,
13、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+1Goto L1L2:7 (6 分)Give out the all basic blocks of the following program fragment and construct the relevant flow
14、 graph(DAG).read CA=0B=1L4: A=A+B第 6 页 共 12 页if BC goto L2B=B+1goto L4L2: write A8. (8 分)Translate the assignment statement bi=b*c-b*dbi=b*c-b*d into(1) A syntax tree.(2) Three address instructions.答案： ：(1)(1) 栈式动态存储分配(2)(2) 堆式动态存储分配(3)(3) 左(4)(4) 语法分析(5)(5) 目标代码生成(6)(6) 表格管理(7)(7) xyz*ab+/+(8)(8) 继
15、承属性(9)(9) a+(i-1)*20+j-1(10)(10)基本块 一、一、选择题（每问选择题（每问 2 分，分，共共 20 分分）1.C B2.D3.B4.A5.D6.A,C7.BCD,选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止。8.BCD，选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止。二、二、解答题解答题1 （1 1）文法存在左递归，消除左递归后的文法为：E(E)E|i E （2 2 分）分）ETEE|（2 2 分）分）T*|+（1 1 分）分）（2 2）(5(5 分分) )没考虑#扣 0.5 分，其它错或少写一个扣 0.5 分FIRST(E)=(,iFIRST(E)=*,+, FIRST(T)=*,+FOLLOW(E)=),*,+,#FOWLLOW(E)= ),*,+,#FOLLOW(T)=(,i（3 3）每错一个扣 0.5 分，全错或不写不得分，扣完为止，共 5 分()i*+#第 7 页 共 12 页EE(E)EEiEEE ETEEE ETEE
