資源描述：
《自下而上語法分析.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。
1、自下而上語法分析對于產(chǎn)生語言來講，白上而下分析的方法是白然的。對于分析語言來講，H下而上分析的方法更白然，因為語法分析處理的對象一開始都是終結(jié)符組成的輸入序列，而不是文法的開始符號。同時，白下而上分析中最一般的方法，LR方法的能力比白上而下分析的LL方法要強，從而使得LR分析成為最為實用的語法分析方法。3.5.1自下而上分析的基本方法思路：從句子3T?始，從左到右掃描3反復用產(chǎn)生式的左部替換產(chǎn)生式的右部、謀求對3的匹配，最終得到文法的開始符號，或者發(fā)現(xiàn)一個錯誤。3.5.1.1規(guī)范歸約與“剪句柄”定義3.13設咿是文法G的一個句型，若存在
2、S=>aA&則稱魄句型邛湘對于A的短語,特別的，若有A-B則稱幌句型叩湘對于產(chǎn)生式A-郎J直接短語,一個句型的最左一直接短語被稱為句柄。##%1直觀上，句型是一個完報結(jié)構(gòu)，短語是句型屮的某部分。S是一個句型，而不是一個短語。%1短語形成的兩個要素：1從S可以推導出A,即S^>ciA§2從A至少一次推導出B即特征：%1短語：以非終結(jié)符為根的了樹屮所有從左到右排列的葉子；%1直接短語：只有父子關系的樹屮所有從左到右排列的葉子（樹高為2）；%1句柄：最左邊父子關系樹屮所有從左到右排列的葉子（句柄是唯一的）。問題：H1+H2是句型H1+H2*H
3、3的一個短語嗎？答案：不是。因為：%1沒有一個E的子樹，它的全部葉子是H1+H2或者%1找不到某個E,使得E=>*E*E3E=>4~H1+H2定義3.14若（焊文法G的句子且滿足下述條件，則稱序列5???，％是（的一個最左歸約。L2Oo=S（S是G的開始符號）3對任何igM=n）,嗚是從對巴句柄替換為相應產(chǎn)生式左部非終結(jié)符得到的。##注意：最左歸約的逆過稈是一個最右推導，分別稱最右推導和最左歸約為規(guī)范推導和規(guī)范歸約。需要解決的問題：%1確定右句型屮將要歸約的了串（確定句柄）；%1確定如何選擇正確的產(chǎn)生式進行歸約。3.5.1.2移進-歸約
4、分析器工作模式解決方法：移進廿1約分析用一個棧“記住”將要歸約句柄的前綴，旬柄未形成前移進，形成后歸約。移進-歸約分析器的工作模式：（不同的分析表決定了不同的分析方法）輸入記號流_iptop輸出移進約分析表符號狀態(tài)找驅(qū)動器圖3.17移進-歸約分析器模型工作方法：放幻燈，每個幻燈片是一個格局。格局：（斗棧，當前剩余輸入苑改變格局的動作）改變格局的動作：%1移進（曲血:輸入序列屮的終結(jié)符進棧。（匹配終結(jié)符）%1歸約（reduce）:將棧頂句柄替換為對應的非終結(jié)符。（歸約產(chǎn)生式）%1接受（accept）:宣告分析成功。%1報錯（eni）D:發(fā)
5、現(xiàn)語法錯誤，調(diào)用錯誤恢復例稈。從移進-歸約分析過程中可以看出:%1句柄總是在棧頂形成。這是因為在分析的過程屮一旦形成某產(chǎn)生式的右部就立即進行歸約，而從左到右掃描輸入，最早形成的白然是最左的直接短語；%1棧屮保留的總是一個右句型的前綴（加上若干終結(jié)符形成句型），稱為活前綴;%1如果將毎次歸約邏輯上認為是構(gòu)造對應產(chǎn)生式的樹，則分析的全過程邏輯上就是從下到上構(gòu)造一棵分析樹；反Z,如果將每次歸約邏輯上認為是剪去假想分析樹上對應產(chǎn)生式的孩了，則分析的全過稈邏輯上就是從下到上為分析樹剪句柄。需要解決的問題：（由分析表確定）%1如何保證棧屮總是活前綴
6、正確移進）；%1如何確定棧頂已經(jīng)形成句柄并選擇正確的產(chǎn)生式進行歸約正確歸約）。3.5.2LR分析LR分析的特點：%1采用最一般的無冋溯移進坍約方法；%1可分析的文法是LL文法的真超集；%1能夠及時發(fā)現(xiàn)錯誤，快到從左到右掃描輸入序列的最大可能;%1分析表較復雜，難以手工構(gòu)造。3.5.2.1LR分析與LR文法<1>移進-歸約分析表LR分析器的核心是LR分析表和丞動器。文法：E-ETJTZT疥
7、F
8、idid—*ETF0s4s51231s6acc2r2s7r23rdrdrd4r6r6r65s4s586s4s5937s4s5108r5r5r59r
9、ls7rl10r3r3r3actbngoto動作表（action）與轉(zhuǎn)移表（goto）:兩者都是二維數(shù)紐.，且行下標由稱Z為狀態(tài)的整型數(shù)統(tǒng)一表示。動作表以終結(jié)符作為列下標，轉(zhuǎn)移表以非終結(jié)符作為列下標。action根據(jù)輸入確定改變格局的動作，而got。僅指示非終結(jié)符的狀態(tài)轉(zhuǎn)移°故僅有動作表與輸入有關。<2>格局與改變格局的動作開始格局：（#Q（曲第一個動作）結(jié)朿格局：（#0S#,接受）出錯格局：（#§曲報錯）改變格局的四個動作：%1actbnaf=si終結(jié)符進棧并轉(zhuǎn)向狀態(tài)i（移進）%1=方用第拎產(chǎn)生式的左部替換棧屮的句柄（與⑤共同完成歸約
10、）%1=ace接收%1=blank報錯%1goto[s,A]=s'：在勸犬態(tài)下遇到A轉(zhuǎn)移到狀態(tài)i事實上，②和⑤共同完成歸約。算法3.8LR分析輸入輸入序列心和文法G的LR分析表actbn與goto輸出若履于
