期末考试试卷A卷

天津理工大学考试试卷

2009〜2010学年度第二学期

《编译原理》期末考试试卷

课程代码：0660116试卷编号:1-A命题日期：2010年6月15日

答题时限：120分钟考试形式：闭卷笔试

得分统计表:

号

—'二三四

一、单项选择题(请从4个备选答案中选择最适合的一项，每小题2分，共20

分)

得分

注意：须将本题答案写在下面的表格中，写在其它地方无效

12345678910

DCBDDBCBDC

1.编译程序是对()

A.汇编程序的翻译B.高级语言程序的解释执行

C.机器语言的执行D.高级语言的翻译

2.词法分析器的输出结果是()

A.单词的种别编码B.单词在符号表中的位置

C.单词的种别编码和自身值D.单词自身值

3.在规范规约中，用()来刻画可规约串。

A.直接短语B.句柄C.最左素短语D.素短语

**

4.与正规式(a|b)(c|d)等价的正规式是()

****

A.a(c|d)|b(c|d)B.a(c|d)|b(c|d)

****

C.a(c|d)|b(c|d)D.(a|b)c|(a|b)d

5.若项目集IK含有Afa•,则在状态K时，仅当面临输入符号awFOLLOW(A)时，才采取

ATa•动作的一定是()

A.LALR文法B.LR(0)文法C.LR(1)文法D.SLR⑴文法

6.四元式之间的联系是通过()实现的。

A.指示器B.临时变量C.符号表D.程序变量

7.文法G：S->xSx|y所识别的语言是（）

***

A.xyxB.（xyx）C.xnyxn（nNO）D.xyx

8.有一语法制导翻译如下所示：

SfbAb{print"1”}

A->（B{print"2”}

Afa{print“3”，

BfAa）{print"4”j

若输入序列为b（（（aa）a）a）b,且采用自下而上的分析方法，则输出序列为（）

A.32224441B.34242421C.12424243D.34442212

9.关于必经结点的二元关系，下列叙述不正确的是（）

A.满足自反性B.满足传递性C.满足反对称型D.满足对称性

10.错误的局部化是指（）。

A.把错误理解成局部的错误B.对错误在局部范围内进行纠正

C.当发现错误时，跳过错误所在的语法单位继续分析下去

D.当发现错误时立即停止编译，待用户改正错误后再继续编译

二、判断题（每小题1分，共5分）

得分

1.文法G的一个句子对应于多个推导，则G是二义性的。（X）

2.动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（J）

3.算符优先文法采用“移进一规约”技术，其规约过程是规范的。（X）

4.删除归纳变量是在强度削弱以后进行。（V）

5.在目标代码生成阶段，符号表用于目标代码生成。（X）

三、简答题（每小题5分，共15分）

得分

*

1.构造正规式（0I1）00相应的正规式并化简。（共5分）

（1）根据正规式，画出相应的NFAM（2分）

0

（2）用子集法将NFA确定化（2分）

IIoII

{x,l,2}{1,2,31HZ

[1,2,3}{1,2,3,41{1,2}

[1,2}[1,2,3}{1,2}

{1,2,3,4){1,2,3,4}{1,2}

将所有子集重命名，得到转换矩阵:

S01

012

132

212

332

（3）化简，并画出DFAM（1分）

划分为状态：{0,2}{1}{3}将这三个状态命名为0,1,2三个状态

S01

010

120

220

2.设文法G[S]:（共5分）

S-S+aT|aT|+aT

T―**aT|*a

（1）写出句型aT+a*a*a的最右推导并画出语法树（2分）

SnS+aTnS+a*aTnS+a*a*anaT+a*a*a

（2）写出该句型中所有的短语、直接短语、句柄和最左素短语。（3分）

短语：aT、*a*a、*a、aT+a*a*a

直接短语：aT、*a

句柄：aT

最左素短语：aT

3.将下列语句翻译为逆波兰表示，三元式、间接三元式和四元式表示：（共5分）

a=（b+c）*e+（b+c）/f

（1）逆波兰表示（1分）

abc+e*bc+f/+=

⑵①

②什b,

*(①C⑻)

③,

④什b,c)

@②,,f,)

⑤(/什,

(4

⑥⑤

("=a,汉

刀

、

可

—

(3)①

②湍

③

④

承

⑤

间­

(4)①四元式(2分)

②(+,b,c,Tl)

③(*,Tl,e,T2)

④(+,b,c,T3)

⑤(/,T3,f,T4)

⑥(+,T2,T4,T5)

(=,T5,-,a)

四、综合题（共60分）

得分

1.已知文法G(S)：(共15分)

S->*A

AT0A1|*

⑴求文法G的各非终结符号的FIRSTVT和LASTVT集合。(5分)

FIRSTVT(S)={*}LASTVT(S)={1,*}

FIRSTVT(A)={0,*}LASTVT(S)={1,*}

（2）构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法。（5分）

*01

*<<>

0<<=

1>

文法G中的任何终结符对至多只存在利优先关系，所以文法G是一个算符优先文法。

（3）分析句子*0*1,并写出分析过程。（5分）

步骤符号栈输入串输出

0#*0*1#

1#*0*1#

2#*0*1#

3#*0*1#

4#*0A1#

5#*OA1#

6H*A#

7#S江分析正确

2.已知文法G(S)：(共15分)

SfaS|bS|a

(1)构造该文法的拓广文法。(1分)

(o)s」s

(1)S-aS

⑵A-bS

(3)A-*a

⑵构造其LR(O)项目集规范族，并给出识别活前缀的DFA。(7分)

⑶构造其SLR分析表，并判断该文法是否是SLR(l)文法。(7分)

状态h移进一规约冲突，计算S的Follow集合：Follow(S)={#},可以采用SLR冲突消解法,

得到如下SLR分析表：

ACTIONGOTO

状态ab#S

03

S1s2

14

Sis2n

25

Sis2

3acc

4ri

5刈

该文法是SLR(1)文法。

3.设有如下基本块：(共10分)

T1=A+B

T2=5

M=T2*4

T3=C-D

T4=M+T3

L=T1*T3

T4=A+B

N=T4

AB520CD

（2）假设变量L,M,N在基本块出口之后是活跃的，给出优化后的四元式序列。（5分）

N=A+B

M=20

T3=C-D

L=N*T3

4.以下程序段是最内循环（共13分）

A=0

1=1

LI:B=J+1

C=B+I

A=C+A

if1=100GOTOL2

1=1+1

GOTOLI

L2:

流图中有一条回边B3一＞B2,且B2DOMB3,所以，有一个循环{B2,B3},B2是循环入口

结点，也是出口结点。

(2)对循环优化(8分)

1.代码外提：对于B2中的赋值四元式B=J+1,由于循环中没有对J的定值操作，所有对J

的定值都在循环外，所以，它是循环中的不变运算，可以进行代码外提。

2.删除归纳变量：循环中I是基本归纳变量，C是与I同族的归纳变量，两者有如下线性关

系：C=B+L则1=100可以用C=B+100替代，相应的1=1+1可用C=C+1替代，再将新的不变

运算提到循环外。

B4

5.有一程序如下：

programex;

a:integer;

procedurePP(x:integer);

begin:

x:=5;x:=a+l

end;

begin

a:=2;

PP(a)；

write(a)

end

试用图表示ex调用PP(a)前后活动记录的过程。(共7分)