第5章語法分析-自底向上的語法分析

1、編譯系統(tǒng)原編譯系統(tǒng)原 理理電氣與信息學(xué)院 王 艷5.1 5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范規(guī)約規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范規(guī)約5.2 FIRST5.2 FIRST集合和集合和FOLLOWFOLLOW集合集合5.3 5.3 遞歸下降分析遞歸下降分析5.4 LL(1)5.4 LL(1)分析方法分析方法5.5 SLR(1)5.5 SLR(1)分析器分析器5.6 LR(1)5.6 LR(1)分析器分析器5.7 LALR(1)5.7 LALR(1)分析器分析器第五章第五章 語法分析語法分析- -自底向上分析自底向上分析5.1 5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約自底向上分析：自底向

2、上分析：從輸入符號串開始，反復(fù)查找當(dāng)前句型從輸入符號串開始，反復(fù)查找當(dāng)前句型的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終結(jié)符，直到規(guī)約到開始符號。結(jié)符，直到規(guī)約到開始符號。基本方法：基本方法：從句子出發(fā)，反復(fù)利用產(chǎn)生式做歸約從句子出發(fā)，反復(fù)利用產(chǎn)生式做歸約 （用產(chǎn)生式的左部替代右部），逐步構(gòu)造語法分（用產(chǎn)生式的左部替代右部），逐步構(gòu)造語法分析樹，最后得到文法的開始符號析樹，最后得到文法的開始符號. .核心：核心：尋找句型與句柄的匹配尋找句型與句柄的匹配5.1 5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約例例5-1. S a

3、 A c B e5-1. S a A c B e A A b A A bb b B d B d 分析分析“abbcdeabbcde”是否為該文法的句子是否為該文法的句子abbcde aAbcde aAcde aAcBe Sabbcde aAbcde aAcde aAcBe S規(guī)范推導(dǎo)：最右推導(dǎo)，得到的句型為規(guī)范句型規(guī)范推導(dǎo)：最右推導(dǎo)，得到的句型為規(guī)范句型規(guī)范歸約：最左歸約，規(guī)范推導(dǎo)的逆過程。即在分析的規(guī)范歸約：最左歸約，規(guī)范推導(dǎo)的逆過程。即在分析的每一步，將當(dāng)前句型的句柄歸約成相應(yīng)的非終結(jié)符。每一步，將當(dāng)前句型的句柄歸約成相應(yīng)的非終結(jié)符。a b b c d ea b b c d eAABSA

4、bA bA A bA A bB dB dS a A c B eS a A c B e5.1 5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約5.1 5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約a ab bbcdeabcdeaAbAbcdeaAccdeaAcd deeaAcBeaAcBe S S句柄：最左直接短語句柄：最左直接短語5.2 5.2 自底向上分析方法的一般過程自底向上分析方法的一般過程自底向上分析也稱移進(jìn)歸約法自底向上分析也稱移進(jìn)歸約法bcde #Aa#移進(jìn)歸約移進(jìn)歸約控制程序控制程序產(chǎn)生式序列產(chǎn)生式序列棧內(nèi)容棧內(nèi)容 + 輸入緩沖區(qū)內(nèi)容輸入緩沖區(qū)內(nèi)

5、容 # 句型句型 #棧棧輸入緩沖區(qū)輸入緩沖區(qū)分析表分析表5.2 5.2 自底向上分析方法的一般過程自底向上分析方法的一般過程步驟步驟 符號棧符號棧 輸入符號串輸入符號串 動作動作145678910111232#a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#Sabbcde#bbcde#bcde#bcde#cde#cde#de#e#e#左界符進(jìn)棧進(jìn)棧進(jìn)棧用Ab歸約進(jìn)棧用AAb歸約進(jìn)棧進(jìn)棧用Bd歸約進(jìn)棧用SaAcBe歸約接受5.2 5.2 自底向上分析方法的一般過程自底向上分析方法的一般過程如何尋找句柄是關(guān)鍵問題：算符優(yōu)先方法和如何尋找句柄是關(guān)鍵問題：算符優(yōu)先方法和LRL

6、R分析法分析法5.3 LR5.3 LR分析法分析法LRLR分析方法對文法適應(yīng)性強(qiáng)；分析能力強(qiáng)；對源程序中分析方法對文法適應(yīng)性強(qiáng)；分析能力強(qiáng)；對源程序中的錯誤診斷靈敏；但方法復(fù)雜，的錯誤診斷靈敏；但方法復(fù)雜，k k值越大，分析方法越值越大，分析方法越復(fù)雜。復(fù)雜。LRLR（0 0）分析是其中最簡單的，但分析能力弱，）分析是其中最簡單的，但分析能力弱，實用性差。實用性差。LRLR（k k）分析方法：）分析方法：L L：從左到右掃描所給定的輸入串：從左到右掃描所給定的輸入串R R：以相反的方向構(gòu)造該輸入串的最右推導(dǎo)：以相反的方向構(gòu)造該輸入串的最右推導(dǎo)k k：做出分析決定需要向前看的輸入符號的個數(shù)：做出

7、分析決定需要向前看的輸入符號的個數(shù)5.3 LR5.3 LR分析法分析法5.3.1 LR5.3.1 LR分析器的邏輯結(jié)構(gòu)分析器的邏輯結(jié)構(gòu)a1 ai an #總控程序總控程序動作表動作表action轉(zhuǎn)移表轉(zhuǎn)移表goto產(chǎn)生式序列產(chǎn)生式序列狀態(tài)符號棧狀態(tài)符號棧輸入緩沖區(qū)輸入緩沖區(qū)分析表分析表SmSm-1S1S0XmXm-1X1#5.3 LR5.3 LR分析法分析法5.3.2 LR5.3.2 LR分析表的構(gòu)成分析表的構(gòu)成（1 1）移近（）移近（S Sn n）：）：將輸入符號移近符號棧，將狀態(tài)將輸入符號移近符號棧，將狀態(tài)n n移近狀態(tài)棧，輸入指針指向下一個輸入符號。移近狀態(tài)棧，輸入指針指向下一個輸入符號

8、。（2 2）歸約（）歸約（R R）：）：用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔?。用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔?。? 3）接受（）接受（A A）：）：輸入符號達(dá)到右界符輸入符號達(dá)到右界符# #時，且符號棧只有文法的開始符號，則分析成功結(jié)束。時，且符號棧只有文法的開始符號，則分析成功結(jié)束。（4 4）報錯（）報錯（E E）：）：在狀態(tài)棧頂狀態(tài)，輸入符號為不應(yīng)該遇到的符號時，則報錯。在狀態(tài)棧頂狀態(tài)，輸入符號為不應(yīng)該遇到的符號時，則報錯。5.3 LR5.3 LR分析法分析法5.3.2 LR5.3.2 LR分析表的構(gòu)成分析表的構(gòu)成文法文法G G：（0 0）S SA A（1 1）A A（A A）（2

9、2）A Aa a5.3 LR5.3 LR分析法分析法5.3.35.3.3LRLR分分析析過過程程5.3 LR5.3 LR分析法分析法5.3.3 LR5.3.3 LR分析過程分析過程文法文法G G：（0 0）S SA A（1 1）A A（A A）（2 2）A Aa a利用分析表分析利用分析表分析符號串符號串“（a a）”步驟步驟狀態(tài)棧狀態(tài)棧 符號棧符號棧 輸入符號串輸入符號串ACTIONGOTO10#(a)#S2202#(a)#S33023#(a)#R244024#(A)#S550245#(A)#R11601#A#ACCEPT5.3 LR5.3 LR分析法分析法5.3.3 LR5.3.3 LR分

10、析過程分析過程5.4 LR(0)5.4 LR(0)分析器分析器拓廣文法：使文法只有一個以識別符號作為左部的產(chǎn)生拓廣文法：使文法只有一個以識別符號作為左部的產(chǎn)生式，從而構(gòu)造出來的分析器有唯一的接受狀態(tài)。式，從而構(gòu)造出來的分析器有唯一的接受狀態(tài)。例例5-3.5-3.對文法對文法G G：E ET|E+T|E-TT|E+T|E-T，T Ti|(E)i|(E)進(jìn)行拓廣進(jìn)行拓廣（0 0）S SE E（1 1）E E T|E+T|E-TT|E+T|E-T（2 2） T Ti|(E)i|(E)5.4 LR(0)5.4 LR(0)分析器分析器5.4.1 5.4.1 活前綴和可歸活前綴活前綴和可歸活前綴 設(shè)設(shè) 是

11、一個規(guī)范句型，其中是一個規(guī)范句型，其中 表示句柄，表示句柄， ，如果如果 ，那么稱符號串，那么稱符號串 是句型是句型 的活前綴，其中的活前綴，其中 含有完整句柄含有完整句柄 ，稱為可歸，稱為可歸活前綴?；钋熬Y。對規(guī)范句型來說，活前綴可有多個，可歸活前綴只有一個對規(guī)范句型來說，活前綴可有多個，可歸活前綴只有一個t*tVtruuu.21)1 (.21riuuurtruuu.21例例5-45-4：有文法：有文法G G：E E T|E+T|E-TT|E+T|E-T， T Ti|(E)i|(E)找出規(guī)范句型找出規(guī)范句型E+(i-i)E+(i-i)的活前綴和可歸活前綴的活前綴和可歸活前綴5.4 LR(0)

12、5.4 LR(0)分析器分析器5.4.1 5.4.1 活前綴和可歸活前綴活前綴和可歸活前綴活前綴：活前綴：E E，E+E+，E+(E+(，E+(iE+(i可歸活前綴：可歸活前綴： E+(i E+(iE+ETE()-ETiTiiE(5.4 LR(0)5.4 LR(0)分析器分析器5.4.2 LR(0)5.4.2 LR(0)項目項目 對某個文法對某個文法G G來說，如果來說，如果 為為G G的一條規(guī)則，的一條規(guī)則，那么對規(guī)則右部加上一個圓點那么對規(guī)則右部加上一個圓點“”，就成為一個項，就成為一個項目。形式為目。形式為 。21A21A例如：例如：S SE E：S SEE， S SEEE EE-TE-

13、T：E EE-TE-T，E EE-TE-T，E EE-TE-T，E EE-TE-T5.4 LR(0)5.4 LR(0)分析器分析器5.4.2 LR(0)5.4.2 LR(0)項目項目 項目中點后面的符號稱為該項目的后繼符號。根項目中點后面的符號稱為該項目的后繼符號。根據(jù)項目點的位置和后繼符號，把項目分成以下幾種：據(jù)項目點的位置和后繼符號，把項目分成以下幾種：(1)(1)移近項目：后繼符號為終結(jié)符號，移近項目：后繼符號為終結(jié)符號， E EE-TE-T(2)(2)待約項目：后繼符號為非終結(jié)符，待約項目：后繼符號為非終結(jié)符， E EE-TE-T(3)(3)歸約項目：后繼符號為空，歸約項目：后繼符號為

14、空， E EE-T E-T (4)(4)接受項目：文法的開始符號接受項目：文法的開始符號S S的歸約項目，的歸約項目， S SEE5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)1 1、項目集的閉包運算、項目集的閉包運算 設(shè)設(shè)I I為一項目集，為一項目集，I I的閉包運算的閉包運算CLOSURE(I)CLOSURE(I)定義如下：定義如下：(1)I(1)I中的每一個項目都屬于中的每一個項目都屬于CLOSURE(I)CLOSURE(I)；(2)(2)如項目如項目 屬于屬于CLOSURE(I)CLOSURE(I)，且，且X

15、 X為非終結(jié)符為非終結(jié)符號，則將形式為號，則將形式為 的項目添加到的項目添加到CLOSURE(I)CLOSURE(I)中；中；(3)(3)重復(fù)重復(fù)(1)(2) (1)(2) ，直到，直到CLOSURE(I)CLOSURE(I)封閉為止。封閉為止。21XAX5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)1 1、項目集的閉包運算、項目集的閉包運算解：解：CLOSURE(I)=CLOSURE(I)=EEE CLOSURE(I)= CLOSURE(I)=EEEEEE+T,EE+T,ETT CLOSURE(I)= CLOSUR

16、E(I)=EEEEEE+T,EE+T,ETT T TTT* *F,TF,TFF CLOSURE(I)= CLOSURE(I)=EEEEEE+T,EE+T,ETT T TTT* *F,TF,TFFFF(E), F(E), Fii 例例5-6 5-6 有文法有文法EE,EE,EE+T, EE+T, ET, TT, TT T* *F,TF,TF, FF, F(E), (E), F Fi,i,設(shè)項目集設(shè)項目集I=I=EEE，求，求CLOSURE(I)CLOSURE(I)5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)2 2、項

17、目集之間的轉(zhuǎn)換函數(shù)、項目集之間的轉(zhuǎn)換函數(shù)GOGO項目的狀態(tài)轉(zhuǎn)換：項目的狀態(tài)轉(zhuǎn)換：XA XA讀X操作 設(shè)設(shè)I I是一個項目集，是一個項目集，X X是任意一個文法符號，則項目是任意一個文法符號，則項目集之間的轉(zhuǎn)換用集之間的轉(zhuǎn)換用GOI,X GOI,X 函數(shù)表示，定義為：函數(shù)表示，定義為： GOI,X=CLOSURE(J) GOI,X=CLOSURE(J)其中，其中，J=J=任何形如任何形如 的項目的項目| I XAXA5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)2 2、項目集之間的轉(zhuǎn)換函數(shù)、項目集之間的轉(zhuǎn)換函數(shù)GOGO

18、解：解：J=EJ=EE+TE+T CLOSURE(J)=E CLOSURE(J)=EE+T TE+T TTT* *F,TF,TFF F F(E), F(E), Fii 例例5-7 5-7 有項目集有項目集I=I=EE,EE,EE+TE+T求求GOI,+GOI,+5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)3 3、舉例說明識別活前綴的有窮自動機(jī)的構(gòu)造方法、舉例說明識別活前綴的有窮自動機(jī)的構(gòu)造方法(1)(1)從文法的開始符號開始。將從文法的開始符號開始。將S SA A作為有窮自動機(jī)的作為有窮自動機(jī)的開始狀態(tài)開始狀態(tài)0

19、0，C C0 0=S=SAA。 S SAA稱為基本項目。稱為基本項目。 (0)S(0)SA A(1)A(1)A(A)(A)(2)A(2)Aa a(2)(2)對項目集中的各成員進(jìn)行閉包運算，形成新的初始對項目集中的各成員進(jìn)行閉包運算，形成新的初始狀態(tài)狀態(tài)C C0 0=S=SA,AA,A(A),A(A),Aa a 。 (3)(3)構(gòu)造構(gòu)造C C0 0的后繼項目集，分別針對的后繼項目集，分別針對A A( (a a進(jìn)進(jìn)行構(gòu)造，如下表所示。行構(gòu)造，如下表所示。 5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)3 3、舉例說明識別

20、活前綴的有窮自動機(jī)的構(gòu)造方法、舉例說明識別活前綴的有窮自動機(jī)的構(gòu)造方法(0)S(0)SA A(1)A(1)A(A)(A)(2)A(2)Aa a(3)(3)構(gòu)造構(gòu)造C C0 0的后繼項目集的后繼項目集 輸入符號輸入符號項目集項目集狀態(tài)狀態(tài)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)AS SAAC1GO0,A=1(A A (A) (A)A A(A)(A)A AaaC2GO0,)=2aA AaaC3GO0,a=3C C0 0=S=SA,AA,A(A),A(A),Aa a 5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)3 3、舉例說明識別活前綴的有窮自

21、動機(jī)的構(gòu)造方法、舉例說明識別活前綴的有窮自動機(jī)的構(gòu)造方法(0)S(0)SA A(1)A(1)A(A)(A)(2)A(2)Aa a(4)(4)構(gòu)造其它狀態(tài)的后繼項目集，直到?jīng)]有新項目集產(chǎn)構(gòu)造其它狀態(tài)的后繼項目集，直到?jīng)]有新項目集產(chǎn)生為止。生為止。 輸入符號輸入符號項目集項目集狀態(tài)狀態(tài)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)AS S(A)(A)C4GO2,A=4(A A (A) (A)A A(A)(A)A AaaC2GO2,)=2aA AaaC3GO2,a=3輸入符號輸入符號項目集項目集狀態(tài)狀態(tài)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù))S S(A)(A)C5GO4,)=55.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)

22、造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項目活前綴的有窮自動機(jī)構(gòu)造項目活前綴的有窮自動機(jī)C=C0,C1,Cn，C0為初始狀態(tài)，C稱為LR(0)項目集的規(guī)范族。5.4 LR(0)5.4 LR(0)分析器分析器5.4.4 LR(0)5.4.4 LR(0)分析表的構(gòu)造分析表的構(gòu)造假設(shè)已經(jīng)構(gòu)造出假設(shè)已經(jīng)構(gòu)造出LR(0)LR(0)的項目集規(guī)范族：的項目集規(guī)范族：C=CC=C0 0,C,C1 1,C,Cn n,其中其中C Ci i為項目集的名字，對應(yīng)狀態(tài)為為項目集的名字，對應(yīng)狀態(tài)為i i，假設(shè)，假設(shè)S S. .是文法是文

23、法開始符號所在的規(guī)則，令包含項目開始符號所在的規(guī)則，令包含項目S S. .的項目集的項目集C Ck k對應(yīng)對應(yīng)的狀態(tài)的狀態(tài)k k為開始狀態(tài)。為開始狀態(tài)。(1)若項目若項目 ，且，且GOCi i,a=Cj j，其中，其中a為終結(jié)符為終結(jié)符號，置號，置ACTIONi,a=“把狀態(tài)把狀態(tài)j和符號和符號a移近棧移近?！?，記，記Sj j；(2)若項目若項目 ，則對于任何輸入符號，則對于任何輸入符號a，a為終結(jié)符為終結(jié)符或或#，置，置ACTIONi,a=“用產(chǎn)生式用產(chǎn)生式A 進(jìn)行歸約進(jìn)行歸約”，記為，記為Rj j；iCaAiCA5.4 LR(0)5.4 LR(0)分析器分析器5.4.4 LR(0)5.4.

24、4 LR(0)分析表的構(gòu)造分析表的構(gòu)造(3)(3)若項目若項目S S.Ci i，置，置ACTIONi,#=“ACTIONi,#=“接受接受”，記為，記為“ACCEPTACCEPT”。(4)(4)若若GOi,A=Cj,AGOi,A=Cj,A為非終結(jié)符，則置為非終結(jié)符，則置GOTOi,A=jGOTOi,A=j。(5)(5)分析表中凡不能用分析表中凡不能用(1) (1) (4)(4)填入信息的單元為空或均填入信息的單元為空或均置為置為ERRORERROR，表示有錯。，表示有錯。5.4 LR(0)5.4 LR(0)分析器分析器5.4.4 LR(0)5.4.4 LR(0)分析表的構(gòu)造分析表的構(gòu)造(0)S

25、(0)SA A(1)A(1)A(A)(A)(2)A(2)Aa aS2S31ACCEPTS2S34R2R2R2R2R1R1R1R1S55.4 LR(0)5.4 LR(0)分析器分析器5.4.5 LR(0)5.4.5 LR(0)分析器的工作過程分析器的工作過程(1)(1)若若ACTIONS,a=Sj,aACTIONS,a=Sj,a為終結(jié)符，則把為終結(jié)符，則把a(bǔ) a移入符號棧，移入符號棧，j j入狀態(tài)棧；入狀態(tài)棧；(2)(2)若若ACTIONS,a=Rj,aACTIONS,a=Rj,a為終結(jié)符或為終結(jié)符或# #，則用第，則用第j j個產(chǎn)生式歸約，個產(chǎn)生式歸約，k k為第為第j j個產(chǎn)生式右部符號串長

26、度，將符號棧、狀態(tài)棧頂?shù)膫€產(chǎn)生式右部符號串長度，將符號棧、狀態(tài)棧頂?shù)膋 k個元素出棧，將產(chǎn)個元素出棧，將產(chǎn)生式左部符號入符號棧；生式左部符號入符號棧；(3)(3)若若ACTIONS,a=“ACCEPT”ACTIONS,a=“ACCEPT”，a a為為# #，則為接受，表示分析成功。，則為接受，表示分析成功。(4)(4)若若GOTOS,A=j,AGOTOS,A=j,A為非終結(jié)符號并且符號棧的棧頂，表示前一個動為非終結(jié)符號并且符號棧的棧頂，表示前一個動作是歸約，作是歸約，A A是歸約后移入符號棧的非終結(jié)符，則將狀態(tài)是歸約后移入符號棧的非終結(jié)符，則將狀態(tài)j j移入狀態(tài)棧；移入狀態(tài)棧；(5)(5)若若

27、ACTIONS,a=ACTIONS,a=空白，則轉(zhuǎn)入錯誤處理?？瞻祝瑒t轉(zhuǎn)入錯誤處理。5.4 LR(0)5.4 LR(0)分析器分析器5.4.5 LR(0)5.4.5 LR(0)分析器的工作過程分析器的工作過程例例5-95-9：分析輸入符號串：分析輸入符號串(a)(a)步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧輸入符號串輸入符號串ACTIONGOTO1234567890020220223022402245024024501#(#(#(a#(A#(A)#(A#(A)#A(a)#(a)#a)#)#)#)#)#S2S2S3R2S5R1S5R1ACCEPT4415.4 LR(0)5.4 LR(0)分析器分析器5.

28、4.6 LR(0)5.4.6 LR(0)文法文法一個項目集包含不同類型的項目，但必須滿足下面兩個條件：一個項目集包含不同類型的項目，但必須滿足下面兩個條件：(1)(1)不能有移進(jìn)項目和歸約項目并存不能有移進(jìn)項目和歸約項目并存移進(jìn)移進(jìn)- -歸約沖突歸約沖突(2)(2)不能有多個歸約項目并存不能有多個歸約項目并存 歸約歸約- -歸約沖突歸約沖突 如果一個文法的項目集規(guī)范族不存在具有如果一個文法的項目集規(guī)范族不存在具有“移進(jìn)移進(jìn)- -歸約沖突歸約沖突”或或“歸約歸約- -歸約沖突歸約沖突”的項目集，那么該文法為的項目集，那么該文法為LR(0)LR(0)文法。文法。5.5 SLR(1)5.5 SLR(

29、1)分析器分析器練習(xí)：練習(xí)：求該文法的項目集規(guī)范族及轉(zhuǎn)換函數(shù)求該文法的項目集規(guī)范族及轉(zhuǎn)換函數(shù)(0)S(0)SE E(1)E(1)EE+TE+T(2)E(2)ET T(3)T(3)TT T* *F F(4)T(4)TF F(5)F(5)F(E)(E)(6)F(6)Fi i狀態(tài)狀態(tài)項目集項目集轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)2ET.TT.*FR2GO2,*=7存在移進(jìn)存在移進(jìn)- -歸約沖突，不是歸約沖突，不是LR(0)LR(0)文法文法5.5 SLR(1)5.5 SLR(1)分析器分析器(0)S(0)SE E(1)E(1)EE+TE+T(2)E(2)ET T(3)T(3)TT T* *F F(4)T(4)TF F

30、(5)F(5)F(E)(E)(6)F(6)Fi i5.5 SLR(1)5.5 SLR(1)分析器分析器5.5.1 SLR5.5.1 SLR解決方法的思想解決方法的思想項目集項目集 存在移進(jìn)存在移進(jìn)- -歸約沖突和歸約歸約沖突和歸約- -歸約沖突歸約沖突.,CrBbA若若FOLLOW(B)FOLLOW(B)、FOLLOW(A)FOLLOW(A)和和b b互不相交，當(dāng)狀態(tài)為互不相交，當(dāng)狀態(tài)為S Si i，輸，輸入符號為入符號為a(aa(a為終結(jié)符或為終結(jié)符或#)#)時，利用下列方法可解決沖突：時，利用下列方法可解決沖突：(1)(1)若若a=ba=b，則移進(jìn)，則移進(jìn)a a；(2)(2)若若aFOLL

31、OW(B)aFOLLOW(B)，則用產(chǎn)生式，則用產(chǎn)生式 歸約；歸約；(3)(3)若若aFOLLOW(C)aFOLLOW(C)，則用產(chǎn)生式，則用產(chǎn)生式 歸約；歸約；(4)(4)其它報錯。其它報錯。 rB.C通過向前查看一個輸入符號來協(xié)助解決沖突，該文法就是通過向前查看一個輸入符號來協(xié)助解決沖突，該文法就是SLR(1)SLR(1)文法。文法。5.5 SLR(1)5.5 SLR(1)分析器分析器5.5.2 SLR(1)5.5.2 SLR(1)分析表的構(gòu)造分析表的構(gòu)造假設(shè)假設(shè)G項目集規(guī)范族：項目集規(guī)范族：C=C0,C1,Cn,其中其中Ci為項目集的為項目集的名字，對應(yīng)狀態(tài)為名字，對應(yīng)狀態(tài)為i，令包含項

32、目，令包含項目S.s的項目集的項目集Ck對應(yīng)的對應(yīng)的狀態(tài)狀態(tài)k為開始狀態(tài)。為開始狀態(tài)。(1)若項目若項目 ，且，且GOCi i,a=Cj j，其中，其中a為終結(jié)符為終結(jié)符號，置號，置ACTIONi,a=“把狀態(tài)把狀態(tài)j和符號和符號a移近棧移近?！保?，記Sj j；(2)若項目若項目 ，則對則對a FOLLOW(A)，a為終結(jié)符為終結(jié)符或或#，置，置ACTIONi,a=“用產(chǎn)生式用產(chǎn)生式A 進(jìn)行歸約進(jìn)行歸約”，記為，記為Rj j；iCaAiCA(3)若項目若項目Ss.Ci，置，置ACTIONi,#=“接受接受”，記為，記為“ACCEPT”。(4)(4)若若GOi,A=Cj,AGOi,A=Cj,A

33、為非終結(jié)符，則置為非終結(jié)符，則置GOTOi,A=jGOTOi,A=j。(5)(5)分析表中凡不能用分析表中凡不能用(1) (1) (4)(4)填入信息的單元為空或均填入信息的單元為空或均置為置為ERRORERROR，表示有錯。，表示有錯。5.5 SLR(1)5.5 SLR(1)分析器分析器5.5.2 SLR(1)5.5.2 SLR(1)分析表的構(gòu)造分析表的構(gòu)造5.5 SLR(1)5.5 SLR(1)分析器分析器5.5.2 SLR(1)5.5.2 SLR(1)分析表的構(gòu)造分析表的構(gòu)造5.5 SLR(1)5.5 SLR(1)分析器分析器5.5.2 SLR(1)5.5.2 SLR(1)分析表的構(gòu)造分

34、析表的構(gòu)造例例5-105-10：分析表達(dá)式：分析表達(dá)式“i i* *(i+i)(i+i)”步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧輸入符號串輸入符號串ACTIONGOTO12345678900503020270274027450274302742#i#F#T#T*#T*(#T*(i#T*(F#T*(Ti*(i+i)#*(i+i)# *(i+i)#*(i+i)#(i+i)#i+i)#+i)#S5R6R4S7S4S5R5R4328+i)#+i)#R2325.5 SLR(1)5.5 SLR(1)分析器分析器5.5.2 SLR(1)5.5.2 SLR(1)分析表的構(gòu)造分析表的構(gòu)造例例5-105-10：分析表達(dá)

35、式：分析表達(dá)式“i i* *(i+i)(i+i)”步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧輸入符號串輸入符號串ACTIONGOTO101112131415161718027480274860274865027486302748590274802748110271002#T*(E+#T*(E+i#T*(E+F#T*(E+T#T*(E#T*(E)#T*F#T#E+i)#i)# )#)#)#)#S6S5R6R4R1S11R5R3931#R21021901#T*(E#ACCEPT8 把能用把能用SLR(1)SLR(1)分析器分析的語言叫做分析器分析的語言叫做SLR(1)SLR(1)語言。如語言。如果一個文法的項目集規(guī)范族的某些項目存在沖突，但這種果一個文法的項目集規(guī)范族的某些項目存在沖突，但這種沖突能用沖突能用SLR(1)SLR(1)方法解決，那么該文法就是方法解決，那么該文法就是SLR(1)SLR(1)文法