I0 I1 I2 I5 I8 S’->S. S->A.a S->Aa. S->dc. S’->.S S->.Aa I3 I4 I6 I9 S->.bAc S->b.Ac S->d.c S->bA.c S->bAc. S->.dc A->d. S->b.da S->.bda I7 I10 A->.d A->.d S->bd.a S->bda. A->d. ③GOTO函数
GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，d)=I4 GOTO(I1,$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7 GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10 ④构建SLR语法分析表如下(FOLLOW(A)={a,c}) 状态 a 0 1 2 3 4 5 6 7 8 9 10 S5 R5 S10|R5 b S3 ACTION c S8|R5 S9 R5 d S4 S7 $ acc R1 R3 R2 R4 S 1 GOTO A 2 6 可以看到在图中存在二义性的条目，故该文法不是SLR(1)文法
2、构造该文法的LALR(1)语法分析表 ①构造该增广文法的LR(1)项集族如下 I0 I1 I3 I5 I7 S’->.S,$ S’->S.,$ S->b.Ac,$ S->Aa.,$ S->bd.a.,$ S->.Aa,$ S->b.da,$ A->d.,c I6 S->.bAc,$ I2 A->.d,c I8 S->bA.c.,$ S->A.a,$ S->.dc,$ S->dc.,$ I4 S->.bda,$ S->d.c,$ A->.d,a A->d.,$ ②项集合并：没有可以合并的项集 ③GOTO函数
GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，d)=I4 GOTO(I1,$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7
I9 S->bAc.,$ I10 S->bda.,$ GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10 ④构造LALR(1)分析表如下 状态 a 0 1 2 3 4 5 6 7 8 9 10 S5 R5 S10 b S3 ACTION c S8 S9 R5 d S4 S7 $ acc R5 R1 R3 R2 R4 S 1 GOTO A 2 6 可见该分析表中不存在二义性的条目，故该文法是LALR(1)文法
习题4.7.5说明下面的文法 S->Aa|bAc|Bc|bBa A->d B->d
是LR(1)的，但不是LALR(1)的 证明：
1、 构造该文法的LR(1)语法分析表 ①构造该文法的增广文法 S’->S S->Aa S->bAc S->Bc S->bBa A->d B->d
②构造该增广文法的LR(1)项集族如下 I0 I1 I2 I6 I10 S->Bc.,$ S’->.S,$ S’->S.,$ S->A.a,$ S->Aa.,$ S->.Aa,$ I7 I4 S->.bAc,$ I3 S->b.Ac,$ S->B.c,$ S->bA.c.,$ S->.Bc,$ S->.bBa,$ S->b.Ba,$ I5 I8 I11 A->.d,c A->.d,a S->bAc.,$ A->d.,a S->bB.a.,$ B->.d,a B->.d,c B->d.,c
②项集合并：没有可以合并的项集
I12 S->bBa.,$ I9 A->d.,c B->d.,a ③GOTO函数
GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，B)=I4 GOTO(I0，d)=I5 GOTO(I1,$)=acc GOTO(I2，a)=I6 GOTO(I3，A)=I7 GOTO(I3，B)=I8 GOTO(I3，d)=I9 GOTO(I4，c)=I10 GOTO(I7，c)=I11 GOTO(I8，a)=I12 ④构造LR(1)分析表如下 状态 a 0 1 2 3 4 5 6 7 8 9 10 11 12 S6 R5 S12 R6 b S3 ACTION c S10 R6 S11 R5 d S5 S9 $ acc R1 R3 R2 R4 S 1 GOTO A 2 7 B 4 8 可见该分析表中不存在二义性的条目，故该文法是LR(1)文法 2、 构造该文法的LALR(1)语法分析表 ①合并LR(1)项集族 I59 A->d.,a/c I5和I9可以合并为I59 B->d.,c/c
②构造LALR(1)语法分析表如下 状态 a 0 1 2 3 4 59 6 7 8 9 10 11 S6 R5|R6 S11 b S3 ACTION c S9 R6|R6 S10 d S59 S9 $ acc R1 R3 R2 R4 S 1 GOTO A 2 7 B 4 8 可见该语法分析表中存在有二义性的条目，故该文法不是LALR(1)文法
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理第4章作业答案(2)在线全文阅读。
相关推荐：