我们可以直接构造它的LR(1)项目集如下:
I0: S′→·S ,#
S→·aAd ,#
S→·bBd ,#
S→·aBe ,#
S→·bAe ,#
I1: S′→S·,#
I2: S→a·Ad ,#
S→a·Be ,#
A→·c ,d
B→·c ,e
I3: S→b·Bd ,#
S→b·Ae ,#
B→·c ,d
A→·c ,e
|
I4: S→aA·d ,#
I5: S→aB·e ,#
I6: A→c·,d
B→c·,e
I7: S→bB·d ,#
I8: S→bA·e ,#
I9: A→c·,e
B→c·,d
I10:S→aAd·,#
I11:S→aBe·,#
I13:S→bBd·,#
I14:S→bAe·,#
|
检查每个项目集Ii可知,在任一项目集中都不含移进-归约冲突或归约-归约冲突。因此文法是LR(1)的,进一步察看项目集可发现I6和I9是同心集:
I6: A→c·,d I9:
A→c·,e
B→c·,e B→c·,d
若合并后则变为:
I6,9:A→c·,d/e
B→c·,e/d
这样就出现了新的归约-归约冲突,因为不管当前符号是d或e既可用产生式A→c归约也可用产生式B→c归约,因而该文法不是LALR(1)文法。当然也不可能是SLR(1)和LR(0)文法。
LALR(1)文法小结:
·一个LR(1)文法项目集的同心集合并后心仍相同,只是超前搜索符集合为各同心集超前搜索符的和集,合并同心集后转换函数自动合并。
·一个LR(1)文法合并同心集后只可能出现归约-归约冲突,而没有移进-归约冲突。
·合并同心集后,对错误的输入串分析可能会推迟发现错误的时间,但错误出现的位置仍是准确的。 |