First集合

First 集合的定義：令X 為一個文法符號（一個終結符或非終結符）或，則集合First (X) 由終結符組成。

基本介紹

• 中文名：First集合
• 定義：文法符號則集合First (X)
• 套用領域：計算機科學
• 類型：彙編語言

簡介

First 集合的定義：令X 為一個文法符號（一個終結符或非終結符）或，則集合First (X) 由終結符組成，此外可能還有，它的定義如下：

（1）若X 是終結符或，則First (X) = {X}。

（2）若X 是非終結符，則對於每個產生式X →X1 X2. . . Xn ，First (X)都包含了F i r s t(X1) -{ }。若對於某個i < n ，所有的集合First (X1), . . . , First (Xi) 都包括了。則First (X) 也包括了First (X i + 1 ) -{ }。若所有集合First (X1), . . . , First (Xn)包括了，則First (X)也包括。

現在為任意串a = X1 X2 . . . Xn （終結符和非終結符的串）定義First ( )，如下所示：First (a)包括First (X1) 對於每個i = 2, . . . , n ，如果對於所有的k = 1, . . . ,i -1 ，First (Xk) 包括了，則First (a)就包括了First (Xi)。最後，如果對於所有的i =1, . . . , n ，First (Xi) 包括了，則First (a)也包括了。

示例

求給定文法的每個候選式的First集

S→Ap S→Bq A→a A→cA B→b B→d

答:

First(S1) = First(A) ={ a,c } First(S2) = First(B)={b,d } First(A1) = {a} First(A2) = {c} First(B1) = {b}
First(B2) = {d}