網(wǎng)絡(luò)編程 第7章.ppt

1、1.第7章，LR分析，2，學習目的，本章將介紹另一種自下而上的分析方法，即LR分析理解LR分析的基本思想，理解可約前綴和活前綴的概念，理解用于識別活前綴的有限自動機的概念，并掌握LR分析器的構(gòu)造思想和方法，對于給定的語法，LR分析器可以構(gòu)造LR(0)、SLR(1)、LALR(1)和LR(1)四種分析器，并可以判斷給定的語法屬于哪四種分析器。對于給定的輸入符號串，構(gòu)造的分析器可以判斷輸入串是否是給定語法的句子，并理解一些二進制語法在LR分析中的應(yīng)用。3.學習指南，LR分析過程是一個規(guī)范的簡化過程。LR分析方法可以根據(jù)當前分析堆棧中的符號串(通常由狀態(tài)表示)和按順序向右看的輸入串的k (K0)符號

2、，唯一地確定分析器的動作是否被移入或減少，以及哪個產(chǎn)品被用于減少，也就是說，它可以唯一地確定句子句柄。其中，K=0是LR(0)分析器，它對語法有很大的限制，但它是構(gòu)造其他LR類分析器的基礎(chǔ)。因此，我們應(yīng)該掌握構(gòu)造LR(0)項集規(guī)范族的基本原則和方法。4，學習指南，當K=1時，它可以滿足當前大多數(shù)高級語言編譯器的實際需要。本章介紹了三種：單反(1)分析是為學習單反(1)分析做準備；LR(1)項集族的構(gòu)建是LALR(1)分析器的構(gòu)建原則和基礎(chǔ)。LALR(1)解析器是目前大多數(shù)高級編程語言采用的語法分析技術(shù)，也是實現(xiàn)YACC(將在第13章中介紹)的基本原理，這是一個編譯解析器的自移動構(gòu)造工具。5.簡

3、歷1960年，他畢業(yè)于凱斯理工學院，并于1963年獲得加州理工學院數(shù)學博士學位。他在學校一直呆到1968年，然后轉(zhuǎn)到斯坦福大學教書。1992年，他光榮地從斯坦福大學退休，并為計算機編程藝術(shù)TEX排版軟件和METAFONT字體設(shè)計軟件烏托邦84“小創(chuàng)造”作出了貢獻：算法X代表非終止符；a代表終結(jié)者。在狀態(tài)轉(zhuǎn)換表gotoi中，x gotoi，x=j3360，當狀態(tài)堆棧的頂部是I，符號堆棧的頂部是非終結(jié)符x時，轉(zhuǎn)到狀態(tài)j，12，移動到Shift:以指示：動作I，a=Sj動作3360，狀態(tài)j和輸入符號a分別進入狀態(tài)堆棧和符號堆棧，并且輸入字符串前進一個字符。j，a，reduced reduce:表示：

4、ACTIONi，a=rk，其中： k表示kth生產(chǎn)公式。動作：讓第k個產(chǎn)品的右邊部分長度為m，左邊的非終止符為a，狀態(tài)堆棧頂部的m個狀態(tài)位置為P1。從符號棧和狀態(tài)棧中分別彈出m個符號；2.非終結(jié)符進入符號堆棧；3.GOTOp，A=q進入狀態(tài)堆棧。q，A，13，accept意味著：ACTIONi，a=acc action :在符號堆棧中只有#和語法開始符號s，并且輸入字符串只有#，因此分析結(jié)束。錯誤意味著：操作I，a=空白操作：錯誤，終止分析，并轉(zhuǎn)移到錯誤處理程序。14，移入，0進入狀態(tài)堆棧；#進入符號堆棧；Ip指向w#的第一個符號。LR驅(qū)動程序算法流，開始，讓我們成為狀態(tài)堆棧的頂部；a是ip所

5、指向的符號；執(zhí)行ACTIONs，a、接收、報告錯誤、減少、直到(ip指向輸入字符串#的末尾，符號堆棧的頂部是E)；初始化，一個進入符號堆棧；將狀態(tài)j輸入狀態(tài)堆棧；使ip指向下一個符號；| |符號從符號堆棧中彈出；從狀態(tài)堆棧中彈出| |符號；讓我們成為狀態(tài)堆棧的頂部；a .進入符號堆棧；轉(zhuǎn)到，a進入狀態(tài)堆棧；產(chǎn)量公式a；錯誤()；/*調(diào)整誤差函數(shù)*/，返回；注：在分析過程中，符號棧的內(nèi)容只是連接其余輸入字符串的一個句型。a、b、b、c、d、e、a、a、b、s、a、b、b、c、d、e、b、b、a、d、abbcde、aabcde、aacde、aacbe、s、3 024 #ab bcde# reduc

6、ed (Ab)，4 023 #aA bcde#移入，5 0236 #aAb cde# reduced (AAb)，6 023 #aA cde#移入，7 0235 #aAc de#移入，8 02358 # AAcd e # reduced(BD 10 023579 # AAcbe # reduction(SaaCBe)，11 01 #S #驗收，語法GS:(1)SaaCBe(2)Ab(3)AAB(4)BDe適用于LR(0)語法的語法LR(0)的語法能力最弱。從理論上講，最重要的是FA如何識別活動前綴，以及DFA如何識別活動前綴。LR(0)分析表結(jié)構(gòu)，17，可返回前綴：如果一個句型的某個前綴的后綴

7、是該句型的句子句柄，那么這個前綴被稱為該句型的可返回前綴。活前綴：S Aw w，wVT* r是前綴，那么r是g的活前綴。也就是說，一個標準句型的前綴。如果句柄后不包含任何符號，則稱為句型的活前綴。* RM，abbcde，aacde，aaCBE，s，a，aa，AAC，aacb，a，ab，a，aa，aab，a，aa，AAC，aacd，s，右句類型活前綴，例如語法GS P14，18，1。活動前綴不包含句柄的任何符號，并且期望從輸入字符串中看到從A的右邊部分推導(dǎo)出的符號字符串。2.活動前綴只包含句柄的一些符號，表示A12的右子串1已經(jīng)出現(xiàn)在堆棧的頂部，預(yù)計將會看到從輸入字符串2推導(dǎo)出的符號。3.活動前

8、綴已經(jīng)包含句柄的所有符號，表示生產(chǎn)公式A的右邊部分已經(jīng)出現(xiàn)在堆棧的頂部。例如，正確的句型aAbcde的活前綴，a，aA，aAb，其中：a不包含任何句柄符號；AA僅包含手柄符號的一部分；aAb包含手柄的所有符號?；顒忧熬Y和句柄之間的關(guān)系：約定：是句子模式的句柄，相應(yīng)的生成公式是A，=12，19，這表示如果確定了句子模式，句柄將相應(yīng)地被確定，也就是說，最左邊的簡單短語確定可用語法具有無限數(shù)量的活動前綴。因為語法有無限的句型，所以可以構(gòu)造一個有限自動機來識別特定語法的所有活動前綴。根據(jù)DFA，可以構(gòu)建LR(0)分析器的一個重要部分。20.拓寬語法：引入一個新的非終結(jié)符作為語法的新發(fā)起者，并添加一個新

9、的公式：SS 3360 s是新的發(fā)起者，S是最初的初始符號。擴展語法的目的是使語法只有一個以識別符號為左部的產(chǎn)物，從而使構(gòu)造的分析器具有唯一的接受狀態(tài)。21，介紹了用點標記的生成公式，表示在分析過程中已經(jīng)識別出(出現(xiàn)在棧頂)多少個漢語語法G的生成公式的正確符號。定義：在語法的每一個產(chǎn)生式的右邊加一個點，叫做g的LR(0)項。點是表示一個項的標記。用項目表達分析的過程。功能：圓點表示通過識別產(chǎn)品的正確符號所達到的位置?？梢詮狞c的左邊部分推導(dǎo)出的符號串已經(jīng)從輸入串中看到，并且希望看到從點的右邊部分推導(dǎo)出的符號串。也就是說，在生產(chǎn)公式的右邊部分添加一個點來劃分獲取的內(nèi)容和要獲取的內(nèi)容：構(gòu)成一個句柄。

10、二。LR(0)項目，22，例如，如果有一個生產(chǎn)SaAcBe，有以下六個項目：特別是：A、A、B、BVN待減、A、A、aVT移入項目、A減項目、S，這是S S初步驗收項目，上述項目稱為LR(0)項目。根據(jù)點的位置以及點后是終止符還是非終止符或者空，項目可分為以下幾類：saacbe、saacbe、saacbe、saacbe、saacbe、23、活動前綴和句柄，以及LR(0)項目、移入項目或待縮減項目A。描述堆棧頂部沒有句柄的任何符號，并期望此時將A的右邊部分推出?；顒忧熬Y不包含句柄的任何符號。移入項或待縮減項A1.2描述了A12的右子串1已經(jīng)出現(xiàn)在堆棧的頂部，期望看到從輸入字符串推導(dǎo)出的符號2?；?/p>

11、動前綴僅包含手柄符號的一部分?？s減項a描述了生產(chǎn)公式a的右邊部分出現(xiàn)在堆棧的頂部?；顒忧熬Y已經(jīng)包含句柄的所有符號。24，3。構(gòu)造一個確定的有限自動機來識別活動前綴。構(gòu)建狀態(tài)2。定義后續(xù)狀態(tài)3。構(gòu)造一個轉(zhuǎn)換函數(shù)，25，1。構(gòu)造一個狀態(tài)，定義：讓我成為文法G的LR(0)項集，并構(gòu)造閉包(1)作為DFA的狀態(tài)。結(jié)束是一個項目閉包(I)中的每個項目都是等價的，也就是說，從預(yù)期縮減的角度來看是相同的；內(nèi)核：除了SS，圓點不是產(chǎn)品最左邊的項目。初始狀態(tài)：讓項SS成為初始狀態(tài)集的核心，并獲得閉包(SS)作為初始狀態(tài)項集，26，舉例(0)SE(擴展語法)(1)E AA(2)E BB(3)A CA(4)A D(

12、5)B CB(6)B D，SE，E AA，E 2。連續(xù)狀態(tài)定義，(1)連續(xù)項定義使項A.X成為項集合中對應(yīng)于某個狀態(tài)U的項，則項AX是項A.X的后繼項，其中X是語法符號字母表中的任何符號(2)連續(xù)狀態(tài)定義閉包(AX)是狀態(tài)U的后繼狀態(tài)，3)構(gòu)造一個轉(zhuǎn)換函數(shù)，并定義(轉(zhuǎn)換函數(shù))如果I是，I:AX，J:AX，X，用狀態(tài)轉(zhuǎn)移圖表示為：28，定義：標識狀態(tài)的整個DFA項集合(狀態(tài))解決方案：1)初始狀態(tài)：閉包(SS) 2)找到一個新的狀態(tài)，轉(zhuǎn)到(1，X)=閉包(J)，其中1是已求解的狀態(tài)3)重復(fù)2)直到?jīng)]有新的狀態(tài)集出現(xiàn)。1.LR(0)項集規(guī)格族的計算；4.lr (0)分析表的構(gòu)造；29.(0)SE(

13、擴展語法)(1)e aa(2)e bb(3)a ca(4)a d(5)b CB(6)b d、b、E，B，E，bB，B，cB，B，d，c，A，c，A，c A，A，d，c，A d，d，d，I1，I2，I3，I5，I6，B，cB，B，cB，B，d，I8，E，bB，I7，B，d，I9，B，cB，I11，c，d，A c A，I10，A，B，c，A，E aA，I4，d，DFA，p36，30，LR(0)語法活動前綴的項集被識別。該算法構(gòu)造了一個離散傅立葉變換。狀態(tài)圖的描述：(1)每個DFA的狀態(tài)是一個稱為LR(0)項集的項集，整個狀態(tài)集稱為LR(0)項集規(guī)范族；(2)在DFA的任何項目集合中，每個項目都是等

14、價的，這意味著從期望縮減的角度來看是相同的；(3)有一個唯一的初始狀態(tài)和幾個最終狀態(tài)，用幾種活動前綴表示識別狀態(tài)；(4)主動前綴的解決方案：從初始狀態(tài)開始，沿著可達狀態(tài)標記路徑。(5)狀態(tài)反映了手柄的識別。31，LR(0)項目集規(guī)范系列(DFA標識g的活動前綴):I0: SE I1: SE I 2: EAa EAa . ca eBa AD I: eBa I43360 EAa I5: Ac。A BCb ACa Bd A . d I6: Ad I73360 eBB I83360 BcB Bd I9333 60 Bd I10: ACa I11: BcB，32，一個項目集我不能有下列情況：(A)移入和

15、減少項目同時存在，所以我有移位/減少沖突；(二)減少和減少物品同時存在，所以我有減少/減少沖突；如果沒有移動-減少沖突，則構(gòu)造LR(0(0)。顯然，LR(0)語法的每個項集不包含任何沖突項。LR(0)語法很弱，甚至表達式語法也不屬于LR(0)。33，示例(0)SE(擴展語法)(1)E Y；E (2) E Y (3) Y (4) Y i:t，I0，S E，E Y；E，E，Y，Y，E，Y；e，e y .se，e，I，y i:t，i1，I2，i3，y，y i:t，非LR(0)語法，34，2。構(gòu)造lr (0)分析表，假設(shè)語法是LR(0輸出動作子表并轉(zhuǎn)到：G分析表的子表。方法：1 .用C=I0，I1，I2，In，G構(gòu)造LR(0)項集規(guī)范族，即帶有活動前綴的DFA。2.狀態(tài)k的分析動作(在分析表中，我們用項集Ik的下標k來表示相應(yīng)的狀態(tài))如下：(a)如果aa屬于Ik并且GO(Ik，a)=Ij，a是最終符號，那么集actionk，a=SJ (shift j)，ij:閉包(Aa)，a，ik3330。A)=Ij，A是非終端符號，然后設(shè)置gotok，a=j，ik3360 A，ij:closure (aa)，A，ik:aa，(d)如果SS屬于ik，設(shè)置動作k，# acc(接受)(e)，它不能用分析表中的上述規(guī)則填寫信息，(b)如果A屬于Ik，設(shè)置所