第05章語法分析-自底向上分析

1S.PO.P語義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語法分析程序詞法分析程序錯誤處理符號表管理2第五章語法分析－自底向上分析教學目標要求明確自底向上分析方法的一般過程。掌握LR分析方法。掌握構(gòu)造LR(0)、SLR(1)、LR(1)、LALR(1)分析表的方法，會使用LR分析法分析句子。35.1規(guī)范推導、規(guī)范句型和規(guī)范歸約5.2自底向上分析方法的一般過程5.3LR分析方法5.4LR(0)分析器5.5SLR(1)分析器5.6LR(1)分析器5.7LALR(1)分析器5.8語法分析程序的自動生成工具－YACC教學內(nèi)容4任務(wù)：按照程序語言的語法規(guī)則，從由詞法分析輸出的源程序符號串中識別出各類語法成分，同時進行語法檢查，為語義分析和代碼生成作準備。語法分析的任務(wù)詞法分析器語法分析器單詞符號語法樹源程序輸入：Token序列輸出：語法成分及組成表現(xiàn)形式：語法樹錯誤報告出錯處理：定位、續(xù)編譯5語法分析的任務(wù)

遞歸子程序法自頂向下

LL(1)分析法TopDown

算符優(yōu)先分析法自底向上

LR(0)、SLR(1)[LR(1)、LALR]BottomUp文法產(chǎn)生語言自動機識別語言6第5章語法分析——自底向上分析

在自底向上的分析方法中，分析過程從輸入符號串開始，通過反復查找當前句型的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終結(jié)符號，直到歸約到開始符號，從而為輸入符號串構(gòu)造一棵分析樹。開始符號字符串7概念回顧推導、歸約最右推導、最左歸約最左推導、最右歸約句型、句子規(guī)范句型短語、簡單短語、句柄8概念回顧推導如：S=>AB=>=>AaBb=>=>aabb歸約如：aabb=>=>AaBb=>=>AB=>S最右推導與最左歸約如：S=>AB=>ABb=>Abb=>Aabb=>aabb最左推導與最右歸約如：S=>AB=>AaB=>aaB=>aaBb=>aabb文法：S::=ABA::=Aa|aB::=Bb|b9概念回顧句型從識別符號推導0步或多步產(chǎn)生的結(jié)果可由非終結(jié)符和終結(jié)符組成句子是特殊的句型完全由終結(jié)符號組成規(guī)范句型每個句子都有規(guī)范推導10概念回顧短語、簡單短語、句柄例句型：Aabb文法：S::=ABA::=Aa|aB::=Bb|bSABAaBbb短語：Aabb、Aa、bb、b簡單短語：Aa、b句柄：Aa115.1規(guī)范推導、規(guī)范句型和規(guī)范歸約

規(guī)范推導：最右推導規(guī)范句型：通過規(guī)范推導能夠得到的句型規(guī)范歸約：最左歸約文法S::=ABA::=Aa|aB::=Bb|b以下哪些句型是規(guī)范句型？aabb、Ab、Aab、aBb、Abb、AaBb125.1規(guī)范推導、規(guī)范句型和規(guī)范歸約例5.1，有文法G[S]：

S::=aAcBeA::=bA::=AbB::=d試分析符號串a(chǎn)bbcde是否為該文法的句子。

方法一：推導首先，我們從文法的開始符號進行規(guī)范推導，依次使用1、4、3、2規(guī)則，就可得到符號串a(chǎn)bbcde。規(guī)范推導過程如下：S=>aAcBe=>aAcde=>aAbcde=>abbcde13方法二：歸約從符號串開始，向上歸約，如果最終能夠規(guī)約到文法的開始符號S，則同樣可以說明該輸入符號串是這個文法的句子。其歸約過程如圖5.1所示。ScBcAaAbdbScBcAaAbdScBcAadScBcAaS(a)b歸約為A(b)Ab歸約為A(c)d歸約為B(d)aAcBe歸約為S(e)圖5.1歸約過程

145.2自底向上分析方法的一般過程

基本思想從輸入符號串開始，通過重復查找當前句型的“可歸約串”并利用有關(guān)規(guī)則進行規(guī)約若能規(guī)約為文法的識別符號,則表示分析成功,輸入符號串是文法的合法句子,否則有語法錯誤.15【例】G[S]:SaAcBeAbAAb Bd分析句子abbcde#16文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcde步驟符號棧輸入符號串動作1）#abbcde#移進2）#abbcde#移進A3）#abbcde#歸約(A→b)4）#aAbcde#移進A5）#aAbcde#歸約(A→Ab)6）#aAcde#移進7）#aAcde#移進B8）#aAcde#歸約(B→d)9）#aAcBe#移進11）#S#接受S10）#aAcBe#歸約SaAcBeaAcdeaAbcdeabbcde17關(guān)鍵：找出當前句型的“可歸約串”

從自底向上分析的一般過程可看出，如何尋找或確定一個句型的句柄，是構(gòu)造一個自左向右掃描、自底向上分析方法必須要解決的一個關(guān)鍵問題。185.3LR分析方法什么是LR(k)分析:

L：從左到右掃描

R：最右推導的逆過程（最左歸約）

k：是指為了作出分析決定而向前看的輸入符號的個數(shù)是一種規(guī)范歸約過程LR(k)分析技術(shù)Knuth于1965年首先提出19Knuth/~knuth/《計算機程序設(shè)計藝術(shù)第1卷基本算法》

98元《計算機程序設(shè)計藝術(shù)第2卷半數(shù)值算法》98元《計算機程序設(shè)計藝術(shù)第3卷排序與查找》98元205.3.1LR分析器邏輯結(jié)構(gòu)LR分析器有一個給定的輸入符號串，一個分析棧和一個有窮的控制系統(tǒng)。#…

…a2a1輸入符號串:分析棧:S0#......SnA有窮的控制系統(tǒng)：分析表(動作、轉(zhuǎn)換)總控程序215.3.2LR分析表的構(gòu)成動作部分,ACTION表示當前狀態(tài)面臨輸入符號時應(yīng)采取的動作;狀態(tài)轉(zhuǎn)換部分，GOTO表示當前狀態(tài)面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài);。分析器的各個狀態(tài)文法的終結(jié)符號及右界符#文法的非終結(jié)符號225.3.2LR分析表的構(gòu)成分析表的動作有下列四種：移進(Sn)：將輸入符號aj移進符號棧，將狀態(tài)n移進狀態(tài)棧，輸入指針指向下一個輸入符號。歸約(R)：當棧頂形成句柄時，按照相應(yīng)的產(chǎn)生式U→W進行歸約。若產(chǎn)生式右部W的長度為n，則將符號棧棧頂n個符號和狀態(tài)棧棧頂n個狀態(tài)出棧，然后將歸約后的文法符號U移入符號棧，并根據(jù)此時狀態(tài)棧頂?shù)臓顟B(tài)Si及符號棧頂?shù)姆朥，查GOTO表，將GOTO[Si，U]移入狀態(tài)棧。235.3.2LR分析表的構(gòu)成分析表的動作有下列四種：（續(xù)）接受(A)：當輸入符號串到達右界符#時，且符號棧只有文法的開始符號時，則分析成功結(jié)束，接受輸入符號串并結(jié)束分析。報錯(E)：在狀態(tài)棧的棧頂狀態(tài)為Si時，如果輸入符號為不應(yīng)該遇到的符號時，即ACTION[Si，aj]=空白，則報錯，說明輸入符號串有語法錯誤。24例：步驟符號棧輸入符號串動作1）#abbcde#移進2）#abbcde#移進4）#aAbcde#移進6）#aAcde#移進7）#aAcde#移進9）#aAcBe#移進11）#S#接受3）#abbcde#歸約(A→b)5）#aAbcde#歸約(A→Ab)8）#aAcde#歸約(B→d)10）#aAcBe#歸約25LR分析器的關(guān)鍵就是構(gòu)造分析表。表5.2給出了文法G：

0)S→A，1)A→(A)，2)A→a的分析表。表5.3LR分析表265.3.3LR分析過程分析開始時，棧內(nèi)的初始狀態(tài)為0，符號棧為#。當狀態(tài)棧頂為p，當前輸入指針指向的符號是a時，查分析動作表p行、a列。如果得到的動作指示ACTION[p,a]是移進Si，則將a壓入符號棧，將狀態(tài)i壓入狀態(tài)棧，然后將輸入指針指向輸入符號串的下一個符號；如果得到的動作指示是歸約Ri，且歸約產(chǎn)生式為B→β，則從符號棧內(nèi)彈出|β|個符號，從狀態(tài)棧內(nèi)彈出|β|個狀態(tài)，假設(shè)此時出棧后的狀態(tài)棧棧頂為p，查狀態(tài)轉(zhuǎn)換表的p行、B列，得到下一個狀態(tài)GOTO[p,B]=q，并將該后繼狀態(tài)q壓入狀態(tài)棧；如果得到的動作指示是接受，則接受輸入的符號串，分析成功結(jié)束；27開始初始狀態(tài)0和#入棧讀符號根據(jù)棧頂狀態(tài)和輸入符號查分析動作表歸約?移進?接受?查狀態(tài)轉(zhuǎn)換表新狀態(tài)入狀態(tài)棧

按產(chǎn)生式i歸約

根據(jù)產(chǎn)生式i的右部符號的個數(shù)，符號棧和狀態(tài)棧相應(yīng)元素出棧

產(chǎn)生式i的左部符號入棧

輸入符號入符號棧

狀態(tài)i入狀態(tài)棧讀符號分析結(jié)束錯誤YYYNNN28例5.2，利用表5.3分析表分析符號串(a)。解：根據(jù)圖5.3所示的分析流程，表5.4列出了符號串(a)的整個分析過程。S2(a)##01S3a)##(0224R2)##(a0233S5)##(A02441R1##(A)02455ACCEPT##A016295.4LR(0)分析方法拓廣文法：使識別符號唯一例5.3,對文法G∶E→T|E+T|E－TT→i|(E)進行拓廣。解：引入一個新的開始符號S，使得文法的開始符號所在的規(guī)則唯一。G[S]：S→EE→T|E+T|E－TT→i|(E)305.4.1活前綴和可歸前綴LR(k)分析法通過活前綴來幫助確定句柄前綴：句型的任意首部如：abc的前綴有ε,a,b,ab,abc規(guī)范句型：通過規(guī)范推導（規(guī)約）得到的句型活前綴：規(guī)范句型中不含句柄右邊任何符號的前綴可歸前綴：含有句柄的活前綴315.4.1活前綴和可歸前綴對于一個規(guī)范句型來說，其活前綴定義如下：設(shè)λβt是一個規(guī)范句型，即λβt是能用最右推導得到的句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么稱符號串u1u2…ui(其中1≤i≤r)是句型λβt的活前綴。含有句柄的活前綴u1u2…ur稱為可歸前綴。對一個規(guī)范句型來說，活前綴可有多個，可歸前綴只有一個。32例：文法G∶E→T|E+T|E-TT→i|(E)，找規(guī)范句型E+(i-i)的活前綴和可歸前綴。ET+E）E（T－ETiiE+(i-i)的語法樹：活前綴為：E，E+，E+(，E+(i，可歸前綴：E+(i33課堂練習文法G[E]：

E→E+T|TT→T*F|FF→(E)|i1、拓廣文法？2、找規(guī)范句型:E+i*i的活前綴和可歸前綴？拓廣文法G[S]：

S→EE→E+T|TT→T*F|FF→(E)|i活前綴為：E，E+，E+i可歸前綴：E+i34課堂練習文法G[S]：S→A

A→(A)A→a找規(guī)范句型:（a）的活前綴和可歸前綴？活前綴為：（，（a可歸前綴：（aSA（A）a語法樹：35S2(a)##01S3a)##(0224R2)##(a0233S5)##(A02441R1##(A)02455ACCEPT##A016均為活前綴文法G[S]：S→A，A→(A)，A→a36LR分析器的工作過程逐步產(chǎn)生文法的規(guī)范句型活前綴的過程當棧頂形成句柄時，立即進行歸約375.4.2LR(0)項目1、項目的定義對某個文法G來說，如果A→α1α2為G的一條規(guī)則，那么，對規(guī)則的右部加上一個圓點，就成為一個項目。其形式為：A→α1·α2圓點是表示項目的一種標記，也就是說，如果一條規(guī)則的右部標有圓點，那么它就是項目。因為圓點的位置不同，一條規(guī)則可以有幾個項目。項目的直觀意義:在分過程中的某一時刻已經(jīng)規(guī)約的部分和等待規(guī)約部分385.4.2LR(0)項目【例】

文法G[S]：S→aS|b寫出其所有的LR(0)項目。S→·aSS→a·SS→aS·

S→·b

S→b·395.4.2LR(0)項目【例】有文法S→E，E→T|E+T|E-T，T→i|(E)，規(guī)則S→E，有下面兩個項目：

S→·E，S→E·規(guī)則E→E－T，有下面四個項目∶E→·E－T，E→E·－T，E→E－·T，E→E－T·

一個產(chǎn)生式對應(yīng)的項目個數(shù)是右部符號長度加1產(chǎn)生式A→ε的項目個數(shù)只有一個，即A→·

40根據(jù)項目中點的位置和后繼符號，項目分為四類：①移進項目：E→E·－T圓點后面是終結(jié)符，表示棧內(nèi)是句柄的一部分，期待從輸入串中移進一個符號，以形成句柄。②待約項目：E→E－·T圓點后面是非終結(jié)符的項目，表示棧內(nèi)是句柄的一部分，為了形成句柄，期待從剩余的輸入串中進行歸約而得到Ｂ，然后才能繼續(xù)分析A的右部。41③歸約項目：E→E－T·④接受項目：S→E·特殊的歸約項目，使用產(chǎn)生式S’→α進行歸約，表示整個句子已經(jīng)分析完畢，分析成功，也即輸入串為該文法的句子。圓點在最后，表示棧頂?shù)牟糠謨?nèi)容已構(gòu)成所期望的句柄，應(yīng)使用產(chǎn)生式A→α進行歸約。422、項目有效性一個項目A→α1·α2對于某個活前綴λα1是有效的，當且僅當存在某個最右推導。

S|*=>λAt|=>

λα1·α2t

，其中t是終結(jié)符號串。43活前綴與句柄的關(guān)系①活前綴已含有句柄的全部符號表示符號棧頂已形成句柄，可以歸約例：產(chǎn)生式：A→α，活前綴：λα，項目A→α·

對活前綴λα有效。當一個點在最后的項目對活前綴有效時，則可以進行歸約，所以把點在最后的項目稱為歸約項目。44活前綴與句柄的關(guān)系②活前綴只含有句柄的部分符號正期待從剩余輸入串中看到句柄的其余符號例：產(chǎn)生式：A→α１α２，活前綴：λα１，項目A→α１·α２對活前綴λα１有效。45活前綴與句柄的關(guān)系③活前綴不含有句柄的任何符號需將余流的輸入符號移進例：產(chǎn)生式：A→α，活前綴：λ，項目A→·α

對活前綴λ有效。一般來說，活前綴與有效項目是多對多關(guān)系。46例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出該文法的所有項目，并找出對活前綴E－有效的項目。解：首先列出每條規(guī)則對應(yīng)的多個項目：S→E，有項目S→·E，S→E·E→T，有項目E→·T，E→T·E→E+T，有項目E→·E+T，E→E·+T，E→E+·T，E→E+T·E→E-T，有項目E→·E-T，E→E·-T，E→E-·T，E→E-T·T→i，有項目Ｔ→·i，Ｔ→i·T→(E)，有項目T→·(E)，T→(·E)，T→(E·)，T→(E)·

47例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出該文法的所有項目，并找出對活前綴E－有效的項目。對活前綴E－有效的項目：E→E－·T，T→·i和T→·(E)S=>E=>E－TS=>E=>E－T=>E－iS=>E=>E－T=>E－(E)485.4.3構(gòu)造識別活前綴的有窮自動機

回顧：有窮自動機——一種識別裝置兩種：DFA－－確定的有窮自動機NFA－－不確定的有窮自動機0Ｓ13104

Ｚ151識別1(0|1)*101的NFA49正規(guī)文法NFA正規(guī)式654312DFA最小化8750有窮自動機的輸入字符：終結(jié)符和非終結(jié)符狀態(tài)轉(zhuǎn)換：每把一個符號進棧，就看成識別過了該符號，進行狀態(tài)轉(zhuǎn)換。因為LR分析時棧中始終保持是活前綴，所以有窮自動機識別過的符號串也是活前綴。終態(tài)：當識別到可歸約前綴（表明在棧中形成句柄），認為到達了識別句柄的終態(tài)，執(zhí)行歸約5.4.3構(gòu)造識別活前綴的有窮自動機515.4.3構(gòu)造識別活前綴的有窮自動機有兩種方法：（1）求出文法的所有項目，按一定規(guī)則構(gòu)造NFA再確定化為DFA－－工作量大，不適用（2）直接構(gòu)造DFA－－分析DFA狀態(tài)的項目集之間、項目集內(nèi)的項目之間的規(guī)律性直接構(gòu)造出DFA（重點掌握）52直接構(gòu)造DFA若項目集中有Y→·X，另一項目集中有Y→X·，則這兩個項目集之間必有一條X弧。將一個活前綴的可能的無窮集對應(yīng)到一個有窮的有效項目集上。先給出兩個定義：項目集的閉包運算狀態(tài)轉(zhuǎn)移函數(shù)GO比較（P43）：狀態(tài)集Ｐ的ε閉包狀態(tài)集Ｐ的α弧轉(zhuǎn)換集531、項目集的閉包運算設(shè)I為一項目集，I的閉包運算CLOSURE(I)定義如下：I中的每一個項目都屬于CLOSURE(I)。如項目A→α1·Xα2屬于CLOSURE(I)，且X為非終結(jié)符號，則將形式為X→·λ的項目添加到CLOSURE(I)中。重復(1)和(2)，直到CLOSURE(I)封閉為止。54例5.6，有文法：E’→E，E→E+T，E→T，T→T*F，T→F，F(xiàn)→(E)，F(xiàn)→i，設(shè)項目集I={E’→·E}，求CLOSURE(I)。解：根據(jù)閉包運算的第1條，CLOSURE(I)={E’→·E}根據(jù)第2條，E→·E+T和E→·T，加進CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T}根據(jù)第3條，T→·T*F和T→·F，加進CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T，T→·T*F，T→·F}將F→·(E)和F→·i，加進CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T，T→·T*F，T→·F，F(xiàn)→·(E)，F(xiàn)→·i}至此，CLOSURE(I)封閉。55文法：

S'→S S→aS S→b例：I={S'→·S}closure(I)=？{S'→·S,S→·aS,S→·b}練習：I={S→a·S}closure(I)=？{S→a·S,S→·aS,S→·b}562、項目集之間的轉(zhuǎn)換函數(shù)GO假設(shè)有一項目為A→α·Xβ，令X是一個字匯表中的符號，則對項目A→α·Xβ進行讀X操作，結(jié)果為項目A→αX·β。設(shè)I是一個項目集,X是任一文法符號，則項目集之間的轉(zhuǎn)換用GO[I,X]函數(shù)表示，定義為：GO[I,X]=CLOSURE(J)其中J={任何具有[A→αX·β]的項目|[A→α·Xβ]∈I}，即對項目集I中所有的項目進行讀X操作的結(jié)果。572、項目集之間的轉(zhuǎn)換函數(shù)GOCLOSURE(J)為對J進行了閉包運算得到的項目集，稱為I的后繼項目集。令狀態(tài)I代表項目集I，狀態(tài)J代表后繼項目集CLOSURE(J)，用狀態(tài)圖表示則為：IJX58例5.7，文法：E’→E，E→E+T，E→T，T→T*F，T→F，F(xiàn)→(E)，F(xiàn)→i，有項目集I={E’→E·，E→E·+T},

求GO[I，+]解：在I中挑出點后是+的項目有：E→E·+T,將點移到+后面得J={E→E+·T}對J進行閉包運算得CLOSURE(J)={E→E+·T,T→·F,T→·T*F,F→·(E),F→·i}GO(I,+)={E→E+·T,T→·F,T→·T*F,F→·(E),F→·i}用狀態(tài)圖表示為：+I：E’→E·E→E·+TJ:E→E+·T,T→·FT→·T*F,F→·(E),F→·i59文法：

S'→S S→aS S→b求GO(I,b)=?GO(I,b)=closure({S→b·})={S→b·}求GO(I,a)=?GO(I,a)=closure({S→a·S})={S→a·S,S→·aS,S→·b}例：I={S'→·S,S→·aS,S→·b

}603、舉例說識別活前綴的有窮自動機的構(gòu)造方法直接構(gòu)造DFA的思想從S‘→·S開始，得到DFA的初態(tài)項目集然后通過狀態(tài)轉(zhuǎn)換函數(shù)GO求其所有的后繼項目集61【例】文法：0)S→A1)A→(A)2)A→a1、構(gòu)造初態(tài)項目集C0C0＝closure（｛S→·A｝）＝｛S→·A，A→·(A)，A→·a｝2、通過狀態(tài)轉(zhuǎn)換函數(shù)GO求其所有的后繼項目集0:

S→·AA→·(A)A→·a1:

S→A·2:

A→(·A)A→·(A)A→·a

3:

A→a·A(a62R1

A→(A)·5GO[4，)]=5A→(A·)4R2

A→a·3GO[2，A]=4GO[2，(]=2GO[2，a]=3A→(·A)A→·(A)A→·a2ACCEPTS→A·1GO[0，A]=1GO[0，(]=2GO[0，a]=3S→·AA→·(A)A→·a0轉(zhuǎn)換函數(shù)項目集狀態(tài)3、繼續(xù)上述后繼項目構(gòu)造過程，直到?jīng)]有新的項目集產(chǎn)生。630:S→·AA→·(A)A→·a1:S→A·2:A→(·A)A→·(A)A→·a

3:A→a·A(a圖5.8識別活前綴的有窮自動機

4:A→(A·)5:A→(A)·A)(a644、識別活前綴的有窮自動機構(gòu)造算法給定一文法G，該文法的開始符號為S。C={C0,C1,…,Cn},其中C0是開始項目集，C稱為LR(0)項目集規(guī)范族。構(gòu)造DFA的算法：C={closure({S’→·S})};do{for(C中的每個項目集I和每個符號X）

if(GO(I,X)非空,且不在C中)

把GO(I,X)加入C中;}while(C增大)returnC;655.4.4LR(0)分析表的構(gòu)造1)若項目A→α·aβ∈Ci且GO[i，a]=Cj，其中a為終結(jié)符，置ACTION[i，a]=“把狀態(tài)j和符號a移進棧”，簡記為“Sj”；

2)若項目A→α·∈Ci，則對于任何輸入符號a或結(jié)束符#，置ACTION[i，a]=“用產(chǎn)生式A→α進行歸約”，簡記為“Rj”(假定A→α是文法G’的第j條產(chǎn)生式)；

3)若項目S→δ·∈Ci，則置ACTION[i，#]=“接收”，簡記為‘A’；

4)若GO[i，A]=Cj，A為非終結(jié)符，則置GOTO[i，A]=j；

5)分析表中凡不能用規(guī)則①-④添入信息的單元為空或均置上ERROR，表示有錯。66R1

A→(A)·5GO[4，)]=5A→(A·)4R2

A→a·3GO[2，A]=4GO[2，(]=2GO[2，a]=3A→(·A)A→·(A)A→·a2ACCEPTS→A·1GO[0，A]=1GO[0，(]=2GO[0，a]=3S→·AA→·(A)A→·a0轉(zhuǎn)換函數(shù)項目集狀態(tài)（1）若A→α·aβ∈Ci，且GO[i，a]=Cj(a∈VT)，則置ACTION[i，a]=Sj；（2）若A→α·∈Ci，則對任意終結(jié)符a或#，置ACTION[i，a]=Rj；（3）若項目S→δ·∈Ci，則置ACTION[i，#]=ACC；（4）若GO[i，A]=Cj，A為非終結(jié)符，則置GOTO[i，A]=j；（5）凡不能用規(guī)則①-④添入信息的單元為空或均置ERROR。項目集規(guī)范族R1R1R1R15S54R2R2R2R234S3S22ACC11S3S20A#a)(GOTOACTION狀態(tài)LR(0)分析表67【例】文法G[S′]：（1）S′→S（2）S→aS|b構(gòu)造識別G所有活前綴的DFA。解題步驟：（1）寫出文法G的拓廣文法G′；（2）利用函數(shù)closure和GO，求出相應(yīng)的項目集規(guī)范族C；（3）根據(jù)項目集和轉(zhuǎn)換函數(shù)，構(gòu)造識別文法G′所有活前綴的DFA；68【例】文法G[S′]：（1）S′→S（2）S→aS|b構(gòu)造G的LR(0)分析表。解題步驟：（1）寫出文法G的拓廣文法G′；（2）利用函數(shù)closure和GO，求出相應(yīng)的項目集規(guī)范族C；（3）根據(jù)項目集和轉(zhuǎn)換函數(shù)，構(gòu)造LR(0)分析表。695.4.5LR(0)分析器的工作過程若ACTION[S，a]=Sj，a為終結(jié)符，則把a移入符號棧，狀態(tài)j移入狀態(tài)棧。若ACTION[S，a]=Rj，a為終結(jié)符或#號，則用第j個產(chǎn)生式歸約。設(shè)k為第j個產(chǎn)生式右部的符號串長度，將符號棧和狀態(tài)棧頂?shù)膋個元素出棧，將產(chǎn)生式左部符號入符號棧。若ACTION[S，#]=ACC，則為接受，表示分析成功。若GOTO[S，A]=j，A為非終結(jié)符號并且是符號棧的棧頂，表示前一個動作是歸約，A是歸約后移入符號棧的非終結(jié)符，則將狀態(tài)j移入狀態(tài)棧。若ACTION[S，a]=空白，則轉(zhuǎn)入錯誤處理。70文法：0)S→A1)A→(A)2)A→a符號串“((a))”的分析過程如下：4R1)##((A)022456S5)##(A02471R1##(A)02458ACC##A019S5))##((A022454R2))##((a02234S3a))##((0223S2(a))##(022S2((a))##01GOTOACTION輸入符號串符號棧狀態(tài)棧步驟715.4.6LR(0)文法定義如果一個文法G的識別活前綴的DFA的每個狀態(tài)不存在任何沖突項目：（1）移進項目和歸約項目并存；（2）多個歸約項目并存。則稱G是一個LR(0)文法。C0={S→·A,A→·(A),A→·a}：移進項目和待約項目共存。C2={A→(·A),A→·(A),A→·a}：移進項目和待約項目共存。{S→E·,E→E·+T}：移進項目和歸約項目并存。{S→E·,E→E+E·}：多個歸約項目并存。72【例】文法G[S]：0)S→A1)A→ab2)A→a判斷文法G[S]是否為LR(0)文法。構(gòu)造項目集規(guī)范族：移進項目和歸約項目并存所以，該文法不是LR(0)文法。73LR(0)分析表：多重定義745.5SLR(1)分析法若LR(0)項目集規(guī)范族中有項目集Ck含移進-歸約或歸約-歸約沖突，Ck={X→α·bβ,Aγ·，Bδ·}若FOLLOW(A)∩FOLLOW(B)=FOLLOW(A)∩=FOLLOW(B)∩=則解決沖突的SLR(1)技術(shù)：對于歸約項目向前查看一個符號a若a=b，則移進a。若a∈FOLLOW(A)，則用產(chǎn)生式A→γ歸約。若a∈FOLLOW(B)，則用產(chǎn)生式B→δ歸約。其它報錯當文法的LR(0)項目集規(guī)范族中存在移進-歸約沖突或歸約-歸約沖突，但能用SLR(1)技術(shù)解決沖突稱此文法為SLR(1)文法。75SLR解決方法FOLLOW(A)＝｛#｝FOLLOW(A)∩=

表中每個入口不含多重定義765.5.2SLR(1)分析表的構(gòu)造1、若A→α·aβ∈Ci且GO[i，a]=Cj，其中a為終結(jié)符，置ACTION[i，a]=“把狀態(tài)j和符號a移進?！?，簡記為“Sj”；2、若項目A→α·∈Ci，則對a(或#)∈FOLLOW(A)，置ACTION[i，a]=“用產(chǎn)生式A→α進行歸約”，簡記為“Rj”(假定A→α是文法G’的第j條產(chǎn)生式)；3、若項目S’→S·∈Ci，則置ACTION[i，#]＝“ACCEPT”；4、若GO[i，A]=Cj，A為非終結(jié)符，則置GOTO[i，A]＝j(luò)；5、分析表中凡不能用規(guī)則1-4添入信息的元素為空或均置上ERROR。77【例】文法G[S]：0)S→A1)A→ab2)A→aFOLLOW(A)＝｛#｝FOLLOW(A)∩=

78SLR分析法構(gòu)造SLR分析表的步驟如下：1)文法拓廣；2)構(gòu)造LR(0)項目集規(guī)范族；3)求出非終結(jié)符的FOLLOW集；4)由構(gòu)造SLR分析表的算法構(gòu)造SLR分析表79例5.11文法：0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→i構(gòu)造LR(0)項目集規(guī)范族：80求出非終結(jié)符的FOLLOW集：文法：0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→iFOLLOW(S)＝｛#｝FOLLOW(E)＝｛＋，），#｝FOLLOW(T)＝｛*，＋，），#｝FOLLOW(F)＝｛*，＋，），#｝81構(gòu)造SLR分析表：FOLLOW(S)＝｛#｝FOLLOW(E)＝｛＋，），#｝FOLLOW(T)＝｛*，＋，），#｝FOLLOW(F)＝｛*，＋，），#｝82符號串“i*(i+i)”的分析過程：8R2+i)##T*(T0274292R4+i)##T*(F027438

S5i+i)##T*(027463R6+i)##T*(i027457

S4(i+i)##T*0275

S7*(i+i)##T0242R4*(i+i)##F0333R6*(i+i)##i052

S5i*(i+i)##01GOTOACTION輸入符號串符號棧狀態(tài)棧步驟

S11)##T*(E027481510R5##T*(E)0274811168R1)##T*(E+T0274859149R4)##T*(E+F0274863133R6)##T*(E+i027486512

S5i)##T*(E+02748611

S6+i)##T*(E027481083課后習題2證明下面文法是SLR(1)文法，但不是LR(0)文法。S→AA→Ab|bBaB→aAc|a|aAb思路：1、構(gòu)造LR(0)項目集規(guī)范族，看是否有歸約－歸約沖突及歸約－移進沖突。如有，則不是LR(0)文法，轉(zhuǎn)步驟2。2、求出非終結(jié)符的FOLLOW集，構(gòu)造SLR(1)分析表，如表中無重定義，則證明該文法是SLR(1)文法，但不是LR(0)文法。84項目集Ci含有項目A→α·，在i下，若a∈FOLLOW(A)，則用A→α歸約SLR分析法存在的問題因為FOLLOW(A)是指所有可能推導出的句型中，可以跟隨在A后的終結(jié)符號集但LR分析法的歸約應(yīng)該僅對規(guī)范句型中跟隨在A后的終結(jié)符有效這種歸約可能導致歸約擴大化？？？？？85LR(1)分析、LALR(1)分析通過尋找新的向前搜索符來解決A→α·Bβ∈I，則B→·γ∈IFOLLOW(B)FIRST(β)用FIRST(β)代替FOLLOW(B)作為用產(chǎn)生式B→γ進行歸約的超前符號信息5.6LR(1)分析器86歸約－歸約沖突考慮如下拓廣文法：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i

項目集規(guī)范族如下表：該文法不是SLR(1)文法FOLLOW(S)={#}FOLLOW(T)={#,+,=,*}8702134567891011i0SET=+T*iEi+iTi*圖5.9識別活前綴的自動機FOLLOW(S)={#}FOLLOW(T)={#,+,=,*}R5面臨的輸入符號集是:T→i

{+,=,*}R2面臨的輸入符號集是: S→i{#}把即將面臨的輸入符號集稱為超前信息885.6.1LR(1)項目LR(1)項目定義：

一個LR(1)項目的形式為[A→α·β，u]其中第一部分是一個LR(0)項目，即帶有圓點的產(chǎn)生式A→α·β，稱為LR(1)項目的核；第二部分u是一個超前掃描字符，且u∈Vt∪{ε}。對于一個LR(1)項目(A→α·β，u)，如果存在最右推導 S|=*>λAt|=>λαβt其中λα是活前綴，且u是t的第一個符號或者是#，那么說這個LR(1)項目對活前綴λα有效。89例5.11有文法如下：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i考慮哪些項目對活前綴E=T有效最右推導G|=*>E=T+i|=>E=T*i+i，所以項目[T→T·*i，+]對活前綴E=T是有效的。最右推導G|=*>E=T*i|=>E=T*i*i,所以項目[T→T·*i，*]對活前綴E=T是有效的。具有相同的核的項目,可以組合成復合項目。因此上兩項目復合成：[T→T·*i,+:*]。復合項目一般形式：

[A→α·β,α1:α2:…:αm]

905.6.2LR(1)項目集規(guī)范族構(gòu)造算法

1、LR(1)項目集的閉包運算

設(shè)I為一LR(1)項目集，LR(1)閉包(closure)運算CLOSURE(I)定義如下：

1)I中的任何LR(1)項目都屬于CLOSURE(I)。

2)如項目[A→α·Xβ，a]屬于CLOSURE(I)，且X為非終結(jié)符號，則所有形為[X→·δ，b]的項目均添加到CLOSURE(I)中，其中，b∈FIRST(βa)。

3)重復(1)和(2),直到CLOSURE(I)封閉為止。

91例5.12有文法如下：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i對[E→·T,=]進行閉包運算因為有產(chǎn)生式T→i,所以[T→·i,=]也屬于該項目集。有產(chǎn)生式T→T*i,所以[T→·T*i,=]也是該項目集成員。項目[T→·T*i,=]的閉包將產(chǎn)生兩個新項目[T→·i,*]和[T→·T*i,*]。最后對[E→.T,=]進行閉包運算得到的項目集為：CLOSURE（[E→·T,=]）＝{[E→·T,=]、[T→·i,=]、[T→.T*i,=]、[T→.i,*]、[T→.T*i,*]}

925.6.2LR(1)項目集規(guī)范族構(gòu)造算法2、LR(1)項目集轉(zhuǎn)換函數(shù)GO

設(shè)I是一個項目集，X是任一文法符號，則GO[I，X]定義為：GO[I，X]=CLOSURE(J)其中J={任何具有[A→αX·β,a]的項目|[A→α·Xβ,a]∈I},