编译原理试题与解析北京工业大学

精品文档精品文档PAGE精品文档

北京工业大学2003-04-2 学期 010700-11 班级《编译原理》

试卷

学号_______________姓名

________________

成绩

___________

题号

一

二

三

四

五

六

分数

.（10分）改写以下文法，使其满足采用自顶向下分析方法的要求。

S?aXcY|YdX?XaY|cY?bYcX|b

岚澗惩閘间铗過击羋蕷競颟奩諄诽。解:

(1)消除X?XaY|c 的左递归

X?cX’

X’?aYX’| ε

提取Y?bYcX|b的左因子Y?bY’

Y’?YcX|ε

整理后，原文法变为

S?aXcY|Yd

X?cX’

X’?aYX’|ε

Y?bZ

Z?YcX|ε

会誹闐谟鐲瑶锗馔驻蝉粪涩浔矯咼。.(15分)考虑文法G[S]：S?xSNy|Nx

N?zN|ε

求出该文法的每个非终结符的FOLLOW集；

构造该文法的预测分析表。

絹遼鲻錯绫马缥泸羁裣国声銣铃复。解:

1、

FIRST(S)={x,z}

FIRST(N)={z, ε}

FOLLOW(S)={#,y,z}

FOLLOW(N)={x,y}辍錛临費讳来債綻嵘诗浹鳄燜殮頓。

2、预测分析表x

y

z

#

S

S?xSNyS?Nx

S?Nx

NN?εN?εN?zN

.(20分)符号串xxyyyx是如下文法G[S]的句子，S?xB|yA

A?xS|yAA|xB?yS|xBB|y

构造该句子的分析树；

写出生成该句子的最左推导；

写出生成该句子的规范归约过程；指出每步归约中的句柄。

珐繪镯語鳐夺霧碛麽飞蟄汇锇廳谘。解:

语法分析树（6分）

S

x B

x B B

y y S

y A

x

S?xB?xxBB?xxyB?xxyyS?xxyyyA?xxyyyx(5分)

规范归约（9分）xxyyyx ?xxByyx

xxByyx?xxByyA

xxByyA?xxByS

xxByS?xxBB

xxBB?xB

xB?S瘓順虧銻軹筝剄蛲诘谰態儺艙謂纾。

句柄为句柄为句柄为句柄为句柄为句柄为

y

x

yA

yS

xBB

xB

.（20分）考虑简单赋值语句的文法G[S]：S?id:=E

E?E+EE?E*EE?id

（1）试构造识别该文法所有规范句型活前缀的有限自动机。

（2）判断该文法是否为LR(0)文法（必须说明理由）。

鸟恆頻鲑櫫塒悶戰唤雳簡軛齒憒趸。解:

(1)

I0:S’?.SS?.id=EI1I1:S’?S.I2:S?id.=ESidEI3:S?id=.EII5I7I9E?.E+E0id+E?.E*EididE?.idI=I3E+I6E*I7I4:S?id=E.2I4I8E?E.+E+E?E.*EI5:E?id.（2）由于I、I、II:E?E+.E89均有移进—归约冲突，64E?.E+EE?.E*E故该文法不是LR(0)文法。E?.idI7:E?E*E?.E+EE?.E*EE?.id

?E.+EE?E.*E

?E.+EE?E.*E

五.（15分）考虑以下语法制导定义

产生式语义规则S?L1.L2Print(+*)L?L1B=2*+=+1L?B==1B?0=0B?1=1（1）写出句子的带注释分析树、或属性计算过程。（2）给出处理该句子的结果（Print输出结果）。解：（1）句子的带注释分析树：print(3+1*2-2)S=2*+=3=2*+=1=+1=2L.=+1=2L==1=1==0=1=1LLB=1B=11=01BB1 0

（2）处理该句子的结果（Print 输出结果）为

.（20分）设语言L是“能被5整除的十进制正整数”组成的集合，

1）试写出描述语言L的正规表达式；

2）画出识别语言L的状态转移图。

解：

（1）语言L的正规表达式