編譯原理-FIRST集、FLLOW集、SELECT集

一、First集：看産生式右部的第一個非終結符(可以包含ε)

1.關于概念我們不做深究，就讓大家知道怎麼做題，應付考試的，深究的夥伴配合書上看

一、求frist,關鍵看産生式左部,計算方法如下：

形如：

1.S->a ,那麼FIRST(S)={a} ,

2.S->AB,那麼FIRST(S)=FIRST(A),如果A->ε,那麼FIRST(S)=FIRST(A)=FIRST(B).

3.S->ε,那麼FIRST(s)={ε}

列題：判斷下列文法是否為LL(1)文法

S->AB

S->bC

A->ε

A->b

B->ε

B->aD

C->AD

C->b

D->aS

D->c

1.當A->b

FRIST(S—>AB)={b}

2.當A->ε，

FRIST(S—>εB)=FRIST(B)={a,ε}

FRIST(S->bC)={b}

熟練後

FRIST(S)=FRIST(A)U{b}U{ε}=FRIST(A)U{b}U{ε}U{a}={a,b,ε}

FRIST(A)={b,ε}

FRIST(B)={a,ε}

FRIST(C)={b}U FRIST(A)={b}UFRIST(D)={b}U{a,c}={a,b,c}

FRIST(D)={a,c}

二、求FLLOW集(不可以包含ε)，看産生式右部，看那個能産生你想要的字元，

FLLOW集：産生式右部所求的非終結符後面的的第一個終結符

1.形如：S->Ab,FLLOW(A)=FIRST(b)={b}

2.S->AB,FLLOW(A)=FIRST(B)

3.S->AB,B->ε, FLLOW(A)=FLLOW(S)

4.給開始符的FLLOW集加上#（這裡的#為句子括号），這裡的S

例如：求FLLOW(S),找到産生式右邊有S的，D->aS。

FLLOW(S)=FLLOW(D)=FLLOW(B)UFLLOW(C)=FLLOW(S)={#}

FLLOW(A)=FRIST(D)UFRIST(B)-{ε}UFLLOW(S)={a,c,#}

//這裡的FLLOW(S)是當B->ε時産生的S->A

FLLOW(B)=FLLOW(S)={#}

FLLOW(C)=FLLOW(S)={#}

FLLOW(D)=FLLOW(B)UFLLOW(C)={#}

非終結符名	是否能推出ε	FRIST集	FLLOW集
S	是	{a,b,ε}	{#}
A	是	{b,ε}	{a,c,#}
B	是	{a,ε}	{#}
C	否	{a,b,c}	{#}
D	否	{a,c}	{#}

3.求SELECT集

形如：1.S->AB，B->ε這樣的産生式，用産生式右部的FIRST集U左部的FLLOW集

2.S->AB這樣的産生式，用産生式右部的FIRST(A)UFIRST(B)集

3.S->aB,S->a,右部的FIRST集

SELECT(S->AB)=FIRST(AB)-{ε}UFLLOW(S)={a,b,#}

SELECT(S->bC)=FIRST(bC)={b}

SELECT(A->ε)=FIRST{ε}-{ε}UFLLOW(A)={a,c,#}

SELECT(A->b)=FIRST(b)={b}

SELECT(B->ε)=FIRST{ε}-{ε}UFLLOW(B)={#}

SELECT(B->aD)=FIRST(aD)={a}

SELECT(C->AD)=FIRST(AD)=FIRST(A)UFIRST(D)={a,b,c}

SELECT(C->b)=FIRST(b)={b}

SELECT(D->aS)=FIRST(a)={a}

SELECT(D->c)=FIRST(c)={c}

4.求SELECT交集

SELECT(S->AB)nSELECT(S->bC)={b}

SELECT(A->ε)nSELECT(A->ε)=空集

SELECT(B->ε)nSELECT(B->aD)=空集

SELECT(C->AD)nSELECT(C->b)={b}

SELECT(D->aS)nSELECT(D->c)=空集

因為S和C 的有相同的左部，交集都不為空，故不是LL(1)文法