有了初态的项目集,其它状态的项目集如何求出? 回顾在构造识别活前缀的NFA时,其两个相邻状态对应的项目是出自同一个产生式,只是圆点的位置相差1,箭弧上的标记为前一个状态和后一个状态对应项目圆点间的符号,(除了箭弧上标记为ε的外)。 由于识别活前缀的DFA的每个状态是一个项目集,项目集中的每个项目都不相同,每个项目圆点后的符号不一定相同,因而对每个项目圆点移动一个位置后,箭弧上的标记也不会完全相同,这样,对于不同的标记将转向不同的状态。例如初态{S′→·E,E→·aA,E→·bB}对第一个项目圆点右移一个位置后变为S′→E·箭弧标记应为E,对第二个项目E→·aA,圆点右移一个位置后,项目变为E→a·A,箭弧标记为a,同样第三个项目为圆点右移一个位置后变为E→b·B,箭弧标记为b,显然,初态可发出三个不同标记的箭弧,因而转向三个不同的状态,也就由初态派生出三个新的状态,对于每个新的状态我们又可以利用前面的方法,若圆点后为非终结符则可对其求闭包,得到该状态的项目集。圆点后面为终结符或在一个产生式的最后,则不会再增加新的项目。 例中新状态的项目E→a·A求其闭包可得到项目集为{E→a·A,A→·cA,A→·d}。同样,另一新状态的项目E→b·B,求其闭包得到项目集为{E→b·B,B→·cB,B→·d},对于新状态仅含项目为S′→E·的则不会再增加新的项目。 这样由初态出发对其项目集的每个项目的圆点向右移动一个位置用箭弧转向不同的新状态,箭弧上用移动圆点经过的符号标记。新状态的初始项目即圆点移动后的项目称为核。例中A→a·A和B→b·B都为核,对核求闭包就为新状态的项目集,为把这个过程写成一般的形式,现定义转换函数 GO(I,X)如下: GO(I,X)=CLOSURE(J) 其中:I为包含某一项目集的状态,X为一文法符号,X∈(VN∪VT),J={任何形如 A→αX·β的项目| A→α·Xβ属于I}。 这也表明,若状态I识别活前缀γ,则状态J识别活前缀γX。圆点不在产生式右部最左边的项目称为核,但开始状态拓广文法的第一个项目S′→·S除外。因此用GO(I,X)转换函数得到的J为转向后状态所含项目集的核。 核可能是一个或若干个项目组成。 这样就可以使用闭包函数(CLOSURE)和转向函数(GO(I,X))构造文法G′的LR(0)项目集规范族,步骤如下: a) 置项目S′→·S为初态集的核,然后对核求闭包,CLOSURE({S′→·S})得到初态的项目集。 b) 对初态集或其它所构造的项目集应用转换函数GO(I,X)=CLOSURE(J)求出新状态J的项目集。 c) 重复b)直到不出现新的项目为止。 需要说明的是由于任何一个高级语言相应文法的产生式是有限的,每个产生式右部的文法符号个数是有限的,因此每个产生式可列出的项目也为有限的,由有限的项目组成的子集即项目集作为DFA的状态也是有限的,所以不论用哪种方法构造识别活前缀的有限自动机必定会在有穷的步骤内结束。 |