期末考试编译原理试卷及答案.doc

资源描述

期末考试编译原理试卷及答案.doc

《期末考试编译原理试卷及答案.doc》由会员分享，可在线阅读，更多相关《期末考试编译原理试卷及答案.doc（12页珍藏版）》请在冰点文库上搜索。

期末考试编译原理试卷及答案.doc

得分

一．填空题（每空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分

（

）

E→（E）E’

E→iE’

E’

E’→ε

E’→TEE’

E’→ε

E’→TEE’

E’→ε

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）

）

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

ε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分）

可以不考虑终结符“#”。

∧

（

）

⋗

∧

⋗

（

⋖

）

⋗

⋖

⋗

⋖

或者

（3）优先函数。

可以不考虑终结符“#”。

每错一个扣0.5分，全错或不写不得分，扣完为止，共5分。

∧

（

）

或者

∧

（

）

三、填空题（每空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分，扣完为止

（1）空白表格也可以填写“错误”字样,共4分，错一个扣0.5分，扣完为止

$（#）

S→aBc

S→bAB

A→aAb

A→b

B→b

B→ε

（2）共6分，其中判断“baabbb是该文法句子”为2分，其他错一个扣0.5分，扣完为止

符号栈

输入串

规则

$BAb

$BA

$BbAa

$BbA

$BbbAa

$BbbA

$Bbbb

$Bbb

$Bb

baabbb$

aabbb$

abbb$

bbb$

bb$

S→bAB

A→aAb

A→b

B→ε

success

（1）共6分，其中判断“该文法为算符优先文法”为2分，其他错一个扣0.5分，扣完为止

（2）共4分，错一个扣0.5分，扣完为止

4．

（1）34242421，共4分，错一个扣0.5分

（2）共4分，错一个扣0.5分，扣完为止

stack

Inputstring

action

$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$

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）b$

a）b$

）b$

shift

reduce,A→a

shift

reduce,B→Aa）

reduce,A→（B

shift

reduce,B→Aa）

reduce,A→（B

shift

reduce,B→Aa）

reduce,A→（B

shift

reduce,S→bAb

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分，基本块划分和流图各为3分，错一处扣1分，扣完为止

展开阅读全文