一、Follow集概述
1、Follow集是什么
Follow集是在编译原理中，指的是文法符号的后跟的可能出现的全部终结符，包括空串 ε。
2、Follow集的作用
在语法分析时，Follow集可以被用来在语法树中自下而上地删除非法的叶子节点，从而构造正确的语法树。更具体地说，Follow集能够用于消除二义性、判断语法错误和及时地探测错误。
3、如何计算Follow集
Follow集的计算需要先计算出所有非终结符的 First 集，然后再通过一定的规则来计算 Follow 集。通常在文法的起始符号后加上一个$，再将$加入到起始符号的Follow集合中。接下来，可以通过以下步骤来进行计算：
① 如果有一条产生式 B->αAβ （其中，α和β可能为空串） ，则把Follow(B)加入到Follow(A)中；
② 如果有一条产生式 B->αA ，或者 A 是文法的开始符号，则把Follow(B)加入到Follow(A)中。
根据这两条规则，按照从第①步开始迭代的顺序，不断地更新非终结符的Follow集。
二、关于Follow集的应用
1、错误分析
在语法分析的过程中，如果我们发现某个非终结符 A 的 Follow 集中包含了某个终结符 t，而 A 无法推导成以 t 开头的字符串，则说明语法分析中存在错误。
2、二义性处理
在 Follow 集的帮助下，我们可以消除语法分析中的二义性。例如，在 E->E+T | T 这个文法中，E 和 T 都可以根据后面的文本解析出两种不同的树，从而导致二义性。但是，如果我们在 Follow 集中加入+和-操作符，则在构建语法树时就无法出现这种歧义。
3、语法树构建
在从左至右和从右至左语法分析算法中，我们可以通过 Follow 集来消除非法的语法结构。如果某个非终结符 A 的 Follow 集中包含了某个终结符 t，而 A 无法推导成以 t 开头的字符串，那么在语法树构建时就应该删除这个非法的叶子节点，从而构造出正确的语法树结构。
三、计算Follow集示例代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 200, M = 30;
char first[N][M], follow[N][M];
struct rule {
int to, next;
char c;
} e[N];
int head[N], cnt;
void add(int from, int to, char c) {
cnt++;
e[cnt].to = to, e[cnt].c = c, e[cnt].next = head[from], head[from] = cnt;
}
void first_calc(int u) {
if (first[u][0])
return;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == u)
continue;
first_calc(v);
if (e[i].c != '#')
for (int j = 0; first[v][j]; j++)
first[u][strlen(first[u])] = first[v][j];
else {
bool flag = 1;
for (int j = i + 1; flag && j <= cnt; j++)
if (e[j].to == u && e[j].c != '#')
for (int k = 0; first[e[j].to][k]; k++)
first[u][strlen(first[u])] = first[e[j].to][k];
else if (e[j].to != u || e[j].c == '#')
flag = 0;
if (flag)
first[u][strlen(first[u])] = '#';
}
}
}
void follow_calc(int u) {
if (follow[u][0])
return;
follow[u][strlen(follow[u])] = '$';
for (int i = 1; i <= cnt; i++) {
if (e[i].to == u || e[i].to != -1 && !strcmp(first[e[i].to], "$") || !strchr(follow[e[i].to], e[i].c))
continue;
if (e[i].c != '#')
for (int j = 0; first[e[i].to][j]; j++)
follow[u][strlen(follow[u])] = first[e[i].to][j];
else
follow_calc(e[i].to);
}
for (int i = 1; i <= cnt; i++)
if (e[i].to == u && e[i].c != '#')
follow_calc(i);
}
int main() {
int n;
cin >> n;
getchar();
char c = getchar();
int u = c - 'A', last = u;
getchar(); getchar();
while (--n) {
c = getchar();
if (c == '\n')
c = getchar();
if (c == '|')
u = last;
else if (isupper(c)) {
last = c - 'A';
if (head[last] == 0)
memset(first[last], '$', sizeof(first[last]));
}
else
add(last, ++cnt, c);
}
memset(first[u], '$', sizeof(first[u]));
first_calc(u);
follow_calc(u);
for (int i = 0; i <= cnt; i++) {
printf("%c->", 'A' + i);
for (int j = head[i]; j; j = e[j].next)
printf("%c", e[j].c);
printf("\nfirst集：{");
for (int j = 0; first[i][j]; j++)
printf("%c ", first[i][j]);
printf("}\nfollow集：{");
for (int j = 0; follow[i][j]; j++)
printf("%c ", follow[i][j]);
printf("}\n\n");
}
return 0;
}
