大三下課程編譯原理

Ch5Ch55.1“移近—LR0)SLR(1)LR1)LALR1)語法分析器的自動生成與第1Ch5Ch5語法分 5.3LR第2Ch5Ch5語法分 G第3Ch5語法分 LR在R分析的每一步，僅據(jù)分析棧當(dāng)前已經(jīng)移進(jìn)和歸約的全部語法符號并最多再向前看k個輸入字符，就能確定適合于文 則的句柄是否已在棧頂形成，從而第4Ch5Ch5語法分 第5CCh5語法分 (LR分析表(LR分析表#

┆┆#

第6Ch5語法分 LR分析器結(jié)構(gòu)與工作原

狀態(tài)

的“歷史”和“展望”信息； # 和歸約(VN#

P第7Ch5語法分 Ch5語法分 ①L→E,②L→③E→

#0E2,5E2④E→ #0E2,5E2輸入字符串a(chǎn)babE(歸約 ，(移進(jìn)棧aE(歸約第8Ch5Ch5語法分 ab,#EL02112345266第9Ch5語法分 Ch5語法分 G(L)的LR①L→E,②L→③E→#0E2,5E2④#0E2,5E2輸入字符串a(chǎn)babE(歸約 ，(移進(jìn)棧aE(歸約第10Ch5語法分 LR分析器結(jié)構(gòu)與工作原

Q×(VT¨{#})Q×VN第11Ch5Ch5語法分 LRstateActionGoto …………第12Ch5Ch5語法分 state…goto(Q0,…goto(Q0,goto(Q1,…goto(Q1,……………goto(Qm,…goto(Qm,Qi?Xi?第13CCh5語法分 goto(Qi,Xi)

goto(Qi,Xi)的Qi、Xi意指當(dāng)前棧頂?shù)牡?4Ch5Ch5語法分 分析動作 state………Qi?ai?第15Ch5Ch5語法分 SQ(移進(jìn)：將ai和Qj狀態(tài)壓入棧jaction(Qi,ai)第16Ch5Ch5語法分 …#…$:a1a2……#…FPaction(Qm,ai)= …#…$:a1a2……#…FP第17CCh5語法分 action(Qi,ai)

SQj(移進(jìn)：將ai和Qj狀態(tài)壓入棧rj(歸約：用第j個產(chǎn)生式歸約第18CCh5語法分 $:a1a2…aiai+1…an……#……PP

,

)=歸約。設(shè)G第j個產(chǎn)生式為：AXm-r+1Xm-r+2…#…AP第19CCh5語法分 Pgotogoto(Qm-r,A)=P…#…A$:a1a2…aiai+1…anF

第20CCh5語法分 action(Qi,ai)

SQj(移進(jìn)：將ai和第jrj(歸約：用第j個產(chǎn)生式歸約)acc(接受：分析成功)error(出錯：語法錯，調(diào)出錯處理程序)第21Ch5Ch5語法分 ab,#EL02112345266第22Ch5Ch5語法分 LR分析器結(jié)構(gòu)與工作原①分析開始，將初始狀態(tài)Q0及輸入字符串左界符 //初始化②據(jù)當(dāng)前分析棧棧頂Qm，當(dāng)前輸入符號ai查action若action(若action(Qm,ai)＝SQj若action(Qmai)＝rj，若action(Qm,ai)＝acc若action(Qmai)＝error第23Ch5Ch5語法分 第24Ch5Ch5語法分 例 G(L)的LR①②③④輸入字符串a(chǎn)ba第25Ch5語法分 棧中狀態(tài)輸入符號 a,b,a ,b,a # ,b,a #

44b,a#5,a#6,a# 7a#8##9########第26Ch5Ch5語法分 L⑥⑤①④②③第27Ch5Ch5語法分 LR分析的關(guān)鍵—LR分析表：集成了全第28Ch5Ch5語法分 LR0)SLR1)LR1)LALR1)語法分析器的自動生成與第29Ch5Ch5語法分 LR0LR(0)第30Ch5Ch5語法分 5.4.1 定義5.6（活前綴R$SaAwaw若串是ab的前綴R則是活前綴；當(dāng)=a，則活前綴特點:第31Ch5語法分 棧中狀態(tài)輸入符號 10a,b,a#10a,b,a#2,b,a#3,b,a#4b,a#5,a#r4(6,a#7a#8##9######r1用規(guī)則①歸約##第32Ch5Ch5語法分 L⑥⑤①④②③第33Ch5Ch5語法分 5.4.1 定義 （LR(0)項目約定：若產(chǎn)生式形式為Aε則其LR(0)項第34CCh5語法分 5.4.1 例

設(shè)文法S→A| A→aA|b|eS→·S→·A→·A→·b

S→AS→BA→a·AA→b·

B→· B→c第35Ch5Ch5 LR(0)句柄a恰好包含在棧中，即當(dāng)前棧中的內(nèi)容構(gòu)成了所期望的剛好含句柄的活前綴，應(yīng)按A→a進(jìn)行歸約。S’a·（S’是開始符號用S’a第36Ch5Ch5語法分 5.4.1 需將a移進(jìn)分析棧。 第37例

設(shè)文法Ch5語法分 5.4.1 B→· SCh5語法分 5.4.1 B→·A→a·A→a·S→AS→BS'→SA→·aAA→·bS'→·SS→·AS→·BA→A→A→bB→cA→aA第38Ch5Ch5語法分 5.4.1 自動機(jī)：①規(guī)定文法開始符號在左側(cè)的產(chǎn)生式(設(shè)S'→A)的第一個LR(0)項目(即S'·A為NFA的唯一初態(tài)；②令所有LR(0)項目分別對應(yīng)NFA第39③若狀態(tài)i和狀態(tài)j出自同一文法G的產(chǎn)生式且兩個狀態(tài)LR(0)i為 iji引一條標(biāo)記為Ｘiiji為待約項目(設(shè)為Ｘ→a·Aβ)，則從狀態(tài)i引ε弧到所有A·g的狀態(tài)。Ch5語法分 Ch5語法分 5.4.1

第40Ch5語法分Ch5語法分 5.4.1 NFAM=(Q，Σ，f，q0，Z

G的

i為則j?f(i，Ｘi若狀態(tài)i為待約項目(設(shè)Ｘ→a·Aβ)A→·gf（i，）第41CCh5語法分 5.4.1 例

設(shè)文法G(S )6 61A→·aA e

5S￠→A3e0S￠→ 3eb

e A→ A→be

第42CCh5語法分 5.4.1 e01AAe01AA6e53eb4I

第43Ch5語法分Ch5語法分 5.4.1 b32A→b.bA4aAA→a.AA→.A→.ba01S＇→A.S＇→.AA→.aAA→.bAaAbaA0aA143b201 ab(b歸約到01 aA(aA歸約到 CC第44Ch5Ch5語法分 LR0LR(0)第45Ch5Ch5語法分 5.4.1 定義例5.12文法G(S的LR(0)項目集規(guī)范族CC=（｛S→｛A→b·｝｛S→A·｝｛A→aA·｝）第46Ch5Ch5語法分 5.4.2 構(gòu)造LR(0)項目集規(guī)范族的方法(之一第一步 第二步 G所有活前綴的 第47CCh5語法分 5.4.2 構(gòu)造LR(0)項目集規(guī)范族的方法

第48Ch5Ch5語法分 5.4.2 假定I是文法G的任一項目集，則構(gòu)造I①I中的每一個項目皆屬于②若形如Aa·Bβ(B∈VN的項目屬于則對G中的任何產(chǎn)生式B第49Ch5Ch5語法分 求項目集轉(zhuǎn)換函數(shù)GOI,X)定義I是文法G的一個項目集，X為G的符號，則GO(I,X)＝closure(J)。J={形如AαX·β的項目|$A→a·Xβ∈I}第50CCh5語法分 5.4.2 構(gòu)造LR(0)項目集規(guī)范族的方法第一步

號，則將產(chǎn)生式S￠→S加入到G中構(gòu)成新的文法G，S為G的開始符號，G稱為G的 法。（使文法開始符號的 第51Ch5語法分 S→A| A→aA|b| B→S→A|BA→aA|b|εB→c第52Ch5語法分 5.4.2 itemsets(GSS

if對CI和每個文法符號X,若GO(I,X)非空且不在C中)GO(I,X)加入C中}while(沒 的項目可以加入}第53Ch5語法分 5.4.2 利用構(gòu)造LR(0)項目集規(guī)范族的方法(之二)求 closure(S￠→.A)={S￠→.A，A→.aA|.b}＝I0GO(I0,a)=closure(A→a.A)={A→a.A，A→.aA|.b}＝I2GO(I0,b)=closure(A→b.)={A→b.}＝I3GO(I2,A)=closure(A→aA.)={A→aA.}＝I4第54Ch5Ch5語法分 5.4.2 {A→a.A，A→.aA|.b}，{A→b.}，{A→abA0abA02311223434第55Ch5語法分 5.4.2 Ch5語法分 5.4.2 包含歸約項目的項目集構(gòu)成終態(tài)集Z第56Ch5語法分 5.4.2 Ch5語法分 5.4.2 初始狀態(tài)0＝{closure(S￠→·S)}if對每個狀態(tài)i和每個文法符號X若GO(i,X)=j非空且不在Q中)while(沒有的狀態(tài)可以加入Q);}第57Ch5語法分 A→a.AA→A→a.AA→.aAA→.b4A→A→aA S￠→.AA→.S￠→.AA→.aAA→.b3A1

A A0b →A1第58Ch5Ch5語法分 LR0LR(0)第59Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)定義①即含移進(jìn)項目又含歸約項目； ②含有多個歸約項目；第60Ch5語法分

0202

ab(b歸約到aA(aA歸約到AaAbAaAb

A→aAA→a.A→aAA→.aAA→.bbS￠→.AA→.aAS￠→.AA→.aAA→.b3A1→A→ACh5Ch5語法分 5.4.3 LR(0)分析表的構(gòu) 對應(yīng)分析表中action(M,a)＝SN(a∈VT)，在DFA中為從狀態(tài)Ｍ出發(fā)，經(jīng)過一條aN； 對應(yīng)分析表中action(Ｍ,a)＝rn(a∈VT)，在式編號為n；③對分析表中GOTO(M，B)＝N(BVN)action(Sk＝acc”,其中k是第62Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)算法 若f(K，a)＝j(luò)(a∈ＶT)，則置action(K,a)＝Sj；第63Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)算法 構(gòu)造LR(0)分析表（續(xù)②若f(k，A)＝j(luò)(A∈ＶN)GOTO(K，A)＝j(luò)③若A→a·k，則對所有終結(jié)符a和結(jié)束符“?！?，置action(K,a)＝rj和action(K,＃)＝rj。(其中假設(shè)產(chǎn)生式Aa·j個產(chǎn)生式S→S·∈k，則置action(K,第64CCh5語法分 5.4.3 LR(0)分析表的構(gòu)4:A→aA4:A→aA2:A→a.A A→. 0:S→.AA0:S→.AA→.aAA→.bbb3:A→bA

ab#A01124341:1:S→A→AA→aA②｜b第65Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)算法 C＝｛I0I1，…，In｝，K 若GOIka)＝Ij(a∈ＶT)action(K,a)＝Sj第66Ch5Ch5 LR(0)算法 構(gòu)造LR(0)分析表（續(xù) 若GOIk,A)＝Ij(A∈ＶN)GOTO(K，A)＝j(luò)③若A→a·∈Ik，則對所有終結(jié)符a＃”，置action(K,a)＝rjaction(K,＃)＝rj(其中假設(shè)產(chǎn)生式Aa·j個產(chǎn)生式 若S→S·∈Ik，則置action(K,⑤第67CCh5語法分 5.4.3 LR(0)分析表的構(gòu)對例5.12的文法G(S有LR(0)項目集規(guī)范族及GO→AA→aA②｜bI0：｛S￠→·A，A→AA→aA②｜bI2：｛A→a·A，A→·aA，A→·bI3：｛A→b·｝I4：｛A→aA·｝ab#A0ab#A0112434

abA02abA02311223434Ch5Ch5語法分 LR0)SLR1)LR1)LALR1)語法分析器的自動生成與第69Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)例 G A→aA|首先文法 G S 第70G①②S①②SCh5 SLR(1)分析與SLR(1)ASAS→Aa#A011233A 3a\文法G是非LR(0)第71Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu) 第72Ch5Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)A→b·的項目集（狀態(tài)）Ii，不管當(dāng)前輸i的那一行的諸元素都指定為rj(其中j為產(chǎn)生式A→b·的編號)?！璱… Ch5Ch5語法分 5.6LR(1)分 action(i,a)={A→ ("a∈VT¨ \用A定義4.5（回顧FOLLOW(A)＝｛a|S=>…Aa…，a∈VT｝若S=>…A，則令?！蔉OLLOW(A)。第74Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)Ii=｛A→b·B→d·，｝FOLLOW(B)，再對任何輸入符號a：當(dāng)a∈FOLLOW(A)時，置actioni＝{A→b歸約當(dāng)a∈FOLLOW(B)時，置actioni＝{Bd歸約 SLR(1)第75Ch5Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)算法 C＝｛I0I1，…，In｝，K 若GOIka)＝Ij(a∈ＶT)action(K,a)＝Sj第76Ch5Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)算法 構(gòu)造SLR(1)分析表（續(xù) 若GOIk,A)＝Ij(A∈ＶN)GOTO(K，A)＝j(luò)③若A→a·∈Ik，則對所有a?FOLLOW(A)，置action(K,a)＝rj。(其中假設(shè)產(chǎn)生式Aa·j個產(chǎn)生式 若S→S·∈Ik，則置action(K,⑤第77Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)算法5.7’構(gòu)造SLR(1) 若f(K，a)＝j(luò)(a∈ＶT)，則置action(K,a)＝Sj；第78Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)算法 構(gòu)造SLR(1)分析表（續(xù) 若f(k，A)＝j(luò)(AＶN)GOTO(K，A)＝j(luò)③若A→a·k，則對所有a?置action(K,a)＝rj(其中假設(shè)產(chǎn)生式Aa·j個產(chǎn)生式 若S→S·∈k，則置action(K,⑤第79Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)定義表，如果每個不含多重定義，則稱它為GSLR(1)SLR(1)分析表構(gòu)造=SLR(1)方法+LR(0)SLR(1)=第80Ch5語法分 SLR(1Ch5語法分 SLR(1)分析與SLR(1)分析表的構(gòu)

FOLLOW(A)a#A0a#A0112330

AAA→aS’→A 3a

第81Ch5Ch5語法分 LR0)SLR1)LR1)LALR1)語法分析器的自動生成與第82Ch5Ch5語法分 5.6LR(1)分SLR(1第83Ch5語法分 5.6LR(1)分例 S→S→LL→R→

為為第第84Ch5Ch5語法分 5.6LR(1)分 0：S’→·SS→·ＲＬ→·*L→R→LRi=2：R→3：S→3：S→i6：S→L=·RL→·*LRiR5：Ｌ→L*L8：R→7：L4:LR→·LL→·*L→*第第85 S→ R→ S→ L→ L L S→ L→ S→ R→Ch5語法分 5.6LR(1)分 狀態(tài)2＝｛S存在移進(jìn)－歸 FOLLOW( FOLLOW(R)∩｛=｝≠\文法G是非SLR(1) Ik：A→b若a∈FOLLOW(A)actionk,a)={A→第86CCh5語法分 5.6LR(1)分 action(k,a)={A→ \用AAb0#…dk=>…Aa…，a∈VAb0#…dk$:…a

第87Ch5Ch5語法分 5.6LR(1)分SLR(1第88Ch5Ch5語法分 5.6LR(1)分 定義 （LR(k)項目［A→a·β，a1a2…akAa·β是一個LR(0ai?VT¨{#}a1a2…ak：第89Ch5Ch5語法分 5.6LR(1)分 定義 （LR(1)有效項目>dAω=>aω 其中：ω∈VT*，=a，a?FIRST(w)a為’#’(當(dāng)w=)，稱a第90例5.16 設(shè)有文法S→ B→aB|LR(1)項目Ba.B,a]對活前綴aaa$S=>BB=>BaB=>Bab=>

=>a=>aaa

當(dāng)w=eCh5Ch5語法分 5.6LR(1)分 LR(1)項目B→a.B,#]對活前綴Baa $SBB=>BaB=>第91CCh5語法分 5.6LR(1)分 例如，對例5.15I2＝｛S→L·=FOLLOW(從[R→L·,#]項目 而[R→L·,=]項目

$S‘SR

L S→ L→ S→ R→第92Ch5Ch5語法分 5.6LR(1)分 若文法G的一個LR(0)項目［Aβ1·R*>RR第93Ch5Ch5語法分 5.4.3 LR(0)分析表的構(gòu)3aAabb4A→b3aAabb4A→bA2S￠→.AA→.aAA→.bA→.aAA→.b→AA→aAA→aA51第94Ch5Ch5語法分 5.6LR(1)分SLR(1第95Ch5Ch5語法分 5.6LR(1)分 1：函數(shù)closure(I2：GO函數(shù)；第96Ch5算法closure(I{

5.6LR(1)分 *注意：待約項目擴(kuò)展的項目doifI[A→a·Bβa及G′中的每個產(chǎn)生式B→γFIRST(ba)b,如果[B→?γ，b]不在I中B→?γ,b]加到I}while(沒 的項目可以加入I)returnI}第97Ch5Ch5語法分 5.6LR(1)分 GOIX){令J＝{[A→aX?β,a]|[A→a?Xβ,a]?I}; }LR(1)LR(1)項目集I的GO函數(shù)：GO(IX)是I中第98Ch5)

5.6LR(1)分 {C=closure({S￠→?S,#});do{

if對C的每個項目IX,若GO(I,X)非空且不在C中)把GO(I,X)加入C中;}while(沒 }

第99Ch5語法分 5.6LR(1)分 算法{初態(tài)0=closureS￠→?Sdo

if對每個狀態(tài)iX若GO(iX)＝j(luò)非空且不在DFA中}while(沒 }

第100Ch5Ch5語法分 5.6LR(1)分 例 S→S→LL→R→第1016Lfi 6Lfi0S’fiS，#

S’fiS，# SfiL＝R，#SfiR，#

LSfiL?＝R，# L，#

RLfi*R，＝/#

SfiR，#

SfiL＝R?，#Lfii，＝/#RfiL，#

12Lfi

10 13Lfi*R?，# Lfi

RLfi

Lfi*R?，＝/#

Rfi

4Lfi8Rfi

LfiLfi

第102Ch5Ch5語法分 5.6LR(1)分SLR(1第103CCh5語法分 5.6LR(1)分 算法

(LR(1)分析表構(gòu)造 的文法G和文法G的LR(1)項目集規(guī)范族C和GO函數(shù)輸出：文法G的LR(1)方法：設(shè)G的LR(1)C＝｛I0,I1,…,［S￠→·S，＃］的項目集為分析表的初態(tài)。第104Ch5Ch5語法分 5.6LR(1)分 算法5.10（續(xù)①對于每個項目集Ii中形如［A→a·Xb，b］的項目，若GO(Ii,X)＝Ij，且X∈VT，置action［i,X］＝SjX∈VN時，則置:GOTO［i,X］＝j(luò)②若歸約項目［A→a·a］∈Ii，Aa為文法的第j個產(chǎn)生式，則置action［i,a］=rj。③若接受項目［S'→S·，#］∈Ii，則置action［i，#］=“acc”④對分析表中不能按上述規(guī)則填入信息的元素，第105CCh5語法分 5.6LR(1)分 算法

(LR(1)分析表構(gòu)造 的文法G和文法G的識別LR(1)輸出：文法G的LR(1)方法：設(shè)G的識別LR(1)Q＝｛0,1,…,令Q的每個狀態(tài)Ｋ第106Ch5Ch5語法分 5.6LR(1)分