构造识别活前缀的FA在线视频

大家好

在上一节对活前缀的讨论当中

我们发现由于活前缀

实际上就是满足一定要求的符号串

那么因此识别活前缀它的工作

和识别单词的工作非常的类似

所以我们可以采用有穷自动机

这种数据模型来实现活前缀的识别

也就是说我们可以把文法的终结符

和非终结符都看成

有穷自动机的输入符号

每次把一个符号进栈

看成已经识别过了这个符号

同时呢状态进行转换

当识别到了可归约前缀的时候

相当于在栈中已经形成了句柄

那么就达到了识别句柄的状态

状态之间的转变是这样的

状态i它的项目当中的圆点

是在Xi之前的

那么我们来看下状态j

它的项目当中的圆点是在Xi后面的

那么状态i和j之间

可以通过标记为Xi的弧来连接

如果状态i当中

圆点后面是一个非终结符Xi

而且Xi呢有多条产生式

状态i可以通过ε弧和圆点

出现在最左边的Xi的项目连接在一起

换言之

这些项目呢其实都是等价的

需要大家注意的一点是

文法的识别符号S

只在第一条规则的左部出现

我们可以引进一个新的非终结符

来作为识别符号

下面我们来看

构造识别活前缀的FA的方法

首先呢我们可以先构造出

不确定的有限状态自动机

写出文法当中的所有项目

每个项目呢都是一个状态

在此我们规定

项目1是NFA的唯一初态

如果状态i和状态j

出自同一个产生式

而且状态j它的圆点

只落后于状态i一个位置

如果i圆点之后的是一个终结符a

那么就可以从

i 到 j 画一条弧标记为a

如果状态i

它圆点后面是一个非终结符A

那么我们可以连接两种弧

第一种呢就是从

状态i画ε弧到所有的A→·β的状态

第二种就是从

状态i到状态j去画弧标记为A

归约的项目呢

表示的是结束状态用双圈表示

现在我们来构造识别文法G(S')

所有活前缀的NFA

首先根据文法的产生式

一共有7个LR(0)项目

项目1通过ε弧

连接到项目2和项目4

项目2在通过a弧连接到项目3

项目3通过ε弧

连接项目2和项目4

项目3通过A连接到项目7

项目1呢通过A连接到项目6

项目4通过b连接到项目5

这样的话我们就构造出了

识别活前缀的

不确定的有限状态自动机

如果我们用项目的编号来代替项目的话

就可以把它画成我们常见的

不确定的

有限状态自动机它的形式了

那么NFA是怎样识别活前缀的呢

对于句子ab来说

大家看到这是它的语法树

那么句子ab归约的第1步

句柄是b

活前缀是ε a ab

这是因为呢我们从状态1出发

经过了状态2 3和4最后到达了终态5

它对应的输入符号分别是ε

a

ε

b

那么此时

活前缀ab当中呢是包含句柄b的

在到底这条路径上面

的任一个状态的时候

所经过的弧上面的标志

连接而成的串都是ab的活前缀

之后呢我们可以通过子集法对

NFA进行确定化形成DFA

那么右边大家看到的就是

DFA它的状态转化图

那么这个状态当中呢大家看到

3 4 5这三个状态是终态

此时句子ab它的归约过程是这样子的

状态1经过a弧达到状态2

再输入b转换到状态4

此时就是一个识别到句柄的一个状态

这个句柄呢就是b

b归约于A

回到状态2输入A

到达状态5状态5呢也是一个终态

识别到的句柄呢是aA

那么规约为A

回到状态1

通过输入A进入状态3

状态3呢也是一个可规约态

那么A可以被规约为S’

那么识别句子的工作呢就结束了

构造NFA的时候

每一个状态呢是单个的一个项目

但是在我们对

NFA进行确定化之后

我们发现有一些状态

其实是项目的集合

譬如在这个DFA当中的初态

那么它就是由S＇→·A

A→·aA

A→·b这三个项目集合在一起的

我们称之为LR(0)的项目集

利用LR(0)项目集规范族

我们可以直接构建一个识别

文法活前缀的DFA

在这里我们将直接使用闭包

和状态转移函数来进行计算

构造出一个DFA

不过呢我们首先对这个状态转换图

做一个说明

其一每个DFA它的状态是一个项目集

我们称之为LR(0)的项目集

整个状态集呢称为

LR(0)项目集规范族

其二在DFA的任意一个项目集内

每个项目是等价的

也就是说从期待归约的

角度来看大家都是相同的

其三

有唯一的一个初态和若干个终态

表示的是有若干种活前缀它的识别状态

其四从初始状态出发

沿着DFA可以到达的状态

它的路径上的标志

可以形成活前缀

其五

状态反映的是识别句柄的情况

那么接下来我们就来看一下

构造LR(0)项目集规范族它的算法

第一步为了保证接受项目它的唯一性

如果多于一个产生式的右部出现开始符号

那么需要对文法进行拓广

引入新的开始符号S'

但是下面这个文法不必进行拓广

因为只有一条产生式它的左部是S

那么这个S呢并不会出现在

其他的产生式的右部里边去

记得要给每一个产生式一个编号

以便标记规约的时候采用哪一条产生式

第二步是构造文法项目集的闭包

假定I是一项目集

那么I中的每一个项目

都属于closure(I)

如果形如A→α·Bβ

圆点后面的B是一个非终结符

如果这样的一个项目呢是属于

closure(I)的话

那么对G′这个文法当中的

任意一个产生式

B→γ的项目B→·γ

它也是属于closure(I)

重复上面的这个步骤

直到不会再有新的项目加入closure(I)为止

例如针对文法G[S]

去求closure({S＇→·A})

首先S＇→·A属于这个闭包

其次圆点后面

这个A呢是非终结符

我们来看在这个文法当中

A有两个产生式

那么A→·aA

还有A→·b也属于这个闭包

接下来再来求closure({A→a·A})

和我们上面的这个求法是类似的

那么这个闭包也包含3个项目

分别是A→a·A

A→·aA

A→·b

第三步求状态转换函数 GO(I X)

第一个参数I是一个LR(0)项集

第二个参数X是后继符号

GO(I X)＝closure(J)

那么状态I和J的关系

就如这个状态转换局部图

首先呢I和J呢都是来自于一个产生式

其次呢这个圆点的位置

状态J落后于状态I一位

直观的来讲

如果I是某个活前缀γ有效项集的话

那么GO(I X)

就是活前缀γX它的有效项集

第四步就是利用

函数closure和GO

来完成LR(0)项目集规范族它的构造

把文法的所有产生式的项目都引出

每个项目都为NFA的一个状态

其中文法的第一个产生式

也就是说第一个项目

S’→.S

是文法的初态集的核心项

找到了文法的初态核心项之后

我们去求这个核心项它的闭包

就得到初态的项目集

接下来我们对项目集

和其它所构造出来的项目集

再应用转换函数GOTO(I X)

去求新的状态J它的项目集

最后呢我们去重复刚才的这一步

直到不会出现新的项目集为止

我们来尝试一下

构造刚才我们所看到的

这个文法

G[S]的LR(0)项目集规范族

首先呢我们找到了

初态的核心项就是S＇→·A

我们去求它的闭包

得到的状态集是

{S＇→·A A→·aA A＇·b}

接下来就是通过状态转换go函数

就好比在状态I0下

如果输入a b A

之后会去到那些状态

那么就出现了大家所看到的

新的项目集

I1

I2

I3

其中呢I2和I3是规约项

对于I1来说

我们再通过状态转换函数go函数

去寻找新的状态集

大家看到

出现了新的项目集就是I4

那么I4呢也是一个规约项

在这一节当中呢我们给大家

介绍了识别活前缀的

有穷状态自动机的有两种方法

第一种方法呢就是通过由文法的产生式

直接去构造

识别活前缀和

可归约前缀的有穷状态自动机

那么这是一个

不确定的有限状态自动机

我们需要对它进行确定化

第二种方法呢就是通过构造文法

G它的LR(0)的项目集规范族

来直接构造识别活前缀的DFA

需要说明的一点是

由于NFA它的确定化

工作量比较大

我们会直接考虑

先构造出项目集规范族

作为DFA的状态来构造DFA

这一节呢就到这里

谢谢大家