3.4.1 First and Follow在线视频

各位同学大家好

今天我们继续来学习

语法分析中的内容

这节课我们重点来学习

First集合和follow集合

然后我们使用first集合

何方类集合

来定义L1文法

我们首先来看一下

First集合的定义

对一个串α来说

它的first集合是指

计算出来

满足α的句子所有可能的开头字符

那么first哈尔

就是一个'a'的集合

而'a'是α所能推导出来的串的首字母的集合

a属于终结符

我们看到这里有一个特殊情况

如果α经过推导之后

可以得到空串

那么空串就加入到First(α)的集合当中

接下来我们看一下

Follow集合的定义

假设有一个符号A

follow集合是只跟

在A后边所有的符号串的开头字符

同样的follow集

它也是一个终结符的集合

假设对于A来说

follow(A)等于

我们在计算语言的句型中

所有可能跟在A后边的字符

在这里仍然有一个特殊情况

假设A是我们整个文法的开头字符

也就是说A是我们的开始符号

那么我们说$

是属于follow(A)的

也就是我们在进行分析的时候

将$作为

开始符号后继的一个符号

这样我们知道

什么时候我们分析结束

所以$就作为开始符号的Follow集合中的元素

接下来我们来学习一下

First集合的求解方法

假设有一个符号X

假设X可以推导出a开头的字符串

那么a如果是一个终结符

就加入到first(X)的集合中

第二假设X可以推导为空串

那么空串就作为First(X)集合中的元素

第三假设X可以推导出以Y开头的字符串

那么我们将first(Y)去掉空串之后

加入到first(X)中

我们再来看一下第四种情况

这是前三种情况的一个一般情况

X可以产生Y1 Y2一直到Yk

那么它其实是一个总结的情况

我们可以从一般的情况开始进行推导

假设X可以产生Y1

我们需要将Y1的first集合

加入到X的first集中

假设X可以产生Y1Y2

我们将Y1的first集

去掉空串之后

加入到X的first集中

然后如果在Y1

可以推导为空串的情况下

我们需要将Y2的first集

加入到X的first集合中

假设Y1和Y2都可以推导为空串

在这种情况下

空串需要加入到X的first的集合中

接下来

如果X可以推导为Y1Y2Y3

我们首先取Y1的first集

去掉空串之后

加入到X的first集中

在Y1推导为空串的情况下

我们需要将Y2的first集取出来

去掉空串之后

加入到X的first的集合中

在Y1和Y2都可以推导为空串的情况下

我们需要将Y3的first集取出来

去掉空串之后

加入到X的first的集中

如果Y1Y2Y3都可以推导为空串

那么X的first集合中应该包含空串

接下来是一个一般的情况

X可以产生Y1 Y2一直到YK

Y1 Y2一直到Y i-1

它们都是非终结符

并且Y1Y2一直到Y i-1的first集合中

都包含空串

那么我们将first(Yj)中的所有非空串集合

加入到first(X)当中

j等于1 2 一直到i

接下来有一个特例

就是Y1~YK都包含空串产生式

那么我们才将空串加入到first(X)中

接下来我们来看一个具体的例子

S可以产生BA

A可以产生BS或者d

B可以产生aA或者bS或者c

我们来针对这个文法求解一下

这里边所有非终结符的first集合

我们可以通过第一个产生式

S可以产生BA

我们可以知道

S的first集应该等于B的first

也就是在这一步

需要将B的first集中

所有的元素加入到S的first的集合中去

根据A可以产生BS或者d

我们可以知道

first(A)应该等于

first(B)加上d这个符号

根据第三个产生式

B可以产生aA或者bS或者c

我们可以知道

First(B)应该等于a b c

这样我们就可以在先求出

First(B)的情况下

求出来first(S)和first(A)

接下来我们就可以知道

First(A)等于first(B)+d 也就是a b c d

而first(S)等于first(B) 也就是a b c

接下来我们再看另一个例子

E可以产生TE'

在这种情况下

我们知道

E的first集

应该等于T的first集

E'可以产生+TE'或者空串

那么可以计算得到

E'的first集合为+和空串

T产生FT'

所以T的first集

等于F的first集

因此first(E)和first(T)

还有F的first集合是一致的

T'可以产生×FT'

或者空串

所以first (T')等于×和空串

最后一条产生式F可以产生(E)或者id

我们可以计算得到

First(F)等于左括号( 加上id

这样我们就出求出来

产生式中

所有非终结符的first集合

接下来我们总结一下

First集合的含义

针对一个符号串α来说

α的first集合

就是从α开始

我们可以推导出来的

符号序列中的开头的终结符

也就是first集合

它是一个终结符的集合

接下来

我们来看一下follow集

follow集针对一个符号A来说

是指计算这个语言的句型中

所有可能跟在A后边的字符

接下来我们学习

follow集合的计算方法

首先针对一个文法符号的开始符号S

我们需要将$加入到S的follow集合中

第2种情况

A产生αBβ

这是一个一般的情况

我们看到B的后边跟着的是β

所以我们需要将β的first集合取出来

去调空串之后

加入到B的follow集中

第三种情况

A可以产生αB或者

A可以产生αBβ

而β经过推导之后

可以得到空串

也就是说

仍然是A可以产生αB这样的情况

如果是这样的话

我们需要将A的follow取出来

加入到B的follow集合中

我们再来看一个具体的例子

仍然是之前的这个文法

S可以产生BA

A可以产生BS或d

B可以产生aA或者bS或者c

我们可以发现

在计算follow集之前

我们需要先计算出First的集合

那么first集合

我们在上一步已经计算完成了

我们接下来需要去计算

所有非终结符的follow集

我们来看一下

这个文法计算follow集的具体步骤

首先我们将first集合写出来

然后我们观察到

S是这个文法的开始符号

所以我们将$加入到S的follow集合中

然后我们看到

第1个产生式 S产生BA

所以B的后边

跟着的是A的first集合

我们需要取出来

First(A)加入到follow(B)中

接下来我们看一下

第2个产生式

A可以产生BS

B的后边跟着的是S的第1个符号

所以我们需要取出来

First(S)加入到B的follow集中

接下来我们就可以计算出

Follow(S)中包括$

follow(B)中包括a b c d

我们观察到第三行产生式

B可以产生aA

在这种情况下

我们需要将B的follow集

加入到A的follow集合中去

接下来我们计算得到

A的follow集等于a b c d

我们观察到

还有一个产生式

B可以产生bS

根据这条产生式

我们需要将B的follow集

加入到S的follow集中去

在加完之后

我们可以得到

S的follow集等于a b c d和$

接下来我们再回头看一下

第一条产生式

S可以产生BA

我们需要将S的follow

加入到A的follow中去

这样A的follow集就变为a b c d $

根据这个文法

我们可以看出来

在计算follow集时

可能一遍是求不完整的

我们需要多次来重复计算follow集

直到所有的集合

不再膨胀为止

接下来我们看下一个例子

仍然是之前的这个文法

我们已经将first集合求出来

然后我们需要在first集合的基础上

计算所有非终结符的follow集合

首先我们看到

E作为文法的开始符号

我们将$符号取出来

加入到E的follow集中

然后我们观察到

第1个产生式

E可以产生TE'

我们需要将E的follow集

加入到E'的follow集中去

然后我们看到

T的后边跟着的是E'

所以取出E'的first集

加入到T的follow集中去

接下来我们看

第3个产生式 T产生FT'

根据这个产生式 我们可以知道

T的follow集

需要加到T'的follow集中去

然后FT'

我们可以知道

我们需要将T'的first集

加入到F的follow集中去

这是我们第1遍的计算结果

在此基础上

我们继续进行follow集的求解

我们仍然观察到

第1个产生式 E产生TE'

因为E'可以推导为空串

所以这个产生式

可以变为E产生T

我们需要将E的follow集

加入到T的follow集中去

同样的T产生FT'

由于T'可以推导为空串

所以需要将T的follow集

加入到F的follow集中去

这是我们第2遍计算的结果

我们在进行follow集合的求解的时候

需要多次重复的计算

直到所有的follow集

不再膨胀为止

这是最终的求解结果

这一小节就到这

谢谢大家