2 FIRST和FOLLOW集合
自顶向下和自底向上的语法分析器都可以用 FIRST 和 FOLLOW 函数来实现。
开始符号集
- 对于文法的某个句型 \alpha，其开始符号集合 FIRST(\alpha) 是说，当这个句型经过若干次推导后，不以非终结符打头了，换言之是以某个终结符 b 打头的，那么这个终结符 b\in FIRST(\alpha)，后者就是由所有这样的 b 组成的。
- FIRST(\alpha)=\{a|\alpha\Rightarrow^*a...,a\in V_T\}\cup\{\varepsilon|\alpha\Rightarrow^*\varepsilon\}
- 即：\alpha 推出的非空串中首终结符和 \alpha 推出空串时的 \varepsilon 组成的集合。
- 如果 \alpha\Rightarrow^*\varepsilon，则规定 \varepsilon\in FIRST(\alpha)；
- 如果对于 A 的任何两个选择 \alpha_i,\alpha_j，其开始符号集合都不相交，那么每次看到一个终结符 a（每次 getToken）都可以做一定正确的选择，这个选择就是满足 a\in FIRST(\alpha) 的那个 \alpha。
- 用提左因子的办法，可以把所有可能导致开始符号集合相交的那些选择合并为一个选择，直到他们分道扬镳。
计算 FIRST(X)，X 是某个终结符或非终结符
如果 X 是某个终结符，则 FIRST(X)=\{X\}
如果 X 是某个非终结符，遍历所有其产生式 X→Y_1Y_2...Y_k，递归计算每一个产生式中的每一个 FIRST(Y_i)，这很容易做到
-
要么全都包含空 \varepsilon（FIRST(X)=FIRST(X)\cup\varepsilon）
-
要么出现了某个满足条件的非终结符 a（FIRST(X)=FIRST(X)\cup a）
如果 X 是某个非终结符，且某个产生式是 X→\varepsilon，则直接 FIRST(X)=FIRST(X)\cup\varepsilon
计算 FIRST(X_1...X_n)，其中每个 X_i 都是某个终结符或非终结符
结果按下面的步骤来获得：
-
FIRST(X_1) 中的所有非 \varepsilon 符号
-
如果 \varepsilon 在 FIRST(X_1),...,FIRST(X_i) 中，那么应当把上面的下标 1 改成 i+1
-
如果所有的 FIRST(X_i) 都只有 \varepsilon，最终的结果也只有它
例子
对下面文法的每个非终结符求 FIRST 集合
- E→TE'
- E'→+TE'|\varepsilon
- T→FT'
- T'→*FT'|\varepsilon
- F→(E)|\textbf{id}
这里采用一种自下而上的求法，避免从上而下导致分支。
（1）FIRST(F)=\{(,\textbf{id}\}；
（2）FIRST(T')=\{*,\varepsilon\}；
（3）FIRST(T)=FIRST(F)；
（4）FIRST(E')=\{+,\varepsilon\}；
（5）FIRST(E)=FIRST(T)；
后继符号集
FOLLOW(A) 被定义为可能在某些句型中紧跟在 A 右边的终结符的集合。
计算 FOLLOW(A)，A 是某个非终结符
不断应用下属规则，直到没有新的终结符可以加入到任意 FOLLOW 集合中为止。
-
如果 A 是开始符号 S，把 \$ 加入 FOLLOW(A) 中
-
如果 A→\alpha B\beta，则将 FIRST(\beta) 除 \epsilon 外的符号加入到 FOLLOW(B)
-
如果 A→\alpha B 或者 A→\alpha B\beta，\varepsilon \in FIRST(\beta)，则将 FOLLOW(A) 加入到 FOLLOW(B)