LR(1)分析法的提出

SLR分析存在的问题

SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)只是归约α的一个必要条件,而非充分条件

对于产生式 A→α的归约,在不同的使用位置, A会要求不同的后继符号

0) S′→S
1) S→L=R
2) S→R
3) L→*R
4) L→id
5) R→L

X FOLLOW( X )
S $
L =, $
R =, $

在特定位置,A的后继符集合是FOLLOW(A)的子集

规范LR(1)项目

将一般形式为 [A→α·β, a]的项称为 LR(1) 项,其中A→αβ 是一个产生式,a 是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符(lookahead)

  • LR(1) 中的1指的是项的第二个分量的长度
  • 在形如[A→α·β, a]且β ≠ ε的项中,展望符a没有任何作用
  • 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可
    以按照A→α 进行归约,这样的a的集合总是FOLLOW(A)的子集,而且它通常是一个真子集

等价LR(1)项目

当β => + ε时,此时b=a叫继承的后继符,否则叫自生的后继符

例:LR(1)自动机

0) S′ →S
1) S→L=R
2) S→R
3) L→*R
4) L→id
5) R→L

LR(1)分析表

FOLLOW(R) = { =,$ }

FOLLOW(L) = { =,$ }

如果除展望符外,两个LR(1)项目集是相同的,则称这两个LR(1)项目集是同心的。

LR(1)项目集闭包

CLOSURE( I ) = I ∪{ [B→·γ, b] | [A→α·Bβ, a] ∈ CLOSURE( I ), B→γ∈P, b∈FIRST(βa)}

SetOfltems CLOSURE ( I ) {
    repeat
    for ( I中的每个项[A → α·Bβ,a ]) 
        for (G'的每个产生式B → γ) 
            for ( FIRST (βa)中的每个符号b ) 
                将[ B → · γ ,b]加入到集合I中;
    until 不能向I中加入更多的项;
    until I ; 
}

GOTO 函数

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

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

为文法G' 构造LR(1)项集族

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(1)自动机的形式化定义

文法

G = (VN , VT , P, S )

LR(1)自动机

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分析表构造算法

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

  • 根据Ii构造得到状态i。状态i 的语法分析动作按照下面的方法决定:

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

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

    • if [A→α·, a ] ∈Ii且A ≠ S' then ACTION[ i, a ]=rj(j是产生式A→α的编号)

    • if [S'→S·, $ ] ∈Ii

    then ACTION [i, $ ]=acc;

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

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

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

留言

撰写回覆或留言