CLOSURE()函数

计算给定项目集I的闭包

CLOSURE(I) = I∪{B→ · γ|A→α·Bβ∈CLOSURE(I) , B→γ∈P}

SetOfltems CLOSURE ( I ) {
    J = I;
    repeat
    for ( J中的每个项A → α·Bβ ) 
        for ( G的每个产生式B → γ ) 
            if ( 项B → · γ不在J中 ) 
                将B → · γ加入J中;
    until 在某一轮中没有新的项被加入到J中;
    return J; 
}

GOTO ()函数

返回项目集I对应于文法符号X的后继项目集闭包

GOTO( I, X )=CLOSURE({A→αX·β | A→α·Xβ∈I })

SetOfltems GOTO ( I,X ) {
    将J 初始化为空集;
    for ( I 中的每个项A → α·Xβ ) 
        将项 A → αX·β 加入到集合J 中;
    return CLOSURE ( J ); 
}

构造LR(0)自动机的状态集

规范LR(0) 项集族(Canonical LR(0) Collection) C={I0}∪{I | ∃J∈C, X∈VN∪VT , I=GOTO(J , X) }

void items( G' ) {
    C={ CLOSURE ({[ S'→ ·S ] } ) };
    repeat
        for (C中的每个项集 I )
            for(每个文法符号X )
                if ( GOTO ( I,X )非空且不在C中) 
                    将GOTO ( I,X )加入C中;
    until在某一轮中没有新的项集被加入到C中;
}

LR(0)分析表构造算法

构造G'的规范LR(0)项集族C = { I0, I1, … , In}

令Ii对应状态i。状态i的语法分析动作按照下面的方法决定:

  • if A→α·aβ∈Ii and GOTO( Ii , a )=Ij then ACTION[ i, a ]=sj

  • if A→α.Bβ∈Ii and GOTO( Ii , B )=Ij then GOTO[ i, B ]=j

  • if A→α·∈Ii 且A ≠ S' then for ∀a∈VT∪{$} do ACTION[ i, a ]=rj
    (j是产生式A→α的编号)

  • if S'→S· ∈Ii then ACTION [ i, $ ]=acc

没有定义的所有条目都设置为“error”

LR(0) 自动机的形式化定义

文法

G = ( VN , VT , P , S )

LR(0)自动机

M = ( C, VN∪VT , GOTO, I0 , F )

C={I0}∪{I | ∃J∈C, X∈VN∪VT, I=GOTO(J,X ) }
I0=CLOSURE({S′ →.S })
F={ CLOSURE({S′ →S.}) }

LR(0) 分析过程中的冲突

文法
(0) E′ → E
(1) E → E+T
(2) E → T
(3) T → T*F
(4) T → F
(5) F → (E)
(6) F → id

移进/归约冲突

表达式文法的LR(0)分析表含有移进/归约冲突

例:移进/归约冲突和归约/归约冲突

文法
(0) S′→ T
(1) T → aBd
(2) T → ε
(3) B →Tb
(4) B → ε

如果LR(0)分析表中没有语法分析动作冲 突,那么给定的文法就称为LR(0)文法

不是所有CFG都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法

原文链接:

最后修改日期:2020年6月1日

留言

撰写回覆或留言