编译原理复习题-给学生(简) 下载本文

《编译原理》复习题

35.文法

S ? A a | b A c | d c | b d a A ? d

造识别活前缀的DFA。请根据这个DFA来判断该文法是不是SLR(1)文法并说明理由。 【解】 S’ S S’

? ? .

S A S a S S ? ? ? .

A a c S A S b S S ? ? ? b . d S A c a S d ? S ? S b ? c S d .d .?

c Follow(S)={#} Follow(A)={a,c}

I4存在冲突且Follow(A)∩{c}={ c} I7存在冲突且Follow(A)∩{a}={ a} 所以不是SLR(1)文法

36.将下图所示的确定有限自动机(DFA)最小化。其中,X为初态,Y为终态。

【解】 1-9 0-9 ?(其它) 2 3 1 0 38.设有文法G[S]:

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

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

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

S S i (1) S S S i + S i S i S * + S i (2) *

aaXb21ba3abYb 【解】 先划分为终态集{Y}和非终态集I={X,1,2,3}

X面对输入符号b时下一状态属于I,而1,2,3面对输入符号b时下一状态属于{Y},故划分为{X}、{1,2,3}

非终态2和非终态3面对输入符号a的下一状态相同,而1不同,即最简状态{X}、{1}、{2,3}、{Y}。按顺序重新命名为0、1、2、3,则得到最简DFA,

a0ab21abb339.程序的文法如下:

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(从语法树分析入手)

(注意:本例只是帮助学生理解题意,不是答案部分)

P D procid ; D ; S procid ; D ; S

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

21

id : T 《编译原理》复习题

40.把下列语句翻译为四元式序列(四元式序号 int real id , # D D ? D ? 从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 | ?

【解】FIRST(T)={ int realFOLLOW(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)分析表如下:

TL TL T T ? T ? int real L L ? id R R R ? , R ? ? id 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)文法。

22

《编译原理》复习题

表1 SLR分析表 状态 0 1 2 3 a S1 S1 S1 ACTION b S2 S2 S2 # r3 acc GOTO S 3 4 5 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

4 r1 请给出句子(a,(a,a))的最左、最右推导,并

指出最右推导中每一个句型的句柄。 5 r2 答:最左推导:S=〉(T)=〉(T,S)=〉(S,

S)=〉(a,S)=〉(a,(T))=〉(a,(T,S))=〉

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

(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))

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

+ 46.将下图的DFA最小化。

/ * * - a b b c d 0 b 1 a 3 a 2 a b b a 4 e a b b

①(-,a,-) ②(*,①,b) ③(*,b,c) ④(+,②,③) ⑤(/,d,e) ⑥(+,④,⑤) 44.证明下面文法S→AaAb|BbBa A→ε B→ε,是LL(1)文法,但不是SLR(1)文法。

证明:

(1)first(AaAb)={a} first(BbBb)={b} ,

0 1 有first(AaAb)∩first(BbBb)=Φ

b b 所以根据LL(1)文法的定义,该文法是LL(1)a 文法。(2分)

(2)为了构造识别活前缀的DFA,初态集包含如

47.设有如下文法:P→D

下四个项目:S→.AaAb S→.BbBa A→.

23

答:初始划分:II={{0,1,2},{3,4}}(1分)

(1)考查{0,1,2},1和2接受a,b后都转向相同的状态,且接受b后转向终态,而0接受b后转向非终态2,所以0与1,2可分,IInew={{0},{1,2},{3,4}}(1分)

(2)考查{3,4},接受a,b后都转向相同的状态,所以3,4不可分。IInew={{0},{1,2},{3,4}}(1分)

将1,2合并用1代表,3,4合并用3代表,最终的最小化DFA如下:

a 3 b

《编译原理》复习题

D→D;D|id:T|proc id;D; T→real|integer

给出一个语法制导定义,打印该程序一共声明了多少个id。 答:

48.识别文法G的活前缀的DFA如下图所示,补 文法 语法制导定义 充P→D Print(D.num) 完D→D1;D2 D.num=D1.num+ 成D2.num 状D→id:T D.num=1 态D→proc D.num=D1.num+ Iid;D1; 1 2 和T→real → IT5integer ,然后根据

49.该图构造SLR(1)分析表。 G:(0) P'→P (1) P→aPb (2) P→Q (3) Q→bQc

(4) Q→bSc (5) S→Sa (6) S→a

Follow(P)={b,$} 1分 Follow(Q)={ b,c,$} 1分 Follow(S)={c,a} 1分 SLR(1)分析表: 0 1 2 3 4 5 6 7 8 9 10 11 12 a S2 S2 S6 R6 S12 R5 Action表 b S5 S5 R2 S7 S5 R1 R3 R4 c R6 R3 S8 S11 R4 R5 $ Acc R2 R1 R3 R4 P 1 4 GOTO表 Q 3 3 9 S 10 I0 :P'→.P P→.aPb P→.Q P I1 :P'→P. I2 : :P→a.Pb a P → .aPb P I4 :P→aP.b 49.给出表达式(a+b)*(c+d/e)的语法树和四元式序列。

答:语法树如下: 四元式序列:

* + + / a d e b c P → .Q b I7 :P→aPb. Q → .bQc a Q→.bQc b Q→.bSc Q→.bSc I8 :Q→bQc. Q b Q I 5 : Q → b.Qc c I3 :P→Q. I9 :Q→bQ.c Q → b.Sc Q b Q→.bQc I10 :Q→bS.c Q → .bSc S I6 : S→a. S→S.a a S → .Sa S → .a c I11 :Q→bSc. a I12 : S→Sa.

答:I2,I5分别如下图所示:

S A

a S→AaAb A→ε b S→BbBa A→ε $ 24

50.构造文法S→AaAb|BbBa A→ε B→ε,的预测分析表。

答:first(S)={a,b},First(AaAb)={a},First(BbBa )={b}

Follow(A)={a,b} Follow(B)={a,b}

①(+,a,b,T1) ②(/,d,e,T2) ③(+,c,T2,T3) ④(*,T1,T3,T4) B B→ε B→ε