首先我们知道LR(0)的项目的形式是[A→α·β ]这样的.而在LR(1)中的项目形式是[A→α·β ,a ],其中A→α·β 为LR(0)项目,称为心,a为终结符或#,称为向前搜索符。对归约项目[A→α·,a],仅当前输入符号是a时,才能用A→α进行归约。一会将会看到具体的例子。
课本上给出的规则是:我将要对照着规则来说明,这里要强调一下,",‘在这里是分隔符。不是终结符。他是一个标志,
以S′→·S,#属于初始项目集中,把’#‘号作为向前搜索符,表示活前缀为γ(若γ是有关S产生式的某一右部)要归约成S时,必须面临输入符为’#‘号才行。因此对初始项目S′→·S,# 求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。具体构造步骤如下:
(1) 构造LR(1)项目集的闭包函数。
a) I 的任何项目都属于CLOSURE(I) b) 若有项目[A→α·Bβ,a ]属于CLOSURE(I),B→γ是文法中的产生式,β∈V*,b∈FIRST(βa), 则[B→·γ,b]也属于CLOSURE(I)中。 c) 重复b)直到CLOSURE(I)不再增大为止。
(2) 转换函数的构造
LR(1)转换函数的构造与LR(0)的相似,GO(I,X)=CLOSURE(J) 其中I是LR(1)的项目集,X是文法符号: J={任何形如[A→αX·β,a]的项目 | [A→α·Xβ,a]∈I}
例如下列文法G′为:
(0) S′→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 构造他的LR(1)项目集规范簇。
以I0=CLOSURE(S′→·S,#)开始。运算。若有项目[A→α·Bβ,a ]属于CLOSURE(I),B→γ是文法中的产生式,β∈V*,b∈FIRST(βa), 则[B→·γ,b]也属于CLOSURE(I)中。此时,我们可以把S看成B,#看成a,然后需要求FIRST集合,此时没有β,a为#,所以FIRST(#)中只有一个b=#,而S有四个产生式。所有四个产生式加上#都是在I0中,最终求得的I0项目集为
{ S′→·S,# S→·aAd,# S→·bAc,# S→·aec,# S→·bed,# }
然后使用GO函数来构造I1,从J={任何形如[A→αX·β,a]的项目 | [A→α·Xβ,a]∈I}我们可以知道I1的核(最初的产生式)就是这里的J,然后呢。X是I(也就是我们的I0)中的·后面的符号,也就是输入符。。可以看到在I0中,X可以为S,a,b,我们先以I1=GO(I0,S)=CLOSURE( S′→S·,# ),注意,·号已经前进了。因为J是I输入进一的项目,求I1,发现·后面没符号了,所以闭包就是他自己了。最终求得的I1的项目集为:
{S′→S·,# }
我们上一步是用的I1=GO(I0,S)来求得,我们求I2的时候使用GO(I0,a)来求,此时X就是a了。然后我们吧I0中符合的项目中的·后移一位得到J然后对J求闭包,就是I2了。此处J=S→a·Ad,# 和S→a·ec,#
I2=GO(I0,a)=CLOSURE(S→a·Ad,# S→a·ec,#),然后又回到了求闭包了。
对于S→a·ec,#,因为输入符下一位是一个终结符,也就是说没有B→γ这样的产生式,所以这个就不用继续向下求闭包了,闭包就是他自己嘛。然后关键是S→a·Ad,# 此处的A相当于规则中的B,d相当于规则中的β,A→e存在。为了确定这个心的向前搜索符,我们根据规则需要求b∈FIRST(βa),这里也就是求First(d#),显然结果为b=d,规则中指出[B→·γ,b]也属于CLOSURE(I),所以可以确定A→·e,d也在I2中。。
最终I2的项目集为
{ S→a·Ad,# S→a·ec,# A→·e,d }
到这里,关键点就说完了。只需要继续求GO(I0,b),然后求GO(I1,X),GO(I2,X)等等。X的确定前面已经说了,就是I1,I2的·后面的符号。就行了。。当然像此处的I1,·后面已经没付好了,所以GO(I1,X)就不用求了。。
这种东西还是要自己手动练习的。所以我给出最终的全部项目集规范簇,大家按照这个步骤来做一做。看看结果对不对吧。 I0: S′→·S,# S→·aAd,# S→·bAc,# S→·aec,# S→·bed,# I1: S′→S·,# I2: S→a·Ad,# S→a·ec,# A→·e,d I3: S→b·Ac,# S→b·ed,# A→·e,c I4: S→aA·d,# I5: S→ae·c,# A→e·,d I6: S→bA·c,# I7: S→be·d,# A→e·,c I8: S→aAd·,# I9: S→aec·,# I10:S→bAc·,# I11:S→bed·,#
构造的过程很繁琐。有点暴力计算的意思。不过,真正算起来步骤还是比较少的。