编译原理之LR(1)分析

发表于 分类于

简单讲讲LR(1)分析法。如果有不对的地方，还请指出！

LR(1)分析法是一种自下而上的文法分析法，L表示从左到右扫描输入串，R表示构造一个最右推到的逆过程，(1)则表示每次“展望”一个字符，即多向前检查一个字符。
LR(1)可以确定多数程序语言的“移进”或“归约”。

LR分析法的适用范围更广，包括了能用LL(1)分析的所有文法。
它用一个状态联系了历史、现在与未来。在栈顶的状态概括了整个栈的内容。
本文主要阐述LR(1)分析法，作为基础的LR(0)和SLR(1)不详细展开。

几个概念

  1. 分析表
  2. 动作(ACTION)表和状态转换(GOTO)表
  3. 有效项目
  4. LR(1)项目[A→α·β,a]

分析表

分析表是LR分析器的核心。LR分析器通过对照这张表分析栈顶状态和输入字符串的字符应采取的下一步动作。如图：

LRTable

ACTION表和GOTO表

分析表包括两部分：ACTION和GOTO。前者规定状态面对某一终结符采取的动作，后者规定状态面对某一非终结符时的下一状态是什么。
ACTION动作表包括了四个动作：移进、归约、接受、出错

有效项目

项目A→α·β对活前缀γα是有效的，是指存在规范推导：
S’ => γAω => γαβω
要注意的是第一规范推导，第二活前缀。

举个栗子~
存在文法G(S’)：

(1) S’→E
(2) E→aB|bB
(3) A→cA|d
(4) B→cB|d

对E→c·B有:S’=>E=>bB=>bcB
则E→c·B对活前缀bc是有效的
对B→·cB有:S’=>E=>bB=>bcB=>bccB
则B→·cB对活前缀bc是有效的
对谁有效看项目·前的非终结符与用项目推导前的字符串结合的那个字符串。

LR(1)项目[A→α·β,a]

A→α·β是一个LR(0)项目，而a则为向前搜索串，在LR(1)分析中长度为1。
PS：向前搜索符只对归约项目有意义，而对其他项目来说是用于产生下一个项目的向前搜索符。

构造分析表

第一步构造项目集族，第二步通过项目集族构造分析表。
有以下文法：

(0)S’->S
(1)S->BB
(2)B->aB
(3)B->b

构造项目集族：从第一个式子(即拓广文法中的S’->S)开始构造
共用到两个函数：CLOSURE(I)和GO(I,X)

前者由项目集中每一个项目生成一个完整项目集。[A->α·Bβ,a]其中B->ξ是一个产生式，对于FIRST(β)中的每一个终结符b，如果[B->·ξ,b]原来不在项目集中，则把它加进去。

eg. I0有[S’->·S,#],而产生式1有S->BB，因此[S->·BB,a/b]∈I0.
以此类推。

后者由一个项目集生成另一个项目集。GO(I,X)=CLOSURE(J),
J={任何形如[A->αX·β,a]的项目|[A->α·Xβ,a]∈I}
意思就是，I中项目遇到符号X，移进产生新项目，该项目属于J

eg. 即[S’->·S,#]∈I0，遇到S移进，得到[S’->S·,#]∈I1

关于向前搜索符，CLOSURE函数得到的与FIRST集，GO函数得到的与前一个项目的向前搜索符有关。
构造分析表：
1.ACTION：项目[A->α·aβ,b]属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为sj，即“把状态j和符号a移进栈”
通俗而言，Ik中项目遇到终结符a，转到Ij，则ACTION[k,a]为sj
2.归约：项目[A->α·,a]属于Ij，则置ACTION[k,a]为rj，即“用产生式A->α归约”（A->α为第j个产生式）
3.GOTO：若GO(Ik,A)=Ij，则置GOTO[k,A]=j
4.接受：若项目[S’->S,#]属于Ik，则置ACTION[k,#]为acc，即“接受”

代码思想##

分析表state，非终结符vn，终结符vt，项目集族I，FIRST集first，产生式集grammar等均为全局变量
项目集族，分析表，产生式集用二维字符串数组表示，非终结符和终结符用以为字符数组表示，FIRST集用二维字符数组表示
其他设置一些辅助变量

核心组成为CLOSURE(I),GO(I,X),总控程序，confirst()
**CLOSURE(k):**传入参数i为项目集编号，从第一个项目开始循环遍历，若·后为非终结符，生成有效项目，如果项目集Ik中不存在该产生式的有效项目，则添加其至Ik；否则，继续操作下一个项目
**GO(k,X):**传入参数k为项目集编号，X为字符；从Ik的第一个项目开始遍历。若·后为X，移进生成有效项目，若其不存在在项目集族I中，则作为新项目集的第一个有效项目；否则，进入下一个循环
在GO函数中生成分析表：若X为终结符，由Ik找到Ij，则置state[k,X]=”sj”
若X为非终结符，由Ik找到Ij，则置state[k,X]=”j”
若Ik中只有一个项目，即是归约项，向前搜索符为b，置state[k,b]=”rj”(j为该项目对应的第j个产生式)
总控程序：设置字符栈，状态栈，获得输入字符串。依次对字符串每一个字符操作，输入串字符X和状态栈顶状态k，在分析表中得到下一步操作。“sj”表示推入状态j，推入字符X；“rj”表示将字符栈顶字符按产生式j：A->αβ归约，状态栈推出αβ数量，再推入state[k,A]所对应的状态；
confirst：见LL(1)分析法

后记##

代码存在的一些问题

  1. GO函数生成新项目集时，判断是否已存在的地方有问题。怎么样才能又快又准确地判断？
    项目不存在于现有的项目集族中，才添加
    我的想法是每次只扫描项目集的第一个项目，若相等则已存在。因为除I0外，第一个一定是由别的项目集生成的，而且向前搜索字符顺序固定，所以只要考虑第一个就可以了。
    这样就存在一个问题：I0含S->·A,a/b，而I1只含S->·A,a，GO(I0,A)和GO(I1,A)第一个都是S->A·,a用上述方法判断为两者相等，而其实是不一样的。
    当文法为二义性文法时会出现此类情况，这就是问题2了。
  2. 二义性问题

碎碎念####

LR(1)分析一开始想自己用有效项目的推导写，结果绕来绕去，写了两天都没写出来。
CLOUSRE和GO函数的想法很好，半天就能写出来。前者求出一个完整项目集，后者生成下一个项目集，分两步求。希望可以举一反三，应用此类思想。
编译原理对我来说有难度，学得不好。写这篇博文也是为了能把知识点串起来，可是掌握得不好，写得不太清晰。

参考资料####

编译原理（第3版） 陈火旺等人编
编译原理老师PPT