构建FIRST集合FOLLOW集合在线视频

同学们

如果我们要进行确定的自顶向下的语法分析

我们不禁要问

什么样的文法

才能进行确定的自上而下的分析呢

我们都知道

确定的自顶向下的分析

首先从文法的开始符号出发

如果某一步推导到了当前的句型

最左边的符号是个非终结符A

并且扫描到的当前输入符号是a

那么如果A有多个候选式的话

当前选中的候选式必须是唯一的

我们通常会选取这样的产生式α来代替A

从α推导出的

第一个终结符恰好是a

那么第一个符号就非常重要

第一个终结符呢就是指

符号串

它的第一个符号

并且是终结符号

可以称为首终结符号

自顶向下的分析当中呢

它对选取候选式具有非常重要的作用

为此呢我们引入了

FIRST

也就是首符号集的概念

我们先来给出FIRST集合它的定义

假定α是文法当中的任意一个符号串

α可以是由终结符或者是非终结符组成的

那么

α它的FIRST集

是所有α能推出的字符串

最左边的这个终结符

如果α经过若干步推导可以得到ε

那么我们就规定

ε是属于FIRST(α)

可以看出FIRST(α)

是从α可能推导出来的

所有开头终结符号或ε

当某个非终结符有多个产生式

而且从这些产生式推导出的最左边的符号

不是ε的时候

我们可以通过检测每一个产生式它的FIRST集

如果互不相交

那么

这个文法的句子

可以进行确定的

自上而下的分析

我们来看第一个例子

候选式aAb它的FIRST集是a

候选式cd的FIRST集是c

候选式c的FIRST集是c

因此S的FIRST集是{a}

A的FIRST集是{c}

来看第二个例子

候选式aA它的FIRST集是a

候选式a它的FIRST集是a

候选式 ε它的FIRST集是 ε

那么S的FIRST集是{a}

A的FIRST集是{a，ε}

下面我们来看文法符号FIRST集合

它的构造方法

对于文法当中的符号X

X可以是终结符

也可以是非终结符

那么

它的FIRST(X)集可以

反复的应用下面的规则进行计算

直到FIRST(X)集合不再增大为止

首先

若X∈Vt

则FIRST(X)={X}

若X∈Vn

而且有形如X→aα的产生式(a∈Vt)

a呢是终结符

或者是具有形如X→ε的产生式

那么就把a或ε加进到FIRST(X)当中去

还有一些产生式它的样式是比较复杂的

比如

文法当中有形如X→Y1Y2…Yk这样的一个产生式

如果Y1∈Vn

那么就把FIRST(Y1)当中一切非ε的符号

加入到FIRST(X)当中去

如果ε∈FIRST(Y1)

那么就把FIRST(Y2)当中所有非ε的终结符

加入到FIRST(X)当中去

如果ε∈FIRST(Y1)

ε∈FIRST(Y2）

那么就把FIRST(Y3)当中

一切非ε的终结符

加入到FIRST(X)当中去

依此类推

如果所有的非终结符它的FIRST集当中

都有ε

那么最后我们把ε加入到FIRST(X)当中去

我们来看第三个例子

首先呢我们可以知道

A的FIRST包含{a, ε}

B的FIRST包括{b, ε}

我们接下来来看一下S的FIRST集

首先我们将

FIRST(A)中一切非ε的符号加如到FIRST(S)当中去

再将

FIRST(B)当中一切非ε的符号加入到FIRST(S)当中去

产生式的第三个部分是c

它是一个终结符

所以我们就把c也加入到FIRST(S)当中去

这样我们就得到了非终结符

S A B的首符集

这个文法呢就是我们之前讨论过的表达式文法

我们来求这个文法的符号串

以及非终结符的FIRST集

根据构建FIRST集的前两个规则

我们可以很快的求得

候选式+TE'它的FIRST集是+

候选式ε的FIRST集是ε

候选式*FT'的FIRST集是*

候选式(E)的FIRST集是

（

候选式i的FIRST集是i

这样的话我们就可以获取

E'，T'和F它的FIRST集

再根据规则3

产生式TE’它的FIRST集是最左边T的FIRST集

继而推导出也是F的FIRST集

那么F的FIRST集是没有ε的

候选式FT’

它的FIRST集是最左边的符号F的FIRST集

那么F他的FIRST集也是没有ε的

所以我们可以看到候选式

TE’和FT'它的FIRST集是一样的

那么非终结符E和T的FIRST集也就一样了

都是{ ( ，i }

还有一种产生式的类型我们没有讨论到

在自顶向下的分析过程中

选择A→ε做为推导的依据

究竟是什么呢

这时候我们需要

A后面紧随的这个符号

与我们当前正在扫描到的符号去做匹配

我们来给出A的后续符号集的定义

任意句型αAaβ中

跟随在A后面的这个终结符a就属于FOLLOW(A)

如果A是某个句型的最右符号

那么就将结束符#添加到FOLLOW(A)当中去

也就是说

FOLLOW(A)

就是所有句型当中紧跟在A后面的终结符号或#

如果A的某个产生式可以推导出ε

那么当A的首符集和它的后继符号集相交为空的时候

可以对文法的句子进行确定的自顶向下的分析

下面我们就来看构造Follow集合它的算法

首先如果A是开始符号的话

则把“#“ 加入到 FOLLOW(A)当中去

譬如左边这个表达式文法的开始符号E

它的FOLLOW集合当中就有#

其次如果产生式形如

要注意β并不是ε

那么跟在A后面的字符串β

所有的非ε首字符集都属于A的Follow集

比如说我们从产生式F→(E)我们可以知道

）属于FOLLOW(E)

最后一类产生式可以用

这个里边的β呢是

可以推出ε

那么紧跟在B后面的字符也会紧跟在A后面

我们可以把FOLLOW(B)加入FOLLOW(A)当中去

比如说从E→TE'

可以看出应该把FOLLOW(E)加入FOLLOW(E')当中去

从E ' →+ TE '

那么我们就可以把FOLLOW(E ')加入FOLLOW(T)当中去

大家要注意FOLLOW集合是不包含ε的

还是表达式文法

这一次我们来求所有非终结符它的FOLLOW集

由于E是开始符号

所以#∈FOLLOW(E)

又因为F →(E)

那么 )∈FOLLOW(E)

那么因此FOLLOW(E)是{#,)}

由于E → TE’

所以我们可以把FOLLOW(E)加入 FOLLOW(E’)

那么因此我们可以得到FOLLOW(E’)={#,)}

从产生式E’→ +TE’

我们可以把FIRST(E’)-{ε}加入FOLLOW(T)

又因为产生式E’→ε

那么我们把 FOLLOW(E’)加入FOLLOW(T)

因此我们得到了FOLLOW(T)={+,),#}

由于T → FT’

那么把FOLLOW(T)加入FOLLOW(T’)

那么FOLLOW(T’)= FOLLOW(T)= {+,),#}

由于T → FT’

可得 FOLLOW(F)=FIRST（T’）-{ε}

又因为T’ →ε，

那么我们可以把FOLLOW(T)加入FOLLOW(F)

因此呢FOLLOW(F)={*,+,),#}

至此呢我们已经给大家介绍了FIRST集

和FOLLOW集它的构造方法

我们来做一下比较

首先呢有两个特殊符号

FIRST集合不可能存在#符号

FOLLOW集合不可能存在ε

其次

FOLLOW集合是为非终结符定义的

而FIRST集合可以为非终结符 终结符或者是符号串定义

最后

FOLLOW集合寻找的是

非终结符“右边”的这个终结符

而FIRST集合寻找的是产生式右部“最左边”的终结符

现在我们回过头来看看

如何判断一个文法是否LL(1)文法

那么LL（1）文法应该满足3个条件

第一

文法不含左递归

第二

对于每个非终结符A

它的各个候选式的首终结符号集

两两不相交

第三

对于文法当中的每个非终结符A

如果它的某个候选式的

首终结符号集合当中包含ε

那么它的FIRST与FOLLOW集相交应该为空

好了我们来看一下这个文法是不是LL(1)文法呢

我们先来观察一下这个文法

文法呢首先不含左递归

没有ε产生式

文法当中只有A有两个候选式

FIRST(:i=e)={ : }

FIRST(=e)={=}

那么这两候选式的FIRST集互不相交

而且A的候选式的FIRST集当中不包含ε

所以这个文法是满足LL(1)文法的条件的

它是LL(1)文法

再来看另外一个文法

它是不是LL(1)文法呢

显然这个文法呢也没有左递归

接着来看一下这个文法有没有回溯

S有两个候选式

首先FIRST((S)S)= {(}

那么ε

这个候选式它的FIRST集是ε

它两也是互不相交的

其次由于S→ε

我们就需要检测

S的FIRST集和它的FOLLOW集是否有交集

我们也看到了FOLLOW(S)是{),#}

那么因此呢

它的FIRST集和FOLLOW集没有交集

所以这个文法也是LL(1)文法

这一节我们讨论了FIRST集合和FOLLOW集构造方法

并且利用这两个集合

去判定一个文法是否是LL(1)文法

这一节课就到这里

谢谢大家