河南科技大学期末考试编译原理试卷及答案.doc
- 文档编号:5015116
- 上传时间:2023-05-07
- 格式:DOC
- 页数:12
- 大小:222KB
河南科技大学期末考试编译原理试卷及答案.doc
《河南科技大学期末考试编译原理试卷及答案.doc》由会员分享,可在线阅读,更多相关《河南科技大学期末考试编译原理试卷及答案.doc(12页珍藏版)》请在冰点文库上搜索。
得分
河南科技大学电信科卷A
一.填空题(每空2分,共20分)
1.不同的编译程序关于数据空间的存储分配策略可能不同,但大部分编译中采用的方案有两种:
静态存储分配方案和动态存储分配方案,而后者又分为
(1)和
(2)。
2.规范规约是最(3)规约。
3.编译程序的工作过程一般划分为5个阶段:
词法分析、(4)、语义分析与中间代码生成,代码优化及(5)。
另外还有(6)和出错处理。
4.表达式x+y*z/(a+b)的后缀式为(7)。
5.文法符号的属性有综合属性和(8)。
6.假设二位数组按行存放,而且每个元素占用一个存储单元,则数组a[1..15,1..20]某个元素a[i,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.自底向上D.自右向左
4.在通常的语法分析方法中,()特别适用于表达式的分析。
A.算符优先分析法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.布尔表达式的计算C.条件语句D.循环语句
得分
三.解答题(共60分)
1.(共15分)已知文法G[E]:
E→ETE|(E)|i
T→*|+
(1)将文法G改造成LL
(1)文法;(5分)
(2)构造文法G中每个非终结符的FIRST集合及FOLLOW集合;(5分)
(3)构造LL
(1)分析表。
(5分)
2.(共12分)给定文法G[S]:
S→S(S)|ε
(1)给出句子(()())()()的规范推导过程;(4分)
(2)指出每步推导所得句型的句柄;(4分)
(3)画出该句子的语法推导树。
(4分)
3.(共8分)在一个移入-规约分析过程中采用以下的语法制导翻译模式,在按一个产生式规约时,立即执行括号中的动作。
A→aB{print“0”;}
A→c{print“1”;}
B→Ab{print“2”;}
(1)当分析器的输入为aacbb时,打印的字符串是什么?
(3分)
(2)写出分析过程。
(5分)
4.(10分)翻译循环语句while(ad)thenx:
=y+z。
要求:
给出加注释的分析树及四元式序列。
参考以下部分翻译模式:
(1)S→ifEthenMS1{backpatch(E.truelist,M.quad);
S.nextlist:
=merge(E.falselist,S1.nextlist)}
(2)S→whileM1EdoM2S1{backpatch(S1.nextlist,M1,.quad);
backpatch(E.truelist,M2,.quad);
S.nextlist:
=E.falselist
emit(‘j,-,-,’M1.quad)}
(3)S→A{S.nextlist:
=makelist()}
(4)L→S{L.nextlist:
=S.nextlist}
(5)M→ε{M.quad:
=nextquad}
(6)E→id1relopid2{E.truelist:
=makelist(nextquad);
e.falselist:
=makelist(nextquad+1);
emit(‘j’relop.op,‘,’id1.place‘,’id2.place‘,’‘0’);
emit(‘j,-,-,0’)}
(7)S→L:
=E{emit(:
=,E.place,-,L.place)}
(8)E→E1+E2{E.place:
=newtemp;
emit(+,E1.place,E2.place,E.place,)}
5.(共15分)设有表格构造文法G[S]:
S→a|∧|(T)
T→T,S|S
(1)计算文法G[S]的FIRSTVT集和LASTVT集。
(5分)
(2)构造G[S]的优先关系表,并判断G[S]是否为算符优先文法。
(5分)
(3)计算G[S]的优先函数。
(5分)
得分
二.单项选择题(每题2分,共10分)
1.设有文法G[I]:
I→I1|I0|Ia|Ic|a|b|c
下列符号串中是该文法句子的有()。
①ab0②a0c01③aaa④bc10
可选项有:
A.①B.②③④C.③④D.①②③④
2.程序的基本块是指()。
A.一个子程序B.一个仅有一个入口和一个出口的语句
C.一个没有嵌套的程序段D.一组顺序执行的程序段,仅有一个入口和一个出口
3.高级语言编译程序常用的语法分析方法中,递归下降分析法属于()分析方法。
A.自左向右B.自顶向下C.自底向上D.自右向左
4.经过编译所得到的目标程序是()。
A.四元式序列B.间接三元式序列
C.二元式序列D.机器语言程序或汇编语言程序
5.运行阶段的存储组织与管理的目的是()。
①提高编译程序的运行速度②节省编译程序的存储空间
③提高目标程序的运行速度④为运行阶段的存储分配做准备
可选项有:
A.①②B.②③C.③④D.④②
得分
2.(10分)已知文法G[S]:
S→aBc|bAB
A→aAb|b
B→b|ε
(4)构造其LL
(1)分析表;
(5)判断符号串baabbb是否为该文法的句子(写出含有符号栈、输入串和规则的分析过程)。
3.(10分)已知文法G为:
E→E+T|T
T→T*P|P
P→i
(1)构造该文法的优先关系表(不考虑语句括号#),并指出此文法是否为算符优先文法。
(2)构造文法G的优先函数表。
4.(8分)在一个移入-规约分析过程中采用以下的语法制导翻译模式,在按一个产生式规约时,立即执行括号中的动作。
S→bAb{print“1”}
A→(B{print“2”}
A→a{print“3”}
B→Aa){print“4”}
(3)当输入序列为b(((aa)a)a)b时,打印的字符串是什么?
(4)写出移入-规约分析过程。
5.(12分)翻译循环语句while(x>y)doif(a=b)thenx:
=2*y+a。
要求:
给出加注释的分析树、三地址码序列及相应的四元式序列。
参考以下部分翻译模式:
(1)S→ifEthenMS1{backpatch(E.truelist,M.quad);
S.nextlist:
=merge(E.falselist,S1.nextlist)}
(2)S→whileM1EdoM2S1{backpatch(S1.nextlist,M1,.quad);
backpatch(E.truelist,M2,.quad);
S.nextlist:
=E.falselist
emit(‘j,-,-,’M1.quad)}
(3)S→A{S.nextlist:
=makelist()}
(4)L→S{L.nextlist:
=S.nextlist}
(5)M→ε{M.quad:
=nextquad}
(6)E→id1relopid2{E.truelist:
=makelist(nextquad);
e.falselist:
=makelist(nextquad+1);
emit(‘j’relop.op,‘,’id1.place‘,’id2.place‘,’‘0’);
emit(‘j,-,-,0’)}
(7)S→L:
=E{emit(:
=,E.place,-,L.place)}
(8)E→E1+E2{E.place:
=newtemp;
emit(+,E1.place,E2.place,E.place,)}
6.(8分)Generateassemblycodeforthefollowingsequenceassumingthatx,yandzareinmemorylocations(noticingonlytworegistersR1andR2).
S=0
I=0
L1:
ifx>ygotoL2
Z=s+a[i]
I=i+1
GotoL1
L2:
7.(6分)Giveouttheallbasicblocksofthefollowingprogramfragmentandconstructtherelevantflowgraph(DAG).
readC
A=0
B=1
L4:
A=A+B
ifB>CgotoL2
B=B+1
gotoL4
L2:
writeA
8.(8分)Translatetheassignmentstatementb[i]=b*c-b*dinto
(1)Asyntaxtree.
(2)Threeaddressinstructions.
答案:
:
(1)栈式动态存储分配
(2)堆式动态存储分配
(3)左
(4)语法分析
(5)目标代码生成
(6)表格管理
(7)xyz*ab+/+
(8)继承属性
(9)a+(i-1)*20+j-1
(10)基本块
一、选择题(每问2分,共20分)
1.CB2.D3.B4.A5.D6.A,C
7.BCD,选对一个得1分且不超过满分,选错一个扣一分,扣完为止。
8.BCD,选对一个得1分且不超过满分,选错一个扣一分,扣完为止。
二、解答题
1.
(1)文法存在左递归,消除左递归后的文法为:
E→(E)E’|iE’(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’
E→iE’
E’
E’→ε
E’→TEE’
E’→ε
E’→TEE’
E’→ε
E’→ε
T
T→*
T→+
2.
(1)规范推导过程如下。
写错推导符号扣0.5分,错写或少写一步推导扣0.5分,扣完为止,最左推导扣2分,共4分。
(2)
(1)中加下划线的部分是句柄,标识如
(1)。
每少写一个句柄扣0.5分,扣完为止,共4分。
(3)每少写步扣0.5分,扣完为止,共4分。
S
S(S)
)
S(S)ε
)
εε
)
S(S)ε
)
S(S)ε
)
εS(S)
)
3.
(1)打印的字符串是:
12020(错一个扣0.5分,共3分)
(2)归约过程中错一步扣0.5分,扣完为止。
(共5分)
4.
(1)每少写一步扣0.5分,扣完为止,共5分。
whileM1.q=100E1.t=102doM2.q=102S1
E1.f=107
doS1.nl=103
(E3.t=102)εL.p=x:
=E4.p=T1
(E3.f=103)
c>dxE5.p=y+E6.p=z
yz
S
εa
E2.f=103
(2)少写一个四元式扣0.5分,全错或不写不得分,回填错误扣0.5分,共5分。
四元式序列为:
5.
(1)少写一个扣1分,全错或不写不得分,共5分。
FIRSTVT(S)={a,∧,(}
FIRSTVT(T)={,a,∧,(}
LASTVT(S)={a,∧,)}
LASTVT(T)={a,∧,),,}
(2)优先表如下。
每错一个扣0.5分,全错或不写不得分,扣完为止,共3分
文法G[S]没有两个非终结符相邻的情况,且其优先表中任一对终结符之间最多满足⋖、⋗、三种关系中的一种,因此是G[S]算符优先文法。
(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目标程序(targetcode)语法分析(syntaxanalyzer)代码优化器(codeoptimizer)代码产生器(codegenerator)符号表管理(symboltablemanager)
2继承属性(inheritedattribute)
3局部优化(localoptimization)
4四元式(quatriple)
5E+*()id
四、单项选择题(每题2分,共10分)
1.B2.D3.B4.D5.C
五、解答题(共70分)
1.
(1)L(G)={0m1m|M≥1}共2分,≥写成>扣1分
(2)S=>0S1=>00S11=>000111,共3分,=>写成->扣1分
(3)共3分,错处扣0.5分,扣完为止
2.
(1)空白表格也可以填写“错误”字样,共4分,错一个扣0.5分,扣完为止
a
b
c
$(#)
S
S→aBc
S→bAB
A
A→aAb
A→b
B
B→b
B→ε
B→ε
(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$
$
$
S→bAB
A→aAb
A→aAb
A→b
B→ε
success
3.
(1)共6分,其中判断“该文法为算符优先文法”为2分,其他错一个扣0.5分,扣完为止
+
*
i
+
>
<
<
*
>
>
<
i
>
>
(2)共4分,错一个扣0.5分,扣完为止
+
*
i
f
2
4
4
g
1
3
5
4.
(1)34242421,共4分,错一个扣0.5分
(2)共4分,错一个扣0.5分,扣完为止
stack
Inputstring
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)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
accept
5.共12分,其中带注释的分析树、三地址码序列和四元式序列分别为4分,错一个序列扣0.5分,而错某点(某项)少于或等于5个扣0.5分
带注释语法树(略)
三地址码序列四元式序列
M1:
if(x>y)gotoM2100(j>,x,y,102)
gotoM4101(j,-,-,108)
M2:
if(a=b)gotoM3102(j=,a,b,104)
gotoM1103(j,-,-,100)
M3:
t1=2*y104(*,2,y,t1)
t2=t1+a105(+,t1,a,t2)
x=t2106(=,t2,-,x)
gotoM1107(j,-,-,100)
M4:
108(-,-,-,-)
6.共8分,错一个扣0.5分,扣完为止
LDR1,0
STS,R1
STI,R1
L1:
LDR1,X
SUBR1,R1,Y(ORSUBR1,Y)
BGTZR1,L2
LDR2,a(R1)
ADDR2,R2,S(ORADDR2,S)
STZ,R2
LDR1,I(从这开始,下面的语句中的R1也可以全部变成R2)
ADDR1,R1,1(ORINCR1)
STI,R1
BRL1
L2:
7.共6分,基本块划分和流图
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 河南 科技大学 期末 考试 编译 原理 试卷 答案