自下而上語(yǔ)法分析-LR

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

LR分析方法的基本思想是：在規(guī)范歸約過(guò)程中，一方面記住已移進(jìn)和歸約出的整個(gè)符號(hào)串(歷史)，另一方面又根據(jù)所用產(chǎn)生式推測(cè)未來(lái)可能碰到的輸入符號(hào)(對(duì)未來(lái)的展望)。當(dāng)某一符號(hào)串類(lèi)似于句柄出現(xiàn)在棧頂時(shí)，需要根據(jù)已記載的“歷史”、“展望”和“現(xiàn)實(shí)”的輸入符號(hào)三方面的內(nèi)容來(lái)決定棧頂?shù)姆?hào)串是否構(gòu)成了真正的句柄，是否需要?dú)w約。一個(gè)LR分析器的組成見(jiàn)下圖。LR分析方法的基本思想一個(gè)LR分析器由3個(gè)部分組成：LR分析程序，又稱(chēng)總控程序。所有的LR分析器都是相同的。分析表(分析函數(shù))，不同的文法分析表不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表也不同，分析表又可分為動(dòng)作表(ACTION)和狀態(tài)轉(zhuǎn)換(GOTO)表兩個(gè)部分，它們都可用二維數(shù)組表示。分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。狀態(tài)棧：(S0,#)為預(yù)先放到棧中的初始狀態(tài)和符號(hào)。文法符號(hào)：X1X2…Xm是目前已移進(jìn)并歸約出的句型部分。其實(shí)它是多余的，已經(jīng)概括到狀態(tài)里。分析器實(shí)際上是一個(gè)帶有先進(jìn)后出棧的確定的有窮自動(dòng)機(jī)。將“歷史”和“展望”綜合成“狀態(tài)”，分析棧用來(lái)存放狀態(tài)，狀態(tài)概括了從分析開(kāi)始直到某一歸約階段的全部歷史和展望資料，不必象算符優(yōu)先分析法中要翻閱棧中的內(nèi)容才能決定是否要進(jìn)行歸約。只需根據(jù)棧頂狀態(tài)和輸入符號(hào)就可以唯一決定下一個(gè)動(dòng)作?？偪爻绦蚋鶕?jù)分析表的內(nèi)容來(lái)決定其下一步的處理動(dòng)作，分析表是根據(jù)具體的文法按某種規(guī)則構(gòu)造出來(lái)的。LR方法：根據(jù)具體文法的分析表對(duì)輸入串進(jìn)行分析處理。LR分析過(guò)程：在總控程序的控制下，從左到右掃描輸入符號(hào)串，根據(jù)分析棧中的狀態(tài)和當(dāng)前輸入符號(hào)，按分析表中的內(nèi)容完成相應(yīng)的分析工作。LR分析表的構(gòu)成狀態(tài)動(dòng)作表ACTION狀態(tài)轉(zhuǎn)換表GOTOa1a2…#X1X2…XkS1S2...Sn分析表的動(dòng)作部分：ACTION[Si，aj]表示當(dāng)分析狀態(tài)棧的棧頂為Si，輸入符號(hào)為aj時(shí)應(yīng)執(zhí)行的動(dòng)作；表中GOTO[Si,Xj]指出棧頂狀態(tài)為Si，碰到文法符號(hào)為Xj時(shí)應(yīng)轉(zhuǎn)到的下一狀態(tài)；動(dòng)作有下列四種：移進(jìn)(Sn)，歸約(R)，接受(A)，報(bào)錯(cuò)(E)LR分析器的關(guān)鍵就是構(gòu)造分析表。文法G：0)S→A，1)A→(A)，2)A→a的分析表：狀態(tài)ACTIONGOTO()a#A0S2S311ACCEPT2S2S343R2R2R2R24S55R1R1R1R1LR的分析流程開(kāi)始初始狀態(tài)0和#入棧讀符號(hào)根據(jù)棧頂狀態(tài)和輸入符號(hào)查分析動(dòng)作表歸約?移進(jìn)?接受?查狀態(tài)轉(zhuǎn)換表新?tīng)顟B(tài)入狀態(tài)棧

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

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

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

輸入符號(hào)入符號(hào)棧

狀態(tài)i入狀態(tài)棧讀符號(hào)分析結(jié)束錯(cuò)誤YYYNNN步驟狀態(tài)棧符號(hào)棧輸入串ACTIONGOTO說(shuō)明10#(a)#S2開(kāi)始時(shí)，0入狀態(tài)棧，#入符號(hào)棧，輸入符號(hào)為(，查動(dòng)作表0行(列為S2，2入狀態(tài)棧，(入符號(hào)棧。202#(a)#S3輸入符號(hào)為a，查動(dòng)作表2行a列為S3，3入狀態(tài)棧，a入符號(hào)棧。3023#(a)#R24輸入符號(hào)為)，查動(dòng)作表3行)列為R2，用A→a歸約，a出符號(hào)棧、A入符號(hào)棧，3出狀態(tài)棧、2為棧頂，查GOTO表2行A列得4，4入狀態(tài)棧。4024#(A)#S5輸入符號(hào)為)，查動(dòng)作表4行)列為S5，5入狀態(tài)棧，)入符號(hào)棧。50245#(A)#R11輸入符號(hào)為#，查動(dòng)作表5行#列為R1，用A→(A)歸約，(A)出符號(hào)棧、A入符號(hào)棧，245出狀態(tài)棧、0為棧頂，查GOTO表0行A列得1，1入狀態(tài)棧。601#A#ACCEPT輸入符號(hào)為#，查動(dòng)作表1行#列為ACCEPT，接受。利用分析表分析符號(hào)串(a)LR文法：對(duì)一個(gè)文法，如果能夠構(gòu)造一個(gè)分析表，且它的每個(gè)入口均是唯一的如何構(gòu)造LR分析表？活前綴和可歸前綴前綴：指從任意符號(hào)串x的末尾刪除0或多個(gè)符號(hào)后得到的符號(hào)串，如u、uni、university都是university的前綴?；钋熬Y：設(shè)λβt是一個(gè)規(guī)范句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么稱(chēng)符號(hào)串u1u2…ui(其中1≤i≤r)是句型λβt的活前綴?？蓺w前綴：含有句柄的活前綴u1u2…ur稱(chēng)為可歸前綴。有文法G∶E→T|E+T|E-T，

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

1.活前綴不含有句柄的任何符號(hào)；

2.活前綴含有句柄的部分符號(hào)；

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

4:

A→(A.)5:

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

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

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