正文
FIRST集和FOLLOW集
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
省略号代表其他相关产生式得出的终结符号,一开始的时候，省略号里面是没有的
求FIRST集
情况壹 如果A只在→的右边出现，那么FIRST(A)={A},例子M→α,FIRST(α)={α}
情况貳 对于A→BCDEFG，
一 如果无B→ε,那么FIRST(A)={……}∪FIRST(B),接着求FIRST(B)
二 如果有B→ε,那么FIRST(A)={……}∪(FIRST(B)-{ε})∪FIRST(CDEFG),接着分别求FIRST(B)-{ε}、FIRST(CDEFG)
情况叁 如果G→ε，那么FIRST(G)={……}∪{ε}
求FOLLOW集
情况壹 如果S是开始符号(一般是第一个产生式)，那么FOLLOW(S)={……,$}
情况贰 一 如果有产生式A→αBCD，且ε不属于FIRST(CD)那么FOLLOW(B)={……}∪(FIRST(CD))
二 如果有产生式A→γBCD，且ε属于FIRST(CD)那么FOLLOW(B)={……}∪(FIRST(CD)-{ε})∪FOLLOW(A)
情况叁 如果有产生式M→CDB，那么FOLLOW(B)={……}∪FOLLOW(M)
例子
对于文法G[A]
A→BCc|gDB
B→bCDE|ε
C→DaB|ca
D→dD|ε
E→gAf|c
FIRST集先看→左边
FIRST(A)=FIRST(BCc)∪FISRT(gDB)
=(FIRST(B)-{ε})∪FIRST(Cc)∪{g}
={b}∪FIRST(DaBc)∪FIRST(cac)∪{g}
={b}∪FIRST(dDaBc)∪FIRST(aBc)∪{c}∪{g}
={b,d,a,c,g}
FIRST(B)=FIRST(bCDE)∪FIRST(ε)
={b,ε}
FIRST(C)=FIRST(DaB)∪FIRST(ca)
=FIRST(dDaB)∪FIRST(aB)∪{c} 相当于(FIRST(D)-{ε})∪FIRST(aB)∪{c}
={d,a,c}
FIRST(D)=FIRST(dD)∪FIRST(ε)
={d,ε}
FIRST(E)=FIRST(gAf)∪FIRST(c)={g,c}
-------------------------------------------------------------------------------------------------------
FOLLOW集先看→右边
FOLLOW(A)={$}∪{f}={f,$}
FOLLOW(B)=FIRST(Cc)∪FOLLOW(A)∪FOLLOW(C)
={d,a,c}∪{f,$}∪FOLLOW(C)先去求FOLLOW(C)再来补
={a,c,d,g,f,$}
FOLLOW(C)={c}∪FIRST(DE)
={c}∪{d}∪FIRST(E)
={c,d,g}
FOLLOW(D)=(FIRST(B)-{ε})∪FOLLOW(A)∪FIRST(E)∪{a}∪FOLLOW(D)
={b}∪{f,$}∪{g,c}∪{a}
={a,b,g,c,f,$}
FOLLOW(E)=FOLLOW(B)={a,c,d,g,f,$}
