MENU

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

June 2, 2020 • Read: 726 • 编程之路,编译原理

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
迭代次数012
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集。

NFIRST0123
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

NFIRST0123
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}

NXYZ
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;
编号012345
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迭代次数012
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次结果一样,循环终止。
- - - 结束 - - -
  • 文章标题:【编译原理】NULLABLE/FIRST/FOLLOW三大集
  • 文章链接:https://blog.canye365.cn/archives/328.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021