程序設(shè)計語言與編譯-編譯原理-自下而上的語法分析課件

第8章自下而上的語法分析第一節(jié)引言自下而上分析：從輸入串出發(fā)，歸約，直至開始符方法：采用棧，在移進的過程中，觀察棧頂是否形成某個產(chǎn)生式的一個候選

第8章自下而上的語法分析第一節(jié)引言自下而上分析：從輸入串G(S)：

SSASSbAccAAa看輸入串bccab的歸約過程一.分析樹bScSccSaccSAccSASbASSASS符號棧

G(S)：一.分析樹bSccaAAbSS符號棧SSSAbccAbaSbAcAacAaSb輸入串bccab分析樹的形成

SSSAbccAbaSbAcAacAaSb輸入串bccab分分析樹的剪枝過程SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA

分析樹的剪枝過程SSSAbccAbaSSSAccAbaSSS

關(guān)鍵問題：如何判斷棧頂符號串是否形

成可歸約串、如何歸約？當(dāng)對不同的歸約串進行歸約，即形成了

不同的自下而上語法分析方法。

關(guān)鍵問題：如何判斷棧頂符號串是否形

設(shè)有文法G，S是開始符號，設(shè)是G的一個句型，若有

S且A

則稱是句型關(guān)于A的短語；++在上面定義中，如果A直接推出,即A，則稱是句型關(guān)于A的直接短語；一個句型的最左直接短語稱為句柄；二.回顧幾個核心概念短語直接短語句柄設(shè)有文法G，S是開始符號，設(shè)是G的一個句型，若有+EET+TTFFi*

G(E)E→E+T|TT→T*F|FF→(E)|i求T*F+i的短語、直接短語、句柄利用推導(dǎo)樹判斷句型的短語

EET+TTFFi*G(E)E→E

素短語：文法G某句型的一個短語是素短語，當(dāng)且僅當(dāng)它至少含有一個終結(jié)符，且除它自身之外不再含更小的素短語；最左素短語：在具有多個素短語的句型中處于最左邊的那個素短語；E1E2+T2T1T3*F2F1i1F3i2素短語：文法G某句型的一個短語是素短語，當(dāng)且僅當(dāng)它至SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA

SSSAbccAbaSSSAccAbaSSSAccAbSSS假定是文法G的一個句子,序列n,n-1,…,0滿足下述條件時稱為規(guī)范歸約。(1)n=α;(2)0為文法的開始符,即0=S;(3)對i,0<in,i-1是從i經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部符號而得到的。三.規(guī)范歸約（最左歸約）

假定是文法G的一個句子,序列n,n-1,…,0EET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE例:G(E)E→E+T│TT→T*F│FF→(E)│ii+i*i的分析過程

EET+FTii*FTiFi+i*iF+i*iT+i*iE+例:G(S)S→aAcBeA→Ab|bB→dabbcde的分析過程SaAcBe

AbdbabbcdeaAbcdeaAcdeaAcBeS

例:G(S)S→aAcBeSaA內(nèi)容回顧

語法分析自上而下自上而下1.規(guī)范規(guī)約內(nèi)容回顧語法分析自上而下自上而下1.規(guī)范規(guī)約1.算符文法上下文無關(guān)文法G,沒有形如P→ε或P→...QR...的產(chǎn)生式,則稱G為算符文法。第二節(jié)算符優(yōu)先分析法一.算符優(yōu)先文法

1.算符文法第二節(jié)算符優(yōu)先分析法一.算符優(yōu)先文法對算符文法G,a,bVT

定義2.終結(jié)符之間的優(yōu)先關(guān)系

(1)a=b:G中有P→...ab...或P→...aQb...++(2)a<b:G中有P→...aQ...且Qb…或QRb...++(3)a>b:G中有P→...Qb...且Q...a或Q…aR對算符文法G,a,bVT定義2.終結(jié)符之間的優(yōu)先若算符文法G的任何終結(jié)符a,b之間的優(yōu)先關(guān)系至多有=、>、<中的一個,則G為一算符優(yōu)先文法。

據(jù)定義，構(gòu)造下述文法G的優(yōu)先關(guān)系表G（E）:E→E+T|TT→T*F|FF→(E)|i3.算符優(yōu)先文法

若算符文法G的任何終結(jié)符a,b之間的優(yōu)先關(guān)系至3.算符優(yōu)先++**ii(())##>>><><<<<>>><<<<<<<<>>>>>>>>==算符優(yōu)先關(guān)系表

++**ii(())##>>><><<<<>>><<<<<<從上表可知:(1)相同終結(jié)符之間的優(yōu)先關(guān)系未必是=(2)有a<b，未必有b>a(3)a、b之間未必一定有優(yōu)先關(guān)系故=、<、>不同于關(guān)系運算符“等于”、“小于”、“大于”

從上表可知:初始化:#棧讀一符號ba=b=#a<b或a=ba>b歸約最左素短語,最左素短語出棧,左部符號入棧結(jié)束b入棧出錯YNYYNN二.算符優(yōu)先分析算法a為棧頂終結(jié)符初始化:#棧讀一符號ba=b=#a<b或a=ba>b歸這是一種結(jié)構(gòu)歸約,處于棧頂待歸約的最左素短語與對應(yīng)的產(chǎn)生式在結(jié)構(gòu)上應(yīng)一致,即長度一致,對應(yīng)的終結(jié)符一致,而非終結(jié)符可以不一致。歸約最左素短語的方法

E→E+TE+E這是一種結(jié)構(gòu)歸約,處于棧頂待歸約的最左素短語與對應(yīng)的產(chǎn)

算法優(yōu)先分析法的實現(xiàn)：使用一個分析棧，當(dāng)其棧頂形成最左素短語時，就進行歸約。分析算法k:=1;S[k]=‘#’;repeatb:=下一輸入符號;ifS[k]VTthenj:=kelsej:=k-1;whileS[j]>bdobeginrepeatQ:=S[j];ifS[j-1]VTthenj:=j-1elsej:=j-2;untilS[j]<Q;

把S[j+1]…S[k]歸約成某個N;k:=j+1;S[k]:=N;endofwhile;ifS[j]<borS[j]=bthenbegink:=k+1;S[k]:=bendelseerroruntila=‘#’;初始化，棧底置輸入串結(jié)束符；棧頂終結(jié)符，如果棧頂是終結(jié)符，則棧頂終結(jié)符是該終結(jié)符；如果棧頂是非終結(jié)符，則棧頂終結(jié)符是下一個終結(jié)符；如果棧頂終結(jié)符的優(yōu)先級大于輸入字符a,開始?xì)w約；在棧頂尋找最左素短語；如果棧頂終結(jié)符的優(yōu)先級小于或等于輸入字符，把輸入字符移進棧；棧頂終結(jié)符=輸入字符=‘#’時，分析結(jié)束算法優(yōu)先分析法的實現(xiàn)：使用一個分析棧，當(dāng)其棧頂形成最左例G(E)E→E+T│TT→T*F│FF→(E)│ii+i*i的分析過程

例G(E)E→E+T│T步驟1234567891011下推棧輸入串動作#i+i*i##<i,移進i#i+i*i#i>+,用Fi歸約#F+i*i##<+,移進+#F+i*i#+<i,移進i#F+i*i#i>*,用Fi歸約#F+F*i#+<*,移進*#F+F*i#*<i,移進i#F+F*i####i>#,用Fi歸約*>#,用TT*F歸約+>#,用EE+T歸約結(jié)束#F+F*F#F+T#E

步驟1234567891011下推棧輸入串動作#i+i*i#EET+FTii*FTiFEET+FTii*FTFEET+FTi*FTFEET+FT*FTFEET+TF

EET+FTii*FTiFEET+FTii*FTFEET+F

FIRSTVT(P)={a|Pa…,或PQa…,aVT,QVN}

++三.優(yōu)先關(guān)系表的構(gòu)造(1)FIRSTVT集若Pa…或PQa…,則aFIRSTVT(P);若PQ…,則FIRSTVT(Q)FIRSTVT(P);直至FIRSTVT(P)不再增大。求法

++三.優(yōu)先關(guān)系表的構(gòu)造(1)FIRSTVT集若Pa…

LASTVT(P)={a|P...a,或P…aQ,aVT,QVN}

++(2)LASTVT集若P...a或P…aQ,則aLASTVT(P);若P...Q,則LASTVT(Q)LASTVT(P);直至LASTVT(P)不再增大。求法

++(2)LASTVT集若P...a或P例G(E)E→E+T│TT→T*F│FF→(E)│iETFFIRSTVTLASTVT(i+*(i)i+*)i*)i(i*

例G(E)E→E+T│TETFFIR(3)構(gòu)造優(yōu)先關(guān)系表

a=b:G中有P→...ab...或P→...aQb...a<b:G中有P→...aQ...且Qb…或QRb...a<bFIRSTVT(Q）a>b:G中有P→...Qb...且Q...a或Q…aRaLASTVT(Q）>b(3)構(gòu)造優(yōu)先關(guān)系表a=b:G中有P→...ab.

FOR每條產(chǎn)生式PX1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均為終結(jié)符THENXi=Xi+1;IFi<=n-2且Xi和Xi+2均為終結(jié)符但Xi+1VNTHENXi=Xi+2;IFXiVT,Xi+1VNTHENaFIRSTVT(Xi+1)Xi<a;IFXiVN,Xi+1VTTHENaLASTVT(Xi)a>Xi+1END;

構(gòu)造優(yōu)先關(guān)系表的算法

構(gòu)造優(yōu)先關(guān)系表的算法例G(E)E→E+T│TT→T*F│FF→(E)│iETFFIRSTVTLASTVT(i+*(i)i+*)i*)i(i*考察E→E+T中的E和+、+和T考察T→T*F中的T和*、*和F考察F→(E)中的(和E

、(和)、E和)

例G(E)E→E+T│TETFFIRSTVTLAS++**ii(())##>>><><<<<>>><<<<<<<<>>>>>>>>==算符優(yōu)先關(guān)系表

++**ii(())##>>><><<<<>>><<<<<<內(nèi)容回顧

條件一：

無

P→ε算符優(yōu)先分析法1.算符文法條件二：

無

P→…QP…2.定義優(yōu)先關(guān)系(1)a=b(2)a<b(3)a>b3.算法優(yōu)先文法優(yōu)先關(guān)系表內(nèi)容回顧條件一：無P→ε算符優(yōu)先分析法1.算符文法條內(nèi)容回顧

5.分析方法初始化:#棧讀一符號ba=b=#a<b或a=ba>b歸約最左素短語,最左素短語出棧,左部符號入棧結(jié)束b入棧出錯YNYYNN內(nèi)容回顧5.分析方法初始化:#棧讀一符號ba=b=#內(nèi)容回顧

5.構(gòu)造算符優(yōu)先表(1)FIRSTVT(2)LASTVT(3)構(gòu)造方法P→...Qb...P→...bQ...P→...ab...或...aQb...內(nèi)容回顧5.構(gòu)造算符優(yōu)先表(1)FIRSTVT(2)L已知文法

G=({a,b,(,)},{S,A,B},S,P)其中

P為S—>bAbA—>(B|aB—>Aa)1.求出文法G的FIRSTVT和LASTVT集。2.構(gòu)造文法G的優(yōu)先關(guān)系表。3.文法G是算符優(yōu)先文法嗎？為什么？課堂練習(xí)已知文法G=({a,b,(,)},{S,A,B},S,P)第二節(jié)LR分析法一.LR(K)分析法自底向上的LR分析法是指從左向右掃描輸入串,每次分析由分析棧中符號及向前搜索K個輸入符號,以確定作為產(chǎn)生式右部的短語(句柄)是否已在分析棧的棧頂形成,從而決定應(yīng)采取的動作。這種分析方法稱為LR(K)分析法。一般只考慮K1的情況。-“L”是指從左至右掃描輸入符號串，-“R”是指構(gòu)造一個最右推導(dǎo)的逆過程，-“k”是指為了作出分析決定而向前看的輸入符號的個數(shù)

第二節(jié)LR分析法一.LR(K)分析法自底向上的LR分析其組成為:分析棧,控制程序,分析表,輸入串輸入串分析棧驅(qū)動程序輸出actiongoto分析表s0...sm-1sma1ai＃......

其組成為:分析棧,控制程序,分析表,輸入串輸入串分析棧驅(qū)動程

1.分析棧存放狀態(tài);初始時,置初始狀態(tài)s0;棧里的每一狀態(tài)概括了從分析開始到某一時刻已進行的分析工作。

1.分析棧存放狀態(tài);初始時,置初始狀態(tài)s0;棧里的每一狀態(tài)2.分析表由action[s,a]和goto[s,x]兩個子表組成。

(1)action[s,a]定義了在狀態(tài)s下,當(dāng)前輸入符號為a時應(yīng)采取的分析動作:移進,歸約,接受,出錯。

(2)goto表是一個狀態(tài)及非終結(jié)符的二維矩陣,goto[s,x]定義了在狀態(tài)s下,面對文法符號x時的狀態(tài)轉(zhuǎn)換。

2.分析表由action[s,a]和goto[s,x例G0(E)(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i的LR分析表如下：

例G0(E)LR分析表狀態(tài)01234567891011actiongotoi+*()＃ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5

LR分析表狀01234567891011actiongoto3.控制程序的工作據(jù)action[s,a]進行(1)若action[s,a]=

sj

,則將狀態(tài)j推入棧頂,輸入指針指向下一輸入符號;(2)若action[s,a]=rj

,則按第j個產(chǎn)生式A歸約,設(shè)||=t,應(yīng)在分析棧棧頂上托t個狀態(tài)出棧,呈現(xiàn)棧頂?shù)臓顟B(tài)設(shè)為si,則根據(jù)si及歸約后的非終結(jié)符A,查goto表,goto[si

,A]=j,則將狀態(tài)j下推入分析棧棧頂。(3)若action[s,a]=acc,則結(jié)束分析,輸入串被接受。(4)若action[s,a]或goto[s,A]不是上述情況,轉(zhuǎn)出錯處理程序

3.控制程序的工作據(jù)action[s,a]進行(1)若ac

序號狀態(tài)符號輸入串動作10#i+i*i#action[0,i]=s520,5#i+i*i#action[5,+]=r6,goto[0,F]=330,3#F+i*i#action[3,+]=r4,goto[0,T]=240,2#T+i*i#action[2,+]=r2,goto[0,E]=150,1#E+i*i#action[1,+]=s660,1,6#E+i*i#action[6,i]=s570,1,6,5#E+i*i#action[5,*]=r6,goto[6,F]=380,1,6,3#E+F*i#action[3,*]=r4,goto[6,T]=990,1,6,9#E+T*i#action[9,*]=s7100,1,6,9,7#E+T*i#action[7,i]=s5110,1,6,9,7,5#E+T*i#action[5,#]=r6,goto[7,F]=10120,1,6,9,7,10#E+T*F#action[10,#]=r3,goto[6,T]=9130,1,6,9#E+T#action[9,#]=r1,goto[0,E]=1140,1#E#action[1,#]=acc,接受例:i+i*i的分析過程(6)F→i序號狀態(tài)符號輸入串動作10#i+i*i#action[0,

序號狀態(tài)符號輸入串動作10i+i*i#action[0,i]=s520,5+i*i#action[5,+]=r6,goto[0,F]=330,3+i*i#action[3,+]=r4,goto[0,T]=240,2+i*i#action[2,+]=r2,goto[0,E]=150,1+i*i#action[1,+]=s660,1,6i*i#action[6,i]=s570,1,6,5*i#action[5,*]=r6,goto[6,F]=380,1,6,3*i#action[3,*]=r4,goto[6,T]=990,1,6,9*i#action[9,*]=s7100,1,6,9,7i#action[7,i]=s5110,1,6,9,7,5#action[5,#]=r6,goto[7,F]=10120,1,6,9,7,10#action[10,#]=r3,goto[6,T]=9130,1,6,9#action[9,#]=r1,goto[0,E]=1140,1#action[1,#]=acc,接受例:i+i*i的分析過程(6)F→i序號狀態(tài)符號輸入串動作10i+i*i#action[0,iEET+FTii*FTiFi+i*IF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE

EET+FTii*FTiFi+i*I特點：歸約符號串總是在棧頂；句柄之后的待入棧符號串總是終結(jié)符；在符號棧中的符號串是規(guī)范句型的前綴.

特點：內(nèi)容回顧

LR分析法(4)總控程序(3)LR分析表(1)輸入串(2)分析棧action[s,a]sj

rj

accerrorgoto[si

,A]=j內(nèi)容回顧LR分析法(4)總控程序(3)LR分析表(1)例子：（0）S'→E（1）E→aA（2）E→bB（3）A→cA（4）A→d（5）B→cB（6）B→d對輸入串bccd#分析。

例子：

序號狀態(tài)符號輸入串動作10#bccd#action[0,b]=s320,3#bccd#action[3,c]=s530,3,5#bccd#action[5,c]=s540,3,5,5#bccd#action[5,d]=s1150,3,5,5,11#bccd#action[11,#]=r6,goto[5,B]=960,3,5,5,9#bccB#Action[9,#]=r5,goto[5,B]=970,3,5,9#bcB#Action[9,#]=r5,goto[3,B]=780,3,7#bB#action[7,#]=r2,goto[0,E]=190,1#E#action[9,*]=accbccd#的分析過程序號狀態(tài)符號輸入串動作10#bccd#action[0,b4.幾種LR分析法LR(0)、SLR(1)、LR(1)、LALR(1)

4.幾種LR分析法LR(0)、SLR(1)、LR(1)、*RR二.LR（0）項目集規(guī)范族1.活前綴:規(guī)范句型的不含句柄之后任何符號的一個前綴。亦即:若A→是文法的一個產(chǎn)生式,且有

SA

則的任何前綴都是規(guī)范句型的活前綴。

*RR二.LR（0）項目集規(guī)范族1.活前綴:規(guī)范句型的已知文法G（S），分析符號串a(chǎn)bbcde是否是G（S）的句子

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d

句子的最右推導(dǎo)過程為：

S=>aAcBe=>aAcde=>aAbcde=>abbcde

已知文法G（S），分析符號串a(chǎn)bbcde是否是G（S）的句子

由于最右推導(dǎo)就是規(guī)范推導(dǎo)，因此句型aAcBe、aAcde、aAbcde、abbcde為規(guī)范句型。

S=>aAcBeaAcBe的活前綴：ε,a,aA,aAc,aAcB,aAcBeS=>aAcBe=>aAcdeaAcde的活前綴：ε,a,aA,aAc,aAcdS=>aAcBe=>aAcde=>aAbcdeaAbcde的活前綴：ε,a,aA,aAbB→dA→AbS=>aAcBe=>aAcde=>aAbcde=>abbcdeA→babbcde的活前綴：ε,a,ab

S=>aAcBe=>aAcde=>aAbcde=>abbcde

由于最右推導(dǎo)就是規(guī)范推導(dǎo)，因此句型S=>aAcBeaAc(1)作為規(guī)范句型的活前綴,它不含句柄后的任何符號。(2)活前綴與句柄之間的三種關(guān)系:活前綴不含句柄的任何符號,此時期待從剩余輸入串中識別由A→的能推導(dǎo)出的符號串;活前綴只含句柄的真前綴,也即產(chǎn)生式A→中已識別于分析棧棧頂之上,

期待從剩余輸入串中識別由所能推導(dǎo)出的符號串;活前綴已含句柄的全部符號,這表明產(chǎn)生式A→的右部符號已在分析棧棧頂之上,應(yīng)將歸約為A。(3)句柄是一類活前綴的后綴,如果能識別一個文法的所有活前綴,自然也就能識別這個文法的所有句柄了。

(1)作為規(guī)范句型的活前綴,它不含句柄后的任何符號。項目:在產(chǎn)生式右部添加一個圓點如A→?、A→?、A→?

左邊：已經(jīng)識別；右邊：等等識別

項目個數(shù)：n+1歸約項目:形如A→?移進項目:形如A→?a，aVT待約項目:形如A→?B，BVN接受項目:形如S→?，S為開始符2.LR（0）項目及分類

項目:在產(chǎn)生式右部添加一個圓點2.LR（0）項目及分類例：產(chǎn)生式S→aAcBe對應(yīng)的6個項目是：[0]S→.aAcBe[1]S→a.AcBe[2]S→aA.cBe[3]S→aAc.Be[4]S→aAcB.e[5]S→aAcBe.

例：產(chǎn)生式S→aAcBe對應(yīng)的6個項目是：3.拓廣文法增加產(chǎn)生式S’→S，從而S’→S?成為唯一的接受項目.4.狀態(tài)轉(zhuǎn)換圖的構(gòu)造一個項目對應(yīng)一個狀態(tài),S’→?S為唯一初態(tài)，其余均為終態(tài)(活前綴識別態(tài))。

3.拓廣文法增加產(chǎn)生式S’→S，從而S’→S?成為唯一的接受構(gòu)造識別所有活前綴的轉(zhuǎn)換圖：每個狀態(tài)是一個LR(0)項目； S→?S是唯一的初態(tài)；所有的其他項目是終態(tài)，是某個活前綴的識別態(tài)；若狀態(tài)i為X→X1…Xi-1?Xi…Xn，狀態(tài)j為X→X1…Xi?Xi+1…Xn，則從狀態(tài)i畫一條有向邊到狀態(tài)j，標(biāo)記為Xi；如果Xi為一非終結(jié)符，并有Xi→1|2|…|m

則從狀態(tài)i畫有向邊到所有狀態(tài)Xi→?i。

S→?EE→?T構(gòu)造識別所有活前綴的轉(zhuǎn)換圖：S→?E例：S→BBB→aBB→bS'→?SS'→S?S→?BBS→B?BS→BB?B→?aBB→a?BB→aB?B→?bB→b?S'→SS→BBB→aBB→b拓廣這個文法的項目有:12S345BB678Ba910b

例：S'→?SS'→S拓廣這個文法的項目有:12S345B*RR5.項目的有效性

(1)對于項目A→?,如果有

SA則稱A→?對活前綴有效。意思是:到達(dá)項目A→?時,已識別出,希望繼續(xù)識別從推出的串。

若A→?B對活前綴有效,則B→?對活前綴也有效。*RR5.項目的有效性(1)對于項目A→?,如果有因為S’AB則,設(shè)’,有

S’ABB’’即S’B’’所以,B→?對也有效。*RRR***RRRRRR*

若A→?B對活前綴有效,則B→?對活前綴也有效。因為S’AB*RRR***RRRRRR*(2)有效項目集:對活前綴有效的項目的集合稱為對的有效項目集。

(3)LR(0)項目集規(guī)范族:文法G的所有有效項目集組成的集合。

(2)有效項目集:對活前綴有效的項目的集合稱為對內(nèi)容回顧

LR分析法輸入串分析?？偪爻绦騆R分析表活前綴規(guī)范句型+不含句柄之后任何符號LR（0）項目歸約項目:形如A→?移進項目:形如A→?a，aVT待約項目:形如A→?B，BVN接受項目:形如S→?，S為開始符狀態(tài)轉(zhuǎn)換圖S→BBB→aB內(nèi)容回顧LR分析法輸入串活前綴規(guī)范句型+不含句柄之后任何符*RR

(1)對于項目A→?,如果有

SA則稱A→?對活前綴有效。

（2)若A→?B對活前綴有效,則B→?對活前綴也有效。有效項目集LR(0)項目集規(guī)范族有效項目*RR(1)對于項目A→?,如果有（2)若A→?6.閉包函數(shù)closure(I)設(shè)I是文法G的一個LR(0)項目集(1)對任何iI,都有iclosure(I);(2)若項目ABclosure(I),且B為文法G的一個產(chǎn)生式,則Bclosure(I)；(3)重復(fù)(2)直至closure不再增大。

6.閉包函數(shù)closure(I)設(shè)I是文法G的一個LR(0)例：S→BBB→aBB→bS'→?SS'→S?S→?BBS→B?BS→BB?B→?aBB→a?BB→aB?B→?bB→b?S'→SS→BBB→aBB→b拓廣這個文法的項目有:

closure({S'?S})Closure(S'→S?)Closure(S→B?B)={S'→S?}={S→B?B,B→?aB,B→?b}={S'→?S,S→?BB,B→?aB,B→?b}={S→B?B,B→?aB,B→?b}例：S'→?SS'→S拓廣這個文法的項目有:closure7.轉(zhuǎn)換函數(shù)Go(I,X)設(shè)XVTVNgo(I,X)=closure(J)J:{任何形如AX的項目|AXI}AX項目集IXAXClosure(AX)Go(I,X)

7.轉(zhuǎn)換函數(shù)Go(I,X)設(shè)XVTVNAX項目集S'→?SS'→S?S→?BBS→B?BS→BB?B→?aBB→a?BB→aB?B→?bB→b?

I0=closure({S'?S})={S'→?S,S→?BB,B→?aB,B→?b}I1=Go(I0,S)=Closure(S→S?)={S→S?}I2=Go(I0,B)=Closure(S→B?B)={S→B?B,B→?aB,B→?b}I3=Go(I0,a)=Closure(S→a?B)={S→a?B,B→?aB,B→?b}I4=Go(I0,b)=Closure(B→?b)={B→b?}S'→?SI0=closure({S'?S})={S'→8.LR(0)項目集規(guī)范族的構(gòu)造beginC:={closure({S’→S})};repeatforC中每一項目集I和文法符號Xdoifgo(I,X)不空且go(I,X)Cthen

把go(I,X)加入C中

untilC不再增大end;

I2={S→?BB,B→?aB,B→?b}go(I2,S)為空8.LR(0)項目集規(guī)范族的構(gòu)造beginI2={S→?

I0=closure({S'?S})I1=go(I0,S)I2=go(I0,B)I3=go(I0,a)I4=go(I0,b)I5=go(I2,B)I6=go(I3,B)={S'→?S,S→?BB,B→?aB,B→?b}={S'→S?}={S→B?B,B→?aB,B→?b}={B→a?B,B→?aB,B→?b}={B→b?}go(I2,a)=go(I2,b)=={S→BB?}go(I3,a)=I3,go(I3,b)=I4={B→aB?},I3I4SBBb1234560abbaBS'→?SS'→S?S→?BBS→B?BS→BB?B→?aBB→a?BB→aB?B→?bB→b?例子I0=closure({S'?S})I1=go(I0,S三.LR（0）分析表的構(gòu)造(1)C={I0,I1,…,In},Ii對應(yīng)狀態(tài)i,I0=closure({S’S})為唯一初態(tài);(2)對每個Ii,若AaIi,且go(Ii,a)=Ij,則action[i,a]=sj;若AIi,A為第j個產(chǎn)生式,

則bVT{#},action[i,b]=rj;若S’SIi,則action[i,#]=acc;(3)若go(Ii,A)=Ij,則goto[i,A]=j;(4)凡不能用規(guī)則(2)、(3)登記的表項均為“錯誤”

三.LR（0）分析表的構(gòu)造(1)C={I0,I1,…,In狀態(tài)Actiongotoab#SB0s3S4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2I0=closure({S'?S})I2=go(I0,B)I3=go(I0,a)I4=go(I0,b)I5=go(I2,B)I6=go(I3,B)={S'→?S,S→?BB,B→?aB,B→?b}={S'→S?}={S→B?B,B→?aB,B→?b}={B→b?}go(I2,a)=go(I2,b)=={S→BB?}go(I3,a)=I3go(I3,b)=I4={B→aB?}I1=go(I0,S)I3I4={B→a?B,B→?aB,B→?b}（0）S'→S（1）S→BB（2）B→aB（3）B→b

狀A(yù)ctiongotoab#SB0s3S4121acc2s3內(nèi)容回顧

LR(0)分析表的構(gòu)造1.擴廣文法2.確定所有項目3.構(gòu)造LR(0)項目規(guī)范族閉包函數(shù)closure(I)轉(zhuǎn)換函數(shù)Go(I,X)ABclosure(I)且B為文法G的一個產(chǎn)生式

I：AXGo(I,X)=Closure(AX)則Bclosure(I)C={I0}={Closure(S’S)}對C中每一個項目集I和每一個文法符合Xgo(I,X)不空且go(I,X)C把go(I,X)加入C中內(nèi)容回顧LR(0)分析表的構(gòu)造1.擴廣文法2.確定所有內(nèi)容回顧

4.構(gòu)造LR(0)分析表C={I0,I1,…,In}若AaIi且go(Ii,a)=Ij則action[i,a]=Sj若AIi

A為第j個產(chǎn)生式則bVT{#}action[i,b]=rj若S’SIiaction[i,#]=acc若ABIi且go(Ii,B)=IjGoto[Ii,B]=Ij內(nèi)容回顧4.構(gòu)造LR(0)分析表C={I0,I1,…,In例G0(E)(0)S’→E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i

例G0(E)I0=closure({S’→S})S’EEE+TET,TT*FTF,F(E)FiI1=go(I0,E)S’EEE+TI2=go(I0,T)ETTT*FI3=go(I0,F)TFS’→EE→E+T│TT→T*F│FF→(E)│i

I4=go(I0,()F(E)EE+TETTT*FTFF(E)FiI6=go(I1,+)EE+TTT*FTFF(E)FiI5=go(I0,i)FiI7=go(I2,*)TT*FF(E),FiI8=go(I4,E)F(E)EE+TI9=go(I6,T)EE+T,TT*FI10=go(I7,F)TT*FI11=go(I8,))F(E)I0=closure({S’→S})S’→EI4=go(I0=closure({S’→E})S’EEE+TET,TT*FTF,F(E)FiI1=go(I0,E)S’EEE+TI2=go(I0,T)ETTT*FI3=go(I0,F)TF

I4=go(I0,()F(E)EE+TETTT*FTFF(E)FiI6=go(I1,+)EE+TTT*FTFF(E)FiI5=go(I0,i)Fi(0)S’→E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→iI0=closure({S’→E})I4=go(I0,(

I7=go(I2,*)TT*FF(E),FiI8=go(I4,E)F(E)EE+TI9=go(I6,T)EE+T,TT*FI10=go(I7,F)TT*FI11=go(I8,))F(E)go(I4,T)=I2go(I4,F)=I3go(I4,()=I4go(I4,i)=I5go(I6,F)=I3go(I6,()=I4go(I6,i)=I5go(I7,()=I4go(I7,i)=I5go(I8,+)=I6go(I9,*)=I7(0)S’→E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→iI7=go(I2,*)I8=go(I4,E)I9=go(I

LR(0)分析表狀態(tài)01234567891011actiongotoi+*()#ETFs5s4123r0accr2s7r2r2r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7/r1r1r1r3r3r3r3r5r5r5r5r2r2r4r4r6r6r1r1r3r3r5r5r0r0s6r0//r2LR(0)分析表狀01234567891011action

I2=go(I0,T)ETTT*FI1=go(I0,E)S’EEE+TI9=go(I6,T)EE+TTT*F移進-規(guī)約沖突該文法不是一個LR（0）文法I2=go(I0,T)I1=go(I0,E)I9=go(I

假定一個LR(0)項目集規(guī)范族有一個項目集I={X?b,A?,B?}四.SLR（1）分析表的構(gòu)造X?bA?移進-規(guī)約沖突B?規(guī)約-規(guī)約沖突假定一個LR(0)項目集規(guī)范族有一個項目集四.SLR（1

通過考察有關(guān)非終結(jié)符的FOLLOW集來解決移進-歸約和歸約-歸約沖突，以此構(gòu)造出來的LR分析表，叫做SLR(1)分析表當(dāng)狀態(tài)I面臨任何輸入符號a時，可采用如下策略：若a=b，則移進若aFOLLOW(A),則用產(chǎn)生式A歸約若aFOLLOW(B),則用產(chǎn)生式B歸約此外，報錯。I={X?b,A?,B?} 通過考察有關(guān)非終結(jié)符的FOLLOW集來解決移進-歸約和歸

一般的解決辦法設(shè)一個LR(0)項目集規(guī)范族有一個項目集I：I={A1?a11,

A2?a22,…,Am?amm,

B1?,B2?,…,Bn?}若滿足{a1,a2,…,am}FOLLOW(Bi)=,i=1,2,…,nFOLLOW(Bi)FOLLOW(Bj)=,i,j=1,2…,n,且ij,則可以通過判斷當(dāng)前的輸入符號a屬于哪一個集合來解決沖突。則按如下策略構(gòu)造SLR(1)分析表：若a=ai(i=1,2,…,n),則移進ai；aFOLLOW(Bi)(i=1,2…,n),則用Bi歸約；此外，按“出錯”處理；一般的解決辦法設(shè)一個LR(0)項目集規(guī)范族有一個項目集I：SLR（1）分析表的構(gòu)造(1)C={I0,I1,…,In},Ii對應(yīng)狀態(tài)i,I0=closure({S’S})為唯一初態(tài);(2)對每個Ii,若AaIi,且go(Ii,a)=Ij,則action[i,a]=sj;若AIi,A為第j個產(chǎn)生式,

則bFOLLOW(A),action[i,b]=rj;若S’SIi,則action[i,#]=acc;(3)若go(Ii,A)=Ij,則goto[i,A]=j;(4)凡不能用規(guī)則(2)、(3)登記的表項均為“錯誤”

SLR（1）分析表的構(gòu)造(1)C={I0,I1,…,In}例G0(E)(0)S’→E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i

FOLLOW(S’)={#}FOLLOW(E)={+,),#}FOLLOW(T)={+,),#,*}FOLLOW(F)={+,),#,*}例G0(E)FOLLOW(S’)={

I1=go(I0,E)S’EEE+TI9=go(I6,T)EE+TTT*FI2=go(I0,T)ETTT*FI6=go(I1,+)s6(0)S’→EFOLLOW(S’)={#}accI7=go(I2,*)s7FOLLOW(E)={+,),#}(2)E→Tr2go(I9,*)=I7s7FOLLOW(E)={+,),#}(1)E→E+Tr1I1=go(I0,E)I9=go(I6,T)I2=go(ISLR(1)分析表狀態(tài)01234567891011actiongotoi+*()#ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5

SLR(1)分析表狀01234567891011action

SLR分析表構(gòu)造步驟1.擴展文法2.列出擴展文法的LR(0)所有項目（0）S’一>S（4)E—>Aa（1)S—>E（5)A—>cA（2)E—>Aa（6)A—>d（3）E—>bB（7)B—>cB（8)B—>dS->EE->Aa|bBA->cA|dB->cB|d1.S’—>·S2.S'一>S.3.S一>.E4.S一>E.5.E一>.Aa6.E一>A.a7.E一>Aa.8.E一>.bB9.E一>b.B10.E一>bB.……1.移進項目2.待約項目3.歸約項目4.接收項目SLR分析表構(gòu)造步驟1.擴展文法2.列出擴展文法的LR(0

S->EE->Aa|bBA->cA|dB->cB|d3.構(gòu)造LR(0)項目規(guī)范族I0=closure({S’→S})S’一>S,S—>E,E—>Aa,E—>bB,A—>cA,A—>dI1=go(I0,S)S’一>S

I2=go(I0,E)S—>EI3=go(I0,A)E—>AaI4=go(I0,b)E—>bB,B—>cB,B—>dI5=go(I0,c)A—>cA,A—>cA,A—>dI6=go(I0,d)A—>d

I7=go(I3,a)E—>Aa

I8=go(I4,B)E—>bBI9=go(I4,c)B—>cBB—>cB,B—>dI10=go(I4,d)B—>d

I11=go(I5,A)A—>cAI12=go(I9,B)B—>cBS->EE->Aa|bB3.構(gòu)造LR(0

4.構(gòu)造LR(0)分析表(1)I0=closure({S’S})為唯一初態(tài);(2)對每個Ii,若Aa…Ii,且go(Ii,a)=Ij,則action[i,a]=sj;若AA…Ii,go(Ii,A)=Ij,則goto[i,A]=j;若AIi,A為第j個產(chǎn)生式,則bVT{#},action[i,b]=rj;若S’SIi,則action[i,#]=acc;4.構(gòu)造LR(0)分析表(1)I0=closure({S

I0：S’一>S,S—>E,E—>Aa,E—>bB,A—>cA,A—>dI1=go(I0,S)：S’一>SI2=go(I0,E)：S—>EI3=go(I0,A)：E—>AaI4=go(I0,b)：E—>bB,B—>cB,B—>dI5=go(I0,c)：A—>cA,A—>cA,A—>dI6=go(I0,d)：A—>dI7=go(I3,a)：E—>Aa

I8=go(I4,B)：E—>bBI9=go(I4,c)：B—>cBB—>cB,B—>dI10=go(I4,d)：B—>d

I11=go(I5,A)：A—>cAI12=go(I9,B)：B—>cB（0）S’一>S（1)S—>E（2)E—>Aa（3）E—>bB（4)E—>Aa（5)A—>cA（6)A—>d（7)B—>cB（8)B—>dI5=go(I5,c)I6=go(I5,d)I9=go(I9,c)I10=go(I9,d)I0：S’一>S,S—>E,E—>Aa,E—>bLR(0)分析表狀態(tài)01234567891011actiongotoabcd#EABs5s6123s4accr1r1s7s10s98s5s6r611s9r8r8r8r5r5r5

Sr1r1r1r6r6r6r6r2r2r2r2r2r3r3r3r3r3s101212r8r8r5r5r7LR(0)分析表狀01234567891011actiongS->EE->Aa|bBA->cA|dB->cB|dLR(0)文法1.歸約—歸約沖突2.移進—歸約沖突無{X?b,A?}{A?,B?}SLR(1)分析表若AIi,A為第j個產(chǎn)生式,

則bFOLLOW(A),action[i,b]=rj;

S->ELR(0)文法1.歸約—歸約沖突2.移進—歸約S’->SS->EE->Aa|bBA->cA|dB->cB|dFollow(S’)=Follow(S)=Follow(E)={#}Follow(A)={a}Follow(B)={#}I2=go(I0,E)：S—>EI2:#:r1I6=go(I0,d)：A—>dI6:a:r6I7=go(I3,a)：E—>AaI7:#:r2

I8=go(I4,B)：E—>bBI8:#:r3I10=go(I4,d)：B—>dI10:#:r8

I11=go(I5,A)：A—>cAI11:a:r5I12=go(I9,B)：B—>cBI12:#:r7

S’->SFollow(S’)=Follow(S)=FollSLR(1)分析表狀態(tài)01234567891011actiongotoabcd#EABs5s6123s4accr1s7s10s98s5s6r611s9r8

Sr2r3s101212r5r7SLR(1)分析表狀01234567891011action文法：G(E)E→E+E|E*E|(E)|I（1）確定文法LR(0)項目規(guī)范族（2）構(gòu)造LR(0)分析表（3）構(gòu)造SLR（1）分析表（4）判斷是不是LR（0）文法（5）判斷是不是SLR（1）文法文法：G(E)E→E+E|E*E|(E)|I(0)S’→E(1)E→E+E(2)E→E*E(3)E→(E)(4)E→iI0=closure({S’→E})S’E,EE+E,EE*E,E(E),EiI1=go(I0,E)S’E,EE+E,EE*E移進-歸約沖突I2=go(I0,()E(E),EE+E,EE*E,E(E),EiI3=go(I0,i)EiI4=go(I1,+)

EE+E,EE+E,EE*E,E(E),EiI5=go(I1,*)EE*E,EE+E,EE*E,E(E),EI(0)S’→EI0=closure({S’→E})I6=go(I2,E)E(E),EE+E,EE*EI7=go(I4,E)EE+E,EE+E,EE*E移進-歸約沖突I8=go(I5,E)EE*E,EE+E,EE*E移進-歸約沖突I9=go(I6,))E(E)I6=go(I2,E)

作業(yè)10.1，10.3，10.4，10.5，10.7作業(yè)10.1，10.3，10.4，10.5，10.7第8章自下而上的語法分析第一節(jié)引言自下而上分析：從輸入串出發(fā)，歸約，直至開始符方法：采用棧，在移進的過程中，觀察棧頂是否形成某個產(chǎn)生式的一個候選

第8章自下而上的語法分析第一節(jié)引言自下而上分析：從輸入串G(S)：

SSASSbAccAAa看輸入串bccab的歸約過程一.分析樹bScSccSaccSAccSASbASSASS符號棧

G(S)：一.分析樹bSccaAAbSS符號棧SSSAbccAbaSbAcAacAaSb輸入串bccab分析樹的形成

SSSAbccAbaSbAcAacAaSb輸入串bccab分分析樹的剪枝過程SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA

分析樹的剪枝過程SSSAbccAbaSSSAccAbaSSS

關(guān)鍵問題：如何判斷棧頂符號串是否形

成可歸約串、如何歸約？當(dāng)對不同的歸約串進行歸約，即形成了

不同的自下而上語法分析方法。

關(guān)鍵問題：如何判斷棧頂符號串是否形

設(shè)有文法G，S是開始符號，設(shè)是G的一個句型，若有

S且A

則稱是句型關(guān)于A的短語；++在上面定義中，如果A直接推出,即A，則稱是句型關(guān)于A的直接短語；一個句型的最左直接短語稱為句柄；二.回顧幾個核心概念短語直接短語句柄設(shè)有文法G，S是開始符號，設(shè)是G的一個句型，若有+EET+TTFFi*

G(E)E→E+T|TT→T*F|FF→(E)|i求T*F+i的短語、直接短語、句柄利用推導(dǎo)樹判斷句型的短語

EET+TTFFi*G(E)E→E

素短語：文法G某句型的一個短語是素短語，當(dāng)且僅當(dāng)它至少含有一個終結(jié)符，且除它自身之外不再含更小的素短語；最左素短語：在具有多個素短語的句型中處于最左邊的那個素短語；E1E2+T2T1T3*F2F1i1F3i2素短語：文法G某句型的一個短語是素短語，當(dāng)且僅當(dāng)它至SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA

SSSAbccAbaSSSAccAbaSSSAccAbSSS假定是文法G的一個句子,序列n,n-1,…,0滿足下述條件時稱為規(guī)范歸約。(1)n=α;(2)0為文法的開始符,即0=S;(3)對i,0<in,i-1是從i經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部符號而得到的。三.規(guī)范歸約（最左歸約）

假定是文法G的一個句子,序列n,n-1,…,0EET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE例:G(E)E→E+T│TT→T*F│FF→(E)│ii+i*i的分析過程

EET+FTii*FTiFi+i*iF+i*iT+i*iE+例:G(S)S→aAcBeA→Ab|bB→dabbcde的分析過程SaAcBe

AbdbabbcdeaAbcdeaAcdeaAcBeS

例:G(S)S→aAcBeSaA內(nèi)容回顧

語法分析自上而下自上而下1.規(guī)范規(guī)約內(nèi)容回顧語法分析自上而下自上而下1.規(guī)范規(guī)約1.算符文法上下文無關(guān)文法G,沒有形如P→ε或P→...QR...的產(chǎn)生式,則稱G為算符文法。第二節(jié)算符優(yōu)先分析法一.算符優(yōu)先文法

1.算符文法第二節(jié)算符優(yōu)先分析法一.算符優(yōu)先文法對算符文法G,a,bVT

定義2.終結(jié)符之間的優(yōu)先關(guān)系

(1)a=b:G中有P→...ab...或P→...aQb...++(2)a<b:G中有P→...aQ...且Qb…或QRb...++(3)a>b:G中有P→...Qb...且Q...a或Q…aR對算符文法G,a,bVT定義2.終結(jié)符之間的優(yōu)先若算符文法G的任何終結(jié)符a,b之間的優(yōu)先關(guān)系至多有=、>、<中的一個,則G為一算符優(yōu)先文法。

據(jù)定義，構(gòu)造下述文法G的優(yōu)先關(guān)系表G（E）:E→E+T|TT→T*F|FF→(E)|i3.算符優(yōu)先文法

若算符文法G的任何終結(jié)符a,b之間的優(yōu)先關(guān)系至3.算符優(yōu)先++**ii(())##>>><><<<<>>><<<<<<<<>>>>>>>>==算符優(yōu)先關(guān)系表

++**ii(())##>>><><<<<>>><<<<<<從上表可知:(1)相同終結(jié)符之間的優(yōu)先關(guān)系未必是=(2)有a<b，未必有b>a(3)a、b之間未必一定有優(yōu)先關(guān)系故=、<、>不同于關(guān)系運算符“等于”、“小于”、“大于”

從上表可知:初始化:#棧讀一符號ba=b=#a<b或a=ba>b歸約最左素短語,最左素短語出棧,左部符號入棧結(jié)束b入棧出錯YNYYNN二.算符優(yōu)先分析算法a為棧頂終結(jié)符初始化:#棧讀一符號ba=b=#a<b或a=ba>b歸這是一種結(jié)構(gòu)歸約,處于棧頂待歸約的最左素短語與對應(yīng)的產(chǎn)生式在結(jié)構(gòu)上應(yīng)一致,即長度一致,對應(yīng)的終結(jié)符一致,而非終結(jié)符可以不一致。歸約最左素短語的方法

E→E+TE+E這是一種結(jié)構(gòu)歸約,處于棧頂待歸約的最左素短語與對應(yīng)的產(chǎn)

算法優(yōu)先分析法的實現(xiàn)：使用一個分析棧，當(dāng)其棧頂形成最左素短語時，就進行歸約。分析算法k:=1;S[k]=‘#’;repeatb:=下一輸入符號;ifS[k]VTthenj:=kelsej:=k-1;whileS[j]>bdobeginrepeatQ:=S[j];ifS[j-1]VTth