按照这个标题搜进来的各位是不是以为这也是和课本一样的内容呢,其实这是我看了两天课本才理解出来的内容啊,绝对和课本不一样。
课本上LR(1)项目集族的构造内容如下:
以S′→·S,#属于初始项目集中,把'#'号作为向前搜索符,表示活前缀为γ(若γ是有关S产生式的某一右部)要归约成S时,必须面临输入符为'#'号才行。我们对初始项目S′→·S,# 求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。具体构造步骤如下:
(1) 构造LR(1)项目集的闭包函数。
a)假定I是一个项目集, I 的任何项目都属于CLOSURE(I)。
b) 若有项目 A→α·Bβ,a 属于CLOSURE(I),B→γ是文法中的产生式,β∈V*,b∈FIRST(βa), 则 B→·γ,b 也属于CLOSURE(I)中。
c) 重复b)直到CLOSURE(I)不再增大为止。
大家是不是看的一头雾水呢。课本上还给出了一个例子:
文法G'为:
(0)S'->S
(1)S->aAd
(2)S->bAc
(3)S->aec
(4)S->bed
(5)A->e
之后直接给出了这个文法的LR(1)项目集规范族:
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·,#
大家是不是在想I5中A->e·,d后的d、I7中A->e·,c后的c是怎么来的呢?
课本的答案是对的,但是写法很是让我们一头雾水,下面让我们来看看答案是怎么出来的:
(‘+’代表‘并’,那个符号不好打,用‘+’来代替了。)
(ε表示空,如果不是空,就结束了,但是空还要计算ε后面的Bac)
(由于B有两个推导式,所以分开来写并求并集,‘+’代表‘并’)