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

第四章自頂向下語法分析方法 學習目標 掌握 LL 1 文法的判別 預測分析法 遞歸子程序的構造方法理解 LL 1 文法了解 不確定的自頂向下分析 語法分析的作用是識別由詞法分析給出的單詞序列是否是給定文法的正確句子 自頂向下基本思想 從文法的開始符出發(fā)企圖推導出與輸入的單詞串完全相匹配的句子 分類 回顧 自上而下的分析方法 定義 從文法的開始符號出發(fā) 反復使用文法的產(chǎn)生式 尋找與輸入符號串匹配的推導 語法樹的構造 將文法的開始符號作為語法樹的根 向下逐步建立語法樹 使語法樹的末端結點符號串正好是輸入符號串 自上而下分析的主要問題選定產(chǎn)生式 例文法G S cAdA abA a識別輸入串w cabd是否為該文法的句子 S cabd S cAd 回顧 自上而下的分析方法 S 成功 不成功 cad S cAd 4 1確定的自頂向下分析思想4 2LL 1 文法的判別4 3某些非LL 1 文法到LL 1 文法的等價變換4 4不確定的自頂向下分析思想4 5確定的自頂向下分析方法 本章內容 4 1確定的自頂向下分析思想 1確定分析的條件2開始符號集FIRST 的定義3后跟符號集FOLLOW A 的定義4選擇集合SELECT A 的定義5LL 1 文法的定義 1 確定分析的條件 從文法的開始符出發(fā) 如能根據(jù)當前的輸入符號 單詞符號 唯一地確定選用哪個產(chǎn)生式進行推導 則分析是確定的 例1設有文法G1 S S pA qBA cAd aB dB b若輸入串W pccadd 自頂向下的推導過程為 S S pA pcAd pccAdd pccadd G1 S 有如下特點 1 每個產(chǎn)生式的右部由終結符開頭 2 同一非終結符的不同產(chǎn)生式的右部由不同的終結符開頭 對于這種文法 在推導過程可以根據(jù)當前的輸入符號唯一確定選哪個產(chǎn)生式往下推導 即分析過程是確定的 例2 設有文法G2 S 為 S Ap BqA a cAB b dB S ccap S cAp ccAp Ap 該例說明 當 1 產(chǎn)生式右部以終結符或非終結符開頭 無空產(chǎn)生式 2 同一非終結符的不同產(chǎn)生式的右部由不同的符號開頭 若輸入串W ccap 自頂向下的推導過程為 對于這種文法 在推導過程選用哪個產(chǎn)生式不直觀 關鍵是判斷產(chǎn)生式右部推出的開始符號 集 分析過程可能是確定的 例3 設有文法G3 S S aA dA bAS 若輸入串W abd 自頂向下的推導過程為 S abd S abAS abS 文法的特點 包含空產(chǎn)生式 aA 對于空產(chǎn)生式左部的非終結符 關鍵是判斷該非終結符的后跟符號 集 分析過程可能是確定的 要進行確定的自頂向下的分析 文法要滿足一定的限制 即文法是LL 1 文法先研究三個定義開始符號集FIRST后跟符號集FOLLOW選擇集合SELECT 2 開始符號集FIRST 的定義 定義 設G VN VT P S 是上下文無關文法 VN VN VT FIRST a a VT且 a 若 則規(guī)定 FIRST 直觀上說文法符號串 的開始符號集是由 推導出的所有的終結符開頭和可能的 組成 例文法G2 S S ApS BqA aA cAB bB dB FIRST Ap a c FIRST Bq b d FIRST a a FIRST cA c FIRST b b FIRST dB d 結論一針對無空產(chǎn)生式的文法G 同一非終結符的任兩個產(chǎn)生式的右部串的First集無交集 即可進行確定的自頂向下分析 3 后跟符號集FOLLOW A 的定義 定義設G VT VN P S 是上下文無關文法 B xAy A B VNx y VN VT FOLLOW A a S Aa a VT 若有S A 則規(guī)定 FOLLOW A 注 輸入串 做為輸入串的結束符 直觀上說 非終結符A的后跟符號集是由句型中緊跟A后的那些終結符 包括 組成 例 文法G3 S S aA dA bAS 由S S得 FOLLOW S 由S aA abAS abbASS abbASaA得a FOLLOW S abbASd得d FOLLOW S FOLLOW S a d 由S aA得 FOLLOW A 由S abAS abAaA得a FOLLOW A abAd得d FOLLOW A FOLLOW A a d FOLLOW A FOLLOW S 解釋當A面對應輸入符a 在自頂向下的分析中應選擇這樣的產(chǎn)生式A i i可導出空串 進行推導 若a First i 則A i可選因 i可能導出空串 A自動獲得匹配 輸入符a有可能與A后的一個符號匹配 故當a Follow A 時 產(chǎn)生式A i亦可選 結論一針對無空產(chǎn)生式的文法G 同一非終結符的任兩個產(chǎn)生式的右部串的First集無交集 即可進行確定的自頂向下分析 結論二 例 文法G3 S S aA dA bAS S aA S d A bAS A First aA a First d d First bAS b First Follow A a d a d a d 回顧 開始符號集FIRST 的定義 定義 設G VN VT P S 是上下文無關文法 A A VN VN VT FIRST a a VT且 a 若 則規(guī)定 FIRST 直觀上說文法符號串 的開始符號集是由 推導出的所有的終結符開頭和可能的 組成 回顧 后跟符號集FOLLOW A 的定義 定義設G VT VN P S 是上下文無關文法 B xAy A B VNx y VN VT FOLLOW A a S Aa a VT 若有S A 則規(guī)定 FOLLOW A 注 輸入串 做為輸入串的結束符 直觀上說 非終結符A的后跟符號集是由句型中緊跟A后的那些終結符 包括 組成 4 選擇集合SELECT A 的定義 定義對給定的上下文無關文法的產(chǎn)生式A A VN V 若 則SELECT A FIRST 若 則SELECT A FIRST FOLLOW A 解釋A的產(chǎn)生式A 1 2 3 A面對應輸入符a 在自頂向下的分析中 對于A i且 i 若a First i 則A i可選對于A j且 j 若a First j Follow A 則A j可選 例 G3 S S aAS dA bASA SELECT S aA FIRST aA a SELECT S d FIRST d d SELECT A bAS FIRST bAS b SELECT A FIRST FOLLOW A a d 若 則SELECT A FIRST 若 則SELECT A FIRST FOLLOW A 結論三同一非終結符的不同產(chǎn)生式A 與A 若SELECT A SELECT A 則一定可以進行確定的自頂向下分析 5 LL 1 文法的定義 定義 上下文無關文法為LL 1 文法的充分必要條件是 對每個非終結符A的兩個不同產(chǎn)生式A 與A 滿足SELECT A SELECT A LL 1 文法的含義是 第一個L 從左到右掃描輸入串第二個L 分析過程用最左推導 1 表明只需向前看1個輸入符號便可以決定選哪個產(chǎn)生式進行推導 類似地 LL k 文法則需要向前看k個輸入符號才可以確定選用哪個產(chǎn)生式 例有文法G S 為 S aASS bA bAA SELECT S aAS a SELECT S b b SELECT A bA b SELECT A a b 由于SELECT A bA SELECT A b 所以文法G S 不是LL 1 文法 當A遇輸入符b時 不能確定選A bA還是A 去推導 4 2LL 1 文法的判別 要判別一個上下文無關文法是否是LL 1 文法分為五步 1 求能推出 的非終結符集2 計算每個產(chǎn)生式右部 的FIRST 集3 計算每個非終結符A的FOLLOW A 集4 計算每個產(chǎn)生式A 的SELECT A 集5 按LL 1 文法的定義判別 1 求出能推出 的非終結符集 算法描述 用T表示能推出 的非終結符集令T Aj Aj 產(chǎn)生式集 對于產(chǎn)生式Ap A1 An若A1 An T 則T T Ap 重復 直至T收斂 不再變化 為止 例G S S AB bCA b B aD C AD bD aS c 非終結符集T 能推出 的非終結符集T為 A B S 2 計算每個產(chǎn)生式右部 的FIRST 集 對每個a VT First a a 對每個A VN 若A 則當前First A 否則當前First A 對每個產(chǎn)生式A X1 Xj Xn First A First A SectionFirst X1 Xj Xn SectionFirst X1 Xj Xn First X1 First X2 First Xj First Xj 1 Xj 1是產(chǎn)生式右部中第一個不能推出 的符號 首先對文法符號X X VT VN 求FIRST X 對每個產(chǎn)生式A X1 Xj Xn做 First A First A SectionFirst X1 Xj Xn 其中SectionFirst X1 Xj Xn First X1 First X2 First Xj First Xj 1 Xj 1是產(chǎn)生式右部中第一個不能推出 的符號若X1 則SectionFirst X1 Xj Xn First X1 若X1 Xn全可推出 則SectionFirst X1 Xn First X1 FIRST Xn 重復3直到每個符號的FIRST集合都不再增大為止 例G S S AB bCA b B aD C AD bD aS c First集 3 First集 2 First集 1 A B C D a b S First集 0 已求出能推出 的非終結符集T為 A B S b b a b ac a ac 斂 斂 斂 斂 斂 斂 斂 c 斂 c c c c 結論 文法符號的First集合如下 First S a b First A b First B a First C a b c First D a c First a a First b b First c c 利用求出每個文法符號的FIRST集求符號串的FIRST集 設右部串 X1X2 Xn當X1 則FIRST FIRST X1 若對任何j 1 j n 都有 FIRST Xj Xj 1為X1X2 Xn中第一個推不出 的符號 則FIRST FIRST X1 FIRST Xj FIRST Xj 1 若對所有i 1 i n 都有 FIRST Xi 則FIRST FIRST X1 FIRST Xn FIRST AB FIRST A FIRST B a b FIRST bC FIRST b b FIRST FIRST b b FIRST AD FIRST A FIRST D b a c FIRST aS FIRST a a 例G S S AB bCA b B aD C AD bD aS c 已求出非終結符的First集合如下 First S a b First A b First B a First C a b c First D a c 產(chǎn)生式右部符號串的開始符集合為 S ABS bCA A bC ADD aS 要判別一個上下文無關文法是否是LL 1 文法分為五步 1 求能推出 的非終結符集T2 計算每個產(chǎn)生式右部 的FIRST 集3 計算每個非終結符A的FOLLOW A 集4 計算每個產(chǎn)生式A 的SELECT A 集5 按LL 1 文法的定義判別 要判別一個上下文無關文法是否是LL 1 文法分為五步 1 求能推出 的非終結符集T2 計算每個產(chǎn)生式右部 的FIRST 集3 計算每個非終結符A的FOLLOW A 集4 計算每個產(chǎn)生式A 的SELECT A 集5 按LL 1 文法的定義判別 3 計算每個非終結符A的FOLLOW A 集 1 對所有A VN 令Follow A 對開始符S 令Follow S 因為S S 顯然 FOLLOW S 2 對每條產(chǎn)生式B xAy 考察產(chǎn)生式右部的每一非終結符A x y V 若y 則Follow A Follow A First y 否則Follow A Follow A First y Follow B 3 重復2 直至對所有A VN Follow A 收斂為止 若a FOLLOW B 則表明S Ba 由于B xAy 且y 則有S Ba xAya xAa 即S xAa 所以a FOLLOW A 例G S 1 S AB 2 S bC 3 A b 4 A 5 B aD 6 B 7 C AD 8 C b 9 D aS 10 D c 已求出非終結符的First集合如下 First S a b First A b First B a First C a b c First D a c D C B a A S Follow集 2 Follow集 1 Follow集 0 c 斂 斂 斂 斂 斂 結論 Follow S Follow A a c Follow B Follow C Follow D 4 計算每個產(chǎn)生式A 的SELECT A 集 按定義計算SELECT A 若右部串 則SELECT A FIRST 若右部串 則SELECT A FIRST FOLLOW A SELECT S AB SELECT S bC SELECT A SELECT A b SELECT B aD SELECT B SELECT C AD SELECT C b SELECT D aS SELECT D c 例G S S AB bCA b B aD C AD bD aS c SELECT S AB FIRST AB FOLLOW S b a SELECT S bC FIRST bC b SELECT A FIRST FOLLOW A a c SELECT A b FIRST b b SELECT B aD FIRST aD a SELECT B FIRST FOLLOW B SELECT C AD FIRST AD b a c SELECT C b FIRST b b SELECT D aS FIRST aS a SELECT D c FIRST c c FIRST AB a b FIRST bC b FIRST FIRST b b FIRST aD a FIRST AD b a c FIRST aS a 5 按LL 1 文法的定義判別 產(chǎn)生式的select集如下 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 b a c SELECT C b b SELECT D aS a SELECT D c c 由于SELECT S AB SELECT S bC b SELECT C AD SELECT C b b 所以文法G S 不是LL 1 文法 對每個非終結符A的任兩個產(chǎn)生式A 與A 滿足SELECT A SELECT A 要判別一個上下文無關文法是否是LL 1 文法分為五步 1 求能推出 的非終結符集T2 計算每個產(chǎn)生式右部 的FIRST 集3 計算每個非終結符A的FOLLOW A 集4 計算每個產(chǎn)生式A 的SELECT A 集5 按LL 1 文法的定義判別 go 由每個產(chǎn)生式的select集構造LL 1 分析表 例G S S AB bCA b B aD C AD bD aS c試判斷該文法是否為LL 1 文法 back 非終結符集T 能推出 的非終結符集T為 A B S 1 求能推出 的非終結符集T back 2 計算每個產(chǎn)生式右部 的FIRST 集 FIRST AB FIRST A FIRST B a b FIRST bC b FIRST FIRST b b FIRST AD FIRST A FIRST D b a c FIRST aS a FIRST aD a back 3 計算每個非終結符A的FOLLOW A 集 back 4 計算每個產(chǎn)生式A 的SELECT A 集 back SELECT S AB FIRST AB FOLLOW S b a SELECT S bC FIRST bC b SELECT A FIRST FOLLOW A a c SELECT A b FIRST b b SELECT B aD FIRST aD a SELECT B FIRST FOLLOW B SELECT C AD FIRST AD FIRST A FIRST A b a c SELECT C b FIRST b b SELECT D aS FIRST aS a SELECT D c FIRST c c 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 b a c SELECT C b b SELECT D aS a SELECT D c c 由每個產(chǎn)生式的select集構造LL 1 分析表 S AB S AB S AB S bC A A A A b B aD B C AD C AD C b C AD D aS D c 5 按LL 1 文法的定義判別 back 根據(jù)LL 1 文法的定義判別 由于SELECT S AB SELECT S bC b SELECT C AD SELECT C b b 所以文法G S 不是LL 1 文法 習題 判別文法G S 是否為LL 1 文法S aSb PP bP P Pc QcQ aQ Q aQ First 2 First 1 P P Q Q S First 0 a First P 斂 b 斂 b First Q 斂 a 斂 a 斂 1 2 ab 斂 b 斂 ab 斂 a 斂 a 斂 ab 斂 ab 斂 習題 判別文法G S 是否為LL 1 文法S aSb PP bP P Pc QcQ aQ Q aQ 2 FIRST aSb FIRST a a FIRST P b FIRST bP FIRST b b FIRST Pc FIRST P b FIRST Qc FIRST Q a FIRST aQ FIRST a a FIRST aQ FIRST a a FIRST Follow 2 Follow 1 P P Q Q S Follow 0 b 收斂 bc bc c 收斂 c 收斂 收斂 收斂 習題 判別文法G S 是否為LL 1 文法S aSb PP bP P Pc QcQ aQ Q aQ 3 SELECT S aSb a SELECT S P b SELECT P bP b SELECT P Pc b SELECT P Qc a SELECT Q aQ a SELECT Q aQ a SELECT Q c 構造LL 1 分析表 根據(jù)LL 1 定義判斷 文法G S 是LL 1 文法 FIRST aSb FIRST a a FIRST P b FIRST bP FIRST b b FIRST Pc FIRST P b FIRST Qc FIRST Q a FIRST aQ FIRST a a FIRST aQ FIRST a a FIRST 4 5 LL 1 分析表 4 3非LL 1 文法到LL 1 文法的等價變換 非LL 1 文法含有左公共因子的文法若文法中含有形如 A r的產(chǎn)生式 稱文法含有左公共因子 顯然 SELECT A SELECT A r 文法不是LL 1 文法 stmt ifexprthenstmt ifexprthenstmtelsestmt other 句型ife1thenife2thens1elses2 推導一stmt ife1thenstmt ife1thenife2thens1elses2 懸空else問題 推導二stmt ife1thenstmtelses2 ife1thenife2thens1elses2 stmt ifexprthenstmt ifexprthenstmtelsestmt other stmt matched stmt unmatched stmtmatched stmt ifexprthenmatched stmtelsematched stmt otherunmatched stmt ifexprthenstmt ifexprthenmatched stmtelseunmatched stmt 含有左遞歸的文法文法中只要含有下列形式的產(chǎn)生式 則稱文法含有左遞歸 A A A B B A 在a 中含有左遞歸的產(chǎn)生式 稱為直接左遞歸在b 中雖然沒有含左遞歸的產(chǎn)生式 但A B A 即A A 稱為間接左遞歸 以直接左遞歸為例 若有如下產(chǎn)生式A A A 其中 和 為任意語法符號串 不難證明有下面關系式 Select A A First A First Select A First 故A A 和A 的Select集相交 不是LL 1 文法 對非LL 1 文法進行等價變換提取左公共因子消除左遞歸注意 變換后的文法不一定是LL 1 文法 文法不含左遞歸和左公共因子只是LL 1 文法的必要條件 1提取左公共因子 將產(chǎn)生式A r等價變換為 A r r 引入一新非終結符A 表示 即得A A A r一般形式 若A 1 2 n 提取左公共因子 即得A A A 1 2 n若在 i中仍含有左公共因子 可再次提取 例文法G1 S aSb aS 提取左因子得 S aS b 引進新非終結符S 得 S aSS S b 2 消除左遞歸 消除直接左遞歸文法G S Sa b可改寫成S bS S aS 一般情形 含直接左遞歸的文法G A A 1 A 2 A m 1 2 n消除左遞歸后改寫成 A 1A 2A nA A 1A 2A mA 消除間接左遞歸將間接左遞歸變成直接左遞歸 再消除算法步驟 把文法的所有非終結符按任一順序排列 如 A1 A2 Ai Ak An從A1開始 按以下順序處理Ak消除左部為Ak的產(chǎn)生式的直接左遞歸若左部為Ak的產(chǎn)生式的右部為非終結符Ai i k 開頭 Ak Ai 則用左部為Ai的所有產(chǎn)生式的右部分別代替Ak Ai 中的Ai 轉至 直至A1 An的消除工作全部完成 退出2 去掉無用產(chǎn)生式 例文法G 1 S Qc c 2 Q Rb b 3 R Sa a 將非終結符排序 R Q S對R 產(chǎn)生式 3 不含直接左遞歸 所以保持不變對Q 把 3 代入 2 得 2 Q Sab ab b 無直接左遞歸對S 把 2 代入 1 得 1 S Sabc abc bc c 有直接左遞歸 消除直接左遞歸得S abcS bcS cS S abcS 處理結果為 R Sa aQ Sab ab bS abcS bcS cS S abcS 由于Q R是不可到達的非終結符 其產(chǎn)生式應刪除 最終得文法G S abcS bcS cS S abcS 示例說明 當非終結符順序為R Q S 消除左遞歸的最終結果為 S abcS bcS cS S abcS 若非終結符順序為S Q R 則消除左遞歸的最終結果為 S Qc cQ Rb bR bcaR caR aR R bcaR 結論 當非終結符的排序不同時 結果的產(chǎn)生式形式不同 但它們是等價的 LL 1 文法任兩個產(chǎn)生式A 都滿足下列條件 FIRST FIRST 若 那么FIRST FOLLOW A LL 1 文法有一些明顯的性質沒有公共左因子不是二義的不含左遞歸 4 4不確定的自頂向下分析思想 不確定的自頂向下分析也稱帶回溯的自頂向下分析定義 不確定是指某個非終結符有多條產(chǎn)生式 而面臨當前輸入符無法唯一確定選用哪條產(chǎn)生式進行推導 只好逐個試探 當分析不成功時 則推翻分析退回到適當位置重新試探其余候選可能的推導 直到把所有可能的推導序列都試完仍不成功 才能確認輸入串不是該文法的句子 不確定的下推自動機理論 PDA deabc WXm 1 q 輸入串 棧 自動機 讀指針 X Z pi 不確定的下推自動機理論 deabc Stack q deabc Stack hi 移動 構形 q w h q a Z pi hi PDA的形式定義PDA與上下文無關語言的重要理論PDA與CFG的對應關系從CFG到PDA的構造舉例 PDA的形式定義PDA與上下文無關語言的重要理論PDA與CFG的對應關系從CFG到PDA的構造舉例 例文法G S S 0S1 c 1 構造其PDA規(guī)則 2 寫出輸入串00c11被接收的移動序列 例1 設有文法S xAyA ab a 對輸入串w xay 推導樹為 由于A的兩條產(chǎn)生式 A ab和A a右部First集交集不為空 從而引起回溯 例2文法G S aASS bA bASA 輸入串w ab 推導樹為 由于A的產(chǎn)生式A 右部能 且Follow A First bAS b 從而引起回溯 例3文法G S SaS b輸入串w baa 推導樹為 由于文法含有左遞歸而引起回溯 4 5確定的自頂向下分析方法 確定的自頂向下分析方法有 LL 1 預測分析器 predictiveparser LL 1 遞歸子程序分析器 recursive descentparser 兩種方法都要求文法是LL 1 文法 4 5確定的自頂向下分析方法 確定的自頂向下分析方法有 LL 1 預測分析器 predictiveparser LL 1 遞歸子程序分析器 recursive descentparser 兩種方法都要求文法是LL 1 文法 4 5 1LL 1 預測分析器 一個預測分析器由三個部分組成 預測分析程序 控制分析過程的進行 分析棧 存放從文法開始符號出發(fā)的自頂向下推導過程中等待匹配的文法符號 開始時放入 和文法開始符 結束時棧應是空的 預測分析表 是一個二維表 元素M A a 的內容是當非終結符A面臨輸入符號a 終結符或 時應選取的產(chǎn)生式 當無產(chǎn)生式時 元素M A a 為出錯處理 error 構造預測分析表步驟 1 把文法轉變?yōu)長L 1 文法 2 求出每條產(chǎn)生式的SELECT集 3 依照SELECT集把產(chǎn)生式填入分析表橫坐標 終結符與 縱坐標 非終結符交點M A a A 放入M A a 若a SELECT A 無產(chǎn)生式的M A a 標記出錯 例 算術表達式文法GE E T TT T F FF E i 1 消除G的左遞歸得到文法G E TE E TE T FT T FT F E i 2 求出每個產(chǎn)生式的select集 G 是LL 1 文法SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F E SELECT F i i F E F i F T T T FT T T T FT T FT T E E E TE E E i E TE E TE 3 依照選擇集合把產(chǎn)生式填入分析表 注 表中空白處為出錯 預測分析程序 上托棧頂符放入X N Y Y N N N N Y Y Y 把 和文法開始符S壓入分析棧 當前輸入符送a 把產(chǎn)生式右部反序進棧 X VT X X a X a 讀下一輸入符到a M X a 有產(chǎn)生式 出錯 結束 出錯 預測分析程序工作過程 輸入串i i i 的分析過程 7 6 5 4 3 2 1 所用產(chǎn)生式 剩余輸入串 分析棧 步驟 8 13 14 15 16 17 12 11 10 9 4 5 2遞歸子程序法 第三次實驗 1實現(xiàn)思想對文法中的每個非終結符編寫一個遞歸過程 識別由該非終結符推出的串 當非終結符有多個產(chǎn)生式時 按當前輸入符屬于哪個產(chǎn)生式的SELECT集可唯一確定選擇哪個產(chǎn)生式進行匹配 當識別到終結符時 與當前輸入符號匹配 并讀取下一輸入符 當識別到非終結符時 則調用該非終結符相應的過程 定義當一個文法滿足LL 1 條件時 就為它構造一個不帶回溯的自頂向下的分析程序這個分析程序由一組遞歸過程組成每個過程對應文法的一個非終結符這樣的一個分析程序稱為遞歸下降分析器 2構造文法G 的遞歸下降分析器 組成 遞歸下降分析器由一個主程序main和每個非終結符對應的一個遞歸過程組成 用到的一些子過程 過程getnext負責讀入下一個TOKEN字過程error 負責報告語法錯誤約定 變量TOKEN存放已讀入的TOKEN字過程進入時變量TOKEN存放了一個待匹配的TOKEN字退出過程時 變量TOKEN中仍存放著一個待匹配的TOKEN字 非終結符相應的分析子程序的構造方法對于每個非終結符U 編寫一個相應的子程序P U 對于產(chǎn)生式U x1 x2 xn x1 xn 關于U的子程序P U 按如下方法構造 if TOKEN first x1 p x1 elseif TOKEN first x2 p x2 else if TOKEN first xn p xn elseERROR 如果U還有空產(chǎn)生式U 則算法中的語句 if TOKEN first xn p xn elseERROR 改寫為if TOKEN first xn p xn elseif TOKEN follow U ERROR 對于符號串x y1y2 ynp x 的含義為 main p y1 p y2 p yn 如yi VN 則P yi 就代表調用yi的子程序 如yi VT 則P yi 為如下述代碼if TOKEN yi getnext TOKEN elseERROR 例 算術表達式文法GE E T TT T F FF E i 1 消除左遞歸得G E TE E TE T FT T FT F E i 2 求出G 的選擇集合SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F E SELECT F i i G 是LL 1 文法 1判斷是否可以應用遞歸子程序法 1 chTOKEN main 主程序 getnext TOKEN E TOKEN 轉匹配E TE if TOKEN ERROR 構造文法G E TE E TE T FT T FT F E i的遞歸下降分析器 2 E TOKEN 匹配E TE T TOKEN 轉匹配T FT E TOKEN 轉匹配E TE 3 E TOKEN 匹配E TE if TOKEN 選擇產(chǎn)生式E TE getnext TOKEN 匹配 讀入下一個Token字 T TOKEN 轉匹配T FT E TOKEN 轉匹配E TE else E 對應的語句 if TOKEN 構造文法G E TE E TE T FT T FT F E i的遞歸下降分析器 4 T TOKEN 匹配T FT F TOKEN 轉匹配F E i T TOKEN 轉匹配T FT 構造文法G E TE E TE T FT T FT F E i的遞歸下降分析器 5 T TOKEN 匹配T FT if TOKEN 選擇產(chǎn)生式T FT getnext TOKEN 匹配 讀下一TOKEN字 F TOKEN 轉匹配F E i T TOKEN 轉匹配T FT else T 對應的語句 if TOKEN 構造文法G E TE E TE T FT T FT F E i的遞歸下降分析器 6 F TOKEN 匹配F E i if TOKEN 選擇產(chǎn)生式F E getnext TOKEN 匹配 讀下一TOKEN字 E TOKEN 轉匹配E TE if TOKEN getnext TOKEN 匹配 讀下一TOKEN字 elseERROR else 選擇產(chǎn)生式F i if TOKEN i getnext TOKEN elseERROR 構造文法G E TE E TE T FT T FT F E i的遞歸下降分析器 特點 優(yōu)點 簡單直觀 易于構造缺點 對文法要求高 必須滿足LL 1 文法 遞歸調用多 速度慢 占用空間多實用性 許多高級語言 如Pascal c等編譯系統(tǒng)常常采用此方法 實驗三 語法分析 實驗目的設計編制一個遞歸下降分析程序 實現(xiàn)對詞法分析程序所提供的單詞序列進行語法檢查和結構分析 加深對構造自頂向下的語法分析器的原理和技術理解與應用 實驗三 語法分析 實驗要求利用C語言編制遞歸下降分析程序 并對C語言的簡單子集進行分析 設計語言文法 運用遞歸下降分析技術 設計和實現(xiàn)語法分析器 具有出錯處理功能 待分析的C語言子集的語法 以擴充的BNF方法描述如下 1 main 2 3 4 5 ID 6 if if else 7 while 8 ii i 9 i 10 本章小結 兩種自頂向下分析方法 遞歸子程序法預測分析法一種文法 LL 1 文法判別方法非LL 1 到LL 1 的轉換