自頂向下語法分析方法完ppt課件

1、第第5章章 自頂向下語法分析方法自頂向下語法分析方法G1S有如下特點(diǎn)：有如下特點(diǎn)： 1 每個產(chǎn)生式的右部由終結(jié)符開頭每個產(chǎn)生式的右部由終結(jié)符開頭; 2 同一非終結(jié)符的不同產(chǎn)生式的右部由同一非終結(jié)符的不同產(chǎn)生式的右部由不同的終結(jié)符開頭。不同的終結(jié)符開頭。對于這種文法，在推導(dǎo)過程可以根據(jù)當(dāng)前的對于這種文法，在推導(dǎo)過程可以根據(jù)當(dāng)前的輸入符號獨(dú)一確定選哪個產(chǎn)生式往下推導(dǎo)，輸入符號獨(dú)一確定選哪個產(chǎn)生式往下推導(dǎo)，即分析過程是確定的。即分析過程是確定的。該例闡明，當(dāng)該例闡明，當(dāng)1 產(chǎn)生式右部以終結(jié)符或非終結(jié)符開頭無產(chǎn)生式右部以終結(jié)符或非終結(jié)符開頭無空產(chǎn)生式；空產(chǎn)生式；2 同一非終結(jié)符的不同產(chǎn)生式的右部由不同

2、同一非終結(jié)符的不同產(chǎn)生式的右部由不同的符號開頭。的符號開頭。對于這種文法，在推導(dǎo)過程選用哪個產(chǎn)生式不直對于這種文法，在推導(dǎo)過程選用哪個產(chǎn)生式不直觀，關(guān)鍵是判別產(chǎn)生式右部推出的開場符號觀，關(guān)鍵是判別產(chǎn)生式右部推出的開場符號集集First集，分析過程能夠是確定的。集，分析過程能夠是確定的。文法的特點(diǎn)是：包含空產(chǎn)生式文法的特點(diǎn)是：包含空產(chǎn)生式對于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判別對于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判別該非終結(jié)符的后跟符號集該非終結(jié)符的后跟符號集Follow集，集，分析過程能夠是確定的。分析過程能夠是確定的。例例 文法文法G3S: SaA|d AbAS|由由 S=* S 得得 # FO

3、LLOWS 由由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOWS=#,a,d由由S=* aA 得得 # FOLLOWA 由由S=* abAS=* abAaA 得得 a FOLLOWA =* abAd 得得 d FOLLOWA FOLLOWA=#,a,d文法的特點(diǎn)是文法的特點(diǎn)是:包含空產(chǎn)生式包含空產(chǎn)生式對于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判別對于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判別該非終結(jié)符的后跟符號集，分析過程能該非終結(jié)符的后跟符號集，分析過程能夠是確定的。夠是確定的。假設(shè)假設(shè)*,那么那么SELECTA=FIRST假設(shè)假設(shè)=*, 那么那么SELECTA=FIRST-

4、FOLLOWAq例例 G3S:q SaA q Sd q AbAS q ASELECTSaA=SELECTSd=SELECTAbAS=SELECTA=假設(shè)假設(shè)*,那么那么SELECTA=FIRST假設(shè)假設(shè)=*, 那么那么SELECTA=FIRST-FOLLOWAFIRSTaA=FIRSTd=FIRSTbAS=FOLLOWA=#,a,bbda可確定可確定不可確定不可確定5.2 LL1文法的判別q要判別一個上下文無關(guān)文法能否是要判別一個上下文無關(guān)文法能否是LL1文法文法q分為五步：分為五步：q 1. 求出能推出求出能推出的非終結(jié)符集的非終結(jié)符集q 2. 計(jì)算每個產(chǎn)生式右部計(jì)算每個產(chǎn)生式右部的的FIR

5、ST集集q 3. 計(jì)算每個非終結(jié)符計(jì)算每個非終結(jié)符A的的FOLLOWA集集q 4. 計(jì)算每個產(chǎn)生式計(jì)算每個產(chǎn)生式A的的SELECTA集集q 5. 按按LL1文法的定義判別文法的定義判別步驟：步驟：1第第1次掃描次掃描掃描文法中的產(chǎn)生式掃描文法中的產(chǎn)生式對能直接推出對能直接推出的產(chǎn)生式左部的終結(jié)符標(biāo)的產(chǎn)生式左部的終結(jié)符標(biāo)“是。是。刪除一切右部含有終結(jié)符的產(chǎn)生式。假設(shè)刪除一切右部含有終結(jié)符的產(chǎn)生式。假設(shè)以某一非終結(jié)符為左部的一切產(chǎn)生式以某一非終結(jié)符為左部的一切產(chǎn)生式都被刪除，那么該非終結(jié)符不能推出都被刪除，那么該非終結(jié)符不能推出，將其標(biāo)為將其標(biāo)為“否。否。2. 計(jì)算每個產(chǎn)生式右部計(jì)算每個產(chǎn)生式右部

6、的的FIRST集集2. 計(jì)算每個產(chǎn)生式右部計(jì)算每個產(chǎn)生式右部的的FIRST集集Xn 3計(jì)算每個非終結(jié)符計(jì)算每個非終結(jié)符A的的FOLLOWA集集1.對一切對一切AVN令令FollowA= ;對開場符對開場符S，令令FollowS=# 由于由于S=*S，顯然，顯然#FOLLOWS2. 對每條產(chǎn)生式對每條產(chǎn)生式AxBy，調(diào)查產(chǎn)生式右部的每一非，調(diào)查產(chǎn)生式右部的每一非終結(jié)符終結(jié)符B， x,y V*，假設(shè)，假設(shè)y不能推出不能推出 FollowB=FollowBFirsty,否那么否那么,假設(shè)假設(shè)y *， FollowB=FollowBFirsty- FollowA3. 反復(fù)反復(fù)2，直至對一切，直至對一切

7、AVN，F(xiàn)ollowA收收斂為止。斂為止。假 設(shè)假 設(shè) a F O L L O W A , 那 么 闡 明那 么 闡 明S=*Aa， 由于由于AxBy，且，且y=*,那么有那么有 S=*Aa=xBya=xBa，即即S=*xBa, 所以所以aFOLLOWB5. 按按LL1文法的定義判別文法的定義判別產(chǎn)生式的產(chǎn)生式的select集如下集如下:SELECTSAB= b,a,#SELECTSbC=bSELECTA= a,c,#SELECTAb= bSELECTB= #SELECTBaD=aSELECTCAD= b,a,cSELECTCb =bSELECTDaS= aSELECTDc= c 由于由于 S

8、ELECTSABSELECTSbC=b SELECTCADSELECTCb=b所以文法所以文法GS不是不是LL1文法文法一個上下文無關(guān)文法是一個上下文無關(guān)文法是LL1文法的充沛文法的充沛必要條件是，對每個非終結(jié)符必要條件是，對每個非終結(jié)符A的兩個不同的兩個不同產(chǎn)生式產(chǎn)生式A與與 A，滿足，滿足SELECTASELECTA=q非非LL1文法文法q含有左公共因子的文法含有左公共因子的文法q假設(shè)文法中含有形如：假設(shè)文法中含有形如：A|r 的的產(chǎn)生式，稱文法含有左公共因子。產(chǎn)生式，稱文法含有左公共因子。q顯然顯然,qSELECTASELECTA r,文法不是文法不是LL1文法文法 5.3 某些非某些非

9、LL1文法到文法到 LL1文法的等價變文法的等價變換換含有左遞歸的文法含有左遞歸的文法文法中只需含有以下方式的產(chǎn)生式含有文法中只需含有以下方式的產(chǎn)生式含有或含有或二者皆有，那么稱文法含有左遞或含有或二者皆有，那么稱文法含有左遞歸歸:AAAB BA在中含有左遞歸的產(chǎn)生式，稱為直接左遞在中含有左遞歸的產(chǎn)生式，稱為直接左遞歸；歸；在中雖然沒有含左遞歸的產(chǎn)生式，在中雖然沒有含左遞歸的產(chǎn)生式，但但A=B=A 即即A=+ A,稱為間接稱為間接左遞歸左遞歸. 5.3 某些非某些非LL1文法到文法到 LL1文法的等價變文法的等價變換換以直接左遞歸為例，假設(shè)有如下產(chǎn)生式以直接左遞歸為例，假設(shè)有如下產(chǎn)生式AA A

10、A | |AA其中其中和和為恣意語法符號串。為恣意語法符號串。不難證明有下面關(guān)系式：不難證明有下面關(guān)系式：SelectSelect AA AA First First A A FirstFirst SelectSelect A A First First 故故AAAA和和AA的的SelectSelect集相交，不是集相交，不是LLLL1 1文法文法 5.3 某些非某些非LL1文法到文法到 LL1文法的等價變文法的等價變換換A A A A 不知何時終了不知何時終了不確定不確定假設(shè)假設(shè)*,那么那么SELECTA=FIRST假設(shè)假設(shè)=*, 那么那么SELECTA=FIRST-FOLLOWAq對非對非

11、LL1文法進(jìn)展等價變換文法進(jìn)展等價變換q提取左公共因子提取左公共因子q消除左遞歸消除左遞歸q留意：變換后的文法不一定是留意：變換后的文法不一定是LL1文法，文法不含左遞歸和左公共因子只文法，文法不含左遞歸和左公共因子只是是LL1文法的必要條件。文法的必要條件。 5.3 某些非某些非LL1文法到文法到 LL1文法的等價變文法的等價變換換將產(chǎn)生式將產(chǎn)生式A|r 等價變換為等價變換為: A|r，將括號內(nèi)用一新引入的非終結(jié)符將括號內(nèi)用一新引入的非終結(jié)符A表示表示,得得 AA，A|r普通方式：假設(shè)普通方式：假設(shè)A1|2|n,提取左公共因子后變?yōu)樘崛∽蠊惨蜃雍笞優(yōu)?A1|2|n ， 引進(jìn)新的非終結(jié)符引進(jìn)

12、新的非終結(jié)符A，得：，得： AA，A 1|2|n假設(shè)在假設(shè)在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.1、提取左公因子、提取左公因子q例文法例文法G1：qSaSb|aS|q 提左因子得提左因子得:SaSb|q 引進(jìn)新的非終結(jié)符引進(jìn)新的非終結(jié)符S得得:qSaSS|qS b|1、提取左公因子、提取左公因子1消除直接左遞歸消除直接左遞歸文法文法G:SSa|b可改寫成可改寫成 SbSS aS|普通情形普通情形:含直接左遞歸的文法含直接左遞歸的文法G：AA1|A2|Am|1|2|n消除左遞歸后改寫成：消除左遞歸后改寫成： A1A|2A|nA A1 A|2 A|m A| 2、消除左遞歸

13、、消除左遞歸2消除間接左遞歸消除間接左遞歸將間接左遞歸變成直接左遞歸，再加以消除。將間接左遞歸變成直接左遞歸，再加以消除。算法步驟：算法步驟：把文法的一切非終結(jié)符按任一順序陳列，把文法的一切非終結(jié)符按任一順序陳列，如：如：A1，A2，An從從A1開場，按以下順序處置開場，按以下順序處置Ai。首先，消除左部為首先，消除左部為Ai的產(chǎn)生式的直接左遞歸；的產(chǎn)生式的直接左遞歸；然后，假設(shè)左部為然后，假設(shè)左部為Ai的產(chǎn)生式的右部為非終結(jié)符的產(chǎn)生式的右部為非終結(jié)符Ajj* ，且，且FollowA FirstbAS =b ，從而引起，從而引起回溯回溯q例例3 3q文法文法G G：SSaSSa SbSbq輸入

14、串輸入串w=baaw=baa，推導(dǎo)樹為，推導(dǎo)樹為: :SSabSbSSa回溯回溯回溯回溯SSaSaSSaSab由于文法含有左遞歸而引起回溯由于文法含有左遞歸而引起回溯5.5 確定的自頂向下分析方法確定的自頂向下分析方法q確定的自頂向下分析方法有：確定的自頂向下分析方法有：q遞歸子程序法遞歸子程序法recursive-descent parserq預(yù)測分析法預(yù)測分析法predictive parserq兩種方法都要求文法是兩種方法都要求文法是LL1文法。文法。q實(shí)現(xiàn)思想：實(shí)現(xiàn)思想：q 對應(yīng)文法中每個非終結(jié)符編寫對應(yīng)文法中每個非終結(jié)符編寫一個遞歸過程，識別由該非終結(jié)符推一個遞歸過程，識別由該非終結(jié)

15、符推出的串。當(dāng)非終結(jié)符有多條產(chǎn)生式時，出的串。當(dāng)非終結(jié)符有多條產(chǎn)生式時，按當(dāng)前輸入符屬于哪條產(chǎn)生式的按當(dāng)前輸入符屬于哪條產(chǎn)生式的SELECT集可獨(dú)一確定選擇哪個產(chǎn)生集可獨(dú)一確定選擇哪個產(chǎn)生式進(jìn)展匹配。式進(jìn)展匹配。q當(dāng)識別到終結(jié)符時，與當(dāng)前輸入符號當(dāng)識別到終結(jié)符時，與當(dāng)前輸入符號匹配，并讀取下一輸入符；匹配，并讀取下一輸入符；q當(dāng)識別到非終結(jié)符時，那么調(diào)用該非當(dāng)識別到非終結(jié)符時，那么調(diào)用該非終結(jié)符相應(yīng)的過程。終結(jié)符相應(yīng)的過程。5.5.1 遞歸子程序法遞歸子程序法5.5.1 遞歸子程序法遞歸子程序法由于遞歸子程序法對每個過程能夠存在直由于遞歸子程序法對每個過程能夠存在直接或間接遞歸調(diào)用，所以對某個

16、過程在退接或間接遞歸調(diào)用，所以對某個過程在退出之前能夠又被調(diào)用，因此有些信息需求出之前能夠又被調(diào)用，因此有些信息需求保管，通常在入口時需保管某些信息，出保管，通常在入口時需保管某些信息，出口時需恢復(fù)口時需恢復(fù)先進(jìn)后出棧。先進(jìn)后出棧。優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡單直觀、易于構(gòu)造簡單直觀、易于構(gòu)造缺陷：缺陷：對文法要求高，必需是對文法要求高，必需是LL1文法文法遞歸調(diào)用多，速度慢，占用空間多遞歸調(diào)用多，速度慢，占用空間多5.5.2 預(yù)測分析方法預(yù)測分析方法一個預(yù)測分析器由三個部分組成：一個預(yù)測分析器由三個部分組成：預(yù)測分析程序：控制分析過程的進(jìn)展。預(yù)測分析程序：控制分析過程的進(jìn)展。分析棧：存放從文法開場符號動身

17、的自頂向下推分析棧：存放從文法開場符號動身的自頂向下推導(dǎo)過程中等待匹配的文法符號。開場時放入導(dǎo)過程中等待匹配的文法符號。開場時放入#和文法開場符，終了時棧應(yīng)是空的。和文法開場符，終了時棧應(yīng)是空的。預(yù)測分析表：是一張二維表，元素預(yù)測分析表：是一張二維表，元素MA,a的內(nèi)容的內(nèi)容是當(dāng)非終結(jié)符是當(dāng)非終結(jié)符A面臨輸入符號面臨輸入符號a終結(jié)符或句子終結(jié)符或句子括號時應(yīng)選取的產(chǎn)生式，當(dāng)無產(chǎn)生式時，括號時應(yīng)選取的產(chǎn)生式，當(dāng)無產(chǎn)生式時，元素內(nèi)容為轉(zhuǎn)向出錯處置。元素內(nèi)容為轉(zhuǎn)向出錯處置。構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表步驟：步驟：1 把文法轉(zhuǎn)變?yōu)榘盐姆ㄞD(zhuǎn)變?yōu)長L1文法文法2 求出每條產(chǎn)生式的求出每條產(chǎn)生式的SELEC

18、T集集3 按照按照SELECT集把產(chǎn)生式填入分集把產(chǎn)生式填入分析表析表對每個終結(jié)符或?qū)γ總€終結(jié)符或用用a表示表示假設(shè)假設(shè)a SELECTA，那么把，那么把A放入放入MA,a中，把一切無定義的中，把一切無定義的MA,a標(biāo)上出錯標(biāo)志。標(biāo)上出錯標(biāo)志。例例 算術(shù)表達(dá)式文法算術(shù)表達(dá)式文法GGEE+TTEE+TTTTTT* *FFFFFFE Eii1消除消除G的左遞歸得到文法的左遞歸得到文法 GETE E+TE TFT T*FTFEi2求出每個產(chǎn)生式的求出每個產(chǎn)生式的select集集,G是是LL1文法文法 SELECTETE = ,i SELECTE+TE = + SELECTE = ,# SELECTT

19、FT = ,i SELECTT*FT = * SELECTT = +,# SELECTFE = SELECTF i = i F EF iFTT T*FTT TT FTT FTTEE E+TEEE#*+iETEETE3 3按照選擇集合把產(chǎn)生式填入分析表按照選擇集合把產(chǎn)生式填入分析表注：表中空白處為出錯注：表中空白處為出錯輸入串輸入串i+i*i#的分析過程的分析過程i+*#EETEETEEE+TEE E TT FTT FTTT T* FTT T FF iF E+匹配匹配 +i*i#ET+7E+TE +i*i#E6T +i*i#ET5i匹配匹配 i+i*i#ETi4Fi i+i*i#ETF3TFT

20、i+i*i#ET2ETE i+i*i#E1所用產(chǎn)生式所用產(chǎn)生式剩余輸入串剩余輸入串分析棧分析棧步驟步驟TFTi*i#ET8Fi i#ETF13i匹配匹配 i#ETi14T #ET15E #E16接受接受 #17*匹配匹配 *i#ETF*12T *FT *i#ET11i匹配匹配i*i#ETi10Fii*i#ETF9i+*#EETEETEEE+TEE E TT FTFTT FTFTTT T* FTFTT T FF i iF E EP96 例例1文法文法GS:SaHHaMd|dMAb|AaM|e1.判別判別GS能否為能否為LL1文法，假設(shè)是，文法，假設(shè)是，請構(gòu)造相應(yīng)的請構(gòu)造相應(yīng)的LL1預(yù)測分析表。預(yù)

21、測分析表。2.假設(shè)假設(shè)GS是是LL1文法，請給出對輸入文法，請給出對輸入串串a(chǎn)aabd#的預(yù)測分析過程，并闡明該輸?shù)念A(yù)測分析過程，并闡明該輸入串能否是入串能否是GS的句子。的句子。思緒：思緒：1 1、判別、判別GSGS能否為能否為LLLL1 1文法，假設(shè)是，請構(gòu)造文法，假設(shè)是，請構(gòu)造相應(yīng)的相應(yīng)的LLLL1 1預(yù)測分析表。預(yù)測分析表。判別能否為判別能否為LLLL1 1文法文法5 5個步驟個步驟求出能推出求出能推出 的非終結(jié)符；的非終結(jié)符；FIRSTFIRST集集FOLLOWFOLLOW集集SELECTSELECT集集判別判別構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表2.2.假設(shè)假設(shè)GSGS是是LLLL1 1文

22、法，請給出對輸入串文法，請給出對輸入串a(chǎn)aabd#aaabd#的預(yù)測分析過程，并闡明該輸入串能否是的預(yù)測分析過程，并闡明該輸入串能否是GSGS的的句子。句子。預(yù)測分析過程匹配勝利即闡明是該文法的句子。預(yù)測分析過程匹配勝利即闡明是該文法的句子。判別能否為判別能否為LLLL1 1文法文法5 5個步驟個步驟求出能推出求出能推出 的非終結(jié)符；的非終結(jié)符； 由文法可得，能推出由文法可得，能推出 的非終結(jié)符為的非終結(jié)符為MM求求FIRSTFIRST集集求求FOLLOWFOLLOW集集求求SELECTSELECT集的交集集的交集 Select SelectHHaMdaMdSelectSelectHHd d=ad=ad= Select SelectMMAbAbSelectSelectMM =a,ed,b=a,ed,b= Select SelectA AaMaMSelectSelectA Ae e=ae=ae=判別：該文法是判別：該文法是LLLL1 1文法。文法。GS:SaHHaMd|dMAb|AaM|e非終結(jié)符非終結(jié)符FIRST集集FOLLOW集集SHMAaa,da,e, a,e,#d,bb構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表