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·,#

  构造的过程很繁琐。有点暴力计算的意思。不过,真正算起来步骤还是比较少的。

comments powered by Disqus