深入理解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;
}