First Set 与 Follow Set

发表于 分类于 本文字数： 1.3k 阅读时长 ≈ 5 分钟
编译原理之语法分析：First Set 与 Follow Set 求解。

为什么需要

First Set？

如果编译器事先知道 “应用 production 规则时产生的字符串的第一个字符是什么”，并将其与输入字符串中的当前字符或标记进行比较，它就可以明智地决定应用哪条 production 规则。

举个例子：

1
2
3
S -> cAd
A -> bc | a
And the input string is "cad".

因此，在上面的例子中，如果它知道在读取输入字符串中的字符 c 并应用 S -> cAd 后，输入字符串中的下一个字符是 a，那么它就会忽略生产规则 A -> bc（因为 b 是这个生产规则产生的字符串的第一个字符，而不是 a），而直接使用生产规则 A -> a（因为 a 是这个生产规则产生的字符串的第一个字符，并且与输入字符串的当前字符相同，也是 a）。
因此，我们可以验证，如果编译器 / 解析器知道应用生产规则可以获得字符串的第一个字符，那么它就可以明智地应用正确的生产规则来获得给定输入字符串的正确语法树。

Follow Set？

1
2
3
A -> aBb
B -> c | ε
And suppose the input string is "ab" to parse.

由于输入的第一个字符是 a，解析器应用 A -> aBb 的规则。

1
2
3
    A
  / |  \
a   B   b

现在，解析器检查输入字符串的第二个字符，即 b，要派生的非终结符是 B，但解析器不能从 B 中得到任何包含 b 作为第一个字符的可派生字符串。
但是语法中确实包含了一个生产规则 B -> ε，如果应用该规则，那么 B 将消失，解析器得到输入 ab，如下图所示。但是，只有当解析器知道生产规则中 B 后面的字符与输入中的当前字符相同时，才能应用该规则。

在 A -> aBb 的 RHS 中，b 跟随非终结符 B，即 FOLLOW(B) = {b}，当前读到的输入字符也是 b，因此解析器应用这个规则。并且能够从给定的语法中得到字符串 ab。

1
2
3
4
5
     A                    A
  /  |  \              /    \
a    B    b    =>     a      b
     |
     ε

所以 FOLLOW Set 可以使非终结符在需要时消失掉，以便从解析树中生成字符串。

结论是，我们需要为一个给定的语法找到 First Set 和 Follow Set，这样解析器才能在正确的位置正确地应用所需的规则。

语法分析中的 First Set

语法符号 X 的 FIRST(X) 是从 X 派生的字符串开始的终结符集合。

计算规则

  1. If x is a terminal, then FIRST(x) = { 'x' }
  2. If X -> ε is a production rule, then add ε to FIRST(X).
  3. If X -> Y1 Y2 Y3 … Yn is a production
    1. FIRST(X) = FIRST(Y1)
    2. If FIRST(Y1) contains ε then FIRST(X) = { FIRST(Y1) – ε } U { FIRST(Y2) }
    3. If FIRST (Yi) contains ε for all i = 1 to n, then add ε to FIRST(X)

例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Production Rules of Grammar
E  -> TE’
E’ -> +T E’ | ε
T  -> F T’
T’ -> *F T’ | ε
F  -> (E) | id

FIRST sets
FIRST(E)  = FIRST(T)
          = { ( , id }
FIRST(E’) = { +, ε }
FIRST(T)  = FIRST(F)
          = { ( , id }
FIRST(T’) = { *, ε }
FIRST(F)  = { ( , id }

例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Production Rules of Grammar
S -> ACB | CbB | Ba
A -> da | BC
B -> g | ε
C -> h | ε

FIRST sets
FIRST(ACB) = FIRST(A) - {ε} U FIRST(CB)
           = FIRST(A) - {ε} U FIRST(C) - {ε} U FIRST(B)
           = { d, g, h, ε }
FIRST(CbB) = FIRST(C) - {ε} U {b}
           = { h, b }
FIRST(Ba)  = FIRST(B) - {ε} U {a}
           = { g, a }

FIRST(S) = FIRST(ACB) U FIRST(CbB) U FIRST(Ba)
         = { d, g, h, ε, b, a}
FIRST(A) = { d } U FIRST(B) - {ε} U FIRST(C)
         = { d, g, h, ε }
FIRST(B) = { g, ε }
FIRST(C) = { h, ε }

语法分析中的 Follow Set

Follow（X）是可以以某种句子形式立即出现在非终结符 X 右侧的一组终结符。

例子：

1
2
3
4
5
6
7
8
9
10
S -> Aa | Ac
A -> b

      S                  S
     /  \              /   \
    A    a            A     c
    |                 |
    b                 b

Here, FOLLOW (A) = {a, c}

规则

  1. FOLLOW(S) = { $ } S is the starting Non-Terminal
  2. If A -> pB is a production, then everything in FOLLOW(A) is in FOLLOW(B)
  3. If A -> pBq is a production, where p , B and q are any grammar symbols, then everything in FIRST(q) except ε is in FOLLOW(B)
  4. If A -> pBq is a production and FIRST(q) contains ε , then FOLLOW(B) contains { FIRST(q) – ε } U FOLLOW(A)

例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Production Rules:
E  -> TE’
E’ -> +T E’ | ε
T  -> F T’
T’ -> *F T’ | ε
F  -> (E) | id

FIRST set
FIRST(E)  = { ( , id }
FIRST(E’) = { +, ε }
FIRST(T)  = { ( , id }
FIRST(T’) = { *, ε }
FIRST(F)  = { ( , id }

FOLLOW Set
FOLLOW(E)  = { $ } U FIRST( ')' )
           = { $, ) }
FOLLOW(E’) = FOLLOW(E)
           = {  $, ) }
FOLLOW(T)  = { FIRST(E’) – ε } U FOLLOW(E’) U FOLLOW(E)
           = { +, $, ) }
FOLLOW(T’) = FOLLOW(T)
           = { +, $ , ) }
FOLLOW(F)  = { FIRST(T’) –  ε } U FOLLOW(T’) U FOLLOW(T)
           = { *, +, $, ) }

例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Production Rules:
S -> aBDh
B -> cC
C -> bC | ε
D -> EF
E -> g | ε
F -> f | ε

FIRST set
FIRST(S) = { a }
FIRST(B) = { c }
FIRST(C) = { b, ε }
FIRST(D) = { FIRST(E) – ε } U FIRST(F)
         = { g, f, ε }
FIRST(E) = { g, ε }
FIRST(F) = { f, ε }

FOLLOW Set
FOLLOW(S) = { $ }
FOLLOW(B) = FIRST(Dh)
          = { FIRST(D) – ε } U FIRST(h)
          = { g, f, h }
FOLLOW(C) = FOLLOW(B)
          = { g, f, h }
FOLLOW(D) = FIRST(h)
          = { h }
FOLLOW(E) = { FIRST(F) – ε } U FOLLOW(D)
          = { f, h }
FOLLOW(F) = FOLLOW(D)
          = { h }

例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Production Rules:
S -> ACB | CbB | Ba
A -> da | BC
B -> g | ε
C -> h | ε

FIRST set
FIRST(S) = { d, g, h, ε, b, a}
FIRST(A) = { d, g, h, ε }
FIRST(B) = { g, ε }
FIRST(C) = { h, ε }

FOLLOW Set
FOLLOW(S) = { $ }
FOLLOW(A) = { FIRST(CB) - ε } U FOLLOW(S)
          = { FIRST(C) - ε } U { FIRST(B) – ε } U FOLLOW(S)
          = { h, g, $ }
FOLLOW(B) = FOLLOW(S) U FIRST(a) U { FIRST(C) – ε } U FOLLOW(A)
          = { $, a, h, g }
FOLLOW(C) = { FIRST(B) – ε } U FOLLOW(S) U FIRST(b) U FOLLOW(A)
          = { g, $, b, h }

参考