【正文】 第 5章 自頂向下的語(yǔ)法分析方法 語(yǔ)法分析的作用是識(shí)別由詞法分析給出的 單詞符號(hào)序列是否是給定文法的正確句子(程序 )。 目前語(yǔ)法分析常用的方法有 : 自頂向下（自上而下）分析 自底向上（自下而上）分析 自頂向下分析法也就是從文法的開(kāi)始符號(hào)出 發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的 句子，若輸入串是給定文法的句子，則必能 推出，反之必然出錯(cuò)。 回顧在 “ 文法和語(yǔ)言 ” 一章中介紹的關(guān)于句子、句型和語(yǔ)言的定義及什么叫最左推導(dǎo)、最右推導(dǎo)和規(guī)范推導(dǎo)的基本概念。 句型、句子、語(yǔ)言的定義 句型 : 有文法 G [S]， 若 S x，且 x∈ V* 則稱 x是文法 G [S]的句型。 符號(hào) 表示經(jīng)過(guò) 0步或若干步的推導(dǎo)。 句子 : 有文法 G[S]，若 S x，且 x∈V T*，則稱 x是文法 G [S]的句子。 例： G[S]： S→0S1 ， S→01 可有推導(dǎo) S 0S1 00S11 000S111 00001111 說(shuō)明 00001111是 G[S]的句子。 句型的分析 句型分析 就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。 最左（最右）推導(dǎo) ：在推導(dǎo)的任何一步 α β ，都是對(duì) α 中的最左（右）非終結(jié)符進(jìn)行替換。 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。 由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 句型分析的有關(guān)問(wèn)題 ① 如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 假定要被替換的最左非終結(jié)符號(hào)是 V，且左部為 V的規(guī)則有 n條：V→A1|A2| … |An，那么如何確定用哪個(gè)右部去替換 V呢？ ② 如何識(shí)別可歸約的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中尋找一個(gè)子串，看它是否能歸約到文法的某個(gè)非終結(jié)符號(hào)，該子串稱為 “ 可歸約串 ” 。 確定的自頂向下分析思想 確定的自頂向下分析方法 :首先要解決從某文法 的開(kāi)始符號(hào)出發(fā)，對(duì)給定的輸入符號(hào)串如何根據(jù) 當(dāng)前的輸入符號(hào) (單詞符號(hào) )唯一地確定選用哪個(gè) 產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo) . 例 若有文法 G1[S]: S → pA |qB A →cAd|a B →d B |c 識(shí)別輸入串 w= pccadd是否是 G1[S]的句子 試探推導(dǎo)過(guò)程： S pA pcAd pccAdd pccadd 試探成功。 這個(gè)文法有以下兩個(gè)特點(diǎn) ： ① 每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開(kāi)始。 ② 如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的 右部由不同的終 結(jié)符開(kāi)始。即每個(gè)產(chǎn)生式的右部的開(kāi)始終結(jié)符不同。 對(duì)于這樣的文法顯然在推導(dǎo)過(guò)程中完全可以根據(jù)當(dāng)前的輸入符號(hào)決定選擇哪個(gè)產(chǎn)生式往下推導(dǎo)，因此分析過(guò)程是唯一確定的。 例 若有文法 G2[S]: S → Ap |Bq A →a|cA B →b|dB 識(shí)別輸入串 w=ccap是否是 G2[S]的句子，那么試探推出輸入串的推導(dǎo)過(guò)程為 ： S Ap cAp ccAp ccap 試探推導(dǎo)成功。 文法的特點(diǎn)是： ① 產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始。 ② 如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的 終結(jié) 符或非終結(jié)符開(kāi)始。 ③ 文法中無(wú)空產(chǎn)生式。 對(duì)于產(chǎn)生式中相同左部含有非終結(jié)符開(kāi)始的產(chǎn)生式時(shí)，在推導(dǎo)過(guò)程中選用哪個(gè)產(chǎn)生式不像例 ，對(duì)于 W=ccap 為輸入串時(shí)，其第一個(gè)符號(hào)是 c，這時(shí)從 S出發(fā)選擇 S→Ap 還是選擇 S→Bq ， 需要知道， Ap或 Bq它們的 開(kāi)始終結(jié)符號(hào)集合 是什么？ 因?yàn)?c是包含在 Ap的 開(kāi)始終結(jié)符號(hào)集合中 ，且不包含在 Bq的 開(kāi)始終結(jié)符號(hào)集合中 ，則選擇 S→Ap 往下進(jìn)行推導(dǎo)。 S → Ap |Bq A →a|cA B →b|dB 一個(gè)文法符號(hào)串的終結(jié)符的首符集定義如下 ： 定義 設(shè) G=(VT， VN， S， P)是上下文無(wú)關(guān)文法 FIRST(α)={a|α aβ,a∈ VT， α,β∈ V*} 若 α ε,則規(guī)定 ε∈ FIRST(α)． 不難求出在例 G2中 FIRST(Ap)={a,c} FIRST(Bq)={b,d} 因此有 FIRST(Ap)∩(FIRST(Bq)= ? 這樣文法 G中， 兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié) 符或非終結(jié)符開(kāi)始。 但它們右部的符號(hào)串可能推導(dǎo)出的First集不相交，因而可以根據(jù)當(dāng)前的輸入符號(hào)是屬于哪個(gè)產(chǎn)生式的FIRST集而決定選擇相應(yīng)產(chǎn)生式進(jìn)行推導(dǎo)，因此仍能構(gòu)造確定的自頂向下分析。 G2： S → Ap |Bq A →a|cA B →b|dB 例 若有文法 G3[S]: S → aA|d A →bAS| ε 識(shí)別輸入串 w=abd是否是 G3[S]的句子 試探推導(dǎo)出 abd的推導(dǎo)過(guò)程為： S aA abAS abS abd 試探推導(dǎo)成功。 文法的特點(diǎn)是： 文法中含有空產(chǎn)生式。從以上推導(dǎo)過(guò)程中我們可以看到在第 2步到第 3步的推導(dǎo)中， 因當(dāng)前面臨輸入符號(hào)為 d，而最左非終結(jié)符 A的產(chǎn)生式右部的開(kāi)始符號(hào)集合都不包含 d，但有 ε， 因此對(duì)于 d 的匹配自然認(rèn)為 只能依賴于在可能的推導(dǎo)過(guò)程中 A的后面的符號(hào)，所以這時(shí)選用產(chǎn)生式 A→ε 往下推導(dǎo)，而 當(dāng)前 A后面的符號(hào)為 S， S產(chǎn)生式右部的開(kāi)始的終結(jié)符號(hào)集合包含了 d，所以可匹配。 當(dāng)一個(gè)文法中相同左部非終結(jié)符的右部存在能 ε的情況則必須知道 該非終結(jié)符的后跟符號(hào)的集合中的符號(hào)是否可以唯一地確定選擇哪個(gè)產(chǎn)生式。 為此，我們定義一個(gè)文法非終結(jié)符的后跟符號(hào)的集合如下： 定義 ： 設(shè) G=(VT， VN， S， P)是上下文無(wú)關(guān) 文法， A∈ VN， S是開(kāi)始符號(hào) FOLLOW(A)=｛ a|S μAβ,且 a∈ VT， a∈ FIRST(β),μ∈ VT* ,β∈ V+｝ 若 S μAβ,且 β ε, 則 ∈ FOLLOW(A)。 也可定義為： FOLLOW(A)={a|S …Aa…,a ∈ VT} 若有 S …A ，則規(guī)定 ∈ FOLLOW(A) 這里我們用 39。39。作為輸入串的結(jié)束符，或稱為句子括號(hào)，如： 輸入串 。 因此當(dāng)文法中含有形如： A→α A→β 的產(chǎn)生式時(shí)，其中 A∈ VN， α,β∈ V*，當(dāng) α,β不同時(shí)推導(dǎo)出空時(shí)，設(shè) α ε,β ε,則當(dāng) FIRST(α)∩( FIRST(β)∪ FOLLOW(A))= 時(shí)，對(duì)于非終結(jié)符 A的替換仍可唯一地確定候選。 綜合以上情況可定義選擇集合 SELECT如下： 定義 給定上下文無(wú)關(guān)文法的產(chǎn)生式 A→α, A ∈ VN,α∈ V*, 若 α ε,則 SELECT(A→α)=FIRST(α) 如果 α ε則： SELECT(A→α)= （ FIRST(α) –{ε}） ∪ FOLLOW(A) 是否所有的文法都能采用確定的自上而下的分析 該文法的特點(diǎn)是： 關(guān)于 A的產(chǎn)生式的不同右部開(kāi)始符號(hào)集合都含有 a，因此要替換非終結(jié)符 A時(shí)，對(duì)當(dāng)前輸入符為 a的情況，不能確定用產(chǎn)