U4_3 语法分析-自底向上分析-LR0/LR1/SLR分析

一、LR分析法

1、概念

是一种自底向上的分析方法（1965年 D.Knuth 提出）。
L：从左向右分析 (left to right)
R：产生“最右推导”(right-most derivation)
k=0：不向前查看符号 ????k=1：向前查看1个符号
从左到右扫描(L)自底向上进行归约(Right-most Derivation)(一定是规范归约）, 是自底向上分析方法的高度概括和集中
历史 + 展望 + 现状 => 句柄

2、流程

根据文法不断进行移进或者规约

规约后回退状态，且得到的终结符也需要回退

3、LR分析器结构及分析表构造

1）结构

状态栈、分析表、控制程序

栈顶状态概括了从分析开始到该状态的全部分析历史和展望信息

2）一些概念

符号串 $X_1{X}_2.....X_m$：从开始状态($S_0$)到当前状态($S_m$)所识别的规范句型的活前缀。

规范句型前缀: 将输入串的剩余部分与其连接起来就构成了规范句型。
如： $x_1{x}_2.....x_m{a}_i...a_n$为规范句型（$x_i$已处理，$a_i$未处理）

对于句型$\alpha \beta t$，$\beta$表示句柄, 如果$\alpha \beta =u_1{u}_2\dots u_r$那么符号串$u_1{u}_2\dots u_i(1\le i\le r)$即是句型$\alpha \beta t$的活前缀。

活前缀: 若分析过程能够保证栈中符号串均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀。

二、LR(0)分析法

1、流程

根据状态转移图得出状态转移表

状态栈：#$S_0{x}_1{S}_1{x}_2......x_{i?1}{S}_{i?1}{x}_i{S}_i$
$S_{i?1}$—当前状态(栈顶状态)
$x_i$— 新的栈顶符号
$S_i$----新的栈顶状态(状态转移)

2、分析动作

1）移近

$ACTION[S_i,a]=s$ （s表示 $shift$，移进）
动作: 将$a$推进栈，并设置新的栈顶状态$S_j$
$S_j=GOTO[S_i,a]$，将指针指向下一个输入符号

2）归约(reduce)

$ACTION[S_i,a]=r_d$ （r表示 reduce，按规则d规约）
条件：某个项目集形如$A\to \beta$.
动作: 将符号串β(假定长度为$n$)连同状态从栈内
弹出, 把$A$推进栈, 并设置新的栈顶状态$S_j$
$S_j=GOTO[S_{i?n},A]$

3、总结

1）LR分析器

构造LR分析器的关键是构造其分析表
构造LR分析表的方法是:

1. 根据文法构造识别规范句型活前缀的有穷自动机DFA
2. 由DFA构造分析表

2）构造DFA

构造DFA：
4. 确定$S$集合，即$LR(0)$项目集规范族，同时确定$S_0$
5. 确定状态转移函数GOTO

LR(0) 是DFA的状态集,其中每个状态又都是项目的集合

项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目

3）构造LR(0)的方法(三步)

1. 将文法拓广
   目的：使构造出来的分析表只有一个接受状态,这是为了实现的方便。
   
2. 根据文法列出所有的项目
3. 将有关项目组合成集合，即DFA中的状态；
   所有状态再组合成一个集合，即LR（0）项目集规范族

举例分析：

3 将有关项目组成项目集,所有项目集构成的集合即为LR(0)
为实现这一步，先定义：
? 项目集闭包closure
? 状态转移函数GOTO

4、局限性

会存在两种冲突，导致LR(0)识别不出来

1. Shift-Reduce冲突
   
2. Reduce-Reduce冲突
   
   因此需要采用偷看解决问题，$LR（0）\to LR（1）$

三、LR(1)分析法

通过“偷看”一个右侧符号，在遇到冲突时辅助决定。
思路：将状态区分的更加细致，构造LR(1)的状态机。

优点就是可以将状态区分的更加细致，构造LR(1)的状态机。
优势：功能强大！任何LR(0)、LL(1)、确定型CFL、LL(k)、LR(k)都有LR(1)的等价文法。

主要问题：状态爆炸，实用性差。

四、SLR（1）：简单LR分析法

1、基本思想

由DFA构造出的SLR分析表,在造表时, 只需向前看一个符号就能确定分析的动作是移进还是归约，所以称为SLR(1)分析表，简称SLR分析表，使用SLR分析表的分析器叫SLR分析器，兼有LR(0)和LR(1)的优点，放弃一些精度。

在LR(0)的基础上，只针对冲突进行处理。

当发生 S-R冲突时，根据FOLLOW集合确定S还是R

2、分析思路

1）构建表

先构造LR(0)的自动机，GOTO表。

2）SLR求ACTION表

1. 求出文法每个非终结符的FOLLOW集合
2. 若项目$A\to \alpha .a\beta \in k$,且$a\in V_t$ ,则置$ACTION[k,a]=s$ (移进）
3. 若项目$A\to \alpha .\in k$, 那么对输入符号$a$,若$a\in FOLLOW(A)$,则置$ACTION[k,a]=r_j$，其中$A\to \alpha$为文法$G’$的第j个产生式。
4. 若项目$E’\to E.\in k$, 则置$ACTION$[ $k,$#] $=accept$
5. 空白格，均置error
   
   看到$follow$应该做规约（已经跳出表达式了）

3、局限性

$FOLLOW(R)$中有=，应该做规约，但是碰到=，E中表达式应该移进，因此还是冲突。

对文法G,若应用上述算法所造出的分析表具有多重定义入口,分析动作不唯一, 则文法G就不是SLR的，需要用别的方法来构造分析表。如下图

五、彩蛋

$LL(k)$是无二义性的，$LL(k)$文法识别的语言都是确定型下推自动机所识别的语言，但反之，不能保证任何一个确定型下推自动机$DPDA$与$LL(k)$等价

LL(k)文法总是一个LR(k)文法 ，$LL(k)$是 $LR(k)$的子集

定义上看，LR(0), LR(1), LR(k), SLR(1), LALR(1)等，要求构造出来的分析表是“确定性”的，也就是分析表不允许存在冲突，无二义性！