现给出直接由产生式构造识别活前缀的DFA LR(1)项目集的闭包CLOSURE的算法, function CLOSURE (I); /* I 是项目集*/ { J:= I; repeat for J 中的每个项目A→α·Bβ,a 和产生式 B→γ; α,β,γ ∈V*;b ∈FIRST(β a), 若B→·γ, b 不在J中 Do 将 B→·γ, b 加到J中 until 再没有项目加到J中 return J }; 对项目[A→α·Bβ,a],计算B的向前搜索符时,应为FIRST(βa),这是因为 β∈V*,即β可能为ε,而a是用产生式A→αBβ归约时的向前搜索符,而现在β为ε,就等于用A→αB归约,向前搜索符为a ,那么用A→αB归约前,必须先用产生式B→γ归约成B,因此,B的向前搜索符时也应为a。 对文法G′的LR(1)项目集族的构造仍以[S′→·S,#]为初态集的初始项目,然后对其求闭包和转换函数,直到项目集不再增大。 也就是对状态I经过符号X后转向状态J,求出J的核后,对核求闭包即为CLOSURE(J)。 |