NULLABLE集合
定义
非终结符X属于集合NULLABLE,当且仅当:
基本情况:
- $X \rightarrow ε$
归纳情况:
- $X \rightarrow Y_1 ,…, Y_n$,(Y 是若干个非终结符,且对于所有 $i$,$Y_i ∈ NULLABLE $集)
即 存在非终结符 $X \rightarrow ε$。
算法
NULLABLE = {};
while (NULLABLE is still changing)
foreach (production p: X-> β )
if (β == ε)
NULLABLE ∪= {X}
if (β == Y1 … Yn)
if (Yi ∈ NULLABLE, i=1,2,...,n )
NULLABLE ∪= {X}
示例
Z -> d
| X Y Z
Y -> c
|
X -> Y
| a
迭代次数 | 0 | 1 | 2 |
---|---|---|---|
NULLABLE | {} | {Y, X} | {Y, X} |
- 第1次迭代:$Y → ε$,并上Y,$X → Y$进而推出$X → ε$,并上$X$
- 第2次迭代:和第1次结果一样,此时NULLABLE不改变,循环结束。
FIRST集
定义
基于归纳的计算规则:
基本情况:
$X → a$
- $FIRST (X) ∪ = \{a\}$
归纳情况:
$X → Y_i,i=1,2,...,n$
- $FIRST (X) ∪ = FIRST(Y_1)$
- $if\ Y_1∈NULLABLE$, $FIRST (X) ∪= FIRST(Y_2)$
- $if\ Y_1,Y_2 ∈NULLABLE$, $FIRST(X) ∪= FIRST(Y_3)$
- ...以此类推
算法
foreach (nonterminal N)
FIRST(N) = {}
while(some set is changing)
foreach (production p: N->β1 … βn)
foreach (βi from β1 upto βn)
if (βi == a …)
FIRST(N) ∪= {a}
break
if (βi == M …)
FIRST(N) ∪= FIRST(M)
if (M is not in NULLABLE)
break;
示例1:
0: S -> N V N
1: N -> s
2: | t
3: | g
4: | w
5: V -> e
6: | d
第一行是迭代次数,第一列是非终结符。内容是FIRST集。
NFIRST | 0 | 1 | 2 | 3 |
---|---|---|---|---|
S | {} | {} | {s, t, g, w} | {s, t, g, w} |
N | {} | {s, t, g, w} | {s, t, g, w} | {s, t, g, w} |
V | {} | {e, d} | {e, d} | {e, d} |
- 第1次迭代:把S对应的N的集合给S,此时N是空所以S是空,把N和V对应的终结符都给N和V;
- 第2次迭代:N给S,N,V不变。
- 第3次迭代:S、V、N的FIRST集的值都不发生改变,此时循环终止。
示例2:
Z -> d
| X Y Z
Y -> c
| ε
X -> Y
| a
已经得出:X、Y ∈ NULLABLE
NFIRST | 0 | 1 | 2 | 3 |
---|---|---|---|---|
Z | {} | {d} | {d, c, ε, a} | {d, c, ε, a} |
Y | {} | {c, ε} | {c, ε} | {c, ε} |
X | {} | {c, ε, a} | {c, ε, a} | {c, ε, a} |
- 第1次迭代:终结符{d}给Z,XYZ给Z(XY都是空,Z给Z相当于没给),{c, ε}给Y,Y, a给X,即{c, ε, a}给X;
- 第2次迭代:X,Y,Z给Z,即{c, ε, a}给Z
- 第3次迭代:Z、Y、X的FIRST集的值都不发生改变,此时循环终止。
当迭代$Z → X Y Z$时,因为$X ∈ NULLABLE$,所以会继续看Y, 同理看完Y看Z, 因为 Z 不属于 NULLABLE,所以停止。换下一行。
FIRST_S
把FIRST集推广到任意串上,即对给出的任意产生式,推出其FIRST集。
公式:
- 若当前输入是终结符N,∪当前输入的FIRST集
- N ∈ NULLABLE,∪下一个输入的FIRST集。
- 若当前输入是非终结符a,∪当前输入,然后结束。
算法
foreach (production p)
FIRST_S(p) = {}
calculte_FIRST_S(production p: N->β1 … βn)
foreach (βi from β1 to βn)
if (βi == a … )
FIRST_S(p) ∪= {a}
break;
if (βi == M … )
FIRST_S(p) ∪= FIRST(M)
if (M is not NULLABLE)
break;
FIRST_S(p) ∪= FOLLOW(N)
示例:
0: Z -> d
1: | X Y Z
2: Y -> c
3: |
4: X -> Y
5: | a
NULLABLE
-
{X, Y}
N | X | Y | Z |
---|---|---|---|
FIRST | {a, c} | {c} | {a, c, d} |
FOLLOW | {a, c, d} | {a, c, d} | {} |
- 编号0: FIRST_S = {d},break;
- 编号1: FIRST_S ∪= FIRST(X) => FIRST_S ∪= FIRST(Y) => FIRST_S ∪= FIRST(Z) => FIRST_S = {a, c, d},break;
- 编号2: FIRST_S = {c},FIRST_S ∪= FOLLOW(Y) => {a, c, d}
- 编号3: FIRST_S = {},FIRST_S ∪= FOLLOW(Y) => {a, c, d}
- 编号4: FIRST_S ∪= FIRST(Y) => FIRST_S = {c},FIRST_S ∪= FOLLOW(Y) => {c, a, d}
- 编号5: FIRST_S = {a},break;
编号 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
FIRST_S | {d} | {a, c, d} | {c} | {a, c, d} | {c, a, d} | {a} |
0: Z -> d # {d}
1: | X Y Z # {a, c, d}
2: Y -> c # {c}
3: | # {a, c, d}
4: X -> Y # {c, a, d}
5: | a # {a}
FOLLOW集
定义
**紧跟随其后面的 终结符或$符号 ,只看右部产生式**。要考虑到 $ε$。 具体做法是把所有包含你要求的符号的产生式都找出来,再看哪个有用
例如:产生式:$S → ABc$ 、$B → b | ε$ 、 $A → a | ε$ ,但只有$S → ABc $有用。跟随在A后面的终结符号是FIRST(B)={b,ε},当FIRST(B)的元素为ε时,跟随在A后的符号就是c,所以 Follow(A)={b,c} 同理 Follow(B)={c}
算法
foreach (nonterminal N)
FOLLOW(N) = {}
while(some set is changing)
foreach (production p: N->β1 … βn)
temp = FOLLOW(N)
foreach (βi from βn downto β1) // 逆序!
if (βi == a … )
temp = {a}
if (βi == M … )
FOLLOW(M) ∪= temp
if (M is not NULLABLE)
temp = FIRST(M)
else
temp ∪= FIRST(M)
示例:
0: Z -> d
1: | X Y Z
2: Y -> c
3: |
4: X -> Y
5: | a
$NULLABLE = \{X, Y\}$
$FIRST(X) = \{a, c\} 、FIRST(Y) = \{c\}、FIRST(Z) = \{a, c, d\}$
N迭代次数 | 0 | 1 | 2 |
---|---|---|---|
Z | {} | {} | {} |
Y | {} | {a, c, d} | {a, c, d} |
X | {} | {a, c, d} | {a, c, d} |
第1次迭代:
- 第0行:temp = {d}
- 第1行的Z:temp = FIRST(Z) = {a, c, d}
- 第1行的Y:FOLLOW(Y) ∪= temp => FOLLOW(Y) = {a, c, d},temp ∪= FIRST(Y) => temp = {a, c, d}
- 第1行的X:FOLLOW(X) ∪= temp => FOLLOW(X) = {a, c, d},temp ∪= FIRST(X) => temp = {a,c, d}
- 第2行:temp = {c}
- 第3行:temp = FOLLOW(Y) = {a, c, d}
- 第4行:temp = FOLLOW(X) ,FOLLOW(Y) ∪= temp,temp ∪= FOLLOW(Y),temp = {a, c, d}
- 第5行:temp = {a}
- 第2次迭代:和第1次结果一样,循环终止。
- - - 结束 - - -