第11講語法分析VII

上下文無關(guān)文法自上而下自下而上LL(1)文法2個函數(shù)遞歸下降預(yù)測分析非遞歸的預(yù)測分析最左推導(dǎo)最右推導(dǎo)！LR文法輸入LR分析程序輸出棧LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$移進-規(guī)約分析歸約移進-歸約沖突規(guī)約-歸約沖突句柄1。句柄與某個產(chǎn)生式的右部符號串相同2。句柄是句型的一個子串3。把句柄歸約成非終結(jié)符代表了最右推導(dǎo)逆過程的一步簡單的LR方法（SLR）規(guī)范的LR方法向前看的LR方法(LALR）溫故知新溫故而知新自下而上分析概述自下而上分析方法LR分析器2歸約歸約，是自下而上分析中的重要動作歸約，對應(yīng)著最右推導(dǎo)的逆過程3abbcdeAABSSaABeAAbc|bBd文法：abbcdeaAbcdeaAdeaABeSrmrmrmrm句柄句柄的非形式定義句型的句柄，是該句型中與一個產(chǎn)生式右部匹配的字符串句柄的精確定義右句型的句柄是一個產(chǎn)生式的右部

，并且該句柄

在用A替換中的句柄之后，得到的是最右推導(dǎo)中的前一個句型令=

ω，則可以通過產(chǎn)生式A->歸約為句型Aω4句柄S*X為X的句柄在移進-歸約分析中，句柄總是出現(xiàn)在棧頂自下而上分析基于識別句柄5自下而上分析方法使用兩種方法：移進shiftABC|xyzABCx|yz歸約reduceCbxy|ijkCbA|ijk6溫故而知新自下而上分析概述自下而上分析方法LR分析器73.5

LR分析器3.5.1

LR分析算法8輸入LR分析程序輸出棧LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$LR語法分析器的行為為描述LR語法分析的行為，引入概念格局(Configuration)用二元組表示

(s0X1s1X2s2…Xmsm,aiai+1…an$)

棧的內(nèi)容尚未處理的輸入Xi代表文法符號，si表示狀態(tài)代表右句型X1X2…Xmaiai+1…an在分析棧中增加了狀態(tài)9初始格局10LR分析程序輸出Action[s,a]Gotos0…a1ai…an$輸入棧移進之前(s0X1s1X2s2…Xmsm,aiai+1…an$)11輸入LR分析程序輸出Action[sm,ai]=“shift

s”GotosmXmsm-1Xm-1…s0…a1ai…an$棧移進之后(s0X1s1X2s2…Xmsmais

,

ai+1…an$)

12LR分析程序輸出Action[sm,ai]=“shift

s”GotosmXmsm-1Xm-1…s0…a1ai…an$ais輸入棧歸約之前13LR分析程序輸出棧Action[sm,ai]=“rA”smXmsm-rXm-r…s0…a1ai…an$Goto[sm-r,A]=s

…輸入歸約從棧中彈出2*||個符號14LR分析程序輸出Action[sm,ai]=“rA”sm-rXm-r…s0…a1ai…an$Goto[sm-r,A]=s

2*||輸入棧歸約從棧中彈出2*||個符號，再進棧15LR分析程序輸出Action[sm,ai]=“rA”ssm-rXm-r…s0…a1ai…an$Goto[sm-r,A]=s

A2*||輸入棧接受16LR分析程序輸出Action[s,$]=“accept”sX1s0…a1ai…an$Goto輸入棧報錯17LR分析程序輸出Action[s,a]未定義…a1ai…an$GotosmXmsm-rXm-r…s0…輸入棧本講綱要活前綴活前綴的DFALR(0)項目集構(gòu)建識別活前綴的DFA構(gòu)造SLR分析表18活前綴活前綴：右句型的前綴，該前綴不超過最右句柄的右端

S

*rm

Aw

rm

w

的任何前綴（包括和

本身）都是一個活前綴。19一個符號串的前綴是指從第一個符號開始的連續(xù)的若干個符號構(gòu)成的子串?；钋熬Y文法例子20SaABeAAbc|bBd自下而上分析時，棧中可能出現(xiàn)的串：aabaAaAbaAbcaAdaABaABeS活前綴：右句型的前綴，該前綴不超過最右句柄的右端

S

*rm

Aw

rm

w

的任何前綴（包括和

本身）都是一個活前綴。活前綴與句柄的關(guān)系文法例子21棧中可能出現(xiàn)的串：aabaAaAbaAbcaAdaABaABeS①活前綴已含有句柄的全部符號，表明產(chǎn)生式A→β的右部β已出現(xiàn)在棧頂。出現(xiàn)句柄（對應(yīng)A->b）出現(xiàn)句柄（對應(yīng)A->Abc）出現(xiàn)句柄（對應(yīng)B->d）出現(xiàn)句柄（對應(yīng)S->aABe）SaABeAAbc|bBd活前綴與句柄的關(guān)系文法例子22棧中可能出現(xiàn)的串：aabaAaAbaAbcaAdaABaABeS①活前綴已含有句柄的全部符號，表明產(chǎn)生式A→β的右部β已出現(xiàn)在棧頂。出現(xiàn)產(chǎn)生式A->Abc右端的一部分，期望從輸入串中看到bc出現(xiàn)產(chǎn)生式S->aABe的右端一部分，期望從輸入串中看到e②活前綴只含句柄的一部分符號如β1表明A→β1β2的右部子串β1已出現(xiàn)在棧頂，當前期待從輸入串中看到β2推出的符號。出現(xiàn)產(chǎn)生式A->Abc右端的一部分，期望從輸入串中看到cSaABeAAbc|bBd活前綴與句柄的關(guān)系文法例子23棧中可能出現(xiàn)的串：aabaAaAbaAbcaAdaABaABeS①活前綴已含有句柄的全部符號，表明產(chǎn)生式A→β的右部β已出現(xiàn)在棧頂。期望出現(xiàn)符號A推出的符號串②活前綴只含句柄的一部分符號如β1表明A→β1β2的右部子串β1已出現(xiàn)在棧頂，當前期待從輸入串中看到β2推出的符號。③活前綴不含有句柄的任何符號，此時期望產(chǎn)生式A→β的右部所推出的符號串。SaABeAAbc|bBdLR分析的核心工作構(gòu)建識別活前綴的DFA基于DFA構(gòu)建分析表24本講綱要活前綴活前綴的DFALR(0)項目集構(gòu)建識別活前綴的DFA構(gòu)造SLR分析表25活前綴分析過程中在分析棧里出現(xiàn)的串，被稱為活前綴活前綴可以用一個DFA來識別例如，下面的產(chǎn)生式文法 SV=E SE V*E Vid EV26請畫出識別上述活前綴的DFA!本講綱要活前綴活前綴的識別LR(0)項目集構(gòu)建識別活前綴的DFA構(gòu)造SLR分析表27LR(0)項目集由一些LR(0)項目組成的集合LR(0)項目在右部的某個地方加點的產(chǎn)生式例如，對于產(chǎn)生式AXYZ對應(yīng)的加點項有A·XYZAX·YZAXY·ZAXYZ·又例如，對于A，其加點項有A·28點的左邊代表歷史信息，右邊代表展望信息。直觀地講，項目表示在分析過程的某一階段，已經(jīng)看到了產(chǎn)生式的多大部分，以及希望看到的部分。分析過程實例通過實例來說明加點項含義29$SaABeAAbc|bBdabbcde$對應(yīng)的加點項是S

·aABe表示什么意思呢？分析剛開始，棧內(nèi)還沒有任何字符，加點項中的·

后面是期望看到的文法符號aS0action(0,a)=s1,表示從狀態(tài)0移進a之后，狀態(tài)遷移到S1S代表移進動作分析過程實例通過實例來說明加點項含義30$SaABeAAbc|bBdbbcde$對應(yīng)的加點項是aSa·

ABeA

·

AbcA

·

bA的來源有兩種可能S0S1狀態(tài)S1對應(yīng)的項目可能有Sa·

ABeA

·

AbcA

·

b下一步動作：action(1,b)=S231$SaABeAAbc|bBdbcde$狀態(tài)S2是從狀態(tài)S1移入b后得到的新狀態(tài)移進符號b后，加點項A

·

b

中的點可以向后移一格，變成Ab

·abS0S1S2狀態(tài)S1Sa·

ABeA

·

AbcA

·

b狀態(tài)S2Ab·下一步動作要對b進行歸約32$SaABeAAbc|bBdbcde$需要看一下在狀態(tài)1，如果后面看到一個符號A后可以將點移動到哪里有兩種可能結(jié)果：aASaA·

BeAA

·bcS0S1狀態(tài)S1Sa·

ABeA

·

AbcA

·

bS2狀態(tài)S2SaA·

BeAA

·bcB

·d33$SaABeAAbc|bBdcde$移進b之后aAbS0S1S2狀態(tài)S2SaA·

BeAA

·bcB

·d新狀態(tài)為：狀態(tài)S3AA

b·

cS334$SaABeAAbc|bBdde$進入新狀態(tài)aAbcS0S1S2S3狀態(tài)S3AA

b·

c狀態(tài)S4AA

bc·S4這是一個歸約狀態(tài)，下一步動作是歸約35$SaABeAAbc|bBdde$到達狀態(tài)aAS0S1S2狀態(tài)S2SaA·

BeAA

·bcB

·d下一步做什么呢？36$SaABeAAbc|bBde$到達狀態(tài)aAS0S1S2狀態(tài)S2SaA·

BeAA

·

bcB

·dd狀態(tài)S5Bd·S5又到了一個歸約狀態(tài)37$SaABeAAbc|bBde$到達狀態(tài)aAS0S1S2狀態(tài)S2SaA·

BeAA

·

bcB

·dB狀態(tài)S6SaAB·

eS638$SaABeAAbc|bBd$到達狀態(tài)aAS0S1S2B狀態(tài)S7SaABe·

S6e狀態(tài)S6SaAB·

e歸約態(tài)！39$SaABeAAbc|bBd$SS0OK大功告成！本講綱要活前綴活前綴的識別LR(0)項目集構(gòu)建識別活前綴的DFA構(gòu)造SLR分析表403.5

LR分析器從文法構(gòu)造識別活前綴的DFA

1.拓廣文法

EE

EE+T|T TT*F|F F(E)|id

41當且僅當分析器使用EE

規(guī)約時，宣告分析成功ErmE+Trm

E+FrmE+idrmT+idrmF+idrmid+id

id+id

F+idT+idE+idE+FE+TE3.5

LR分析器從文法構(gòu)造識別活前綴的DFA 2.構(gòu)造LR(0)項目集規(guī)范族I0:

E·E E·E+T

E·T T

·T*F T

·F F

·(E) F

·id42閉包函數(shù)closure(I)1、I的每個項目均加入closure(I)2、如果Aα·Bβ在closure(I)中，且Bγ是產(chǎn)生式，那么如果項目B·γ還不在closure(I)中的話，那么把它加入。EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器從文法構(gòu)造識別活前綴的DFA 2.構(gòu)造LR(0)項目集規(guī)范族I0:

E·E (核心項目) E·E+T E·T T·T*

F (非核心項目，

T·F 通過對核心項目求閉包 F·(E)而獲得） F·id43E’·E及所有的點不在產(chǎn)生式右部的左端的項目EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器從文法構(gòu)造識別活前綴的DFA 2.構(gòu)造LR(0)項目集規(guī)范族I0: I1:

E·E EE· E·E+T EE·+T E·T T·T*

F T·F F·(E) F·id

44EE

EE+T|TTT*F|FF(E)|idI1:=goto(I0,E)I1:=goto(I0,X)定義：滿足[A·X]屬于I0

的所有項目[AX·]的集合的閉包3.5

LR分析器從文法構(gòu)造識別活前綴的DFA 2.構(gòu)造LR(0)項目集規(guī)范族I0: I1:=goto(I0,E)

E·E EE· E·E+T EE·+T E·T T·T*

F I2:=goto(I0,T) T·F E

T·

F·(E) TT·*

F

F·id

45EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器從文法構(gòu)造識別活前綴的DFA

2.構(gòu)造LR(0)項目集規(guī)范族I0: I1:

E·E EE· E·E+T EE·+T E·T T·T*

F I2: T·F E

T·

F·(E) TT·*

F

F·id

I3:=goto(I0,F)

TF·46EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器I0: I4:=goto(I0,(

)

E·E F(·E) E·E+T E·E+T E·T E·T T·T*

F T·T*

F T·F T·F F·(E) F·(E) F·id F·id

I5:=goto(I0,id

)

F

id·473.5

LR分析器48

I1:

EE· EE·+TI6

:

EE+·T T·T*F

T·F

F·(E)

F·id

EE

EE+T|TTT*F|FF(E)|idI1I0EI3I2I4I5TF(id3.5

LR分析器49

I1I0EI3I2I4I5TF(idI2:ET·TT·*F

I7:TT

*·FF·(E)

F·id

EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器50

I1I0EI3I2I4I5TF(idEE

EE+T|TTT*F|FF(E)|idI3:

T

F·

3.5

LR分析器51

I1I0EI3I2I4I5TF(idEE

EE+T|TTT*F|FF(E)|idI3:

T

F·

52

I1I0EI3I2I4I5TF(idEE

EE+T|TTT*F|FF(E)|idI4:

F

(·E) E·E+T E·TT·T*F T

·F F·(E) F·id

I2: ET·

TT·*F

I8:

F(E·) EE·+TI3:

TF·

I4:

F(·E)

...

I5:

F

id·

3.5LR分析器53I5:F

id·

EE

EE+T|TTT*F|FF(E)|idI1I0EI3I2I4I5TF(id3.5LR分析器54I1I0+EI6I3I2I4I8I7I5指向I2指向I3T*F(Eidid(FTEE

EE+T|TTT*F|FF(E)|id

55

I1I0+指向I7EI6I9I3I2I4I11I8I7I10*TI5指向I4指向I3指向I5指向I4指向I5指向I6指向I2指向I3F(FTid*id(F(Eid+)id(FT本講綱要活前綴活前綴的識