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所有可能推导的，开头为终结符的集合或者是ε
例子
==大写字母表示非终结符，小写字母表示终结符。==
- 后面跟的是==终结符==
...
A->aB|ε （a开头且为终结符）
A->c
...
First(A)={a，ε，c}
- 后面跟非终结符（一）
...
A->Ba
B->b
...
First(A)={b}
- 后面跟非终结符（二）
...
A->Bc
B->b|ε
...
First(A)={b,c}
为什么这里c也是呢，A->Bc，而B可以->b|ε，当B为ε时，A->c
- 后面跟非终结符（三）
...
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）中；
（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(P)={ else, ε } | Follow(P)={ else, # }（首先找到S->IETSP|O,P后面没东西，Follow(S)加入到Follow(P)），因为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(p)
follow(p)=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，其他同理
预测分析表：
