直观上说文法符号串β
的开始符号集是由β
推导
出的所有的
终结符开头
和
可能的ε
组成。
例题：
文法G 2 [S]:
S→Ap
S→Bq
A→a
A→cA
B→b
B→dB
求出每条规则右部的符号串的FIRST集合
FIRST(Ap)={a,c}
FIRST(Bq)={b,d}
FIRST(a)={a }
FIRST(cA)={c}
FIRST(b)={b}
FIRST(dB)={d}
这里注意一点在求FIRST集合时很多时候会忘了ε，如果推导不出来那就没关系但是如果可以推导出来的话一定要写上。
注意哦在FIRST集合中我们是没有#的只有ε
FLLOW集合 定义 ：
G=(V N , V T , P, S) 是上下文无关文法 B→xAy ， (A, B ∈ V N , x,y∈(VN∪ V T )* )
FOLLOW(A)={a|S=>*…Aa… ， a ∈ V T } ， 若有 S=>* …A ，则规定 # ∈ FOLLOW(A)
注：输入串 # ，‘ # ’做为输入串的结束符
直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些 终结符 （包括 # ）组成
FOLLOW(A) 的计算方法
1 如果 A 为文法的识别符号，则规定 # ∈ FOLLOW(A)
2 如果有形如 B→α Aβ 的规则，则 FIRST(β) 的非空元素 ∈ FOLLOW(A)
3 如果有 β=>*ε ，或者形如 B→α A 的规则，则 把 FOLLOW(B) 加入到 FOLLOW(A) 中
反复使用上述规则，直到每个非终结符的 FOLLOW 集不再增大为止
之所以说这个复杂跟他的第3条规则有很大的关系反复使用这个规则在计算中会很复杂。
注意哦在FOLLOW集合中我们是没有ε的只有#
例子：
文法 G 3 [S]: S→aA|d A→bAS|ε
FOLLOW(A)=Follow(S) ∪ {FIRST(S)-{ ε }} ={#} ∪{a,d} ={#, a, d}
FOLLOW(S)= {#} ∪ FOLLOW(A) ={#, a, d}
SELECT 集合定义：
这个是跟之前的FIRST集合和FOLLOW集合是有很大关系的。
G=(V N , V T , P, S) 是上下文无关文法
A → β ， (A ∈ V N , β ∈ (V N∪ V T )* )
若 β ≠>*ε, 则 SELECT(A→β)=FIRST(β)
若 β=>*ε, 则 SELECT(A→β)=(FIRST(β)-{ε} ) ∪ FOLLOW(A)
例子：
G 3 [S]:
S→aA
S→d
A→bAS
A→ε
SELECT(S→aA)=FIRST(aA)={ a }
SELECT(S→d)=FIRST(d)={ d }
SELECT(A→bAS)=FIRST(bAS)={ b }
SELECT(A→ε) =(FIRST(ε)-{ε})+ FOLLOW(A)={ #,a,d }
注意哦在SELECT集合中我们是没有ε的只有#
现在我们可以讨论LL(1)
文法了
首先是部分定义
一个上下文无关文法为
LL(1)
文法的
充分必要条件
是
，对每个非终结符
A
的两个不同产生式
A→α与
A→β
，
满足
SELECT(A→α)∩SELECT(A→β)=Φ
LL(1)
文法的含义
第一个
L——
从左到右扫描输入串
第二个
L——
分析过程用最左推导
(1)——
表明只需向前看
1
个输入符号便可以决定选哪
个产生式进行推导（类似地，
LL(k)
文法则需要向前
看
k
个输入符号才可以确定选用哪个产生式）
要判别一个上下文无关文法是否是
LL(1)
文
法，分为五步：
求能推出
ε
的非终结符集
计算每个产生式
右部
β
的
FIRST(β)
集
计算每个
非终结符
A
的
FOLLOW(A)
集
计算每个
产生式
A→β
的
SELECT(A→β)
集
按
LL(1)
文法的定义判别