3.5.4 规范的LR分析方法在线视频

各位同学大家好

这节课我们来学习

语法分析中的LR分析方法

我们之前已经学过SLA文法

我们为什么要来学习LR(I)分析方法

是因为SLR文法

它的描述能力是有限的

我们来看一个例子

通过这个例子

我们可以了解到

每一个SLR(1)文法都不是二义的

但是有许多非二义的文法不是SLR文法

这是由于本身 SLR文法

它的描述能力有限

比如说给定一个文法

S可以产生V=E

S可以产生E

V可以产生乘号E

V可以产生id

E可以产生V

我们首先对这个文法进行拓广

也就是 S'产生S 加入到其中

然后我们来构造识别活前缀的DFA

我们首先来计算I0

I0当中包括S'产生点S

S可以产生点V=E

S可以产生点E

V可以产生点乘号E

V可以产生点id

E可以产生点V

在计算完成I0之后

我们要计算I1、I2、I3等等

也就是I0经过那些符号所到达的状态

假设I1是经过I0碰到S之后所到达的状态：S'可以产生S点

然后我们来计算I2

I2 是 I0 在碰到V之后所到达的状态

S可以产生V点等号E

E可以产生V点

我们观察一下I2这个状态

在 I2 中根据第1个项目

S可以产生V点等号E

我们知道点出现在整个产生式的中间

也就是一个项目的中间

那么这个点的出现

导致我们碰到等号的时候

需要进行移进的动作

也就是状态2所在的行、等号所在的列

我们需要填写移进

假设移进之后

进入到第6个状态

而我们在碰到 I2 当中

第2个项目 E产生V点

我们需要进行归约

而归约的时候

我们需要按照 E 的follow集来进行归约

按照这个文法

我们在求 E 的follow集的时候

我们观察到 E 的follow集是包含等号的

也就是说

我们需要按照2这个状态、等号所在的列来进行归约

大家会发现这两个项目

导致它们在填写表的时候

出现了冲突

但是这个文法中

实际上并不存在着

E等号开头的右句型

也就是在这一步中移进是正确的

归约实际上是不对的

那么为什么会出现这种状态呢？

首先，我们知道这个文法

它本身不是SLR(1)文法

所以出现了这个情况

其次，我们在填写归约的时候

由于计算了follow集

按照(E)的follow集来进行归约

实际上这个范围过大

我们应该按照的是

右句型可能出现的那些符号来进行归约

而不是按照follow集来进行归约

所以接下来

我们来学习第二种分析方法

规范的LR分析方法

也就是LR(1)分析

我们来看一下

LR分析表和之前的变化

主要是项目集的定义发生了变化

我们添加了前向搜索符

用这个前向搜索符

保证我们每次看到的符号

都是从开始符号所能推导出来的符号

我们先来读一下它的定义

假设有一个项目

A可以产生α点β

如果我们最终用这个产生式进行归约之后

我们期望看到的符号是a

那么我们这个加点项对应的前向搜索符就是a

也就是在这种情况下

我们将前向搜索符

加入到当前的项目当中

写为A产生α点β逗号a

a是紧跟在β之后的一个符号

而且a是我们从产生式的开始符号进行推导

应该跟在β之后的那些符号

我们增加了一个前向搜索符

目的是为了增强它的描述能力

也就是保证我们每一次进行归约的时候

按照前向搜索符来进行归约

保证它的范围是合适的

接下来我们学习下LR(1)项目

也就是在LR(0)项目的基础上

我们让它带上搜索符务

将项目定义为A产生α点β，A 这样的形式

对于一个项目A产生α点β逗号a

对一个活前缀γ是有效的

含义是什么呢

我们来把它写为数学的公式

假设存在着一个推导 S可以产生δAω

假设下一步

我们需要推导的是A

把它写为δαβω

那么也就意味着

A可以推导为αβ

其中α和β是当前的句柄

我们假设γ等于δα

那么a是ω的第1个符号

或者ω一个是空串，并且a就是$这个符号

这个意思也就是说

β的后边紧跟着的是a

如果ω是空串的话

那么β的后边跟着的应该是$这个符号

接下来我们学习一下有效的概念

那么假设

我们从最右推导来进行推导

S按照上面的文法S产生BB

B产生bB或者a

我们进行最右推导

S可以推导出来一个串bbBba

接下来我们需要推导的是B

我们将它推为bbbBba

也就是B推导为bB

那么对于B产生b点B逗号b

对这个LR(1)项目来说

它对于一个活前缀bbb是有效的

它的意思是说

LR(1)项目当中

A产生α点β逗号a 对活前缀γ是有效的

所以当前

我们对于活前缀γbbb是有效的

我们接下来再看一下

有效项目的定义

如果B产生b点B逗号b 对于γ是有效的

我们可以根据这一条来进行如下的判定

也就是对一个更为一般的项目

A产生α点β逗号a来说

如果β不为空

β不为空的话

我们想 β 的后边应该跟着的是a

那么我们应该采取移进的动作

还有一种情况是β可能为空

如果β为空

整个项目就变成了A产生α点逗号a

而这个α的后边应该跟着的是a

那么我们需要进行归约

此时需要按照a来进行归约

这个和LR(0)项目是不一样的

不再参照follow(A)来进行归约

而是将这个范围缩小

它应该是之前follow(A)的子集或者真子集

我们观察到

在添加了前向搜索符之后

可以让LR(1)分析方法

在进行归约的时候

缩小了之前的分析范围

那么怎么样来填加紧向搜索符呢？

我们仍然从拓广文法这一条开始

假设初始项目集S'产生点S

我们把它的前向搜索符写为$

也就是把它写为S'产生点S逗号$

那么我们通过这一条来保证S'或者S的后边

紧跟着的符号应该是$

然后在这个基础上

来计算其它项目集的前向搜索符

在计算闭包函数的时候

我们采用如下的两条规则

首先 I 中的任何项目

都属于当前的闭包集合

其次，假设有一个项目

A可以产生α点Bβ逗号a

如果在当前的闭包集合当中

那么B产生γ是文法对应的一个产生式

我们观察到这个项目当中

点出现B之前

所以B产生点γ应该加入到其中

而B的后边跟着的应该是β

如果β为空，应该跟着的是a

所以我们把上述情况统一

B的后边应该跟着的是b

这个b是first(βA)中的元素

我们通过这个来保证

在B产生γ进行归约之后

出现的输入字符b是句柄αBβ当中B的后继的符号

或者是αBβ归约为A之后，可能出现的终结符

接下来我们用加了前向搜索符之后的方法

来判断一下

这个文法是不是能解决之前出现的冲突问题

我们从I0开始进行计算

I0当中第1条是拓广文法

S'产生点S后边跟的前向搜索符是$

我们也就是用S'产生S进行归约之后

希望看到的符号是$

接下来

我们来计算闭包的集合

我们需要把它来跟定义当中加以一一的进行对比

定义当中 A产生α点Bβ逗号a

我们在这里缺失的符号

我们用空串来表示

S'产生空串点S空串逗号$

看一下每一个符号

在闭包集合中的对应关系

也就是接下来

我们需要求first(βA)

那么由于 S后边跟着是空串

也就是first(βA)当前等于$

所以我们接下来计算

S可以产生点V等号E逗号，后边跟着前向搜索符是$

以及S产生点E

后边跟着前向搜索符是$

加入这一条之后

我们观察到

S对应的LR(1)项目集中前向搜索符

是根据它的前一条得到的

而S无论扩展为什么样

它的前向搜索符都是$

下一步我们要加入的是

和V相关的那些项目

那么V可以产生点等号E

后边跟前向搜索符

是来自于S产生点V等号E逗号$

在第2个项目当中

S可以产生点V等号E逗号$

V的后边跟着的是等号

所以在第4个项目中

V可以产生点乘号E逗号

前向搜索符写的是等号

我们加入的理由

是根据第2个项目 S产生V等号E

它是句柄这一部分

我们期望V的后边跟着的符号是等号

下一步我们需要加入的是

E对应的那些项目

因为点出现在了第3个项目E之前

那么E的后边跟着的前向搜索符

来自于S产生点E 逗号$

所以E产生点V跟的前向搜索符是 $

那么此时我们有一个问题

当前闭包的计算是不是结束了呢？

没有！

为什么没有呢？

因为E产生点V逗号$

这一个项目的出现

使得我们的闭包需要继续进行膨胀

它们是V产生点乘号E逗号$

V产生点id逗号$

我们观察到这两条和之前的差别

它们的差别是在前向搜索符上

所以我们把它统一写为

V产生点乘号E, 等号/$

V也产生点id

前向搜索符是等号和$

那么在I0的基础上

我们再继续碰到V的时候

来计算I2

我们看到I0当中

在碰到V之后，进入到I2这个状态

所以I2的计算

是从I0出发

点在V之前移动到V之后

而要保持这个项目当中

前向搜索符是不发生变化的

所以它变为S产生V点等号E逗号$

E产生V点逗号$

那么有了这两条之后

我们就在继续来填写 LR分析表的时候

我们就发现

根据第1个项目

我们在碰到等号的时候，需要进行移进

根据第2个项目

看到等号的时候，是不填归约的

而是在看到$的时候填归约

也就是解决了之前的移进归约冲突

说明当前这个文法

它不是SLR(1)文法，而是LR(1)文法

接下来我们通过另一个例子

来看一下完整的一个过程

这个例子是S可以产生BB

B可以产生bB或者a

我们来构造规范的LR分析表

第1步

我们来拓广文法，加入S'产生S

然后我们来构造I0这个状态

S'产生点S 后边跟的前向搜索符是$

然后S可以产生点BB 后边跟着搜索符是$

B可以产生点bB

后边跟的前向搜索符应该是第2个B的first集

也就是b和a

然后第4条项目B可以产生点a，前向搜索符仍然是b和a

然后I0就计算完成了

我们仍然观察到

这是经过闭包来进行计算

第1个项目是核心项目

后边3个是非核心项目

接下来我们从I0出发

可能碰到点之后的那些符号

可以碰到S、可以碰到B、可以碰到b和a

碰到S进入到I1状态

碰到B进入到I2状态

碰到b进入到I3状态

碰到a进入到I4状态

然后依次往下进行计算

假设整个的计算结果

我们已经把它画出来了

实际上我们会观察到

在LR(1)分析表中

这个状态还是非常多的

只有三个产生式，但是最终有十个状态

下一步我们来学习

基于DFA来构造我们对应的LR(1)分析表

首先仍然是action表的构造方法

我们来看一下第1种情况

A产生α点aβ逗号 B

假设在 Ii 这个状态中

碰到a之后进入到 Ij 这个状态

我们在动作表中

需要在 I 所在的行、a所在的列

移进之后进入到 j 状态

所以写为sj

第2个情况

A可以产生α点，前向搜索符是a，并且A不等于S'

在这种情况下

我们需要进行归约

参照A产生α产生式进行归约

并且我们将 i 所在的行、a所在的列

就是看到a之后进行归约

按照第 j 个产生式 A产生α进行归约

第3个情况是一个特殊情况

S'产生S点，看到的前向搜索符是$

我们就将 i 这个状态所在的行、$所在的列

写上接受这个状态

再填完上述的这些状态之后

如果出现了冲突

那么当前这个文法

就不是LR(1)文法

然后我们看一下

GoTo函数的填写

跟之前是一样的

如果在 Ii 这个状态

碰见A进入到 Ij 这个状态

那么在转移表中

Ii 所在的行、A所在的列

我们需要填入进入到第 j 个状态

同样的

如果上述原则

没能填写的状态

都是一个出错的状态

初始状态是S'产生点S，看到的符号是$

这一小节就到这

谢谢大家