&nbsp 在前面我们已经介绍了《First集与Follow集》，下面我们将介绍Select集，以及它和LL(1)型文法的关系。

一、Select集的构造

    给定文法 G，对于产生式 A→α，α ∈ V*，则可选集 SELECT(A→α) 有：

• （1）若 α ≠ ε，且 α ≠+> ε，则 SELECT(A→α) = FIRST(α)
• （2）若 α ≠ ε，但 α =+> ε，则 SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)
• （3）若 α = ε，则 SELECT(A→α) = FOLLOW(A)

    第 1 条是，当 α ≠ ε，且通过1次或多次推不出 ε，SELECT(A→α) = FIRST(α)
    第 2 条是，当 α ≠ ε，但 α 经有限步可推出 ε，SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)（注意是一个 α，一个 A）
    第 3 条是，当 α = ε，SELECT 集就等于左部 A 的 FOLLOW 集

1.1 下面来看一个例子：

A → BCc | gDB
B → bCDE | ε
C → DaB | ca
D → dD | ε
E → gAf | c

非终结符	First	Follow
A	{ a, b, c, d, g }	{ f, # }
B	{ b, ε }	{ a, c, d, g, f, # }
C	{ a, c, d }	{ c, d, g }
D	{ d, ε }	{ a, b, c, g, f, # }
E	{ c, g }	{ a, c, d, g, f, # }

右边的产生式	First
BCc	{ a, b, c, d }
gDB	{ g }
bCDE	{ b }
ε	{ ε }
DaB	{a, d}
ca	{ c }
dD	{ d }
gAf	{ g }
c	{ c }

    根据上表，可求出Select集如下：
SELECT(A → BCc) = { a, b, c, d }
SELECT(A → gDB) = { g }
SELECT(B → bCDE) = { b }
SELECT(B → ε) = { a, c, d, g, f, # }
SELECT(C → DaB) = { a, d }
SELECT(C → ca) = { c }
SELECT(D → dD) = { d }
SELECT(D → ε) = { a, b, c, g, f, # }
SELECT(E → gAf) = { g }
SELECT(E → c) = { c }

二、Select集与LL(1)型文法

2.1 LL(1)型文法的判定

    如果有相同左部的Select集交集为空，则是LL(1)型文法。

2.2 使用Select集构建LL(1)分析表

    构造方法：

1. 若 a∈SELECT(A→α)，则把 A→α 加至 M[A, a] 中。
2. 把所有无定义的 M[A, a] 标上“出错标志”。为了使表简化，表中空白处为出错。

    下面看另一个例子：
G[S]: S → aH
H → aMd
H → d
M → Ab
M → ε
A → aM
A → e

产生式	First	Follow	Select
S → aH	{ a }	FOLLOW(S) = { # }	SELECT(S→aH) = FIRST(aH) = { a }
H → aMd	{ a }	FOLLOW(H) = { # }	SELECT(H→aMd) = FIRST(aMd) = { a }
H → d	{ d }		SELECT(H→d) = FIRST(d) = { d }
M → Ab	{ a, e }	FOLLOW(M) = { b, d }	SELECT(M→Ab) = FIRST(Ad) = { a, e }
M → ε	{ ε }		SELECT(M→ε) = FOLLOW(M) ={ d, b }
A → aM	{ a }	FOLLOW(A) = { b }	SELECT(A→aM) = FIRST(aM) = { a }
A → e	{ e }		SELECT(A→e) = FIRST(e) = { e }

    根据上面求出的Select集，就可以写出LL(1)分析表：

	a	b	d	d
S	S → aH
H	H → aMd		H → d
M	M → Ab	M → ε	M → ε	M → Ab
A	A → aM			A → e