深入理解Follow集

一、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 
#include 
#include 

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 > 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 ", '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;
}