编译原理复习题

直接短语:T*F, i1, i2 句柄:T*F

素短语:T*F, i1, i2 最左素短语:T*F

五、FIRSTVT集合和LASTVT集合,构造优先关系表

1、设文法G(S):

S?(A)|a A?A+S|S

1)构造各非终结符的FIRSTVT集合和LASTVT集合。 2)构造优先关系表。

2、设文法G3为: S?AaBc A?Aa|a B?b

1)构造各非终结符的FIRSTVT集合和LASTVT集合。 2)构造优先关系表。

3)求句型AaBc的最左素短语。

答:1) 非终结符的FIRSTVT 集合和LASTVT 集合为: FIRSTVT(S)={a}, LASTVT(S)={c}, FIRSTVT(A)={a}, LASTVT(A)={a}, FIRSTVT(B)={b}, LASTVT(B)={b}。 2)则优先关系表为:

3)句型AaBc 的最左素短语为:

对于#AaBc#,##,则最左素短语为AaBc。 3、设文法G(S):

S?SiA|AA?A?B|B B?)A*|(1) 构造各非终结符的FIRSTVT和LASTVT集合; 2) 构造优先关系表。 答:1)FIRSTVT(S)={ i,+,),( } FIRSTVT(A)={ +,),( } FIRSTVT(B)={ ),( } LASTVT(S)={ i,+,*,( } LASTVT(A)={ +,*,( } LASTVT(B)={ *,( } 2)优先关系表

六、LR分析

1、已知文法

A→aAd|aAb|ε

判断该文法是否是 SLR(1)文法,若是构造相应分析表。

答:拓展文法为 G′ ,增加产生式 S′→A产生式排序为: S' →A

A →aAd A →aAb A →ε

由产生式知: First (S' ) = {ε,a} First (A ) = {ε,a} Follow(S' ) = {#} Follow(A ) = {d,b,#}

G’ 的 LR(0) 项目集族及识别活前缀的 DFA 如下图所示:

在 I0 中:

A→.aAd 和 A →.aAb 为移进项目, A →. 为归约项目,存在移进 - 归约 冲突,因此所给文法不是 LR(0) 文法。 在 I0 、 I2 中:

Follow(A) ∩{a}= {d , b , #} ∩{a}=Φ

所以在 I0 、 I2 中的移进 - 归约冲突可以由 Follow 集解决,所以 G 是 SLR(1) 文法。

构造的 SLR(1) 分析表如下:

2、若有定义二进制数的文法如下:

S→L·L|L L→LB|B B→0|1

试为该文法构造 LR 分析表,并说明属哪类 LR 分析表。

3、已知文法G[S]:

S→MH|a H→LSo|ε K→dML|ε L→eHf

M→K|bLM

判断G 是否是LL(1)文法,如果是,构造LL(1)分析表。

4、考虑文法:

S →A S | b A →S A | a

1)构造文法的 LR(0)项目集规范族及相应的 DFA。 2)构造文法的 SLR 分析表。

答:1) 令拓广文法 G’ 为 (0) S’ →S (1)S →A S (2)S →b (3)A →S A (4)A →a

其 LR(0) 项目集规范族及识别该文法活前缀的 DFA 如下图所示: FOLLOW(S)={#,a,b} FOLLOW(A)={a,b}

LR(0) 项目:

2) 文法的 SLR 分析表如下:

因为 I5 中: FOLLOW ( A ) ∩{a , b}≠Ф I7 中: FOLLOW ( S ) ∩{a , b}≠Ф 所以,该文法不是 SLR ( 1 )文法。

联系客服:779662525#qq.com(#替换为@)