发布时间 : 星期一 文章编译原理复习题更新完毕开始阅读081a93fa3968011ca30091f1
直接短语：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#，#
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 ）文法。