《編譯原理》第五章

《《編譯原理》第五章》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、確定分析自頂向下語(yǔ)法分析(CH5)不確定分析(回溯)語(yǔ)法分析算符優(yōu)先分析(CH6)自底向上語(yǔ)法分析LR分析(CH7)注：在以后各個(gè)章節(jié)的分析中，若沒有特別說明，所討論的文法均為上下文無(wú)關(guān)文法。1（上下文無(wú)關(guān)文法）句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型的過程，或者說是某個(gè)推導(dǎo)的構(gòu)造過程。2語(yǔ)法樹－推導(dǎo)的幾何表示?句型aabbaa的可能推導(dǎo)序列和語(yǔ)法樹例:G[S]:SS→aASaASA→SbASbAaA→SSabaS→aS?aAS?aAa?aSbAa?aSbbaa?aabbaaA→baS?aAS?aSbAS?aabAS?a

2、abbaS?aabbaaS?aAS?aSbAS?aSbAa?aabAa?aabbaa3語(yǔ)法分析?在語(yǔ)言的編譯實(shí)現(xiàn)中，把句子分析的過程稱為語(yǔ)法分析，即完成這個(gè)任務(wù)的程序稱為語(yǔ)法分析程序或稱為識(shí)別程序。分析算法又稱識(shí)別算法。?從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。4語(yǔ)法分析算法分類?自上而下分析法：從文法的開始符號(hào)出發(fā)，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。?自下而上分析法：從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。

3、5兩種方法反映了語(yǔ)法樹的兩種構(gòu)造過程。自上而下方法是從文法符號(hào)開始，將它做為語(yǔ)法樹的根，向下逐步建立語(yǔ)法樹，使語(yǔ)法樹的結(jié)果正好是輸入符號(hào)串；自下而上方法則是從輸入符號(hào)串開始，以它做為語(yǔ)法樹的結(jié)果，自底向上的構(gòu)造語(yǔ)法樹。6自上而下分析對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)著手，自上而下地為輸入串構(gòu)造一棵語(yǔ)法樹，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。本質(zhì)上是一個(gè)試探過程，反復(fù)使用不同地產(chǎn)生式謀求匹配輸入串的過程。7自上而下的語(yǔ)法分析的一般過程例：文法G：S→cAdA→abA→a識(shí)別輸入串w=cabd是否為該文法的句子SSScAdc

4、Adab推導(dǎo)過程：S?cAdcAd?cabd8自上而下的語(yǔ)法分析的一般過程(1)S→cAd(2)A→ab(3)A→a識(shí)別輸入串w=cad是否為該文法的句子識(shí)別輸入串w=caa的過程：1.S?cAd1.S?cAd2.后選擇(2)擴(kuò)展A，得到推導(dǎo)S?cAd2.選擇(2)擴(kuò)展A，得到推導(dǎo)S?cAd?cabd?cabd這時(shí)3.回溯回到推導(dǎo)S?cAdw的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得4.選擇(3)擴(kuò)展A，得到推導(dǎo)S?cAd以匹配，但第三個(gè)符號(hào)d卻不能與下?cad一葉子結(jié)點(diǎn)b匹配5.A沒有選擇了！回溯到推導(dǎo)S?怎么辦？-查看A有無(wú)另一個(gè)選擇，有！c

5、Ad回溯，把A為根的子樹剪掉，掃描過6.再回溯S有無(wú)另一個(gè)選擇？沒有！的輸入串中的a吐出來(lái),再試探用產(chǎn)生宣告分析失敗。式（3）構(gòu)造推導(dǎo)S?cAd?cad9自上而下的語(yǔ)法分析面臨的問題-實(shí)現(xiàn)考慮（1）回朔（2）文法的左遞歸性S→Sa10（1）回溯的原因例G[S]:S→xAyA→ab｜a若當(dāng)前輸入串為xay，首先構(gòu)造的推導(dǎo)S?xAy?匹配?進(jìn)一步推導(dǎo)對(duì)A可選擇A→ab替換，得S?xAy?xabyxayxaby?匹配?xa都已匹配，當(dāng)前面臨輸入符為y與b不能匹配，所以將輸入串指針退回到a，對(duì)A的替換重新選用下一個(gè)產(chǎn)生式A→a進(jìn)行試探，S?x

6、Ay?xay輸入串中當(dāng)前符a得到匹配，指針向前移動(dòng)到y(tǒng)，與語(yǔ)法樹中y匹配，匹配成功。由于相同左部的產(chǎn)生式的右部開始符號(hào)相同而引起回溯。11在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：B→A1

7、A2

8、…

9、An，那么如何確定用哪個(gè)右部去替代B？-------什么信息用于Parser做正確選擇?(輸入串,文法特點(diǎn))12（2）左遞歸例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想選用產(chǎn)生式(1)來(lái)推導(dǎo)S?Sa語(yǔ)法樹末端結(jié)點(diǎn)最左符號(hào)為非終結(jié)符，

10、所以選用（1）繼續(xù)推導(dǎo)S?Sa?Saa此時(shí)語(yǔ)法樹末端結(jié)點(diǎn)最左符號(hào)仍為非終結(jié)符，所以選用（1）繼續(xù)推導(dǎo)S?Sa?Saa?Saaa問題——試圖用S匹配輸入串時(shí)，出現(xiàn)：在沒有讀入任何輸入符號(hào)的情況下，又得重新要求S去進(jìn)行新的匹配原因——文法含有左遞歸13自上而下的語(yǔ)法分析－－左遞歸規(guī)則G[S]:S→San??????????????S→bL={ba

11、n≥1}W=baaaSbSSaSa14左遞歸：關(guān)于非終結(jié)符P的規(guī)則直接左遞歸：若P→Pα

12、βα、β∈V*且α、β不以P開頭一般左遞歸：若P=>*PαS→Aa,A→Sb,…15自上而下分析的進(jìn)一步

13、討論?自上而下分析也稱面向目標(biāo)的分析方法，也就是從文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的符號(hào)串完全匹配的句子，若能構(gòu)造出推導(dǎo)則表明輸入串是給定文法的句子，否則表明該輸入不是給定文法的句子。自上而下分析對(duì)文法的要求－文法不能