資源描述：
《《編譯原理》第五章》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、確定分析自頂向下語法分析(CH5)不確定分析(回溯)語法分析算符優(yōu)先分析(CH6)自底向上語法分析LR分析(CH7)注：在以后各個章節(jié)的分析中，若沒有特別說明，所討論的文法均為上下文無關文法。1（上下文無關文法）句型的分析句型分析就是識別一個符號串是否為某文法的句型的過程，或者說是某個推導的構造過程。2語法樹－推導的幾何表示?句型aabbaa的可能推導序列和語法樹例: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語法分析?在語言的編譯實現(xiàn)中，把句子分析的過程稱為語法分析，即完成這個任務的程序稱為語法分析程序或稱為識別程序。分析算法又稱識別算法。?從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結束。4語法分析算法分類?自上而下分析法：從文法的開始符號出發(fā)，尋找與輸入符號串匹配的推導，或者說，為輸入串尋找一個最左推導。?自下而上分析法：從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。
3、5兩種方法反映了語法樹的兩種構造過程。自上而下方法是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結果正好是輸入符號串；自下而上方法則是從輸入符號串開始，以它做為語法樹的結果，自底向上的構造語法樹。6自上而下分析對任何輸入串，試圖用一切可能的辦法，從文法開始符號著手，自上而下地為輸入串構造一棵語法樹，或者說，為輸入串尋找一個最左推導。本質(zhì)上是一個試探過程，反復使用不同地產(chǎn)生式謀求匹配輸入串的過程。7自上而下的語法分析的一般過程例：文法G：S→cAdA→abA→a識別輸入串w=cabd是否為該文法的句子SSScAdc
4、Adab推導過程：S?cAdcAd?cabd8自上而下的語法分析的一般過程(1)S→cAd(2)A→ab(3)A→a識別輸入串w=cad是否為該文法的句子識別輸入串w=caa的過程：1.S?cAd1.S?cAd2.后選擇(2)擴展A，得到推導S?cAd2.選擇(2)擴展A，得到推導S?cAd?cabd?cabd這時3.回溯回到推導S?cAdw的第二個符號可以與葉子結點a得4.選擇(3)擴展A，得到推導S?cAd以匹配，但第三個符號d卻不能與下?cad一葉子結點b匹配5.A沒有選擇了！回溯到推導S?怎么辦？-查看A有無另一個選擇，有！c
5、Ad回溯，把A為根的子樹剪掉，掃描過6.再回溯S有無另一個選擇？沒有！的輸入串中的a吐出來,再試探用產(chǎn)生宣告分析失敗。式（3）構造推導S?cAd?cad9自上而下的語法分析面臨的問題-實現(xiàn)考慮（1）回朔（2）文法的左遞歸性S→Sa10（1）回溯的原因例G[S]:S→xAyA→ab｜a若當前輸入串為xay，首先構造的推導S?xAy?匹配?進一步推導對A可選擇A→ab替換，得S?xAy?xabyxayxaby?匹配?xa都已匹配，當前面臨輸入符為y與b不能匹配，所以將輸入串指針退回到a，對A的替換重新選用下一個產(chǎn)生式A→a進行試探，S?x
6、Ay?xay輸入串中當前符a得到匹配，指針向前移動到y(tǒng)，與語法樹中y匹配，匹配成功。由于相同左部的產(chǎn)生式的右部開始符號相同而引起回溯。11在自上而下的分析方法中如何選擇使用哪個產(chǎn)生式進行推導？假定要被代換的最左非終結符號是B，且有n條規(guī)則：B→A1
7、A2
8、…
9、An，那么如何確定用哪個右部去替代B？-------什么信息用于Parser做正確選擇?(輸入串,文法特點)12（2）左遞歸例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想選用產(chǎn)生式(1)來推導S?Sa語法樹末端結點最左符號為非終結符，
10、所以選用（1）繼續(xù)推導S?Sa?Saa此時語法樹末端結點最左符號仍為非終結符，所以選用（1）繼續(xù)推導S?Sa?Saa?Saaa問題——試圖用S匹配輸入串時，出現(xiàn)：在沒有讀入任何輸入符號的情況下，又得重新要求S去進行新的匹配原因——文法含有左遞歸13自上而下的語法分析－－左遞歸規(guī)則G[S]:S→San??????????????S→bL={ba
11、n≥1}W=baaaSbSSaSa14左遞歸：關于非終結符P的規(guī)則直接左遞歸：若P→Pα
12、βα、β∈V*且α、β不以P開頭一般左遞歸：若P=>*PαS→Aa,A→Sb,…15自上而下分析的進一步
13、討論?自上而下分析也稱面向目標的分析方法，也就是從文法的開始符號出發(fā)企圖推導出與輸入的符號串完全匹配的句子，若能構造出推導則表明輸入串是給定文法的句子，否則表明該輸入不是給定文法的句子。自上而下分析對文法的要求－文法不能
