3.6.3 Simple LR在线视频

各位同学大家好

这节课

我们来学习语法分析中

自下而上的分析方法中

SLR分析表的构造

为了来构造SLR分析表

我们需要来构造识别活前缀的DFA

为了构造识别活前缀的DFA

我们需要来学习

如何来计算LR0项目集

然后我们才能够造出识别活前缀的DFA

我们先来看一下LR分析表

它的主要作用

LR分析表是用来进行LR分析的

也就是LR分析的核心动作

它主要有两点

我们根据LR0项目

来构造识别活前缀的DFA

然后我们根据DFA来构造

对应的分析表

我们首先回顾一下活前缀是指

我们在分析栈里边出现的那些串

活前缀可以使用一个DFA来进行识别

比如说

我们给出大家一个如下的文法

S可以产生V=E

S可以产生E

V可以产生星号E

V可以产生id

E可以产生V

那么怎么把这个文法

对应的识别活前缀的DFA画出来呢？

这其实是一件很难的事情

想要直接来画是不可能的

我们需要去构造LR0项目集

然后才能来根据LR0项目集

构造识别活前缀的DFA

我们首先来看一下LR0项目集

LR0项目集是指一些由LR0项目组成的集合

那么什么是LR0项目呢？

LR0项目是指在产生式的右部某个合适的位置加点之后的产生式

我们可以通过一个例子来学习一下

假设有一个产生式A产生XYZ

我们可以在它的右部合适的位置加入点

比如说把它写为A产生点XYZ

A产生X点YZ

A产生XY点Z

A产生XYZ点

点的意思表示的是希望

在点的左边是指我们已经看到的部分

在点的右边表示我们希望看到的部分

比如说对于第1个项目，A产生点XYZ

此时我们什么都没有看到

我们接下来希望看到的是XYZ

对于第2个项目，A产生X点YZ

我们当前已经看到了X

接下来我们期望看到的是Y和Z

对于第3个项目，A产生XY点Z

我们当前已经看到了XY

接下来我们希望看到Z

对于最后一个项目A产生XYZ点

我们当前已经看到了XYZ

我们接下来不需要再看到其它的符号

我们其实可以想到

针对最后一个情况

A产生XYZ点

如果点已经出现在整个产生式的末尾

我们需要进行的是归约的动作

在这里加点的时候

有一个特殊的例子

对于A→ ε 这种情况下

我们加点之后

得到的LR0项目就是A→点

接下来我们从一个例子

来看一下如何来加点

假设有一个文法

E产生E+T或者T

T产生T×F或者F

F产生(E)或者id

那么我们观察到

这个文法当中它的开始符号是E

而E又出现在产生式的右部

所以为了加以区别

我们在整个文法的最前方

加入了一条文法

我们将它称之为拓广文法

也就是红色的这条，E'产生E

我们使用E'作为整个文法的开始符号

然后我们在进行移进归约的时候

如果归约得到了E'

我们认为整个的移进归约分析程序已经结束

那么针对id+id这个串

我们得到的最右推导动作在这里边

我们看到

对于E'→E串来说

它是宣告着整个移进归约分析动作的结束

我们来通过文法

构造LR0项目级的规范族

我们从I0这个状态出发

I0表示的是一个状态

首先我们从拓广文法这一条开始

我们将E'产生点E加入到I0当中

那么I0作为一个集合

我们需要去计算它的闭包

因为我们是来构造识别活前缀的DFA

DFA需要将所有当前状态的等价状态加进去

那么在这一步

我们实际上计算的是闭包函数

我们先来看一下

对一个闭包函数的含义

I中的每个项目加入到当前的闭包函数中

对于A产生α点Bβ

对于这个产生式来说

我们需要将B产生γ 这个产生式加入到当前的集合中

也就是B产生点γ

作为一个新出现的项目

需要加入到当前的闭包函数中

也就是这个项目

是当前项目的一个等价的状态

所以需要加入到 I0 当中去

我们观察一下

E'产生点E

点在E之前

E作为一个非终结符

它有对应的产生式

所以我们需要将 E产生点E+T、E产生点T 加入到I0当中

然后接下来我们又观察到点出现在了T之前

我们需要将T所有对应的产生式

加入到当前的状态I0当中

T产生点 T×F

T产生点F

接下来，点出现在F之前

所以我们需要将F对应的产式式加入其中

加了点之后

对应的F产生式变成了F对应的项目

F可以产生点 ( E )

F可以产生id

接下来我们继续看一下

I0是不是可以继续往其中加入更多的元素

也就是I0是不是可以继续来进行膨胀

如果I0不能继续膨胀

那么当前I0的计算就完成了

接下来我们看一下

对于I0当中，E'产生点E

这个项目是我们直接加入其中的

而剩下的6个项目

是由于点出现在产生式右部第1个非终结符号之前而加入的

也就是我们经过闭包函数计算所加入的项目

我们将这些项目称之为非核心项目

如果在计算的过程中

我们知道非核心项目是可以通过求闭包而得到

如果为了压缩空间

实际上非核心项目是可以不写的

在有了I0之后

接下来我们需要通过I0

来计算识别活前缀的DFA

也就是通过I0

我们可能碰到哪些符号

我们观察一下I0

那么在I0这个项目集中

点在E之前、T之前、F之前、左括号之前和id之前

也就是， I0应该碰到的是这些符号

是一个正确的状态转移

那么首先I0可能会碰到E

如果I0碰到E的话

我们用goto这个函数来表示这种情况

也就是goto(I0, E) 进入到 I1这个状态

goto函数的具体含义是这样的

假设我们有一个项目

A产生α点Xβ

真的碰到X之后，我们进入到一个新的状态

其中包含项目

A产生αX点β

这个项目对应的集合的闭包

也就是强调每一次

我们计算完一个集合之后

要计算当前集合对应的闭包函数

保证当前这个集合

不再膨胀了为止

那么针对 I1 来说，它从 I0 这个状态真的看到E点

从 I0 状态当中，所有E之前移动到E之后

就变为E'产生E点，E产生E点加T

接下来我们需要计算闭包函数

如果点没有出现在非终结符之前

那么当前 I1 不需要继续膨胀

也就是I1的计算完成了

接下来我们计算I2

I2是从I0出发

真的碰到了T所到达的状态

E产生T点

T产生T.×F

同样的不需要进行闭包函数的计算

然后我们来计算I3

I3是从I0出发碰到F所到达的状态

只有一条，T产生F点

接下来继续

我们要来计算I4

那么I4是从I0这个状态出发

碰到左括号所到达的状态

我们观察到 F产生左括号 点E右括号

接下来我们仍然需要去计算闭包函数

因为点出现在了非终结符E之前

所以E产生点E+T 需要加入到其中

E产生点T 需要加入到其中

而E产生点T 加入到其中之后

引起更多的闭包函数的计算

也就是T产生点T×F

T产生点F

然后点出现在了F之前

那么F对应的产生式需要继续加点之后

变为对应的项目

加入到其中

F产生点左括号E右括号

F产生点id

接下来I0还有最后的一个状态变化

也就是在它碰到id之后进入到I5这个状态

F产生id点

那么对于这个项目来说

不需要进行闭包的计算

接下来我们观察到I1这个状态

如果再碰到加号之后，进入到I6这个状态

那么I2这个状态

在碰到乘号之后，可能进入到I7这个状态

接下来I3这个状态对应的项目集

T产生F点

点出现在整个产生式的末尾

所以I3没有对应的状态转换

我们再来看I4

那么在I4碰到E之后，进入到I8这个状态

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

碰到F之后，进入到I3这个状态

碰到左括号之后，进入到I4这个状态

当然回到I4这个状态

我们只写了 I4 当中的核心项目

碰到id之后，回到I5这个状态

我们把之前碰到的这些状态转换

画为对应的图

这个图就是识别活前缀的DFA

我们继续把I6、I7、I8等等

对应的状态都画出来

我们看到这是一个完整的当前文法

识别活前缀的DFA所画出来的图

我们根据这张图来构造SLR分析表

我们看一下

如何根据识别活前缀的DFA来构造SLR分析表

SLR分析表的一般过程是如下三步

首先我们观察一个文法

是不是需要进行拓广

如果需要进行拓广的话，

我们需要添加一个新的产生式 S'产生S

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

接下来根据识别活前缀的DFA来构造SLR分析表

那么在构造分析表的时候

我们分为几个大的步骤

首先我们来判断action，也就是动作表的填写

如果A产生α点aβ出现在一个状态Ii当中

并且Ii在碰到a之后

进入到 Ij 这个状态

那么在动作表中

这个状态 i 所在的行a所在的列

我们就把它填为移进这个动作

移进之后，进入到第 j 个状态

如果A产生α点 出现在 Ii 这个状态中

那么点已经出现在整个产生式的末尾

我们需要进行归约

那么参照哪些符号进行归约呢？

我们按照follow(A)中所有的元素a

我们将 i 所在的行a所在的列

写上归约这个状态

并且参照第 j 个产生式进行归约

第 j 个产生式对应的就是A产生α 这个产生式对应的编号

第3种情况

S'产生S点

如果在 Ii 这个状态中

我们知道这一条是拓广文法所在的状态

我们就将 i 所在的行$ 所在的列写为接受

在填完 action 动作表之后

如果发生了冲突

就说明当前这个文法不是SLR文法

然后接下来我们看一下goto函数

也就是转移表的构造

对于所有的非终结符A来说

如果在 Ij 这个状态

碰见A之后

进入到 Ij 这个状态

那么我们就在 i 所在的行、A 所在的列

我们填上进入到第 j 个状态

就是写上 j

我们如果在填完 action 表和goto表之后

发现有一些地方没有填写

没有填写的地方

都是置为出错的状态

分析器的初始状态是S'产生S对应的项目集所对应的状态

接下来我们来看一个例子

对于这个文法来说

它的状态I2当中包含的项目集

有E产生T点、 T产生T.×F

我们需要针对这两个项目集

来进行填写动作表和转移表

第1个项目E产生T点

点出现在整个产生式的末尾

需要进行归约

我们需要将follow(E) 取出来

假设follow(E)在求出来之后，是{ $, +, ) }

所以2所在的行

就是2这个状态所在的行

$所在的列、+加号所在的列以及 )括号所在的列

我们需要填写上进行归约

假设是参照2号产生式

E产生T来进行归约

然后第2个项目T产生T点×F

需要进行移进

碰到星号的时候移进

所以在2这个状态所在的行、星号所在的列

我们写上移进之后

进入到第7个状态，写为S7

这一小节就到这

谢谢大家