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

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