LR(1)项目集规范簇的构造
首先我们知道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·,# 构造的过程很繁琐。有点暴力计算的意思。不过，真正算起来步骤还是比较少的。