如何理解自頂向下分析中的First表和Follow表?

---

要理解一個概念，第一步先要知道人們為什麼要發明這個概念：

目的1：first set 和follow set 的作用都是為了計算predict set（predict set 在有些書中叫做LL table）。

目的2：predict set 是預測分析（predict parsing）的核心。我在 shift reduce，預測分析，遞歸下降分析（這是解析方法）和LL(K) LR(K) SLR以LALR的關係？ - 彭飛的回答 這個回答中提到：LL通過預測驅動，而LR通過預測來解決衝突

這裡我給個書上的例子（圖片盜自《Language Implementation Patterns》)：

這個LL parser 對應的grammar 是：

可以看到有三個產生式可以產生stat 這個非終結符（這裡的stat 是開始符號）。換句話說LL parser 在自頂向下分析的過程中：1）predict：先確定要生成的非終結符，即語法樹節點類型，2）match：再根據已經確定的非終結符去匹配（展開）到下一層。

在這個例子中，我們從stat 開始，要確定stat 展開到下一步三個選項中的哪一個（也就是說這裡需要一個語句，但具體是哪種語句呢？），這時就要用if 來根據每個產生式的predict set 來判斷這裡到底需要哪種stat。可以從代碼中看出returnstat的predict set 是{『return』}，assign的是{id}，ifstat 的是{『if』}。而且這三個產生式的predict set 沒有任何交集，if 語句只需要比對下一個輸入符號就可以確定需要產生的非終結符，這就叫做LL(1)第二步，當理解了這個概念的意圖之後就要學習它在任意例子上的應用了。因為現實中的編程語言不可能像上面的例子一樣簡單，我們需要一套形式化的演算法來計算first set，follow set，然後進一步計算predict set

這裡我直接放一個我們上課時用的handout，簡單明了：

這裡有幾個點需要注意一下：

1. 對於任意符號串（非終結符和終結符）都存在first set。圖中大寫字母N 表示非終結符，小寫字母x 表示終結符，希臘字母代表任意串；

2. 每一個非終結符才有follow set；

3. 每一個獨立的產生式都有一個predict set；

4. 重點是那個小黑點運算符，他也揭示了predict set 的本質。即當N 的產生式體不能為空時，我們只需要根據接下來輸入的最開頭（first）就可以判斷需要產生哪個N（就像上面的例子一樣），而當N 的產生式體可以為空時，接下來的輸入中有可能就根本不包含N 這個部分，但作為語法樹的一部分我們任然需要它，所以還要看看N 可能會被哪些符號跟隨（follow），如果下一個輸入是follow set 中的元素，我們就可以規約出一個空的N。

---

看了題主問了不少關於編譯原理方面的問題。而這些絕大多數能在書中找到，個人認為一個人通過看書而獲得知識的能力是個人學習能力重要的組成部分。所以題主應該沉下心來，仔細看書或者Google，培養自學能力。（將來工作後，如果還這樣毛毛糙糙，隨隨便便遇到一個新知識點就像別人尋求答案？你要別人怎麼想。）

---

我理解的：First表示展開，Follow表示收縮。（撇太小了，不明顯，改中文並加粗。）

First表可以告訴你，在expr_E狀態下，你token獲取到的是id，這時候會在expr_E中調用expr_T，在expr_T中調用expr_F，相當於構建（展開）一顆的樹，從expr_F返回後，掃描下一個token，並進入expr_T撇，加入這時候掃描的是一個token +，在狀態T撇下，+是T撇的一個Follow，這時候就要從expr_T撇返回（收縮），一直返回到E。

這時候進入出E-&>TE撇中的E撇，在E撇中，+是First (E撇)，因此構造出下面那顆樹。

E
/
T
/
F T
/
id

E
/
T E
/ / |
F T + T E
/ |
id NULL


---

推薦閱讀：