《编译原理》复习题

56．构造下述文法的SLR（1）分析表。

G[S]：S→（A） A→ABB|B B→b

解：拓广文法：（1分） S′→S （0）

S→（A） （1） A→ABB （2）

A→B （3） B→b （4）

识别活前缀的DFA：（4分）

I：S′→.S 0 S→.(A) S I1：S′→S. ( ) I2：S→(.A) A→.ABB A→.B B→.b B I5： A→B. I4： B→b. A I3：S→(A.) A→A.BB B→.b b I6： S→(A). B I7：A→AB.B B→.b B I8：A→ABB. b

FIRST集和follow集：（1分）

First（S）={（，c} follow( S)={#} First（A）={b} follow(A)={b,)} First（B）={b} follow(B)={b,)}

SLR(1)分析表：（4分） 0 1 2 3 4 5 6 7 8 （ S2 ） S6 R4 R3 R2 ACTION b S4 S4 R4 R3 S4 R2 # Acc R1 S 1 GOTO A 3 B 5 7 8 57．有一语法制导定义如下： S→bAb print “1” A→（B print “2”

41

《编译原理》复习题

A→a print “3” B→aA) print “4” 若输入序列为b（a（a（aa）））b，且采用自下而上的分析方法，则输出序列为（__34242421____）。

58．写出赋值语句X= -(a+b)/(c-d)-(a+b*c)的逆波兰表示。

Xab+-cd-/abc*+-=

59．为文法

G[S]：S→（L）|a L→L，S|S

写一语法制导定义，它输出句子中括号嵌套的最大层次数。

解： 使用num属性描述括号的嵌套最大层次数

S?→S print（S.num） S→（L） S.num=L.num+1 S→a S.num=0

L→L(1)，S L.num=if L(1).num>S.num then LL→S L.num= S.num

每个式子1分。 60．设有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b

该文法句型aAcbBdcc的句柄是_______Bd_____________。

61．2．已知文法G[S]如下：构造该文法的LR（0）分析表。

G[S]：S→BB B→aB|b 解：拓广文法：（1分） （0）S?→S （1）S→BB （2）B→aB （3）B→b

识别活前缀的DFA 如下：

(1)

.num else S.num

42

《编译原理》复习题

I0： S??.S S?.BB B?.ab S I1： S??S. B I2： B I5： B?.b b S?B.B S?BB. b B?.ab a a B?.b b I3： b I4： a B?a.B B?b. B?.ab B?.b B I6： B?aB. LR(0)分析表如下：

状态 Action Goto a b # S B 0 S3 S4 1 2 1 acc 2 S3 S4 5 3 S3 S4 6 4 R3 R3 R3 5 R1 R1 R1 6 R2 R2 R2 43