《自頂向下語(yǔ)法分析方法.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《自頂向下語(yǔ)法分析方法.ppt（147頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第5章自頂向下語(yǔ)法分析方法 語(yǔ)法分析 SyntaxAnalysis 是編譯程序的核心部分 詞法分析只是將字符形式的源程序中的各個(gè)單詞識(shí)別出來 形成單詞的機(jī)內(nèi)表示形式 但是這些單詞串如何構(gòu)成更大的語(yǔ)法成分 語(yǔ)句 那就由語(yǔ)法分析來完成 語(yǔ)法分析的主要任務(wù)就是 組詞成句 即在詞法分析識(shí)別出單詞串的基礎(chǔ)上 根據(jù)語(yǔ)言的語(yǔ)法規(guī)則 識(shí)別出各類語(yǔ)法成分 如 語(yǔ)句 程序 等 將完成語(yǔ)法分析任務(wù)的程序稱為語(yǔ)法分析程序 也稱為語(yǔ)法分析器或簡(jiǎn)稱分析器 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)是用上下文無關(guān)文法描述的 因此 語(yǔ)法分析器的實(shí)現(xiàn)原理就是按所給定的文法G 識(shí)別輸入符號(hào)串 是否為一個(gè)句子 即 L G 成立嗎 同時(shí)檢查和處理語(yǔ)法錯(cuò)誤 語(yǔ)法分析的關(guān)鍵是句型識(shí)別問題 給定一串單詞 即文法的終結(jié)符 怎樣知道它是不是該文法產(chǎn)生的一個(gè)句子呢 可以利用推導(dǎo) 或者利用語(yǔ)法樹來進(jìn)行判斷 一般來說 語(yǔ)法分析的過程就是為一個(gè)句子建立語(yǔ)法樹的過程 語(yǔ)法分析的方法很多 按照建立語(yǔ)法樹的不同方向 通常將語(yǔ)法分析分為兩類 一類是自頂向下分析法 另一類是自底向上分析法 本章主要介紹自頂向下分析法 自底向上分析法 第4章教學(xué)內(nèi)容 語(yǔ)法分析的任務(wù) 確定的自頂向下語(yǔ)法分析的基本思想 LL 1 文法的定義和判別方法 非LL 1 文法到LL 1 文法的等價(jià)變換 確定的自頂向下分析方法 遞歸下降分析法預(yù)測(cè)分析法 自底向上語(yǔ)法分析的基本思想 短語(yǔ) 直接短語(yǔ)和句柄的定義 以及如何利用語(yǔ)法樹尋找短語(yǔ) 直接短語(yǔ)和句柄 自底向上語(yǔ)法分析方法 優(yōu)先分析法LR分析法 一 自頂向下的語(yǔ)法分析思想 自頂向下 top down 分析法的基本思想 自頂向下語(yǔ)法分析的基本思想是以文法的開始符號(hào)為樹根 采用最左推導(dǎo) 試圖自上而下地為輸入的單詞串構(gòu)造一棵語(yǔ)法樹 若語(yǔ)法樹的端末節(jié)點(diǎn)從左向右排列恰好是輸入串 則該輸入串就是文法的句子 否則就不是 這種分析過程實(shí)質(zhì)是一種試探過程 是反復(fù)使用不同產(chǎn)生式來匹配輸入串的過程 示例 例4 1 設(shè)有以下文法G1 S S aABA bA cB dBe de輸入串a(chǎn)bbcde的最左推導(dǎo)如下 S aAB abAB abbAB abbcB abbcde因此 輸入串a(chǎn)bbcde是該文法G1的句子 下面從建立語(yǔ)法樹來看句子的推導(dǎo)過程 為了自頂向下地構(gòu)造輸入串a(chǎn)bbcde的語(yǔ)法樹 首先按文法的開始符號(hào)產(chǎn)生根節(jié)點(diǎn)S 再根據(jù)產(chǎn)生式規(guī)則自頂向下地生長(zhǎng)這棵語(yǔ)法樹 語(yǔ)法樹的建立過程如圖所示 S aAB bA bA c de 自頂向下分析法也稱面向目標(biāo)的分析方法 在對(duì)輸入串進(jìn)行最左推導(dǎo)的過程中 在選擇產(chǎn)生式時(shí)其實(shí)是一種試探方法 如果每一步選擇產(chǎn)生式來匹配的時(shí)候都能夠每選必中 則這種方法稱為確定的分析方法 否則在選擇產(chǎn)生式時(shí)面臨多種可能 不知道選擇哪一個(gè)產(chǎn)生式合適 就是不確定的分析方法 因此自頂向下分析法又可分為確定的和不確定的兩種 確定的分析方法對(duì)文法有一定的限制 但由于實(shí)現(xiàn)方法簡(jiǎn)單 直觀 便于手工構(gòu)造或自動(dòng)生成語(yǔ)法分析器 因而仍是目前常用的方法之一 不確定的方法即帶回溯的分析方法 這種方法實(shí)際上是一種窮舉的試探方法 因此效率低 代價(jià)高 因而極少使用 1 不確定的自頂向下分析 不確定的自頂向下分析法的基本思想是 對(duì)任何輸入串 試圖用一切可能的辦法 從文法的開始符號(hào)出發(fā) 自上而下的為它建立一棵語(yǔ)法樹 如果試探成功 則 為相應(yīng)文法的句子 否則 就不是文法句子 這種分析過程本質(zhì)上是一種窮舉試探過程 是反復(fù)使用不同規(guī)則 謀求匹配輸入串的過程 因此這種匹配過程往往一次不能成功 需要重新匹配 稱為回溯 引起回溯的原因在于文法中關(guān)于某個(gè)非終結(jié)符的產(chǎn)生式有多個(gè)時(shí) 而根據(jù)面臨的輸入符無法唯一確定選擇哪個(gè)產(chǎn)生式來匹配 從而引起回溯 自頂向下分析法中存在的問題 回溯問題左遞歸問題 回溯問題 回溯時(shí)需要恢復(fù)到出錯(cuò)點(diǎn)位置 刪去曾經(jīng)匹配過的符號(hào) 還包括一些語(yǔ)義處理 因此處理回溯是一項(xiàng)復(fù)雜的工作 在回溯時(shí) 要清除在回溯之前編譯程序所做的大量記錄工作 然后重新開始記錄 這就降低了語(yǔ)法分析的效率 避免回溯是自頂向下語(yǔ)法分析中需要解決的問題之一 回溯的具體表現(xiàn) 回溯具體表現(xiàn)為下列兩種情況 1 由于相同左部的產(chǎn)生式的候選式的FIRST集交集不為空而引起回溯 2 由于相同左部非終結(jié)符的候選式存在能推導(dǎo)出 的產(chǎn)生式 且該非終結(jié)符的FOLLOW集中含有其它候選式的FIRST集的元素 表現(xiàn)一示例 由于相同左部的產(chǎn)生式的候選式的FIRST集交集不為空而引起回溯 例4 6 設(shè)有文法G6 S 為 S xAyA 串x y的分析過程 S xAy S x 選擇產(chǎn)生式S xAy 當(dāng)前要替換的非終結(jié)符 當(dāng)前要匹配的輸入符 A 可選擇兩個(gè)產(chǎn)生式A 或A 回溯 回到出錯(cuò)點(diǎn) 重新選擇產(chǎn)生式A 成功 原因 上述文法發(fā)生回溯的原因就在于A的兩個(gè)產(chǎn)生式的候選式的第一個(gè)符號(hào)都是 從而根據(jù)輸入符 來選擇A的產(chǎn)生式時(shí)有多種可能 因此會(huì)引起回溯 即 關(guān)于A的產(chǎn)生式的可選集交集不為 SELECT A SELECT A 表現(xiàn)二示例 由于相同左部非終結(jié)符的候選式存在能推導(dǎo)出 的產(chǎn)生式 且該非終結(jié)符的FOLLOW集中含有其它候選式的FIRST集的元素 例如 例4 5的文法G5 S aASS bA bAA 對(duì)輸入串a(chǎn)b 的試探推導(dǎo)過程 S aAS S aAS bA S aAS b 原因 上述文法發(fā)生回溯的原因就在于選擇產(chǎn)生式A 相當(dāng)于與A的后隨符號(hào)FOLLOEW A a b 匹配 但是由于A的后隨符號(hào)b與A的第一個(gè)候選式的第一個(gè)符號(hào)b相同 從而根據(jù)輸入符b來選擇A的產(chǎn)生式時(shí)有多種可能 因此會(huì)引起回溯 即 關(guān)于A的產(chǎn)生式的可選集交集不為 SELECT A bA SELECT A b 左遞歸問題 例4 7 算術(shù)表達(dá)式的文法G7 E 為 E E T TT T F FF i E 對(duì)輸入串i i i進(jìn)行試探推導(dǎo) 結(jié)論 當(dāng)一個(gè)文法是左遞歸的 采用自頂向下分析法會(huì)使分析過程陷入無限循環(huán)之中 回溯會(huì)使語(yǔ)法分析動(dòng)作不確定 而左遞歸會(huì)使語(yǔ)法分析程序陷入無限循環(huán)之中 這些都使得語(yǔ)法分析的動(dòng)作是不確定的 不確定的語(yǔ)法分析方法 帶回溯的自頂向下分析法 實(shí)際上是一種窮舉的試探方法 當(dāng)分析不成功時(shí)則推翻以前的分析退回到適當(dāng)位置再重新試探其余候選式可能的推導(dǎo) 這樣需要記錄已選過的產(chǎn)生式 直到把所有可能的推導(dǎo)序列都試完仍不成功才能確認(rèn)輸入串不是該文法的句子而報(bào)錯(cuò) 由于在編譯程序真正實(shí)現(xiàn)時(shí)往往是邊分析邊插入語(yǔ)義動(dòng)作 因而帶回溯的語(yǔ)法分析方法代價(jià)很高 效率很低 在實(shí)用編譯程序中幾乎不用 因此對(duì)它實(shí)現(xiàn)的詳細(xì)算法不做介紹 2 確定的自頂向下的分析 確定的自頂向下分析方法 首先要解決從文法的開始符號(hào)出發(fā) 如何根據(jù)當(dāng)前的輸入符號(hào) 單詞符號(hào) 唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo) 或構(gòu)造一棵相應(yīng)的語(yǔ)法樹 例4 2 若有文法G2 S S aABA bBA cAB aB d文法G2的句子acbad的自頂向下分析過程如下 示例一 注意 是輸入結(jié)束符 以上最左推導(dǎo)所建立輸入串a(chǎn)cbad的語(yǔ)法樹如圖所示 S aAB cA bB a d 選擇產(chǎn)生式是唯一的 在第2步推導(dǎo)時(shí) 當(dāng)前要替換的非終結(jié)符為A 面臨的輸入符為c 所以選擇A的產(chǎn)生式來推導(dǎo)時(shí) 只能選產(chǎn)生式A cA 而不能選A bB 同樣 在第5步推導(dǎo)時(shí) 當(dāng)前要替換的非終結(jié)符為B 面臨的輸入符為d 所以選擇B的產(chǎn)生式來推導(dǎo)時(shí) 只能選產(chǎn)生式B d 而不能選B a 這樣就保證上述每一步推導(dǎo)都是確定的 文法的特點(diǎn) 文法G2有以下兩個(gè)特點(diǎn) 1 每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開始 2 如果兩個(gè)產(chǎn)生式有相同的左部 那么它們的右部由不同的終結(jié)符開始 對(duì)于這樣的文法顯然在推導(dǎo)過程中完全可以根據(jù)當(dāng)前要替換的非終結(jié)符和輸入符號(hào)決定選擇哪個(gè)產(chǎn)生式往下推導(dǎo) 因此分析過程是唯一確定的 示例二 例4 3 若有文法G3 S 為 S AaS BbA cA dAB eB fB 文法G3的句子ddca的自頂向下分析過程如下 以上最左推導(dǎo)所建立輸入串ddca的語(yǔ)法樹如圖所示 S Aa dA dA c 文法的特點(diǎn) 這個(gè)文法的特點(diǎn)是 1 產(chǎn)生式的右部不全是由終結(jié)符開始 2 如果兩個(gè)產(chǎn)生式有相同的左部 它們的右部是由不同的終結(jié)符或非終結(jié)符開始 3 文法中無空產(chǎn)生式 討論 對(duì)于產(chǎn)生式中相同左部含有非終結(jié)符開始的產(chǎn)生式 在推導(dǎo)過程中選用哪個(gè)產(chǎn)生式不像G2文法那樣直觀 對(duì)于輸入串ddca 其第一個(gè)符號(hào)是d 這時(shí)從S出發(fā)選擇S Aa還是選擇S Bb時(shí) 需要知道Aa或Bb能推導(dǎo)出的首終結(jié)符號(hào)集合是什么 即Aa d 還是Bb d 若Aa d 成立 則選擇S Aa往下推導(dǎo) 若Bb d 成立 則選擇S Bb往下推導(dǎo) 其它情況則為不確定推導(dǎo)或出錯(cuò) 首終結(jié)符號(hào)集 定義4 1 設(shè)G VN VT P S 是上下文無關(guān)文法 是由非終結(jié)符與終結(jié)符組成的任意符號(hào)串 用FIRST 表示 的首終結(jié)符集 則FIRST a a a VT VN VT 若 則規(guī)定FIRST 空集 求符號(hào)串Aa與Bb的首終結(jié)符集 因?yàn)锳a ca Aa dAa 所以FIRST Aa c d 因?yàn)锽b eb Bb fBb 所以FIRST Bb e f 但是FIRST Aa FIRST Bb 因而可以根據(jù)當(dāng)前的輸入符號(hào)是屬于哪個(gè)產(chǎn)生式右部的首終結(jié)符集而決定選擇相應(yīng)產(chǎn)生式進(jìn)行推導(dǎo) 即當(dāng)前要替換的非終結(jié)符為S 面臨的輸入符為d時(shí) 只能選擇產(chǎn)生式S Aa 因?yàn)閐 FIRST Aa 這樣仍然是確定的自頂向下分析 假如考慮文法中有 產(chǎn)生式時(shí) 將會(huì)產(chǎn)生什么問題呢 先看下面的例子 例4 4 若有文法G4 S S aABA bBA cAA B aB d 文法G4的句子aca的自頂向下分析過程如下 以上最左推導(dǎo)所建立輸入串a(chǎn)ca的語(yǔ)法樹如圖所示 S aAB cA a 討論 考查以上推導(dǎo) 在第3步到第4步的推導(dǎo)中 即acAB acB時(shí) 因?yàn)楫?dāng)前要替換的最左非終結(jié)符為A 面臨輸入符為a 而關(guān)于A的產(chǎn)生式右部的首終結(jié)符集都不包含a 但有 因此對(duì)于a的匹配自然認(rèn)為只能依賴于在可能的推導(dǎo)過程中A的后面的符號(hào) 所以這時(shí)選用產(chǎn)生式A 往下推導(dǎo) 而當(dāng)前A后面的符號(hào)為B B的產(chǎn)生式右部的首終結(jié)符集包含了a 所以可匹配 由此可以看出 當(dāng)前輸入符a與A后面的非終結(jié)符B匹配 當(dāng)某一非終結(jié)符的產(chǎn)生式中含有 產(chǎn)生式時(shí) 它的非空產(chǎn)生式右部的首終結(jié)符集兩兩不相交 并與在推導(dǎo)過程中緊跟該非終結(jié)符右邊可能出現(xiàn)的首終結(jié)符號(hào)集也不相交 則仍可構(gòu)造確定的自頂向下分析 為此 我們?yōu)榉墙K結(jié)符引入后隨符號(hào)集的概念 后隨符號(hào)集 定義4 2 設(shè)G VN VT P S 是上下文無關(guān)文法 A是G中的非終結(jié)符 用FOLLOW A 表示A的后隨符號(hào)集 則有 FOLLOW A a S Aa a VT 特別地 若有S A 則規(guī)定 FOLLOW A 換句話說 FOLLOW A 是指在G的各個(gè)句型中位于A后面的那些終結(jié)符或 用 作為輸入串的結(jié)束符 或稱為句子括號(hào) 如 輸入串 對(duì)于例4 4中的文法G4 可用觀察法求得FOLLOW A a d 在自頂向下分析過程中 如果當(dāng)前要替換的非終結(jié)符A面臨輸入符a或d時(shí) 應(yīng)該選擇產(chǎn)生式A 去匹配 而當(dāng)面臨b或c時(shí) 則分別選擇產(chǎn)生式A bB或A cA去匹配 因此當(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的替換仍可唯一地確定產(chǎn)生式 SELECT集 在自頂向下分析過程中 對(duì)每個(gè)產(chǎn)生式的選擇都可由輸入符來決定 綜合以上情況 為每個(gè)產(chǎn)生式定義一個(gè)可選集 SELECT 如下 可選集的定義 定義4 3 給定上下文無關(guān)文法的產(chǎn)生式A A VN V 則定義 如果 則SELECT A FIRST 如果 則SELECT A FIRST FOLLOW A 特別地 如果 則SELECT A FOLLOW A 可選集的含義 可選集的含義如下 在自頂向下分析過程中 如果當(dāng)前要替換的最左非終結(jié)符為A 面臨輸入符為a SELECT A 時(shí) 則可以選擇產(chǎn)生式A 來匹配 因此 只要文法G的某一個(gè)非終結(jié)符A的各個(gè)可選集互不相交 則語(yǔ)法分析程序就可以根據(jù)當(dāng)前輸入符和A的可選集來唯一正確的選擇A的某個(gè)產(chǎn)生式去匹配 LL 1 文法 定義4 4 一個(gè)上下文無關(guān)文法是LL 1 文法的充分必要條件是關(guān)于同一非終結(jié)符的各個(gè)產(chǎn)生式的可選集互不相交 LL 1 文法的含義是 第一個(gè)L表明自頂向下分析過程中是從左到右掃描輸入串 第二個(gè)L表明分析過程中采用最左推導(dǎo) 1表明只需向前查看一個(gè)輸入符號(hào)便可決定選擇哪個(gè)產(chǎn)生式 規(guī)則 進(jìn)行推導(dǎo) 類似地 也可以有LL k 文法 也就是需要向前查看K個(gè)符號(hào)才能夠確定選擇哪個(gè)產(chǎn)生式 通常采用K 1 個(gè)別情況采用K 2 示例 例4 4 文法G4 S S aABA bBA cAA B aB d 計(jì)算可選集 SELECT S aAB a SELECT A bB b SELECT A cA c SELECT A FOLLOW A a d SELECT B a a SELECT B d d 顯然有 SELECT A bB SELECT A cA b c SELECT A bB SELECT A b a d SELECT A cA SELECT A c a d SELECT B a SELECT B d a d 所以 該文法是LL 1 文法 示例 例4 5 設(shè)文法G5 S 為 S aASS bA bAA 因?yàn)橛?SELECT S aAS FIRST aAS a SELECT S b FIRST b b SELECT A bA FIRST bA b SELECT A FOLLOW A FIRST S a b 所以 SELECT S aAS SELECT S b a b SELECT A bA SELECT A b a b 因此 該文法不是LL 1 文法 因而也就不可能進(jìn)行確定的自頂向下語(yǔ)法分析 原因 從對(duì)輸入串 ab的下列兩種不同推導(dǎo)過程來看 第一種推導(dǎo)過程可為 S aAS abAS abS在句型abS中由于S不能推出 所以第一種推導(dǎo)過程推不出ab 第二種推導(dǎo)過程可為 S aAS aS ab第二種推導(dǎo)過程推出了ab 以上兩種推導(dǎo)中 當(dāng)?shù)诙酵茖?dǎo)時(shí)當(dāng)前輸入符為b 對(duì)句型aAS中的A用哪個(gè)產(chǎn)生式推導(dǎo)不能唯一確定 也就是導(dǎo)致了這個(gè)文法不能進(jìn)行確定的自頂向下分析 也即非LL 1 文法是不能進(jìn)行確定的自頂向下分析 結(jié)論 確定的自頂向下語(yǔ)法分析要求文法是LL 1 文法 二 LL 1 文法 LL 1 文法是一類可以進(jìn)行確定的自頂向下語(yǔ)法分析的文法 根據(jù)LL 1 文法的定義 對(duì)于同一非終結(jié)符A的任意兩個(gè)產(chǎn)生式A 和A 都要滿足 SELECT A SELECT A 這樣 當(dāng)前非終結(jié)符A面臨輸入符a時(shí) 如果a SELECT A 則可以選擇產(chǎn)生式A 去準(zhǔn)確匹配 從而解決回溯問題 LL 1 文法的判別 采用確定的自頂向下分析技術(shù)時(shí) 首先必須判別所給文法是否是LL 1 文法 因而對(duì)任何給定的文法需要計(jì)算FIRST FOLLOW SELECT集合 進(jìn)而判別該文法是否為L(zhǎng)L 1 文法 1 構(gòu)造FIRST集 符號(hào)串 的首終結(jié)符集為FIRST 定義 FIRST a a a VT VN VT 若 則規(guī)定FIRST 構(gòu)造FIRST集的算法 對(duì)于文法符號(hào)串 VN VT 構(gòu)造FIRST 的算法如下 反復(fù)使用如下規(guī)則 直至FIRST集不再增大為止 若 a 且a是終結(jié)符 則FIRST a 若 X X是非終結(jié)符 且有X b 則把b加入FIRST 中 若 X1X2 Xk X1 X2 Xk都是非終結(jié)符 首先把FIRST X1 加入FIRST 中 若X1X2 Xi 則把FIRST Xi 1Xi 2 Xk 加入FIRST 中 其中1 i k 1 若X1X2 Xk 則把FIRST 加入FIRST 中 在構(gòu)造FIRST集的算法中 第 條規(guī)則中的情況最復(fù)雜 下面具體說明一下 設(shè) ABC A B C都是非終結(jié)符 則分情況討論 若A 則FIRST FIRST A 若A 但B 則FIRST FIRST A FIRST BC 若AB 但是C 則FIRST FIRST A FIRST B FIRST C 若ABC 但是 則FIRST FIRST A FIRST B FIRST C FIRST 示例一 例4 8 若文法G8 S 為 S ABS bCA A bB B aDC ADC bD aSD c 求各非終結(jié)符的FIRST集 FIRST S FIRST AB FIRST bC S AB S bC FIRST A FIRST B b A b a b b a FIRST A FIRST b b A b FIRST B FIRST aD a B aD FIRST C FIRST AD FIRST b C AD C b FIRST A FIRST D b A b a c b b a c FIRST D FIRST aS FIRST c D aS D c a c a c 結(jié)果 所以最終求得 FIRST S b a FIRST A b FIRST B a FIRST C b a c FIRST D a c 2 構(gòu)造FOLLOW集 非終結(jié)符A的后隨符號(hào)集的定義為 FOLLOW A a S Aa a VT 特別地 若有S A 則規(guī)定 FOLLOW A 構(gòu)造FOLLOW集的算法 對(duì)文法中每一非終結(jié)符A 構(gòu)造FOLLOW A 的算法如下 反復(fù)使用如下規(guī)則 直至FOLLOW集不再增大為止 若A是文法的開始符號(hào) 則把輸入結(jié)束符 加入FOLLOW A 中 若B Aa a是終結(jié)符 則把a(bǔ)加入FOLLOW A 中 若B AX X是非終結(jié)符 則把FIRST X 加入FOLLOW A 中 若B A或B A 且 則把FOLLOW B 加入FOLLOW A 中 注意 在構(gòu)造FOLLOW集的算法中 將第 條規(guī)則解釋一下 如果有句型 Ba 顯然a是B的后隨符號(hào) a FOLLOW B 而B A 用它往下進(jìn)行推導(dǎo)有S Ba Aa 那么a也是A的后隨符號(hào) a FOLLOW A 即FOLLOW B 中的后隨符號(hào)都是FOLLOW A 中的后隨符號(hào) 同樣的 如果有B A 且 用它往下進(jìn)行推導(dǎo)有 S Ba A a Aa 即也有FOLLOW B 中的后隨符號(hào)都是FOLLOW A 中的后隨符號(hào) 示例一 例4 8 若文法G8 S 為 S ABS bCA A bB B aDC ADC bD aSD c 求各非終結(jié)符的FOLLOW集 FOLLOW S FOLLOW D S是文法的開始符號(hào) D aS FOLLOW S FOLLOW A FIRST B FIRST D FOLLOW S S AB 且B C AD a c FOLLOW B FOLLOW S S AB FOLLOW C FOLLOW S S bC FOLLOW D FOLLOW B FOLLOW C B aD C AD FOLLOW S 結(jié)果 所以最終求得 FOLLOW S FOLLOW A a c FOLLOW B FOLLOW C FOLLOW D 計(jì)算此文法各個(gè)產(chǎn)生式的可選集 SELECT集 首先考慮計(jì)算產(chǎn)生式的右部是終結(jié)符開頭的 其可選集只包含這一個(gè)終結(jié)符 SELECT S bC FIRST bC b SELECT A b FIRST b b SELECT B aD FIRST aD a SELECT C b FIRST b b SELECT D aS FIRST aS a SELECT D c FIRST c c 再來考慮計(jì)算產(chǎn)生式是 產(chǎn)生式 其可選集為相應(yīng)產(chǎn)生式左部的FOLLOW集 SELECT A FOLLOW A a c SELECT B FOLLOW B 再考慮復(fù)雜的情況 產(chǎn)生式的右部是非終結(jié)符開頭的 其可選集的計(jì)算要取決于相應(yīng)產(chǎn)生式右部的符號(hào)是否能夠推導(dǎo)出 AB SELECT S AB FIRST AB FOLLOW S b a AD SELECT C AD FIRST AD a b c 結(jié)果 最后將產(chǎn)生式的可選集整理如下 SELECT S AB b a SELECT S bC b SELECT A a c SELECT A b b SELECT B SELECT B aD a SELECT C AD a b c SELECT C b b SELECT D aS a SELECT D c c 判斷是否為L(zhǎng)L 1 文法 因?yàn)?SELECT S AB SELECT S bC b a b b SELECT A SELECT A b a c b SELECT B SELECT B aD a SELECT C AD SELECT C b a b c b SELECT D aS SELECT D c a c 結(jié)論 不是LL 1 文法 由于關(guān)于非終結(jié)符S的產(chǎn)生式的可選集的交集不為空集 即意味著當(dāng)前的最左非終結(jié)符為S 面臨的輸入符為b時(shí) 可以選擇產(chǎn)生式S AB或者S bC來匹配 同樣 關(guān)于非終結(jié)符C的產(chǎn)生式的可選集的交集也不為空集 因此 這個(gè)文法的自頂向下語(yǔ)法分析動(dòng)作是不確定 所以 該文法不是LL 1 文法 三 某些非LL 1 文法到LL 1 文法的等價(jià)轉(zhuǎn)換 LL 1 文法的性質(zhì) LL 1 文法是無二義性的 LL 1 文法不含左遞歸 LL 1 文法沒有公共左因子 非LL 1 文法的改造 消除左遞歸消除回溯 提取左公因子 1 消除文法的左遞歸 當(dāng)一個(gè)文法是左遞歸文法時(shí) 采用自頂向下分析法會(huì)使分析過程進(jìn)人無窮循環(huán)之中 文法左遞歸是指文法中的某個(gè)非終結(jié)符A存在推導(dǎo)A A 而自頂向下分析法是采用最左推導(dǎo) 即每次替換的都是當(dāng)前句型中的最左非終結(jié)符 當(dāng)試圖用非終結(jié)符A去匹配輸人串時(shí) 結(jié)果使當(dāng)前句型的最左非終結(jié)符仍然為A 也就是說 在沒有讀進(jìn)任何輸人符號(hào)的情況下 又重新要求A去進(jìn)行新的匹配 于是造成無窮循環(huán) 所以采用自頂向下分析法進(jìn)行語(yǔ)法分析需要消除文法的左遞歸性 遞歸文法 遞歸文法 遞歸文法是指對(duì)文法中任一非終結(jié)符A 若存在一個(gè)推導(dǎo)序列 在推出的符號(hào)串中又出現(xiàn)了該非終結(jié)符本身 即A A 則該文法是遞歸的 若文法中對(duì)任一非終結(jié)符A有推導(dǎo)A A 則稱該文法是左遞歸的 若文法中對(duì)任一非終結(jié)符A有推導(dǎo)A A 則稱該文法是右遞歸的 左遞歸 左遞歸又可以分為直接左遞歸和間接左遞歸 直接左遞歸 若文法中的某一產(chǎn)生式形如A A V 則稱該文法是直接左遞歸的 間接左遞歸 若文法中存在某一非終結(jié)符A 使得A A 至少需要兩步推導(dǎo) 則稱該文法是間接左遞歸的 消除直接左遞歸的方法一 方法一 只需將產(chǎn)生式進(jìn)行改寫 使之不含左遞歸 為此需要引進(jìn)一個(gè)新的非終結(jié)符 把含有左遞歸的產(chǎn)生式改寫成右遞歸的產(chǎn)生式即可 設(shè)有產(chǎn)生式是關(guān)于非終結(jié)符A的直接左遞歸A A V 且 不以A開頭 對(duì)A引入一個(gè)新的非終結(jié)符A 把上式改寫為 A A A A 改寫前后產(chǎn)生式是等價(jià)的 前式推導(dǎo) A A A A n n后式推導(dǎo) A A A A nA n從A推出的符號(hào)串的集合是相同的 也就是說 它們是等價(jià)的 一般情況 若某文法中非終結(jié)符A的產(chǎn)生式形如 A A 1 A 2 A n 1 A n 1 2 m 1 m其中 i j V i 1 n j 1 m 且 j不以A開頭 則可用下述方法消除直接左遞歸 引入一個(gè)新的非終結(jié)符A A 1A 2A m 1A mA A 1A 2A n 1A nA 示例 例4 10 算術(shù)表達(dá)式文法G7 E E E T TT T F FF i E 消除直接左遞歸后 文法變成 E TE E TE T FT T FT F i E 消除直接左遞歸的方法二 方法二 采用擴(kuò)充BNF表示法改寫含直接左遞歸的產(chǎn)生式 在擴(kuò)充的BNF表示中 有如下約定 花括號(hào) 表示符號(hào)串 的可出現(xiàn)0次或多次 即表示 表示符號(hào)串 的可出現(xiàn)m次至n次 m為最小次數(shù) n為最大次數(shù) 例如 A A 可改寫為 A m n 方括號(hào) 表示 10 即 的出現(xiàn)可有可無 它用來表示可供選擇的符號(hào)串 例如 A 可改寫為 A 圓括號(hào) 利用圓括號(hào)可在產(chǎn)生式右部中提取公共因子 例如 A 1 2 m 1 m可改寫為 A 1 2 m 1 m 示例 例4 11 算術(shù)表達(dá)式的文法G7 E 為 E E T TT T F FF i E 對(duì)文法G7用擴(kuò)充BNF表示法對(duì)其進(jìn)行改寫 示例 因?yàn)楫a(chǎn)生式E E T T表示E所生成的符號(hào)串由T開頭且后跟0個(gè)或多個(gè)十T 而產(chǎn)生式T T F F表示T所生成的符號(hào)串由F開頭且后面跟0個(gè)或多個(gè) F 所以該文法可改寫成如下形式 E T T T F F F i E 消除間接左遞歸的方法 消除直接左遞歸是比較容易的 但是消除間接左遞歸就不是那么容易的事 方法一 采用代入法把間接左遞歸變成直接左遞歸 方法二 直接改寫文法 示例 例4 12 設(shè)有文法G10 S S A A S 因?yàn)镾 A S 所以S是一個(gè)間接遞歸的非終結(jié)符 為了消除這種間接左遞歸 將 式代入 式 即可得到與原文法等價(jià)的文法 可以證明 S S 式是直接左遞歸的 可以采用前面介紹的消除直接左遞歸的方法 對(duì)文法進(jìn)行改寫后可得文法 S S S S 2 消除回溯 在自頂向下分析過程中 當(dāng)某個(gè)非終結(jié)符A對(duì)應(yīng)多個(gè)候選式時(shí) 如果其中有幾個(gè)候選式的左端第一符號(hào)相同 那么就會(huì)使得語(yǔ)法分析程序無法根據(jù)當(dāng)前要替換的非終結(jié)符和當(dāng)前輸人符唯一地決定選用哪個(gè)候選式來替換A 只能采用試探的辦法 任選某個(gè)候選式去試探一次 如果不能導(dǎo)致最終正確地匹配 只得再換另一個(gè)候選式去試探 從而引起回溯 在自頂向下分析過程中 由于回溯需要推翻前面的分析 包括已做的一大堆語(yǔ)義工作 重新去進(jìn)行試探 這樣大大降低了語(yǔ)法分析器的工作效率 因此 需要消除回溯 對(duì)于上述情況 即 同一非終結(jié)符有多個(gè)候選式的首符相同 可以采用提 左因子 的方法來改造文法 使得文法的每個(gè)非終結(jié)符的各個(gè)候選式的首符都不相同 從而可以消除上面所說的回溯現(xiàn)象 提取公共左因子 若A的產(chǎn)生式為 A 1 2經(jīng)過提取公共左因子 原產(chǎn)生式變?yōu)?A A A 1 2 一般情況 若A的產(chǎn)生式為 A 1 2 k 1 k經(jīng)過提取公共左因子 原產(chǎn)生式變?yōu)?A A A 1 2 k 1 k如果 m n 其中1 m n k 中仍然含有公共左因子 則可反復(fù)提取它們的共同左因子 直到每個(gè)新引入的非終結(jié)符的產(chǎn)生式再無公共左因子為止 示例 例4 15 前面例4 6中的文法G6 S 為 S xAyA 關(guān)于A的產(chǎn)生式有公共左因子 提取公共左因子a后 文法改寫為 S xAyA A A 計(jì)算該文法的可選集 SELECT S xAy x SELECT A A SELECT A SELECT A FOLLOW A FOLLOW A y 因?yàn)?SELECT A SELECT A y 所以 上述文法是LL 1 文法 這時(shí)再用自頂向下分析方法分析符號(hào)串x y 就不會(huì)產(chǎn)生回溯了 示例 例4 15 設(shè)有文法G13 S 為 S aSbS ab關(guān)于S的產(chǎn)生式有公共左因子 提取公共左因子a后 文法改寫為 S a Sb b 進(jìn)一步變換為文法G13 S 其產(chǎn)生式為 S aS S Sb b 計(jì)算該文法的可選集 SELECT S aS a SELECT S Sb FIRST Sb FIRST S a SELECT S b b 因?yàn)?SELECT S Sb SELECT S b a b 所以 上述文法是LL 1 文法 可以進(jìn)行確定的自頂向下的語(yǔ)法分析 三 確定的自頂向下分析方法 特征 根據(jù)下一個(gè)輸入符號(hào)為當(dāng)前要處理的非終結(jié)符選擇產(chǎn)生式要求 文法是LL 1 的語(yǔ)法分析方法 1遞歸下降分析法2預(yù)測(cè)分析法 1 遞歸下降分析法 遞歸子程序法是比較簡(jiǎn)單直觀易于構(gòu)造的一種語(yǔ)法分析方法 實(shí)現(xiàn)思想 文法中每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸過程 子程序 每個(gè)過程的功能是識(shí)別由該非終結(jié)符推出的串 當(dāng)某非終結(jié)符的產(chǎn)生式有多個(gè)候選式時(shí)能夠按LL 1 形式可唯一地確定選擇某個(gè)候選式進(jìn)行推導(dǎo) 示例 例4 10 算術(shù)表達(dá)式文法G7 E E E T TT T F FF i E 消除直接左遞歸后 文法變成 E TE E TE T FT T FT F i E 計(jì)算FIRST集與FOLLOW集 各非終結(jié)符的FIRST集為 FIRST E i FIRST E FIRST T i FIRST T FIRST F i 各非終結(jié)符的FOLLOW集合為 FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F 計(jì)算SELECT集 各產(chǎn)生式的SELECT集為 SELECT E TE FIRST TE i SELECT E 十TE SELECT E FOLLOW E SELECT T FT FIRST FT i SELECT T FT SELECT T FOLLOW T 十 SELECT F E SELECT F i i 該文法是LL 1 文法 因?yàn)?SELECT E 十TE SELECT E SELECT T FT SELECT T SELECT F E SELECT F i 所以 該文法中關(guān)于同一個(gè)非終結(jié)符的產(chǎn)生式的SELECT集兩兩不相交 因此 該文法是LL 1 文法 可以進(jìn)行確定的自頂向下語(yǔ)法分析 遞歸子程序 E E TE 非終結(jié)符E對(duì)應(yīng)的子程序?yàn)?E T E 遞歸子程序 E E TE 非終結(jié)符E 對(duì)應(yīng)的子程序?yàn)?E ifsym read sym T E elseifsym FOLLOW E return elseerror 遞歸子程序 T T FT 非終結(jié)符T對(duì)應(yīng)的子程序?yàn)?T F T 遞歸子程序 T T FT 非終結(jié)符T 對(duì)應(yīng)的子程序?yàn)?T ifsym read sym F T elseifsym FOLLOW T return elseerror 遞歸子程序 F F i E 非終結(jié)符F對(duì)應(yīng)的子程序?yàn)?F ifsym i read sym elseifsym read sym E ifsym read sym elseerror 主程序 main read sym E if sym printf 分析成功 elseprintf 分析失敗 示例 例4 11 算術(shù)表達(dá)式的文法G7 E E E T TT T F FF i E 對(duì)文法G7用擴(kuò)充BNF表示法對(duì)其進(jìn)行改寫成如下形式 E T T T F F F i E 遞歸子程序 E E T T 非終結(jié)符E對(duì)應(yīng)的子程序?yàn)?E T while sym read sym T 遞歸子程序 T T F F 非終結(jié)符T對(duì)應(yīng)的子程序?yàn)?T F while sym read sym F 遞歸子程序 F F i E 非終結(jié)符F對(duì)應(yīng)的子程序?yàn)?F ifsym i read sym elseifsym read sym E ifsym read sym elseerror 主程序 main read sym E if sym printf 分析成功 elseprintf 分析失敗 2 預(yù)測(cè)分析法 預(yù)測(cè)分析法用一個(gè)分析棧存放當(dāng)前要替換的非終結(jié)符的某個(gè)候選式的符號(hào)串 倒放在棧內(nèi) 當(dāng)非終結(jié)符呈現(xiàn)在棧頂時(shí) 它就是當(dāng)前非終結(jié)符 此外 還使用一張矩陣形式的預(yù)測(cè)分析表 它是根據(jù)可選集構(gòu)造的 它的入口指出了某非終結(jié)符和某終結(jié)符匹配時(shí)所應(yīng)選擇的候選式和語(yǔ)義動(dòng)作 預(yù)測(cè)分析程序的總控程序就是利用棧頂符號(hào)和當(dāng)前輸人符號(hào)對(duì)輸人串進(jìn)行預(yù)測(cè)分析 而預(yù)測(cè)的信息則存放在預(yù)測(cè)分析表的相應(yīng)入口里 一個(gè)預(yù)測(cè)分析程序是由三個(gè)部分組成 總控程序 表驅(qū)動(dòng)程序 預(yù)測(cè)分析表 先進(jìn)后出的語(yǔ)法分析棧 預(yù)測(cè)分析程序的模型 預(yù)測(cè)分析程序?qū)嶋H上就是一個(gè)下推自動(dòng)機(jī) 它是用下推自動(dòng)機(jī)來識(shí)別輸入符號(hào)串的 輸入串 總控程序預(yù)測(cè)分析表 LL 1 分析表 棧頂符號(hào) x1 xn 分析棧 預(yù)測(cè)分析法表 LL 1 分析表 表示 一個(gè)矩陣 或二維數(shù)組 M A a 行 對(duì)應(yīng)文法的一個(gè)非終結(jié)符A列 對(duì)應(yīng)一個(gè)終結(jié)符a或輸入結(jié)束符 大小 m n m是文法中非終結(jié)符數(shù) n是終結(jié)符數(shù) 1 外加一個(gè)結(jié)束符 數(shù)組的值M A a 存放著面臨輸人符號(hào)a時(shí) 所應(yīng)選擇A的某條產(chǎn)生式 即指出當(dāng)前推導(dǎo)所應(yīng)使用的產(chǎn)生式 數(shù)組中的空白入口中應(yīng)填人適當(dāng)?shù)某鲥e(cuò)處理子程序名或編號(hào) 即此種情況下存在語(yǔ)法錯(cuò)誤 預(yù)測(cè)分析表的構(gòu)造 預(yù)測(cè)分析法的實(shí)現(xiàn)關(guān)鍵在于預(yù)測(cè)分析表 預(yù)測(cè)分析表是指分析棧中的文法符號(hào)與輸入串中的符號(hào)的一種匹配關(guān)系 記為M A a 其中A為分析棧中的符號(hào) a為輸入符號(hào) 可以由可選集直接來構(gòu)造預(yù)測(cè)分析表 預(yù)測(cè)分析表的構(gòu)造算法 預(yù)測(cè)分析表的構(gòu)造算法是 對(duì)每個(gè)終結(jié)符a SELECT A 把A 填入M A a 中 把所有無定義的M A a 均填上 出錯(cuò)標(biāo)志 結(jié)論 上述算法可應(yīng)用于任何文法G以構(gòu)造它的分析表M 但對(duì)于某些文法 有些M A a 中可能有若干個(gè)產(chǎn)生式 或者說有些M A a 可能是多重定義的 如果G是左遞歸或回溯的 那么M至少含有一個(gè)多重定義入口 因此 消除左遞歸和提取公共左因子將有助于獲得無多重定義的分析表M 可以證明 一個(gè)文法G的預(yù)測(cè)分析表M不含多重定義入口 當(dāng)且僅當(dāng)該文法是LL l 文法 示例 例4 19 前述算術(shù)表達(dá)式的文法G7 E 為 E TE E 十TE T FT T FT F i E 表達(dá)式文法的預(yù)測(cè)分析表 預(yù)測(cè)分析程序的工作流程 預(yù)測(cè)分析程序在總控程序控制下進(jìn)行對(duì)輸入串的分析 利用分析棧記錄分析過程中使用的文法符號(hào) 輸入串中存放的終結(jié)符號(hào)串 分析棧中存放的是終結(jié)符和非終結(jié)符組成的符號(hào)串 預(yù)測(cè)分析表的工作流程 1 分析開始時(shí) 首先將棧底符號(hào) 及文法的開始符號(hào)S依次推入分析棧的棧底 并對(duì)各條指示器置初值 此時(shí)分析棧和輸入串的格局為 用箭頭表示輸入串指針和棧頂指針當(dāng)前所指向的位置 預(yù)測(cè)分析表的工作流程 2 設(shè)在分析的某一步 分析棧和余留的輸入符號(hào)串處于如下的格局 此時(shí) 可根據(jù)棧頂?shù)奈姆ǚ?hào)Xm的不同情況 分別處理 情形一 若Xm為終結(jié)符 即xm VT 且Xm ai 時(shí) 則表明棧頂符號(hào)已與當(dāng)前正掃視的輸入符號(hào)相匹配 此時(shí)應(yīng)將Xm從棧中彈出 而且將輸入指針向前移動(dòng)一個(gè)位置至ai 1 從而得到如下格局 情形二 若Xm為非終結(jié)符 即Xm VN 則以Xm及ai組成符號(hào)對(duì) Xm ai 查分析表M 假設(shè)M Xm ai 中存放著關(guān)于Xm的一個(gè)產(chǎn)生式Xm ABC 此時(shí) 首先將Xm從分析棧中彈出 并將該產(chǎn)生式右部ABC的逆替換棧頂符號(hào) 即把ABC按逆序推入棧中 此即用該產(chǎn)生式推導(dǎo)一步 輸入指針不動(dòng) 從而得到新的格局如下 否則出錯(cuò) 即M Xm ai ERROR 則調(diào)用出錯(cuò)處理程序來進(jìn)行處理或宣告分析失敗 情形三 若xm ai 即輸入串與分析棧均為空 則表明輸入符號(hào)串已完全得到匹配 此時(shí)可宣告分析成功 結(jié)束工作 接收輸入串 此時(shí)的格局如下 反復(fù)使用第二步進(jìn)行處理 直至分析成功或者分析失敗 示例 例4 19 算術(shù)表達(dá)式的文法G7 E 為 E TE E 十TE T FT T FT F i E 給出輸入串i i的分析過程 分析棧 棧頂符 輸入符 剩余輸入串 E E i 查表E TE i i 2 E T T i 查表T FT i i 3 E T F F i 查表F ii i 4 E T i i i 匹配 i E T T 查表T i E E 查表E TE i 7 E T 匹配i E T T i 查表T FT i 9 E T F F i 查表F ii 10 E T i i i 匹配 11 E T T 查表T 12 E E 查表E 13 成功接收 示例 例4 19 設(shè)有文法G16 P 為 P begind XendX d XX sYY sYY 用預(yù)測(cè)分析法分析的步驟分為四步 1 是否需要改寫文法 如果文法是左遞歸的 或者具有公共左因子 則需要對(duì)文法進(jìn)行改寫 因?yàn)樯鲜鑫姆℅16不具有左遞歸和公共左因子 所以不需要對(duì)文法進(jìn)行改寫 直接證明該文法是LL 1 文法即可 2 判斷文法是否為L(zhǎng)L 1 文法 該文法的各個(gè)產(chǎn)生式的SELECT集為 SELECT P begind Xend begin SELECT X d X d SELECT X sY s SELECT Y sY SELECT Y FOLLOW Y FOLLOW X end 因?yàn)?SELECT X d X SELECT X sY d s SELECT Y sY SELECT Y end 所以 該文法是LL 1 文法 3 根據(jù)可選集構(gòu)造預(yù)測(cè)分析表 根據(jù)構(gòu)造預(yù)測(cè)分析表的算法 可得上述文法的預(yù)測(cè)分析表如表所示 4 給出輸入串的分析過程 給出輸入串begind s send的分析過程 分析棧 棧頂符 輸入符 剩余輸入串1 P P begin 查表begind s send 2 endX dbegin begin begin 匹配d s send 3 endX d d d 匹配 s send 4 endX 匹配s send 5 endX X s 查表X sYs send 6 endYs s s 匹配 send 7 endY Y 查表Y sY send 8 endYs 匹配send 9 endYs s s 匹配end 10 endY Y end 查表Y end end end end 匹配 12 成功接收 LL 1 分析中的一種錯(cuò)誤處理辦法 發(fā)現(xiàn)錯(cuò)誤1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配2非終結(jié)符A于棧頂 面臨的輸入符為a 但分析表M的M A a 為空 應(yīng)急 恢復(fù)策略跳過輸入串中的一些符號(hào)直至遇到 同步符號(hào) 為止 同步符號(hào)的選擇1把FOLLOW A 中的所有符號(hào)作為A的同步符號(hào) 跳過輸入串中的一些符號(hào)直至遇到這些 同步符號(hào) 把A從棧中彈出 可使分析繼續(xù)2把FIRST A 中的符號(hào)加到A的同步符號(hào)集 當(dāng)FIRST A 中的符號(hào)在輸入中出現(xiàn)時(shí) 可根據(jù)A恢復(fù)分析 小結(jié) 1 語(yǔ)法分析的任務(wù) 2 確定的自頂向下語(yǔ)法分析方法的基本思想 存在的問題是 左遞歸和回溯 3 分析方法 預(yù)測(cè)分析法