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

求FIRST集和FOLLOW集

2024-09-18 18:51:58   221人阅读

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

文法如下：

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集


联系
我们