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

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