【编译原理】NULLABLE/FIRST/FOLLOW三大集

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次结果一样，循环终止。