資源描述：
《編譯原理實(shí)用教程 楊德芳 第6章 LR分析技術(shù)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第6章LR分析技術(shù)本章學(xué)習(xí)目標(biāo)LR(k)分析器是這樣一種分析程序：它總是按從左到右的方式掃描輸入串，并按照自底向上的方式進(jìn)行歸約。在這種分析過程中，它至多向前查看k個(gè)輸入符號就能確定當(dāng)前的動(dòng)作是移進(jìn)還是歸約。本章要點(diǎn)：LR分析的基本原理LR（0）分析表的構(gòu)造SLR（1）分析表的構(gòu)造LR（1）分析表的構(gòu)造LALR（1）分析表的構(gòu)造6.1LR分析器的工作原理自底向上分析方法是一種移進(jìn)—?dú)w約過程，當(dāng)分析棧的棧頂符號串形成句柄時(shí)就采取歸約動(dòng)作，因而自底向上分析方法的關(guān)鍵問題是在分析過程中如何確定句柄。LR分析方法根據(jù)當(dāng)前分析棧中的符號串（通常用狀態(tài)來表示）和向右順
2、序查看輸入串的k（k≥0）個(gè)符號就能惟一確定句柄。LR分析方法的歸約過程正是規(guī)范推導(dǎo)的逆過程，所以LR分析過程是一種規(guī)范歸約。LR(k)分析方法是1965年Knuth提出的。括號中的k表示向右查看輸入串符號的個(gè)數(shù)。這種方法比起自頂向下的LL（k）分析方法和自底向上的優(yōu)先分析對文法的限制要少得多。也就是說對于大多數(shù)無二義性上下文無關(guān)文法描述的語言都可以用相應(yīng)的LR分析器識別。而且這種方法還具有分析速度快，能準(zhǔn)確、及時(shí)地指出出錯(cuò)位置等優(yōu)點(diǎn)。它的主要缺點(diǎn)是對于一個(gè)實(shí)用語言文法分析器的構(gòu)造工作量相當(dāng)大，實(shí)現(xiàn)比較困難。1．LR分析的概述一個(gè)LR分析器由三部分組成：（
3、1）總控程序，也稱為驅(qū)動(dòng)程序。對所有的LR分析器總控程序是相同的。（2）分析表或分析函數(shù)。不同的文法其分析表不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表也不同，分析表又可分為動(dòng)作表（ACTION）和狀態(tài)轉(zhuǎn)換表（GOTO）兩部分,，們都用二維數(shù)組表示。（3）分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號所決定。其中SP為棧頂指針，S[i]為狀態(tài)棧，X[i]為文法符號棧。狀態(tài)棧的內(nèi)容按關(guān)系GOTO[Si，X]=Sj。其中X為終結(jié)符或非終結(jié)符。輸入串a(chǎn)bcdefg#總控程序輸出S0#S1X1……SnXnSPACT
4、ION表GOTO表圖6-1LR分析器的工作過程ACTION[Si,a]規(guī)定了棧頂狀態(tài)為Si時(shí)遇到輸入符號a應(yīng)該執(zhí)行的動(dòng)作。動(dòng)作有4種可能：（1）移進(jìn)：當(dāng)Sj=GOTO[Si,a]成立，則把Sj移入到狀態(tài)棧，把a(bǔ)移到文法符號棧，其中i和j表示狀態(tài)。（2）歸約：當(dāng)在棧頂形成句柄為?時(shí)，則用?歸約為相應(yīng)的非終結(jié)符A，即當(dāng)文法中有A??的產(chǎn)生式，當(dāng)?的長度為?（即
5、?
6、=?）時(shí)，則從狀態(tài)棧和文法符號棧中自棧頂向下去掉?個(gè)符號，即棧指針SP減去?；并把A移入文法符號棧，再把滿足Sj=GOTO[Si,A]的狀態(tài)移進(jìn)狀態(tài)棧，其中Si為修改后指針的棧頂狀態(tài)。（3）接受ac
7、c：當(dāng)歸約到文法符號棧中只剩文法的開始符號S時(shí)，并且輸入符號串已結(jié)束即當(dāng)前輸入符是?#?，則分析成功。（4）報(bào)錯(cuò)：當(dāng)遇到狀態(tài)為某一個(gè)狀態(tài)下出現(xiàn)不該遇到的文法符號棧時(shí)，則報(bào)錯(cuò)。說明輸入串不是該文法能接受的句子。2．LR分析舉例表達(dá)式文法G[E]如下所示，它對應(yīng)的LR分析表如表6-1所示。（1）E?E+T（2）E?T（3）T?T*F（4）T?F（5）F?（E）（6）F?i狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r
8、1r110r3r3r3r311r5r5r5r5步驟狀態(tài)棧符號棧輸入串動(dòng)作說明10#i+i*i#ACTION[0,i]=S5,將狀態(tài)5壓棧205#i+i*i#r6：用F?i歸約，GOTO(0，F(xiàn))=3入棧303#F+i*i#r4：用T?F歸約，GOTO(0，T)=2入棧402#T+i*i#r2：用E?T歸約，GOTO(0，E)=1入棧501#E+i*i#ACTION[1,+]=S6，將狀態(tài)6壓棧6016#E+i*i#ACTION[6,i]=S5，將狀態(tài)5壓棧70165#E+i*i#r6：用F?i歸約，GOTO(6，F(xiàn))=3入棧80163#E+F*i#r4：用
9、T?F歸約，GOTO(6，T)=9入棧90169#E+T*i#ACTION[9,*]=S7，將狀態(tài)7壓棧1001697#E+T*i#ACTION[7,i]=S5，將狀態(tài)5壓棧11016975#E+T*i#r6：用F?i歸約，GOTO(7，F(xiàn))=10入棧120169710#E+T*F#r3：用T?T*F歸約，GOTO(6，T)=9入棧130169#E+T#r1：用E?E+T歸約，GOTO(0，E)=1入棧1401#E#ACC：分析成功我們主要是關(guān)心的問題是如何由文法構(gòu)造LR分析表。對于一個(gè)文法，如果能構(gòu)造一張分析表，使得它的每一個(gè)入口均是惟一確定的，則稱這個(gè)
10、文法是LR文法。對于一個(gè)LR文法，當(dāng)分析器對輸入串進(jìn)行自左向右掃描
