3.5.5 LALR分析方法在线视频

各位同学大家好

这节课

我们来学习

语法分析方法中

自下而上的分析方法

学习LALR分析方法

为什么要学习这种分析方法呢

我们从前面的例子

已经看到

LR分析表它的状态数目也比较多

LALR分析方法是在前两种分析方法的基础上

进行了折中

它希望分析表能够更紧凑一些

LALR分析方法是高德纳提出来的一种分析方法

我们看到 SLR分析表

它由于描述能力弱、状态数目有限

而使得可以比较紧凑的实现这种分析方法

不必消耗太多的内存

而LR(1)文法它的描述能力比较强

但是状态数目又太多

需要消耗的内存数目比较大

分析表也比较大

LALR分析方法

在上述两种分析方法中

进行了折中

它的分析表大小介于

上述两种分析方法中间

LALR分析方法的做法是这样的

首先我们来构造LR(1)分析方法

然后我们需要去合并 LR(1)分析表当中的同心项目集

什么是同心项目集呢？

同心项目集是指去掉搜索符之后

它们的项目是一样的那些集合

比如说

对于B产生点bB逗号$

B产生点bB逗号B或者A

略去搜索符之后

它们是一样的

都是B产生点bB

这样的集合

我们将它称之为同心项目集

我们可以把它们合并

合并之后

就可以写为B产生点bB，前向搜索符是$、b、A

然后我们来观察一下之前的DFA

我们看到 I4和 I7这两个状态是同心项目集

它们的心都是B产生A点

而搜索符是不一样的

除了 I4和 I7

还有没有其它的同心项目集呢？

我们看到 I3和 I6 也是同心项目集

此外 I8 和 I9 也是同心项目集

所以我们可以将上述的项目集进行合并

合并之后

我们就消除掉了三个状态

这样整个的分析表

在填写之后就变得比较简单、比较小

接下来我们来看一个例子

假设我们一个输入bbA

那么这个串我们来用

LALR 分析表来进行分析一下

我们假设站定初始状态是0

输入的末尾我们加入$

我们首先根据栈顶的符号和输入的第1个符号去查表

观察表里边写的是移进还是归约？

那么表里边假设写的是移进

我们需要去进行移进

我们将输入的b移入到栈里边

之后进入到状态36

也就是从I0这个状态碰到b之后

进入到I36这个状态

然后栈顶是36

输入是b仍然去查表

我们看36这个状态

在碰到b之后

仍然去进行移进

然后进入到36这个状态

所以现在里栈边有两个b

栈顶是36这个状态

输入只剩a

我们还根据栈顶的状态36以及输入的符号a决定下一步的动作

仍然是要进行移进

我们将a移入到栈中

之后我们进入到47这个状态

进入到47这个状态之后

我们看到的是输入的符号只剩$

我们根据47这个状态

看到输入的符号是$

需要进行归约

将a归约为B

所以47和a弹栈

把它归为B之后

进入到89这个状态

接下来我们仍然会看到

栈顶元素是89

输入是$

我们去查分析表

发现表里边写的是进行归约

所以我们将栈顶元素89、B、36和b弹栈

然后将B入栈

入栈之后状态是89

输入是$

然后我们在这种情况下

继续去进行移进归约分析

同样去查表

我们发现表里边仍然写的是归约

那么我们就继续进行归约

我们将89、B、36、b弹栈

然后B入站

之后栈顶元素是2

输入是$

那么接下来我们仍然去查表

这一步我们查表的时候

发现是出错的状态

没有办法继续向下进行

也就是

LALR分析方法

它可能多进行了几步无效的归约

接下来我们来分析一下

LALR 分析方法的特点

在合并同心项目集之后

可能出现哪些问题呢？

在合并同心项目集之后

它不会引起新的移进归约冲突

也就是说

如果原来就有移进归约冲突

那么在合并之后，仍然有移进归约冲突

如果原来没有移进归约冲突

那么在合并之后，仍然没有移进归约冲突

假设同心项目集中具备这样两个项目

A可以产生α点，搜索符是a或者b

B可以产生β点aγ，搜索符是c或d

我们可以根据这个同心项目集知道

在合并之前

一定存在着这样的项目

A产生α，前向搜索符是X

我们用X表示a或者b

B可以产生β点aγ，前向搜索符是Y

我们用Y来表示c或者d

假设X是a

我们在看到第1个项目的时候

需要进行归约

而在看到第2个项目的时候

需要进行移进

也就是说

合并之后的同心项目集中

如果存在着移进归约的冲突

它一定是由合并之前的移进归约冲突引起的

而不是由于合并引起的移进归约分析冲突

如果存在，合并之前也一定存在着这样的冲突

所以之前的LR(1)文法就存在着冲突

这是矛盾的

所以我们可以知道

同心项目级的合并

不会引起新的移进归约分析冲突

但是合并同心项目集可能引起新的归约归约冲突

我们仍然通过一个例子来看一下

假设有一个文法

S可以产生aAd或者bBd或者aBd或者bAd

A和B都可以产生c

对ac有效的项目

我们可以将它写出来

A可以产生c，搜索符是d

B可以产生c，搜索符是e

我们观察到在看到c的时候

由于前向搜索符不同

我们可以根据前向搜索符

决定将c是归约为A还是归约为B

而对bc有效的项目

A可以产生c点，前向搜索符是e

B可以产生c点，前向搜索符是d

这种情况下

我们仍然可以根据前向搜索符

决定将c归约为A还是归约为B

但是假设我们合并同心项目集

合并之后就变成了A产生c点，搜索符是de

B产生c点，搜索符是de

合并完成之后

由于前向搜索符都是一样

我们在看见c之后

没有办法根据前向搜索符

确定是将它归约为B还是归约为A

也就是说

这个文法说明了合并同心项目集

可能出现新的归约归约冲突

那么这个文法

它是 LR(1) 文法，它不是LALR(1)文法

我们再来看一下如何来构造 LALR 分析表

那么首先

我们需要构造LR(1)项目集规范族

然后我们来寻找 LR(1)项目集规范族当中的同心项目集

我们把那些同心相集来进行合并

合并完成之后

我们按照构造LR(1)分析表的方式

来构造对应的分析表

这一小节就到这

谢谢大家