First/Follow/Firstvt/Lastvt集合

First/Follow/Firstvt/Lastvt 集合

设文法 G

$G = (V_T,V_N,S,P) \\ V_N为非空有限的终结符号集 \\ V_T为非空有限的终结符号集 \\ S为文法的开始符号或识别符号,代表语言最终要得到的语法范畴 \\ P为产生式规则 \\$

2 型文法（上下文无关文法）

设文法 G，对 P 中的每个产生式限制形如

$A \to \alpha$

其中， $A \in V_N, \alpha \in (V_T \cup V_N)^*$ 则称文法 G 为 2 型文法。

First 集合

设 G 为上下文无关文法，则

$FIRST(A) = \{\alpha | A \Rightarrow \alpha...,\alpha \in V_T\}$

理解

First(A)集合是以 A 为开始符的集合，A 所有能够推导出的终结符或 $\varepsilon$

A->aB| $\varepsilon$

A->c

First(A) = {a, $\epsilon$ ,c}

A->Ba

B->b

First(A) = {b}

A->Bc

B->b| $\epsilon$

First(A) = {b,c, $\epsilon$ }

A->BC

B->b| $\epsilon$

C->c| $\epsilon$

First(A) = {b,c, $\epsilon$ }

对于文法的开始符号 S, 置#于 Follow(S)中
若 $A\to \alpha B \beta$ 是一个产生式，则 $Follow(B)$ += $(First(\beta) - \{\varepsilon\})$
若 $A\to \alpha B$ 是一个产生式，则 $Follow(B)$ += $Follow(A)$
若 $A\to\alpha B \beta$ 是一个产生式，且 $\beta \to \varepsilon$ ，则 $Follow(B)$ += $Follow(A)$

综合例题一

G(S): S->IETSP|O
I->if
E->b
O->other
L->else
T->then
P->LS|ε

First	Follow
First(S) = {if,other}	Follow(S) =

Follow(S) += First§-{ $\epsilon$ } = {else}

Follow(S) =

Follow(T) += Follow(B) - { $\epsilon$ }

Follow()

消除直接左递归

$A\to A\alpha|\beta$

其中 $\alpha、\beta\in(V_T\cup V_N)^*$ ， $\beta$ 不以 A 打头

则可改写为如下形式

$A\to\beta A'$

$A'\to \alpha A'|\varepsilon$

FIRSTVT(T)集合

非终结符 T 的最左终结符集合

LASTVT(T)集合

非终结符 T 的最右终结符集合

(未完待续)