自下而上語法分析

《自下而上語法分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、自下而上語法分析對于產(chǎn)生語言來講，自上而下分析的方法是自然的。對于分析語言來講，自下而上分析的方法更自然，因為語法分析處理的對象一開始都是終結(jié)符組成的輸入序列，而不是文法的開始符號。同時，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要強(qiáng)，從而使得LR分析成為最為實用的語法分析方法。3.5.1自下而上分析的基本方法思路：從句子ω開始，從左到右掃描ω，反復(fù)用產(chǎn)生式的左部替換產(chǎn)生式的右部、謀求對ω的匹配，最終得到文法的開始符號，或者發(fā)現(xiàn)一個錯誤。3.5.1.1規(guī)范歸約與“剪句柄”定義3.13設(shè)αβδ是文

2、法G的一個句型，若存在S=*>αAδ，A=+>β，則稱β是句型αβδ相對于A的短語，特別的，若有A→β，則稱β是句型αβδ相對于產(chǎn)生式A→β的直接短語。一個句型的最左直接短語被稱為句柄。##①直觀上，句型是一個完整結(jié)構(gòu)，短語是句型中的某部分。S是一個句型，而不是一個短語。②短語形成的兩個要素：1．從S可以推導(dǎo)出A，即S=*>αAδ；2．從A至少一次推導(dǎo)出β，即A=+>β。特征：①短語：以非終結(jié)符為根的子樹中所有從左到右排列的葉子；②直接短語：只有父子關(guān)系的樹中所有從左到右排列的葉子（樹高為2）；③句柄：最左邊父子關(guān)系樹

3、中所有從左到右排列的葉子（句柄是唯一的）。問題：id1+id2是句型id1+id2*id3的一個短語嗎？答案：不是。因為：①沒有一個E的子樹，它的全部葉子是id1+id2；或者②找不到某個E，使得E=>*E*id3，E=>+id1+id2定義3.14若α是文法G的句子且滿足下述條件，則稱序列αn，αn-1，...，α0是α的一個最左歸約。1.αn=α2.α0=S（S是G的開始符號）3.對任何i(0

4、別稱最右推導(dǎo)和最左歸約為規(guī)范推導(dǎo)和規(guī)范歸約。需要解決的問題：①確定右句型中將要歸約的子串（確定句柄）；②確定如何選擇正確的產(chǎn)生式進(jìn)行歸約。3.5.1.2移進(jìn)-歸約分析器工作模式解決方法：移進(jìn)-歸約分析――用一個?！坝涀　睂⒁獨w約句柄的前綴，句柄未形成前移進(jìn)，形成后歸約。移進(jìn)-歸約分析器的工作模式：（不同的分析表決定了不同的分析方法）工作方法：放幻燈，每個幻燈片是一個格局。格局：（#棧，當(dāng)前剩余輸入#，改變格局的動作）改變格局的動作：①移進(jìn)（shift）：輸入序列中的終結(jié)符進(jìn)棧。（匹配終結(jié)符）②歸約（reduce）：將棧

5、頂句柄替換為對應(yīng)的非終結(jié)符。（歸約產(chǎn)生式）③接受（accept）：宣告分析成功。④報錯（error）：發(fā)現(xiàn)語法錯誤，調(diào)用錯誤恢復(fù)例程。從移進(jìn)-歸約分析過程中可以看出：①句柄總是在棧頂形成。這是因為在分析的過程中一旦形成某產(chǎn)生式的右部就立即進(jìn)行歸約，而從左到右掃描輸入，最早形成的自然是最左的直接短語；②棧中保留的總是一個右句型的前綴（加上若干終結(jié)符形成句型），稱為活前綴；－13－③如果將每次歸約邏輯上認(rèn)為是構(gòu)造對應(yīng)產(chǎn)生式的樹，則分析的全過程邏輯上就是從下到上構(gòu)造一棵分析樹；反之，如果將每次歸約邏輯上認(rèn)為是剪去假想分析樹上

6、對應(yīng)產(chǎn)生式的孩子，則分析的全過程邏輯上就是從下到上為分析樹剪句柄。需要解決的問題：（由分析表確定）①如何保證棧中總是活前綴(正確移進(jìn))；②如何確定棧頂已經(jīng)形成句柄并選擇正確的產(chǎn)生式進(jìn)行歸約(正確歸約)。3.5.2LR分析LR分析的特點：①采用最一般的無回溯移進(jìn)-歸約方法；②可分析的文法是LL文法的真超集；③能夠及時發(fā)現(xiàn)錯誤，快到從左到右掃描輸入序列的最大可能；④分析表較復(fù)雜，難以手工構(gòu)造。3.5.2.1LR分析與LR文法<1>移進(jìn)-歸約分析表LR分析器的核心是LR分析表和驅(qū)動器。文法：E→E-T

7、TT→T*F

8、FF→-

9、F

10、idid-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3actiongoto動作表（action）與轉(zhuǎn)移表（goto）：兩者都是二維數(shù)組，且行下標(biāo)由稱之為狀態(tài)的整型數(shù)統(tǒng)一表示。動作表以終結(jié)符作為列下標(biāo)，轉(zhuǎn)移表以非終結(jié)符作為列下標(biāo)。action根據(jù)輸入確定改變格局的動作，而goto僅指示非終結(jié)符的狀態(tài)轉(zhuǎn)移。故僅有動作表與輸入有關(guān)。<2>格局與改變格局的動作－13－開始格局：（#0，ω#，第一個動作）結(jié)

11、束格局：（#0S，#，接受）出錯格局：（#δ，ω'#，報錯）改變格局的四個動作：①action[s,a]=si：終結(jié)符進(jìn)棧并轉(zhuǎn)向狀態(tài)i（移進(jìn)）②=rj：用第j個產(chǎn)生式的左部替換棧中的句柄（與⑤共同完成歸約）③=acc：接收④=blank：報錯⑤goto[s,A]=s'：在s狀態(tài)下遇到A轉(zhuǎn)移到狀態(tài)s'。事實上，②和⑤共同完成歸約。算