First集

官方定义

设G=(VT，VN，S，P)是上下文无关文法 ，则

（1）如果X是终结符，则FIRST(X) = { X } 。

（2）如果X是非终结符，且有产生式形如X → a…，则FIRST( X ) = { a }。

（3） 如果X是非终结符，且有产生式形如X → ABCdEF…（A、B、C均属于非终结符且包含 ε，d为终结符），需要把FIRST( A )、FIRST( B )、FIRST( C )、FIRST( d )加入到 FIRST( X ) 中。

（4）如果X经过一步或多步推导出空字符ε，将ε加入FIRST( X )。

理解定义

FIRST(A)是以A为开始符的集合，A所有可能推导的，开头为终结符的集合或者是ε

例子

大写字母表示非终结符，小写字母表示终结符。

1. 后面跟的是终结符

...
A->aB|ε	（a开头且为终结符）
A->c
...
First(A)={a，ε，c}

2. 后面跟非终结符（一）

...
A->Ba
B->b
...
First(A)={b}

3. 后面跟非终结符（二）

...
A->Bc
B->b|ε
...
First(A)={b,c}
为什么这里c也是呢，A->Bc，而B可以->b|ε，当B为ε时，A->c

4. 后面跟非终结符（三）

...
A->BC
B->b|ε
C->c|ε
...
First(A)={b,c,ε}
为什么是b,c,ε呢，当B为ε时，A->C，而C->c|ε，b同理

Follow集

官方定义

假定S是文法G的开始符号，对于G的任何非终结符A,我们定义

理解定义

Follow(A)为紧跟在非终结符A后面的终结符的集合或’#’。

求解规则

（1）对于文法的开始符号S,置#于Follow（S）中；**(对于一个文法G(S)来说,求公理S的FOLLOW集的时候，由于没有一个产生式的右部包含S，所以我们规定S的FOLLOW集是｛#｝，就是一个句型的结束符)

（2）若A->αBβ是一个产生式，则把First(β) \ {ε} 加入到Follow（B）中**（B后面有东西，β是紧跟其后，如果β是终结符则直接将β加进去）**

（3）若A->αB是一个产生式，或A->αBβ是一个产生式且β=>ε，则把Follow(A)加入到Follow(B)中（B后面没有东西，即β=>ε）

理解求解规则

（1）对于开始符号，首先将#放入Follow集中

（2）规则2中，形如A->αBβ

（α可以是终结符或者非终结符或者直接为空，β可以是终结符或者非终结符，
注意β不能为空，B后面要有东西，
注意β不能为空，B后面要有东西，
注意β不能为空，B后面要有东西）

比如

A->aBC，a为空时，A->BC  
A->aBd，a为空时，A->Bd

将First(β) \ {ε}（即First(β)除去ε） 加入到Follow（B）中

总结：B后面有东西时，FOLLOW(B)中加上FIRST(B),但别把ε加进去。

（3）形如A->αB(α可以是终结符或者非终结符或者直接为空)或者A->αBβ是一个产生式且β=>ε

比如

A->B（α为空）
A->cB（α不为空）

A->αBβ是一个产生式且β=>ε:
A->dBC
C->ε

将Follow(A)加入到Follow(B)中。

综合例子

综合例子一

注意：[if] 是一个终结符，同理[b] [other] [else] [then]

G(S)：（下面有什么推导就要写什么的FIRST集合和FOLLOW集合）
S->IETSP|O
I->if
E->b
O->other
L->else
T->then
P->LS|ε

First	Follow
First(S)={if,other}	Follow(S)={ #, else }（首先找到S->IETSP|O,S后面是P，对应规则2）
First(I)={ if }	Follow(I)={ b }
First(E)={ b }	Follow(E)={ then }
First(O)={ other }	Follow(O)={ else, # }（首先找到S->IETSP|O,O后面没东西，对应规则3）
First(L)={ else }	Follow(L)={ if, other }（只有P->LS|ε，对应规则2）
First(T)={ then }	Follow(T)={ if, other }
First§={ else, ε }	Follow§={ else, # }（首先找到S->IETSP|O,P后面没东西，Follow(S)加入到Follow§），因为P是由S推导：S->IETSP|O

综合例子一 中反馈的问题：

• S->IETSP|O 中求Follow(S)能运用规则2和3来求解S吗？

可以的，虽然规则中给出的是A和B两个不同的非终结符，但是
A和B在实际运用的过程中是可以相等的，即B=A
A和B在实际运用的过程中是可以相等的，即B=A
A和B在实际运用的过程中是可以相等的，即B=A
S->IETSP|O S后面有P,利用规则3，将First(P)加入Follow(S)中
但是，发现P可以等于ε，即S->IETS，利用规则二，将Follow(S)加入Follow(S)中

• 在求Follow(S)发现P->LS|ε也是存在的，那么follow(s)={#,else}+follow( p )，而算到follow( p )发现follow( p )=follow(s) 就不知道怎么算了

我们需要同时满足
follow(s)={#,else}+follow§
follow§=follow(s)
将第二个式子带入一式得到
follow(s)={#,else}+follow(s)
注意：不能将follow(s)约掉，而是要想怎么样上面的等式仍然成立
那么，我们就会发现follow(s)只能等于{#,else}
因为 {#,else}={#,else}+{#,else}是成立的

综合例子二

G(E):
E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|i

First	Follow
First(E)={ (, i }	Follow(E)={ #, ) }
First(E’)={ +, ε }	Follow(E’)={ #, ) }
First(T)={ (, i }	Follow(T)={ +, #, ) }
First(T’)={ *, ε }	Follow(T’)={ +, #, ) }
First(F)={ (, i }	Follow(F)={ *, +, #, ) }

综合例子二 中反馈的问题：

• 为什么求E的FOLLOW集看到F->(E)|I直接将)右括号直接加入Follow中

  这个问题需要回到最初的定义来理解 follow集的意思是紧跟后面的符号集，E后面有），即E后面有终结符。 属于规则二，但是终结符没有first和follow，所以直接添加即可。

综合例子三

G[S]: S→aH
H→aMd
H→d
M→Ab
M→ε
A→aM
A→e

First	Follow
First(S)={ a }	Follow(S)={ # }
First(H)={ a, d }	Follow(H)={ # }
First(M)={ a, e, ε }	Follow(M)={ d, b }
First(A)={ a, e }	Follow(A)={ b }

综合例子四

G(E):E->TE'
E'->+E|ε
T->FT'
T'->T|ε
F->PF'
F'->*F'|ε
P->(E)|a|b|^

First	Follow
First(E)={ (, a, b, ^ }	Follow(E)={ #, ) }
First(E’)={ +, ε }	Follow(E’)={ #, ) }
First(T)={ (, a, b, ^ }	Follow(T)={ +, #, ) }
First(T’)={ (, a, b, ^ ,ε }	Follow(T’)={ +, #, ) }
First(F)={ (, a ,b, ^ }	Follow(F)={ (, a, b, ^, +, #, ) }
First(F’)={ *, ε }	Follow(F’)={ (, a, b, ^, +, #, ) }
First( P )={ (, a, b ,^ }	Follow( P )={ *, (, a, b, ^, +, #, ) }

综合例子四中反馈的问题：

怎么求follow(E)和follow(E‘)?

根据G(E)和规则一，#加入follow(E)
根据P->(E)|a|b|^和规则二，)加入follow(E)
根据E’->+E|ε和规则三，将follow（E’）到follow（E）里面

根据E->TE’和规则三得到将follow（E）到follow（E‘）里面

=>
Follow(E)={#,)}+Follow(E’)
Follow(E’)=Follow(E)
根据综合例子一中一样的分析方法
Follow(E)={#,)}+Follow(E)=>Follow(E)={#,)}

LL(1)文法的判断

根据LL(1) 文法的定义来判断，分三步走：
(1) 文法不含左递归

(2) 对文法中的任一个非终结符A的各个产生式的侯选首终结符集两两不相交，即：若

A->α1|α2|…|αn ，则

First(αi)∩ First(αj) = ∅ ( i ≠ j )

(3) 对文法中的每个非终结符A,若它存在某个首终结符集含有ε ，则

First(αi)∩Follow(A) = ∅ （i=1,2,…,n）

SELECT集合

已知文法G[S]：
　　S→MH|a
　　H→LSo|ε
　　K→dML|ε
　　L→eHf
　　M→K|bLM
　　判断G是否是LL(1)文法，如果是，构造LL(1)分析表。

select(S->MH)=First(MH)-{ε}∪Follow(S)={d,b,e,#,o}
select(S->a)={a}
所以select(S->MH)∩select(S->a)=φ

select(H->LSo)=First(L)={e}
select(H->ε)=Follow(H)={#,f,o}
select(H->LSo)∩select(H->ε)=φ

select(K->dML)={d}
select(K->ε)=Follow(K)={e,#,o}
select(K->dML)∩select(K->ε)=φ

select(M->K)=First(k)-{ε}∪Follow(M)={d,e,#,o}
select(M->bLM)={b}
select(M->K)∩select(M->bLM)=φ

这里可以推出是LL(1)文法

select(S->MH)={d,b,e,#,o}
select(S->a)={a}
select(H->LSo)={e}
select(H->ε)={#,f,o}
select(K->dML)={d}
select(K->ε)={e,#,o}
select(L->eHf)={e}
select(M->K)={d,e,#,o}
select(M->bLM)={b}
对应以下预测分析表，如：S在有S->a得a，即在a那格->a，其他同理

预测分析表：