遞歸的預(yù)測(cè)分析法

遞歸的預(yù)測(cè)分析法是指：在遞歸下降分析中，根據(jù)預(yù)測(cè)分析表進(jìn)行產(chǎn)生式的選擇。根據(jù)每個(gè)非終結(jié)符的產(chǎn)生式和LL(1)文法的預(yù)測(cè)分析表，為每個(gè)非終結(jié)符編寫對(duì)應(yīng)的過程：

過程.png

主過程.png

PROGRAM表示為程序，其中program與end為關(guān)鍵字。DELIST表示標(biāo)識(shí)符的序列。STLIST表示語句的序列，s表示語句。

PROGRAM的過程.png

DECLIST的過程.png

DECLISTN的過程.png

STLIST的過程.png

STLISTN的過程.png

TYPE的過程.png

若過程中不發(fā)生錯(cuò)誤則說明輸入是符號(hào)文法的。

非遞歸的預(yù)測(cè)分析法

非遞歸的預(yù)測(cè)分析不需要為每個(gè)非終結(jié)符編寫遞歸下降過程，而是根據(jù)預(yù)測(cè)分析表構(gòu)造一個(gè)自動(dòng)機(jī)，也叫表驅(qū)動(dòng)的預(yù)測(cè)分析。

自動(dòng)機(jī).png

下推自動(dòng)機(jī)比有窮自動(dòng)機(jī)識(shí)別能力更強(qiáng)，有窮自動(dòng)機(jī)的識(shí)別能力不強(qiáng)是因?yàn)槠渥R(shí)別能力不強(qiáng)。如若想識(shí)別上圖例子中語言的句子，就需要讀入a的個(gè)數(shù)。但有窮自動(dòng)機(jī)不具備專門的存儲(chǔ)器因此它利用不同的狀態(tài)記錄a的個(gè)數(shù)n。但n是趨于無窮而有窮自動(dòng)機(jī)的狀態(tài)數(shù)是有窮的，這就導(dǎo)致有窮自動(dòng)機(jī)無法識(shí)別這樣的語言。

非遞歸的預(yù)測(cè)分析法.png

上圖輸出的產(chǎn)生式序列就相當(dāng)于一個(gè)最左推導(dǎo)

表驅(qū)動(dòng)的預(yù)測(cè)分析法

輸入：一個(gè)串w和文法G的分析表M
輸出：如果w 在L(G) 中，輸出w的最左推導(dǎo)；否則給出錯(cuò)誤提示
方法：最初，語法分析器的格局如下：輸入緩沖區(qū)中是w$ ，G的開始符號(hào)位于棧頂，其下面是$。下面的程序使用預(yù)測(cè)分析表M生成了處理這個(gè)輸入的預(yù)測(cè)分析過程

預(yù)測(cè)分析過程.png

遞歸的預(yù)測(cè)分析法vs.非遞歸的預(yù)測(cè)分析法

遞歸的預(yù)測(cè)分析法vs.非遞歸的預(yù)測(cè)分析法.png

遞歸預(yù)測(cè)分析法是根據(jù)產(chǎn)生式的右部來編寫程序，因此直觀性比較好。

預(yù)測(cè)分析法實(shí)現(xiàn)步驟：

1. 構(gòu)造文法
2. 改造文法：消除二義性、消除左遞歸、消除回溯。
3. 求每個(gè)變量的FIRST 集和FOLLOW 集，從而求得每個(gè)候選式的求得每個(gè)候選式的SELECT 集。
4. 檢查是不是 LL(1) 文法。若是， 構(gòu)造預(yù)測(cè)分析表。
5. 對(duì)于遞歸的預(yù)測(cè)分析，根據(jù)預(yù)測(cè)分析表為每一個(gè)非終結(jié)符編寫一個(gè)過程；對(duì)于非遞歸的預(yù)測(cè)分析，實(shí)現(xiàn)表驅(qū)動(dòng)的預(yù)測(cè)分析算法；

預(yù)測(cè)分析中的錯(cuò)誤處理

預(yù)測(cè)分析中的錯(cuò)誤檢測(cè)

兩種情況下可以檢測(cè)到錯(cuò)誤

• 棧頂?shù)慕K結(jié)符和當(dāng)前輸入符號(hào)不匹配
• 棧頂非終結(jié)符與當(dāng)前輸入符號(hào)在預(yù)測(cè)分析表對(duì)應(yīng)項(xiàng)中的信息為空

預(yù)測(cè)分析中的錯(cuò)誤恢復(fù)

恐慌模式：

1. 忽略輸入中的一些符號(hào)，直到輸入中出現(xiàn)由設(shè)計(jì)者選定的同步詞法單元 (synchronizing token) 集合中的某個(gè)詞法單元。其效果依賴于同步集合的選取。集合的選取應(yīng)該使得語法分析器能從實(shí)際遇到的錯(cuò)誤中快速恢復(fù)。

例如可以把FOLLOW(A)中的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。這么做的原因是當(dāng)棧頂為非終結(jié)符A的時(shí)候檢測(cè)到錯(cuò)誤，說明A在識(shí)別過程中遇到了問題，此時(shí)就會(huì)放棄對(duì)A這個(gè)成分進(jìn)行識(shí)別而從它后面的成分繼續(xù)分析，因此當(dāng)FALLOW(A)符號(hào)出現(xiàn)的時(shí)候就可以立即進(jìn)行同步。此時(shí)將A出棧，從它后面的成分繼續(xù)進(jìn)行分析。

2. 如果終結(jié)符在棧頂而不能匹配，一個(gè)簡(jiǎn)單的辦法就是彈出此終結(jié)符。

同步詞法單元.png

由于E'與T'有空產(chǎn)生式，它們的FOLLOW集中對(duì)應(yīng)的符號(hào)，對(duì)應(yīng)對(duì)空產(chǎn)生式的應(yīng)用，因此它們不作為同步詞法單元。

分析表的使用方法：

• 如果M[A,a ]是空，表示檢測(cè)到錯(cuò)誤，根據(jù)恐慌模式忽略輸入符號(hào)a。
• 如果M[A,a ]是synch，則彈出棧頂?shù)姆墙K結(jié)符A，試圖繼續(xù)分析后面的語法成分。
• 如果棧頂?shù)慕K結(jié)符和輸入符號(hào)不匹配，則彈出棧頂?shù)慕K結(jié)符。

恐慌模式處理錯(cuò)誤.png