第5章語(yǔ)法分析-自底向上的語(yǔ)法分析

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)分析器分析器第五章第五章 語(yǔ)法分析語(yǔ)法分析- -自底向上分析自底向上分析5.1 5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約自底向上分析：自底向

2、上分析：從輸入符號(hào)串開(kāi)始，反復(fù)查找當(dāng)前句型從輸入符號(hào)串開(kāi)始，反復(fù)查找當(dāng)前句型的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終結(jié)符，直到規(guī)約到開(kāi)始符號(hào)。結(jié)符，直到規(guī)約到開(kāi)始符號(hào)?；痉椒ǎ夯痉椒ǎ簭木渥映霭l(fā)，反復(fù)利用產(chǎn)生式做歸約從句子出發(fā)，反復(fù)利用產(chǎn)生式做歸約 （用產(chǎn)生式的左部替代右部），逐步構(gòu)造語(yǔ)法分（用產(chǎn)生式的左部替代右部），逐步構(gòu)造語(yǔ)法分析樹(shù)，最后得到文法的開(kāi)始符號(hào)析樹(shù)，最后得到文法的開(kāi)始符號(hào). .核心：核心：尋找句型與句柄的匹配尋找句型與句柄的匹配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ī)范歸約：最左歸約，規(guī)范推導(dǎo)的逆過(guò)程。即在分析的每一步，將當(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句柄：最左直接短語(yǔ)句柄：最左直接短語(yǔ)5.2 5.2 自底向上分析方法的一般過(guò)程自底向上分析方法的一般過(guò)程自底向上分析也稱(chēng)移進(jìn)歸約法自底向上分析也稱(chēng)移進(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 自底向上分析方法的一般過(guò)程自底向上分析方法的一般過(guò)程步驟步驟 符號(hào)棧符號(hào)棧 輸入符號(hào)串輸入符號(hào)串 動(dòng)作動(dòng)作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ò)程自底向上分析方法的一般過(guò)程如何尋找句柄是關(guān)鍵問(wèn)題：算符優(yōu)先方法和如何尋找句柄是關(guān)鍵問(wèn)題：算符優(yōu)先方法和LRL

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

7、分析決定需要向前看的輸入符號(hào)的個(gè)數(shù)5.3 LR5.3 LR分析法分析法5.3.1 LR5.3.1 LR分析器的邏輯結(jié)構(gòu)分析器的邏輯結(jié)構(gòu)a1 ai an #總控程序總控程序動(dòng)作表動(dòng)作表action轉(zhuǎn)移表轉(zhuǎn)移表goto產(chǎn)生式序列產(chǎn)生式序列狀態(tài)符號(hào)棧狀態(tài)符號(hào)棧輸入緩沖區(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）：）：將輸入符號(hào)移近符號(hào)棧，將狀態(tài)將輸入符號(hào)移近符號(hào)棧，將狀態(tài)n n移近狀態(tài)棧，輸入指針指向下一個(gè)輸入符號(hào)。移近狀態(tài)棧，輸入指針指向下一個(gè)輸入符號(hào)

8、。（2 2）歸約（）歸約（R R）：）：用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔?。用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔＃? 3）接受（）接受（A A）：）：輸入符號(hào)達(dá)到右界符輸入符號(hào)達(dá)到右界符# #時(shí)，且符號(hào)棧只有文法的開(kāi)始符號(hào)，則分析成功結(jié)束。時(shí)，且符號(hào)棧只有文法的開(kāi)始符號(hào)，則分析成功結(jié)束。（4 4）報(bào)錯(cuò)（）報(bào)錯(cuò)（E E）：）：在狀態(tài)棧頂狀態(tài)，輸入符號(hào)為不應(yīng)該遇到的符號(hào)時(shí)，則報(bào)錯(cuò)。在狀態(tài)棧頂狀態(tài)，輸入符號(hào)為不應(yīng)該遇到的符號(hào)時(shí)，則報(bào)錯(cuò)。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分分析析過(guò)過(guò)程程5.3 LR5.3 LR分析法分析法5.3.3 LR5.3.3 LR分析過(guò)程分析過(guò)程文法文法G G：（0 0）S SA A（1 1）A A（A A）（2 2）A Aa a利用分析表分析利用分析表分析符號(hào)串符號(hào)串“（a a）”步驟步驟狀態(tài)棧狀態(tài)棧 符號(hào)棧符號(hào)棧 輸入符號(hào)串輸入符號(hào)串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、析過(guò)程分析過(guò)程5.4 LR(0)5.4 LR(0)分析器分析器拓廣文法：使文法只有一個(gè)以識(shí)別符號(hào)作為左部的產(chǎn)生拓廣文法：使文法只有一個(gè)以識(shí)別符號(hào)作為左部的產(chǎn)生式，從而構(gòu)造出來(lái)的分析器有唯一的接受狀態(tài)。式，從而構(gòu)造出來(lái)的分析器有唯一的接受狀態(tài)。例例5-3.5-3.對(duì)文法對(duì)文法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、一個(gè)規(guī)范句型，其中是一個(gè)規(guī)范句型，其中 表示句柄，表示句柄， ，如果如果 ，那么稱(chēng)符號(hào)串，那么稱(chēng)符號(hào)串 是句型是句型 的活前綴，其中的活前綴，其中 含有完整句柄含有完整句柄 ，稱(chēng)為可歸，稱(chēng)為可歸活前綴?；钋熬Y。對(duì)規(guī)范句型來(lái)說(shuō)，活前綴可有多個(gè)，可歸活前綴只有一個(gè)對(duì)規(guī)范句型來(lái)說(shuō)，活前綴可有多個(gè)，可歸活前綴只有一個(gè)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)項(xiàng)目項(xiàng)目 對(duì)某個(gè)文法對(duì)某個(gè)文法G G來(lái)說(shuō)，如果來(lái)說(shuō)，如果 為為G G的一條規(guī)則，的一條規(guī)則，那么對(duì)規(guī)則右部加上一個(gè)圓點(diǎn)那么對(duì)規(guī)則右部加上一個(gè)圓點(diǎn)“”，就成為一個(gè)項(xiàng)，就成為一個(gè)項(xiàng)目。形式為目。形式為 。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)項(xiàng)目項(xiàng)目 項(xiàng)目中點(diǎn)后面的符號(hào)稱(chēng)為該項(xiàng)目的后繼符號(hào)。根項(xiàng)目中點(diǎn)后面的符號(hào)稱(chēng)為該項(xiàng)目的后繼符號(hào)。根據(jù)項(xiàng)目點(diǎn)的位置和后繼符號(hào)，把項(xiàng)目分成以下幾種：據(jù)項(xiàng)目點(diǎn)的位置和后繼符號(hào)，把項(xiàng)目分成以下幾種：(1)(1)移近項(xiàng)目：后繼符號(hào)為終結(jié)符號(hào)，移近項(xiàng)目：后繼符號(hào)為終結(jié)符號(hào)， E EE-TE-T(2)(2)待約項(xiàng)目：后繼符號(hào)為非終結(jié)符，待約項(xiàng)目：后繼符號(hào)為非終結(jié)符， E EE-TE-T(3)(3)歸約項(xiàng)目：后繼符號(hào)為空，歸約項(xiàng)目：后繼符號(hào)為

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

15、 X為非終結(jié)符為非終結(jié)符號(hào)，則將形式為號(hào)，則將形式為 的項(xiàng)目添加到的項(xiàng)目添加到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)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)1 1、項(xiàng)目集的閉包運(yùn)算、項(xiàng)目集的閉包運(yùn)算解：解：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è)項(xiàng)目集設(shè)項(xiàng)目集I=I=EEE，求，求CLOSURE(I)CLOSURE(I)5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)2 2、項(xiàng)

17、目集之間的轉(zhuǎn)換函數(shù)、項(xiàng)目集之間的轉(zhuǎn)換函數(shù)GOGO項(xiàng)目的狀態(tài)轉(zhuǎn)換：項(xiàng)目的狀態(tài)轉(zhuǎn)換：XA XA讀X操作 設(shè)設(shè)I I是一個(gè)項(xiàng)目集，是一個(gè)項(xiàng)目集，X X是任意一個(gè)文法符號(hào)，則項(xiàng)目是任意一個(gè)文法符號(hào)，則項(xiàng)目集之間的轉(zhuǎn)換用集之間的轉(zhuǎn)換用GOI,X GOI,X 函數(shù)表示，定義為：函數(shù)表示，定義為： GOI,X=CLOSURE(J) GOI,X=CLOSURE(J)其中，其中，J=J=任何形如任何形如 的項(xiàng)目的項(xiàng)目| I XAXA5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)2 2、項(xiàng)目集之間的轉(zhuǎn)換函數(shù)、項(xiàng)目集之間的轉(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 有項(xiàng)目集有項(xiàng)目集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)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)3 3、舉例說(shuō)明識(shí)別活前綴的有窮自動(dòng)機(jī)的構(gòu)造方法、舉例說(shuō)明識(shí)別活前綴的有窮自動(dòng)機(jī)的構(gòu)造方法(1)(1)從文法的開(kāi)始符號(hào)開(kāi)始。將從文法的開(kāi)始符號(hào)開(kāi)始。將S SA A作為有窮自動(dòng)機(jī)的作為有窮自動(dòng)機(jī)的開(kāi)始狀態(tài)開(kāi)始狀態(tài)0

19、0，C C0 0=S=SAA。 S SAA稱(chēng)為基本項(xiàng)目。稱(chēng)為基本項(xiàng)目。 (0)S(0)SA A(1)A(1)A(A)(A)(2)A(2)Aa a(2)(2)對(duì)項(xiàng)目集中的各成員進(jìn)行閉包運(yùn)算，形成新的初始對(duì)項(xiàng)目集中的各成員進(jìn)行閉包運(yù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的后繼項(xiàng)目集，分別針對(duì)的后繼項(xiàng)目集，分別針對(duì)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)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)3 3、舉例說(shuō)明識(shí)別

20、活前綴的有窮自動(dòng)機(jī)的構(gòu)造方法、舉例說(shuō)明識(shí)別活前綴的有窮自動(dòng)機(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的后繼項(xiàng)目集的后繼項(xiàng)目集 輸入符號(hào)輸入符號(hào)項(xiàng)目集項(xiàng)目集狀態(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)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)3 3、舉例說(shuō)明識(shí)別活前綴的有窮自

21、動(dòng)機(jī)的構(gòu)造方法、舉例說(shuō)明識(shí)別活前綴的有窮自動(dòng)機(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)的后繼項(xiàng)目集，直到?jīng)]有新項(xiàng)目集產(chǎn)構(gòu)造其它狀態(tài)的后繼項(xiàng)目集，直到?jīng)]有新項(xiàng)目集產(chǎn)生為止。生為止。 輸入符號(hào)輸入符號(hào)項(xiàng)目集項(xiàng)目集狀態(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輸入符號(hào)輸入符號(hào)項(xiàng)目集項(xiàng)目集狀態(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、造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)5.4 LR(0)5.4 LR(0)分析器分析器5.4.3 5.4.3 構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)構(gòu)造項(xiàng)目活前綴的有窮自動(dòng)機(jī)C=C0,C1,Cn，C0為初始狀態(tài)，C稱(chēng)為L(zhǎng)R(0)項(xiàng)目集的規(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)的項(xiàng)目集規(guī)范族：的項(xiàng)目集規(guī)范族：C=CC=C0 0,C,C1 1,C,Cn n,其中其中C Ci i為項(xiàng)目集的名字，對(duì)應(yīng)狀態(tài)為為項(xiàng)目集的名字，對(duì)應(yīng)狀態(tài)為i i，假設(shè)，假設(shè)S S. .是文法是文

23、法開(kāi)始符號(hào)所在的規(guī)則，令包含項(xiàng)目開(kāi)始符號(hào)所在的規(guī)則，令包含項(xiàng)目S S. .的項(xiàng)目集的項(xiàng)目集C Ck k對(duì)應(yīng)對(duì)應(yīng)的狀態(tài)的狀態(tài)k k為開(kāi)始狀態(tài)。為開(kāi)始狀態(tài)。(1)若項(xiàng)目若項(xiàng)目 ，且，且GOCi i,a=Cj j，其中，其中a為終結(jié)符為終結(jié)符號(hào)，置號(hào)，置ACTIONi,a=“把狀態(tài)把狀態(tài)j和符號(hào)和符號(hào)a移近棧移近棧”，記，記Sj j；(2)若項(xiàng)目若項(xiàng)目 ，則對(duì)于任何輸入符號(hào)，則對(duì)于任何輸入符號(hào)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)若項(xiàng)目若項(xiàng)目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，表示有錯(cuò)。，表示有錯(cuò)。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)分析器的工作過(guò)程分析器的工作過(guò)程(1)(1)若若ACTIONS,a=Sj,aACTIONS,a=Sj,a為終結(jié)符，則把為終結(jié)符，則把a(bǔ) a移入符號(hào)棧，移入符號(hào)棧，j j入狀態(tài)棧；入狀態(tài)棧；(2)(2)若若ACTIONS,a=Rj,aACTIONS,a=Rj,a為終結(jié)符或?yàn)榻K結(jié)符或# #，則用第，則用第j j個(gè)產(chǎn)生式歸約，個(gè)產(chǎn)生式歸約，k k為第為第j j個(gè)產(chǎn)生式右部符號(hào)串長(zhǎng)

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

27、ACTIONS,a=ACTIONS,a=空白，則轉(zhuǎn)入錯(cuò)誤處理?？瞻?，則轉(zhuǎn)入錯(cuò)誤處理。5.4 LR(0)5.4 LR(0)分析器分析器5.4.5 LR(0)5.4.5 LR(0)分析器的工作過(guò)程分析器的工作過(guò)程例例5-95-9：分析輸入符號(hào)串：分析輸入符號(hào)串(a)(a)步驟步驟狀態(tài)棧狀態(tài)棧符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串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)文法文法一個(gè)項(xiàng)目集包含不同類(lèi)型的項(xiàng)目，但必須滿(mǎn)足下面兩個(gè)條件：一個(gè)項(xiàng)目集包含不同類(lèi)型的項(xiàng)目，但必須滿(mǎn)足下面兩個(gè)條件：(1)(1)不能有移進(jìn)項(xiàng)目和歸約項(xiàng)目并存不能有移進(jìn)項(xiàng)目和歸約項(xiàng)目并存移進(jìn)移進(jìn)- -歸約沖突歸約沖突(2)(2)不能有多個(gè)歸約項(xiàng)目并存不能有多個(gè)歸約項(xiàng)目并存 歸約歸約- -歸約沖突歸約沖突 如果一個(gè)文法的項(xiàng)目集規(guī)范族不存在具有如果一個(gè)文法的項(xiàng)目集規(guī)范族不存在具有“移進(jìn)移進(jìn)- -歸約沖突歸約沖突”或或“歸約歸約- -歸約沖突歸約沖突”的項(xiàng)目集，那么該文法為的項(xiàng)目集，那么該文法為L(zhǎng)R(0)LR(0)文法。文法。5.5 SLR(1)5.5 SLR(

29、1)分析器分析器練習(xí)：練習(xí)：求該文法的項(xiàng)目集規(guī)范族及轉(zhuǎn)換函數(shù)求該文法的項(xiàng)目集規(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)項(xiàng)目集項(xiàng)目集轉(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解決方法的思想解決方法的思想項(xiàng)目集項(xiàng)目集 存在移進(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，輸，輸入符號(hào)為入符號(hào)為a(aa(a為終結(jié)符或?yàn)榻K結(jié)符或#)#)時(shí)，利用下列方法可解決沖突：時(shí)，利用下列方法可解決沖突：(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)其它報(bào)錯(cuò)。其它報(bào)錯(cuò)。 rB.C通過(guò)向前查看一個(gè)輸入符號(hào)來(lái)協(xié)助解決沖突，該文法就是通過(guò)向前查看一個(gè)輸入符號(hào)來(lái)協(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項(xiàng)目集規(guī)范族：項(xiàng)目集規(guī)范族：C=C0,C1,Cn,其中其中Ci為項(xiàng)目集的為項(xiàng)目集的名字，對(duì)應(yīng)狀態(tài)為名字，對(duì)應(yīng)狀態(tài)為i，令包含項(xiàng)

32、目，令包含項(xiàng)目S.s的項(xiàng)目集的項(xiàng)目集Ck對(duì)應(yīng)的對(duì)應(yīng)的狀態(tài)狀態(tài)k為開(kāi)始狀態(tài)。為開(kāi)始狀態(tài)。(1)若項(xiàng)目若項(xiàng)目 ，且，且GOCi i,a=Cj j，其中，其中a為終結(jié)符為終結(jié)符號(hào)，置號(hào)，置ACTIONi,a=“把狀態(tài)把狀態(tài)j和符號(hào)和符號(hào)a移近棧移近?！?，記，記Sj j；(2)若項(xiàng)目若項(xiàng)目 ，則對(duì)則對(duì)a FOLLOW(A)，a為終結(jié)符為終結(jié)符或或#，置，置ACTIONi,a=“用產(chǎn)生式用產(chǎn)生式A 進(jìn)行歸約進(jìn)行歸約”，記為，記為Rj j；iCaAiCA(3)若項(xiàng)目若項(xiàng)目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，表示有錯(cuò)。，表示有錯(cuò)。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)棧符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串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)棧符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串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)分析器分析的語(yǔ)言叫做分析器分析的語(yǔ)言叫做SLR(1)SLR(1)語(yǔ)言。如語(yǔ)言。如果一個(gè)文法的項(xiàng)目集規(guī)范族的某些項(xiàng)目存在沖突，但這種果一個(gè)文法的項(xiàng)目集規(guī)范族的某些項(xiàng)目存在沖突，但這種沖突能用沖突能用SLR(1)SLR(1)方法解決，那么該文法就是方法解決，那么該文法就是SLR(1)SLR(1)文法