本系列為個(gè)人編譯原理學(xué)習(xí)筆記，謬誤之處懇請(qǐng)高人指點(diǎn)，感激不盡！

內(nèi)容整理自西安電子科技大學(xué) 王小兵、張南老師的編譯原理課程。

使用預(yù)測(cè)分析器的自上而下分析

使用預(yù)測(cè)分析器進(jìn)行的自上而下分析是非遞歸的。預(yù)測(cè)分析器模型其實(shí)是一種 PDA（下推自動(dòng)機(jī)，Pushdown Definite Automata），其結(jié)構(gòu)如下圖所示

上圖中的“有限狀態(tài)轉(zhuǎn)移控制”類(lèi)似于詞法分析中的自動(dòng)機(jī)。下推自動(dòng)機(jī)在單純的自動(dòng)機(jī)旁增加了一個(gè)下推棧。將該模型進(jìn)一步具體化，即得到預(yù)測(cè)分析器模型，如下圖所示。

這里的“驅(qū)動(dòng)器”，是一個(gè)能夠控制讀寫(xiě)頭讀取輸入記號(hào)流中記號(hào)的算法，該算法要綜合讀到的記號(hào)、下推棧情況和預(yù)測(cè)分析表的內(nèi)容，來(lái)修改符號(hào)棧和控制輸出。

PDA 可以識(shí)別形如 ：ωcω^r 的串，這樣的串是 DFA 無(wú)法識(shí)別的，這類(lèi)串也無(wú)法使用正規(guī)式進(jìn)行描述。（ ω^r 的意思是終結(jié)符序列 ω 的反轉(zhuǎn)形式，比如 ababcbaba）。而對(duì)于形如 CSG 那種的 ωcω 串，則 PDA 也無(wú)法進(jìn)行識(shí)別。

預(yù)測(cè)分析器通過(guò)【格局與格局的變換】進(jìn)行分析。

格局

格局是一個(gè)三元組 (棧頂元素^top，剩余輸入^ip，改變格局的動(dòng)作)，改變格局的動(dòng)作通過(guò)查表確定，具體動(dòng)作包括：展開(kāi)非終結(jié)符、匹配終結(jié)符、報(bào)告分析成功（^top= ^ip=#）、報(bào)告出錯(cuò)（遇到上述情況之外的其他情況，要調(diào)用錯(cuò)誤恢復(fù)例程）

我們可以將預(yù)測(cè)分析器看作一個(gè)逐步運(yùn)行（Step）的機(jī)器，每一個(gè) step 都會(huì)讓預(yù)測(cè)分析器到達(dá)一個(gè)新的 格局 ，直到到達(dá)接收格局為止（或者到達(dá)出錯(cuò)格局，即發(fā)現(xiàn)語(yǔ)法錯(cuò)誤。比如推出來(lái)的終結(jié)符和讀寫(xiě)頭讀到的終結(jié)符不一樣，或者棧頂和讀寫(xiě)頭當(dāng)前指向的終結(jié)符所對(duì)應(yīng)的預(yù)測(cè)分析表元素為空）

使用預(yù)測(cè)分析器進(jìn)行分析的實(shí)例

預(yù)測(cè)分析器需要借助預(yù)測(cè)分析表來(lái)構(gòu)造語(yǔ)法分析樹(shù)。

在進(jìn)行語(yǔ)法分析時(shí)，預(yù)測(cè)分析器根據(jù)符號(hào)棧（下推棧）棧頂元素和驅(qū)動(dòng)器讀寫(xiě)頭指向的記號(hào)流中的記號(hào)來(lái)查詢預(yù)測(cè)分析表，根據(jù)預(yù)測(cè)分析表中對(duì)應(yīng)項(xiàng)的情況來(lái)決定下一步的操作。預(yù)測(cè)分析表形式如下：

預(yù)測(cè)分析表的行首是非終結(jié)符，列首是終結(jié)符。

• 當(dāng)棧頂是非終結(jié)符時(shí)，展開(kāi)：需要根據(jù)預(yù)測(cè)分析表查到候選項(xiàng)，然后使用該候選項(xiàng)來(lái)展開(kāi)棧頂?shù)姆墙K結(jié)符——彈出棧頂非終結(jié)符，將表中的對(duì)應(yīng)項(xiàng)逆序壓入到下推棧中（注意順序，產(chǎn)生式右部是反著壓進(jìn)去的，因?yàn)榭傄３謴淖蟮接彝茖?dǎo)）。
• 當(dāng)棧頂時(shí)終結(jié)符時(shí)，匹配：若此時(shí)棧頂?shù)慕K結(jié)符與驅(qū)動(dòng)器讀寫(xiě)頭讀到的終結(jié)符相同，則將該棧頂元素彈出，同時(shí)讀寫(xiě)頭向后移動(dòng)一個(gè)記號(hào)。

對(duì)于消除了左遞歸和公共左因子的如下 CFG，我們可以根據(jù)其來(lái)構(gòu)造一個(gè)預(yù)測(cè)分析表（具體構(gòu)造方式留到后面再說(shuō)）

L → E;L|ε
E → TE'
E' → +TE'|-TE'|ε
T → FT'
T' → *FT'|/FT'|mod FT'|ε
F → (E)|id|num

我們根據(jù)如下算法，來(lái)進(jìn)行非遞歸預(yù)測(cè)分析

其實(shí)，就是重復(fù)進(jìn)行這樣的操作：根據(jù)讀寫(xiě)頭指向的終結(jié)符、棧頂元素查預(yù)測(cè)分析表，不斷把表中查到的元素壓入棧頂。因?yàn)槭菑拈_(kāi)始符號(hào)開(kāi)始推導(dǎo)的，所以棧中會(huì)出現(xiàn)【根據(jù)預(yù)測(cè)分析表查到新的非終結(jié)符入棧】的情況。如果推導(dǎo)時(shí)棧頂是非終結(jié)符，則讀寫(xiě)頭不需要移動(dòng)，一直指向之前停下的位置。但隨著推導(dǎo)的進(jìn)行，非終結(jié)符終究會(huì)推出終結(jié)符（這個(gè)終結(jié)符也要和前面非終結(jié)符一樣，被壓入棧），如果這個(gè)推導(dǎo)出來(lái)的、當(dāng)前正好在下推棧棧頂?shù)慕K結(jié)符和讀寫(xiě)頭指向的符號(hào)相同，那么就是【匹配上了】

下圖說(shuō)明了【棧頂是非終結(jié)符時(shí)，進(jìn)行展開(kāi)】的過(guò)程，執(zhí)行非遞歸預(yù)測(cè)算法插圖中的第二個(gè)紅色虛線框內(nèi)的代碼：

下圖同時(shí)說(shuō)明了【棧頂是非終結(jié)符時(shí)，進(jìn)行展開(kāi)】和【棧頂是終結(jié)符時(shí)，進(jìn)行匹配】的過(guò)程。對(duì)于后一個(gè)過(guò)程，執(zhí)行非遞歸預(yù)測(cè)算法插圖中的第一個(gè)紅色虛線框內(nèi)的代碼：

FIRST、FOLLOW 集合的構(gòu)造

預(yù)測(cè)分析表，其實(shí)是一個(gè)【為我們指明推導(dǎo)的方向】的工具。那么如何構(gòu)造這個(gè)工具呢？

構(gòu)造過(guò)程分為兩步：1. 根據(jù)文法給出的產(chǎn)生式構(gòu)造 FIRST、FOLLOW 集合，2. 根據(jù)這兩個(gè)集合來(lái)構(gòu)造預(yù)測(cè)分析表。

因此，F(xiàn)IRST、FOLLOW 集合的構(gòu)造是這里的重中之重。

我們根據(jù)下面的塊中的產(chǎn)生式來(lái)學(xué)習(xí)這兩個(gè)集合

FIRST 集合

文法符號(hào)序列 α 的 FIRST 集合為： FIRST(α) = { a | α=> a...，a ∈ T }，若 α=>ε ，則 ε ∈ FIRST(α)

說(shuō)白了，F(xiàn)IRST(α) 就是 α 能推出來(lái)的所有串（aka. 文法符號(hào)序列）中的第一個(gè)終結(jié)符的集合。如果從某個(gè)非終結(jié)符開(kāi)始，一步推不到終結(jié)符，那就多推幾次。如果直接推出來(lái)個(gè) ε，就把 ε 也加入當(dāng)前 FIRST 集合。

我們以對(duì)上面寫(xiě)的產(chǎn)生式求 FIRST 集合為例，來(lái)了解怎么求 FIRST 集合。

1. 求 FIRST 集合的過(guò)程要順著我們的一堆產(chǎn)生式從下向上進(jìn)行，也就是先求 FIRST(F)，最后求 FIRST(L)。對(duì)于產(chǎn)生式 F → (E)|id|num，容易看出， F 經(jīng)過(guò)一步推導(dǎo)能推出的所有串的第一個(gè)終結(jié)符有：(、id、num，因此 FIRST(F) = { (, id, num }；
2. 對(duì)于產(chǎn)生式 T' → *FT'|/FT'|mod FT'|ε，T' 經(jīng)過(guò)一步推導(dǎo)能推出的所有串的第一個(gè)終結(jié)符有：*、/、mod。而又因?yàn)?T' 能夠直接一步推導(dǎo)出 ε，所以 ε 也要加入到 FIRST(T') 中，即 FIRST(T') = {*, /, mod, ε}；
3. 對(duì)產(chǎn)生式 T → FT'，T 沒(méi)有一步推導(dǎo)就能得到的終結(jié)符，所以要繼續(xù)推導(dǎo)，再推導(dǎo)一步會(huì)得到：T=>FT'=>(E)T' 或 T=>FT'=>idT' 或 T=>FT'=>numT'，由此我們可以看到，T 經(jīng)過(guò)兩步推導(dǎo)能夠推導(dǎo)出的第一個(gè)終結(jié)符有：(、id、num，（由于 F 推不出 ε，也就是說(shuō) F 無(wú)法被穿透，因此關(guān)于從 T 經(jīng)過(guò)推導(dǎo)推出的第一個(gè)終結(jié)符就都和 F 的終結(jié)符相同了），因此 FIRST(T) = FIRST(F) = { (, id, num }；
4. 對(duì)于產(chǎn)生式 E' → +TE'|-TE'|ε ，與上面的 2 同理，可得 FIRST(E') = { +, -, ε }；
5. 對(duì)于產(chǎn)生式 E → TE'，與上面的 3 同理，可得 FIRST(E) = FIRST(T) = FIRST(F) = { (, id, num }
6. 對(duì)于產(chǎn)生式 L → E;L|ε，要結(jié)合上面的 3 和 2 一起理解。首先該產(chǎn)生式可以經(jīng)過(guò)多步推導(dǎo)后得到終結(jié)符，這個(gè)和 3 同理。然后，該產(chǎn)生式本身也能推出 ε，這與 2 同理。最終可得：FIRST(T) = { ε, (, id, num }

即，最終可得：

FIRST(F/T/E) = { (  id  num }
FIRST(T’) = { *  /  mod  ε }
FIRST(E’) = { + -  ε }
FIRST(L)  = { ε  (  id  num }

FOLLOW 集合

非終結(jié)符 A 的 FOLLOW 集合如下： FOLLOW(A) = { a | S=*> ...Aa...，a∈T }，若 A 是某句型的最右符號(hào)，則 #∈FOLLOW(A)

說(shuō)白了，就是從開(kāi)始符號(hào)可以導(dǎo)出的所有含 A 的文法符號(hào)序列中 A 之后的終結(jié)符。

舉個(gè)例子的話大概是：FOLLOW(A) 是終結(jié)符的集合，從開(kāi)始符號(hào)開(kāi)始，經(jīng)過(guò)多步推導(dǎo)得到的句型中有【Aa】，則FOLLOW集合中的元素就是這些 a。想要真正理解 FOLLOW 集合，建議嘗試在腦內(nèi)畫(huà)一個(gè)下推棧進(jìn)行推導(dǎo)（如果腦補(bǔ)不出來(lái)，那耐心點(diǎn)一步步畫(huà)在紙上也是不錯(cuò)的選擇），這樣會(huì)簡(jiǎn)單許多。

我們以對(duì)上面寫(xiě)的產(chǎn)生式求 FOLLOW 集合為例，來(lái)了解怎么求 FOLLOW 集合。

1. 求 FOLLOW 集合的過(guò)程要順著產(chǎn)生式從上往下進(jìn)行，也就是先求 FOLLOW(L)，最后求 FOLLOW(F)。首先求第一個(gè)產(chǎn)生式 L → E;L|ε 左部的非終結(jié)符 L 的 FOLLOW 集合 FOLLOW(L)。
   因?yàn)槲覀兿胍獙ふ业氖窃诮?jīng)過(guò)推導(dǎo)后跟在 L 后面的終結(jié)符，因此我們要首先掃一眼全部的產(chǎn)生式，看看 L 都在哪些產(chǎn)生式中出現(xiàn)過(guò)以獲取線索。很不幸，只在第一個(gè)產(chǎn)生式中出現(xiàn)過(guò)……如果選擇 E;L 進(jìn)行推導(dǎo)將導(dǎo)致 L 的遞歸——也就是說(shuō)若只用這個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，無(wú)論怎么推都永遠(yuǎn)推不出一個(gè)緊隨 L （除了#之外）的終結(jié)符，最終還是要面對(duì)只有 L 的問(wèn)題。而若選擇 ε 展開(kāi) L 則會(huì)導(dǎo)致 L 的穿透，暴露出文法的結(jié)束符號(hào) # ，因此 FOLLOW(L) = {#}；

2. 再來(lái)看第二個(gè)產(chǎn)生式 E → TE'，這一步我們求該產(chǎn)生式左部的非終結(jié)符 E 的 FOLLOW 集合 FOLLOW(E)。 因?yàn)槲覀兿胍獙ふ业氖窃诮?jīng)過(guò)推導(dǎo)后跟在 E 后面的終結(jié)符，因此我們先來(lái)整體看一下所有的產(chǎn)生式?？梢园l(fā)現(xiàn)非終結(jié)符 E 在第一行的產(chǎn)生式 L → E;L|ε 和最后一行的產(chǎn)生式 F → (E)|id|num 中都有出現(xiàn)。產(chǎn)生式 L → E;L|ε 說(shuō)明，從開(kāi)始符號(hào) L 開(kāi)始，經(jīng)過(guò)一步推導(dǎo)得到 E;L ，即 L=*>...E;...因此我們要將 ; 加入到 FOLLOW(E) 中 。此外，我們還可以發(fā)現(xiàn)在最后一個(gè)產(chǎn)生式 F → (E)|id|num 中，E 后面接上了終結(jié)符 )，這說(shuō)明，從開(kāi)始符號(hào) L 開(kāi)始，經(jīng)過(guò)多步推導(dǎo)，可以出現(xiàn)某一刻將 F 用 (E) 展開(kāi)的情況——即：L=*>...(E)...，因此我們要將 ) 加入到FOLLOW(E) 中。除了這兩個(gè)產(chǎn)生式之外，再也沒(méi)有其他右部包含 E 的產(chǎn)生式，也就是說(shuō)我們找完了 E 后面緊跟終結(jié)符的所有情況，故得到：FOLLOW(E) = { ;, ) }；

3. 再看第三個(gè)產(chǎn)生式 E' → +TE'|-TE'|ε ，這一步求 FOLLOW(E')。 經(jīng)過(guò)觀察，我們發(fā)現(xiàn)除了這個(gè)產(chǎn)生式本身，只有第二行的 E → TE' 中出現(xiàn)了 E' 。通過(guò)觀察這兩個(gè)產(chǎn)生式，我們可以發(fā)現(xiàn)：下推棧中的 E' 只有一個(gè)來(lái)源，就是被使用 E → TE' 展開(kāi) E 而來(lái)。那也就是說(shuō)，之前在下推棧中【位于 E 下面的非終結(jié)符】將被 E' “繼承”

4. 下面來(lái)看第四個(gè)產(chǎn)生式 T → FT' ，這一步求 FOLLOW(T)。 我們發(fā)現(xiàn) T 還出現(xiàn)在第二個(gè)產(chǎn)生式 E → TE' 中，因此要將 FIRST(E') 加入到 FOLLOW(T) 中。而又因?yàn)?E' 可穿透，因此也要考慮 E' 穿透的情況，故要將 FOLLOW(E) 也加入到 FOLLOW(T) 中。另外，因?yàn)?FOLLOW 集合中不能包含 ε，故 ε 不能被加入到 FOLLOW(T) 中。最后，FOLLOW(T) = { +, -, ;, ) }

5. 第五個(gè)產(chǎn)生式 T' → *FT'|/FT'|mod FT'|ε ，這一步求 FOLLOW(T')。 與上面的 3 同理，F(xiàn)OLLOW(T) 被 FOLLOW(T') ”繼承“，得到 FOLLOW(T') = FOLLOW(T) = {+, -, ;, ) }

6. 第六個(gè)產(chǎn)生式 F → (E)|id|num ，這一步求 FOLLOW(F)。 由產(chǎn)生式 T' → \*FT'|/FT'|mod FT'|ε 可知，F(xiàn)IRST(T') 應(yīng)被加入 FOLLOW(F)。而 T' 可穿透，故 FOLLOW(T') 也應(yīng)被加入 FOLLOW(F)。因此，FOLLOW(F) = { *, /, mod, +, -, ;, ) }

即，最終可得：

FOLLOW(L) = { # }
FOLLOW(E/E’) = { )  ; }
FOLLOW(T/T’) = { + - ; ) }
FOLLOW(F) = { + -  *  /  mod  )  ; }