《编译原理》复习题

a0ab1a2b3b

37．请画出识别无符号十进制整数的状态转换图 【解】

１-９ ０-９ 1 2 ?(其它) 3 0

38．设有文法G[S]:

S→S*S|S+S|(S)|i

该文法是否为二义文法,并说明理由？

【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。 S S S * S S + S i S + S S * S i (1) i i i i (2)

39．程序的文法如下：

P → D

D → D;D | id : T | proc id; D; S

写一语法制导定义，打印该程序一共声明了多少个id 【解】 属性num表示id个数 P → D print(D.num) D → D(1)；D(2) D.num = D(1).num + D(2).num D → id : T D.num = 1 D → proc id; D(1); S D.num = D(1).num + 1

例：proc id; proc id; id : T; S; S（从语法树分析入手） （注意：本例只是帮助学生理解题意，不是答案部分）

33

《编译原理》复习题

P D procid ; D ; S procid ; D ; id : T

40．把下列语句翻译为四元式序列（四元式序号从1开始）： while (A > B) if (C > D)

X = Y * Z

else

X = Y + Z 【解】(1) (j>, A, B, 3) (2) (j, _, _, 11) (3) (j>, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X) (7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11)

41.构造下面文法的LL（1）分析表。 G[D]: D ? TL

T ? int | real L ? id R

R ? , id R | ?

S 34

《编译原理》复习题

【解】FIRST(T)={ int real } FOLLOW(T)={ id } FIRST(L)={ id } FOLLOW(L)={ #} FIRST(R)={ , ?} FOLLOW(R)={ #}

FIRST(D)={ int real } FOLLOW(D)={#} 因为FIRST(int)∩FIRST(real)=Φ

FIRST(, id R)∩FOLLOW(R)=Φ

所以是LL（1）文法，LL（1）分析表如下： D T L R int D ? TL T ? int real D ? TL T ? real id L ? id R , # R ? , id R R ? ? 42．给定文法S→aS|bS|a，下面是拓广文法和识别该文法所产生的活前缀的DFA。判断该文法是否是SLR(1)文法：如果是构造其SLR(1)分析表，如果不是请说明理由。

(1)将文法G(S)拓广为G(S’)：

(0)S’→S (1)S→aS (2)S→bS (3)S→a

(2)识别该文法所产生的活前缀的DFA如图1所示。

图1

【解】注意到状态I1存在“移进-归纳”冲突，计算S的FOLLOW集合： FOLLOW(S)={#}

{a}∩{b}∩FOLLOW(R)=Φ

可以采用SLR冲突消解法，得到如下的SLR分析表。

从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。

35

《编译原理》复习题

表1 SLR分析表

状态 0 1 2 3 4 5 a S1 S1 S1 ACTION b S2 S2 S2 # r3 acc r1 r2 GOTO S 3 4 5

43．给出表达式-a*b+b*c+d/e的语法树和三元式序列。

答：语法树 三元式

+ + * * - a b b c d e / ①（-，a，-） ②（*，①，b） ③（*，b，c） ④（+，②，③） ⑤（/，d，e） ⑥（+，④，⑤）

44．证明下面文法S→AaAb|BbBa A→ε B→ε，是LL（1）文法，但不是SLR（1）文法。

证明：

（1）first（AaAb）={a} first（BbBb）={b} ，有first（AaAb）∩first（BbBb）=Φ 所以根据LL（1）文法的定义，该文法是LL（1）文法。（2分） （2）为了构造识别活前缀的DFA，初态集包含如下四个项目：S→.AaAb S→.BbBa A→. B→. 但该项目中有两个可归约项目：A→. B→.，产生归约-归约冲突，而follow（A）={a，b}，follow（B）={a，b}，有follow（A）∩follow（B）≠Φ，所以使用向前看一个终结符的方法不能解决此冲突，所以该文法不是SLR（1）文法。（3分）

45．现有文法G[S]

S→a|ε|(T) T→T,S|S

请给出句子（a,(a,a)）的最左、最右推导，并指出最右推导中每一个句型的句柄。 答：最左推导：S=〉（T）=〉（T，S）=〉（S，S）=〉（a，S）=〉（a，（T））=〉（a，（T，S））=〉（a，（S，S））=〉（a，（a，S））=〉（a，（a，a））

最右推导： S=〉（T）=〉（T，S）=〉（T，（T））=〉（T，（T，S））=〉（T，（T，a））=〉（T，（S，a））=〉（T，（a，a））=〉（S，（a，a））=〉（a，（a，a））

句型的句柄是为加下划线的部分

36