自下而上語法分析-LR

LR（K）方法概述一種自下而上的語法分析方法。當(dāng)前最廣義的無回溯的“移進(jìn)-歸約”方法。根據(jù)棧中的符號串和向前查看的k(k0)個輸入符號，就能唯一確定分析器的動作是移進(jìn)還是歸約，以及用哪個產(chǎn)生式進(jìn)行歸約。優(yōu)點：文法適用范圍廣；識別效率高；查錯能力強；可自動構(gòu)造。邏輯組成：總控程序＋LR分析表分析表的四種構(gòu)造方法：LR(0)，SLR(1)，規(guī)范LR，LALR

LR分析方法的基本思想是：在規(guī)范歸約過程中，一方面記住已移進(jìn)和歸約出的整個符號串(歷史)，另一方面又根據(jù)所用產(chǎn)生式推測未來可能碰到的輸入符號(對未來的展望)。當(dāng)某一符號串類似于句柄出現(xiàn)在棧頂時，需要根據(jù)已記載的“歷史”、“展望”和“現(xiàn)實”的輸入符號三方面的內(nèi)容來決定棧頂?shù)姆柎欠駱?gòu)成了真正的句柄，是否需要歸約。一個LR分析器的組成見下圖。LR分析方法的基本思想一個LR分析器由3個部分組成：LR分析程序，又稱總控程序。所有的LR分析器都是相同的。分析表(分析函數(shù))，不同的文法分析表不同，同一個文法采用的LR分析器不同時，分析表也不同，分析表又可分為動作表(ACTION)和狀態(tài)轉(zhuǎn)換(GOTO)表兩個部分，它們都可用二維數(shù)組表示。分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。狀態(tài)棧：(S0,#)為預(yù)先放到棧中的初始狀態(tài)和符號。文法符號：X1X2…Xm是目前已移進(jìn)并歸約出的句型部分。其實它是多余的，已經(jīng)概括到狀態(tài)里。分析器實際上是一個帶有先進(jìn)后出棧的確定的有窮自動機。將“歷史”和“展望”綜合成“狀態(tài)”，分析棧用來存放狀態(tài)，狀態(tài)概括了從分析開始直到某一歸約階段的全部歷史和展望資料，不必象算符優(yōu)先分析法中要翻閱棧中的內(nèi)容才能決定是否要進(jìn)行歸約。只需根據(jù)棧頂狀態(tài)和輸入符號就可以唯一決定下一個動作。總控程序根據(jù)分析表的內(nèi)容來決定其下一步的處理動作，分析表是根據(jù)具體的文法按某種規(guī)則構(gòu)造出來的。LR方法：根據(jù)具體文法的分析表對輸入串進(jìn)行分析處理。LR分析過程：在總控程序的控制下，從左到右掃描輸入符號串，根據(jù)分析棧中的狀態(tài)和當(dāng)前輸入符號，按分析表中的內(nèi)容完成相應(yīng)的分析工作。LR分析表的構(gòu)成狀態(tài)動作表ACTION狀態(tài)轉(zhuǎn)換表GOTOa1a2…#X1X2…XkS1S2...Sn分析表的動作部分：ACTION[Si，aj]表示當(dāng)分析狀態(tài)棧的棧頂為Si，輸入符號為aj時應(yīng)執(zhí)行的動作；表中GOTO[Si,Xj]指出棧頂狀態(tài)為Si，碰到文法符號為Xj時應(yīng)轉(zhuǎn)到的下一狀態(tài)；動作有下列四種：移進(jìn)(Sn)，歸約(R)，接受(A)，報錯(E)LR分析器的關(guān)鍵就是構(gòu)造分析表。文法G：0)S→A，1)A→(A)，2)A→a的分析表：狀態(tài)ACTIONGOTO()a#A0S2S311ACCEPT2S2S343R2R2R2R24S55R1R1R1R1LR的分析流程開始初始狀態(tài)0和#入棧讀符號根據(jù)棧頂狀態(tài)和輸入符號查分析動作表歸約?移進(jìn)?接受?查狀態(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é)束錯誤YYYNNN步驟狀態(tài)棧符號棧輸入串ACTIONGOTO說明10#(a)#S2開始時，0入狀態(tài)棧，#入符號棧，輸入符號為(，查動作表0行(列為S2，2入狀態(tài)棧，(入符號棧。202#(a)#S3輸入符號為a，查動作表2行a列為S3，3入狀態(tài)棧，a入符號棧。3023#(a)#R24輸入符號為)，查動作表3行)列為R2，用A→a歸約，a出符號棧、A入符號棧，3出狀態(tài)棧、2為棧頂，查GOTO表2行A列得4，4入狀態(tài)棧。4024#(A)#S5輸入符號為)，查動作表4行)列為S5，5入狀態(tài)棧，)入符號棧。50245#(A)#R11輸入符號為#，查動作表5行#列為R1，用A→(A)歸約，(A)出符號棧、A入符號棧，245出狀態(tài)棧、0為棧頂，查GOTO表0行A列得1，1入狀態(tài)棧。601#A#ACCEPT輸入符號為#，查動作表1行#列為ACCEPT，接受。利用分析表分析符號串(a)LR文法：對一個文法，如果能夠構(gòu)造一個分析表，且它的每個入口均是唯一的如何構(gòu)造LR分析表？活前綴和可歸前綴前綴：指從任意符號串x的末尾刪除0或多個符號后得到的符號串，如u、uni、university都是university的前綴?；钋熬Y：設(shè)λβt是一個規(guī)范句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么稱符號串u1u2…ui(其中1≤i≤r)是句型λβt的活前綴。可歸前綴：含有句柄的活前綴u1u2…ur稱為可歸前綴。有文法G∶E→T|E+T|E-T，

T→i|(E)，找規(guī)范句型E+(i-i)的活前綴和可歸前綴。解：首先畫出E+(i-i)的語法樹可找出第一個i是句柄，那么λβ=E+(i，t=-i)因此活前綴為：E，E+，E+(，E+(i，其中E+(i是可歸前綴。ET+E）E（T-ETii活前綴意味著，當(dāng)前還未形成句柄，或剛剛形成句柄。在活前綴的右邊添上一些終結(jié)符號后，總可以構(gòu)成一個規(guī)范句型。LR識別過程中，棧里面的符號就是一個活前綴。棧里面的符號添加上適當(dāng)?shù)慕K結(jié)符號串就可以得到一個句型。在任何時候，只要輸入串已掃描過的部分能構(gòu)成一個活前綴，則意味著所掃描過的這一部分沒有錯誤?；钋熬Y和句柄的關(guān)系

1.活前綴不含有句柄的任何符號；

2.活前綴含有句柄的部分符號；

3.活前綴已含有句柄的全部符號。LR(0)項目LR(0)項目的定義：文法的每一個產(chǎn)生式的右部添加一個圓點（.），則構(gòu)成文法的一個LR(0)項目。直觀地，一個項目指明了在分析過程的某一時刻，已經(jīng)看到的一個產(chǎn)生式的多少。LR(0)項目A→xyz的LR(0)項目：A→.xyzA→x.yzA→xy.zA→xyz.項目集：若干個項目組成的集合稱為項目集。例如：對于上述產(chǎn)生式的4個項目即構(gòu)成一個項目集。后繼符號：在項目中緊跟在符號“·”后面的符號稱為該項目的后繼符號。后繼符號表示下一時刻讀到的符號。后繼符號有多種，據(jù)此將項目分為多種：后繼符號為終結(jié)符：Aα·aβ,稱為移進(jìn)項目；后繼符號為非終結(jié)符：Aα·Bβ,稱為待約項目；后繼符號為空：即圓點在最右邊Aα·,稱為歸約項目；歸約項目的左邊是文法的開始符號Sα·,稱為接受項目。后繼符號集：項目集中各項目的后繼符號所組成的集合稱為后繼符號集。例如：項目集｛EE·＋T，F(xiàn)·i｝的后繼符號集為｛＋，i｝可以由文法的所有LR(0)項目，構(gòu)造識別文法所有活前綴的FA。在此構(gòu)造過程中，需要對文法進(jìn)行拓廣，并利用CLOSURE函數(shù)和GO函數(shù)。LR(0)項目集規(guī)范族定義定義：構(gòu)成識別一個文法活前綴的DFA的項目集（狀態(tài)）的全體稱為這個文法的LR(0)項目集規(guī)范族。文法G的拓廣文法文法G[S]的拓廣文法：G’[S’]=G[S]+{S’→S}拓廣的原因：使得語法分析有唯一的“接受”項目：S’→S.項目集I的閉包CLOSURE(I)設(shè)I是文法G的任一項目集，則定義和構(gòu)造CLOSURE(I)的規(guī)則如下：①屬于I的任何項目也屬于CLOSURE(I)；②若A→α.Bβ屬于CLOSURE(I)，那么，對于任何關(guān)于B的產(chǎn)生式B→γ,項目B→.γ也屬于CLOSURE(I)；③重復(fù)執(zhí)行以上兩步，直到CLOSURE(I)不再增大為止。項目集閉包的例子文法： 0.E’→E 1.E→E+T 2.E→T 3.T→T*F 4.T→F 5.F→(E) 6.F→iI={[E’→.E]}CLOSURE(I)還包含以下項：[E→.E+T][E→.T][T→.T*F][T→.F][F→.i][F→.(E)]GO(I,X)函數(shù)用于定義項目集之間的轉(zhuǎn)換。定義：設(shè)I是一個項目集,X是任一文法符，則GO(I,X)定義為：GO(I,X)=CLOSURE(J),其中J={任何具有[A→αX.β]的項目|[A→α.Xβ]∈I}I:A→α·XβJ:A→αX·βXLR(0)項目集規(guī)范族構(gòu)造算法ITEMSETS(G’);{C={CLOSURE({S’→.S})};重復(fù)以下操作:對C中每個項目I和I中每個緊接“.”的文法符號xIfGO(I,x)非空且不屬于Cthen將GO(I,x)加到C直到C不再增大；}例：拓廣文法為：0)S→A，1)A→(A)，2)A→a0:

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

S→A.2:

A→(.A)A→.(A)A→.a

3:

A→a.A(a識別活前綴的有窮自動機

4:

A→(A.)5:

A→(A).A)(aLR(0)項目集規(guī)范族的說明如果LR(0)項目集規(guī)范族中的每個項目集看做FA一個狀態(tài)，則項目集規(guī)范族的GO函數(shù)把這些項目集連接成一個DFA。令I(lǐng)0(CLOSURE({S’→.S}))為DFA的初態(tài)，則該DFA就是恰好識別文法所有活前綴的有限自動機。結(jié)論：對于任一文法G,關(guān)于該文法的LR(0)項目集規(guī)范族的GO函數(shù)定義了一個識別文法所有活前綴的DFA。有效項目定義：一個項目[A→α1.α2]稱為對某個活前綴λα1是有效的，當(dāng)且僅當(dāng)存在某個規(guī)范推導(dǎo)S=*>λAt=>λα1α2t

其中，α1α2是規(guī)范句型λα1α2t的句柄，t是一個終結(jié)符號串。有效項目的識別：有效項目的圓點就是活前綴的終止點。引入有效項目的意義：根據(jù)棧中活前綴的有效項目確定下一步的動作。具體的，α2=ε,說明棧中已經(jīng)形成句柄，下一步應(yīng)該進(jìn)行歸約；α2

≠ε,說明棧中尚未形成句柄，下一步應(yīng)該進(jìn)行移進(jìn)?；钋熬Y與有效項目的關(guān)系同一項目可能對多個活前綴是有效的對同一活前綴，可能存在多個有效項目活前綴有效項目的結(jié)論一個活前綴w的有效項目集，正是由識別文法所有活前綴的DFA的初態(tài)出發(fā)，經(jīng)由標(biāo)記為w的路徑所到達(dá)的那個項目集。語法分析過程中，棧中的活前綴的有效項目集就是棧頂?shù)臓顟B(tài)所代表的那個項目集。舉例構(gòu)造識別下列文法活前綴的有窮自動機S→A|BA→aAb|cB→aBb|d指出LR（0）項目的分類LR(0)文法如果文法G’的項目集規(guī)范族的每個項目集中不存在下述沖突項目：①移進(jìn)項目和歸約項目并存，②多個歸約項目并存，則稱文法G’為LR(0)文法。只有對于LR(0)文法，才能構(gòu)造它的LR(0)分析表。LR(0)分析表的構(gòu)造設(shè)文法G’的項目集規(guī)范族C={I0,I1,…,In},令其中每個項目集的下標(biāo)作為分析器的狀態(tài)，令包含項目[S’→.S]的項目集Ik的下標(biāo)k為分析器的初態(tài)。則構(gòu)造LR(0)分析表的步驟如下：①若項目A→α.aβ∈Ii且GO(Ii,a)=Ij,其中a為終結(jié)符，置ACTION[i,a]=“把狀態(tài)j和符號a移進(jìn)?！?，簡記為“sj”;②若項目A→α.∈Ii,則對于任何輸入符a或結(jié)束符#，置ACTION[i,a]=“用產(chǎn)生式A→α進(jìn)行歸約”，簡記為“rj”(假定A→α是文法G’的第j條產(chǎn)生式);③若項目S’→S.∈Ii,則置ACTION[i,#]=“接收”，簡記為‘a(chǎn)ccept’；④若GO(Ii,A)=Ij,A為非終結(jié)符，則置GOTO(i,A)=j⑤分析表中凡不能用規(guī)則①-④添入信息的元素均置上ERROR。狀態(tài)ACTIONGOTO()a#A0S2S311ACCEPT2S2S343R2R2R2R24S55R1R1R1R1構(gòu)造LR（0）分析表的步驟小結(jié)文法拓廣；利用CLOSURE和GO函數(shù)，求出C;構(gòu)造識別活前綴的DFA；由算法構(gòu)造LR(0)分析表舉例構(gòu)造下列文法的LR（0）分析表S→A|BA→aAb|cB→aBb|dLR(0)分析法面臨的問題只有LR(0)文法才能構(gòu)造LR(0)分析表；LR(0)文法是一種非常簡單的文法，這種文法的活前綴識別自動機的每一個狀態(tài)（項目集）都不含沖突項目。然而，即使是定義簡單表達(dá)式的文法也不是LR(0)文法。構(gòu)造文法{E’→EE→E+T|TT→T*F|FF→(E)|i}的項目集規(guī)范族，找出其中的沖突項目。移進(jìn)-歸約沖突問題的解決許多沖突可以通過考察有關(guān)非終結(jié)符的FOLLOW集而得到解決，即通過向前查看一個輸入符號來協(xié)助解決沖突。考慮如下項目集中的沖突：Ii:{A→α.bβ,B→α.,C→α.}SLR解決方法的基本思想設(shè)LR(0)項目集規(guī)范族的某個項目集I中含有i個移進(jìn)項目A1→α.a1β1,A2→α.a2β2,……,Ai→α.aiβi和j個歸約項目B1→α.,B2→α.,……,Bj→α.若已知集合{a1,a2,…,ai},FOLLOW(B1),FOLLOW(B2),…,FOLLOW(Bj)兩兩無交(且沒有兩個FOLLOW集含有#),則I中的沖突動作可以通過查看當(dāng)前輸入符號a屬于上述j+1個集合中的哪一個集合而獲得解決，即①若a∈{a1,a2,…,ai},則移進(jìn)a；②若a∈FOLLOW(Bk),則用產(chǎn)生式Bk→α進(jìn)行歸約；③其它則報錯。SLR（1）分析表的構(gòu)造設(shè)文法G’的項目集規(guī)范族C={I0,I1,…,In},令其中每個項目集的下標(biāo)作為分析器的狀態(tài)，令包含項目[S’→.S]的項目集Ik的下標(biāo)k為分析器的初態(tài)。則構(gòu)造LR(0)分析表的步驟如下：①若項目A→α.aβ∈Ii且GO(Ii,a)=Ij,其中a為終結(jié)符，置ACTION[i,a]=“把狀態(tài)j和符號a移進(jìn)棧”，簡記為“sj”;②若項目A→α.∈Ii,則對所有a（或#）∈FOLLOW(A)，置ACTION[i,a]=“用產(chǎn)生式A→α進(jìn)行歸約”，簡記為“rj”(假定A→α是文法G’的第j條產(chǎn)生式);③若項目S’→S.∈Ii,則置ACTION[i,$]=“接收”，簡記為‘a(chǎn)cc’；④若GO(Ii,A)=Ij,A為非終結(jié)符，則置GOTO(i,A)=j⑤分析表中凡不能用規(guī)則①-④添入信息的元素均置上ERROR。構(gòu)造SLR分析表的步驟小結(jié)文法拓廣；構(gòu)造識別活前綴的DFA；求出非終結(jié)符的FOLLOW集；由算法構(gòu)造SLR分析表有關(guān)SLR的定義SLR分析表：由SLR方法構(gòu)造出的分析表，若不含多重定義，則稱為文法的SLR分析表SLR分析器：利用SLR分析表的分析器SLR(1)文法：能構(gòu)造出SLR分析表的文法 構(gòu)造SLR分析表的例子簡單表達(dá)式文法：E’→EE