首页 > 代码库 > 求FIRST集和FOLLOW集

求FIRST集和FOLLOW集

花了点时间弄了个大概,希望对和我一样的人有所帮助。
 

文法如下:

E -> TE‘
E‘ -> +TE‘|ε
T -> FT‘
T‘ -> *FT‘|ε
F -> (E)|id
----------------------------------------------------------------------------------------------------------------------------------------------------
FIRST集:由非终结符号推出的所有的开头符号或ε
规则:终结符的FIRST集,即是他本身。
所以,FIRST(+) = {+}, FIRST(*) = {*}, FIRST(id) = {id}, FIRST(() = {(}, FIRST()) = {)}
FIRST(E): 列出与E相关的产生式: E->TE‘  T -> FT‘  F -> (E)|id,
显然,F->(  / id,  T-> (  / id,  所以,FIRST(F) = {(,id}, FIRST(T) = {(,id}, FIRST(E) = {(,id}
FIRST(E‘) = {+,ε}
FIRST(T‘) = {*,ε}
FOLLOW集:紧跟随其后面的终结符号或#
和FIRST集不同的是:FOLLOW集只是针对非终结符而言,因为FIRST集和FOLLOW集设计的初衷就是
根据当前句型的最左语法变量A和当前输入符号a可以唯一的选择A的候选式αi来替换A,
从而实现对G的句子进行确定的自顶向下分析。所以终结符可以直接与输入符号进行匹配,不需要FOLLOW集。
实现:把所有包含你要求的符号的产生式都找出来。
FOLLOW(E): F -> (E)|id, E后面就是),其他包含E的都没有,所以FOLLOW(E)={),#}
FOLLOW(E‘):   由  E -> TE‘ 和 F -> (E)|id  推出 F -> (TE‘)|id ,所以FOLLOW(E)={),#}
FOLLOW(T):    由  E -> TE‘  和  E‘ -> +TE‘|ε ,T后面是E‘ (即:+TE‘|ε),所以,T有+,
                        再根据F -> (E)|id   E -> TE‘  推出 F -> (TE‘)|id,当 E‘ -> ε时,T后面是),所以,T有 ).
                        故FOLLOW(T) = {+,),#}
FOLLOW(T‘):   由  E -> TE‘ 和 F -> (E)|id  推出 F -> (TE‘)|id,且 T -> FT‘,所以  F -> (FT‘E‘)|id
                         T‘ 后面紧跟 E‘,E‘ -> +TE‘|ε,当E‘ -> +TE‘时,T‘ 有 +。当E‘ -> ε 时,T‘ 有 )
                        故FOLLOW(T‘) = {+,),#}
FOLLOW(F):  由  E -> TE‘ 和 F -> (E)|id  推出 F -> (TE‘)|id,且 T -> FT‘ ,T‘ -> *FT‘|ε,所以  F -> (FT‘E‘)|id
当 T‘ -> *FT‘时,F有 *,当T‘ -> ε时,F后紧跟E‘,当E‘ -> +TE‘时,F有 +,当E‘ -> ε时,F 有 )
                       故FOLLOW(F) = {*,+,),#}

 

 
另一个例子:
文法:
S --> aA 
S --> d
A --> bAS
A --> ε
求出该文法的First集 和 Follow集。
 
严谨的说  First集 是针对候选式而说的。在此把书上的求候选式First集的算法写一下:
--------------------------------------------------------------------------------------------------------------------------------
输入:文法G = (V,P,T,S),α = (v ∪ T)*,α = X1.....Xn
输出:First(α)
步骤:
1、计算First(X1);
2、First(α) = First(X1) - {ε}
3、k = 1
4、while(ε ∈ First(Xk) and k < n)    do begin
                First(α) = First(α) ∪ (First(Xk+1) - {ε})
                k = k +1   end
5、if(k = n and ε ∈ First(Xk))  then First(α) = First(α) ∪ {ε}
--------------------------------------------------------------------------------------------------------------------------------
First(S) = {a,d}
First(A) = {b,ε}
First(aA) = {a}
First(d) = {d}
First(bAS) = {b}
First(ε) = {ε}
 
咋看之下 Follow(S) = {#}  实则不然
(1)S --> aA            (2)A --> bAS
由2得: Follow(A) = First(S) = {a,d, #}
又因为 1 式:S --> aA,Follow(S) = Follow(A) = {a,d, #}

求FIRST集和FOLLOW集