【正文】 語(yǔ)法分析■構(gòu)造識(shí)別文法所有規(guī)范句型活前綴構(gòu)造識(shí)別文法所有規(guī)范句型活前綴 DFA的方法的方法構(gòu)成識(shí)別文法規(guī)范句型活前綴 DFA的每一個(gè)狀態(tài)是由若干個(gè) LR(0)項(xiàng)目所組成的集合，稱為 LR(0)項(xiàng)目集。為了使 “接受 ”項(xiàng)目唯一，對(duì)文法 G進(jìn)行拓廣。增加一個(gè)唯一的開始符號(hào) S’，及產(chǎn)生式 S’?S。（設(shè) S為文法 G的開始符號(hào)）Date 59信息學(xué)院 孫麗云第 4章 語(yǔ)法分析設(shè)設(shè) I是文法是文法 G的一個(gè)的一個(gè) LR(0)項(xiàng)目集合，項(xiàng)目集合， I的項(xiàng)目閉包的項(xiàng)目閉包 closure(I)定義為：定義為：(1)I?closure(I)。(2)若項(xiàng)目若項(xiàng)目 A??.B??closure(I)， 且且 B??是是 G的產(chǎn)生式的產(chǎn)生式，則項(xiàng)目，則項(xiàng)目 B?.??closure(I)。(3)closure(I)僅包含上述兩條規(guī)則確定的僅包含上述兩條規(guī)則確定的 LR(0)項(xiàng)目。項(xiàng)目。項(xiàng)目閉包項(xiàng)目閉包：：轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)：：若若 I是文法是文法 G的一個(gè)的一個(gè) LR(0)項(xiàng)目集，項(xiàng)目集， X是是 G中的文法符號(hào)。中的文法符號(hào)。go(I,X)=closure(J)其中其中 J={A??X.?|A??.X??I}稱函數(shù)稱函數(shù) go(I,X)為轉(zhuǎn)移函數(shù)。為轉(zhuǎn)移函數(shù)。項(xiàng)目項(xiàng)目 A??X.?稱為項(xiàng)目稱為項(xiàng)目 A??.X?后繼。后繼。■構(gòu)造識(shí)別文法所有規(guī)范句型活前綴構(gòu)造識(shí)別文法所有規(guī)范句型活前綴 DFA的方法的方法Date 60信息學(xué)院 孫麗云第 4章 語(yǔ)法分析E’→EE’→EE→E+nE→E+nE→E+nE→E+nE→n E→n DFAE39?！鶨E→E+nE→nE→nE39?！鶨E→E+nE→E+nEn +n0 12 E→E+n 3 4■構(gòu)造識(shí)別文法所有規(guī)范句型活前綴構(gòu)造識(shí)別文法所有規(guī)范句型活前綴 DFA的方法的方法（ 1）求 closure({S’?.S})，得到初態(tài)項(xiàng)目集；，得到初態(tài)項(xiàng)目集；（（ 2）對(duì)初態(tài)項(xiàng)目集或其他已構(gòu)造的項(xiàng)目集，應(yīng)用狀）對(duì)初態(tài)項(xiàng)目集或其他已構(gòu)造的項(xiàng)目集，應(yīng)用狀態(tài)轉(zhuǎn)移函數(shù)態(tài)轉(zhuǎn)移函數(shù) GO(I,X)求出新的項(xiàng)目集；求出新的項(xiàng)目集；（（ 3）重復(fù)（）重復(fù)（ 2）直到不出現(xiàn)新的項(xiàng)目集為止；）直到不出現(xiàn)新的項(xiàng)目集為止；（（ 4）轉(zhuǎn)移函數(shù)）轉(zhuǎn)移函數(shù) GO建立狀態(tài)之間的連接關(guān)系。建立狀態(tài)之間的連接關(guān)系。Date 61信息學(xué)院 孫麗云第 4章 語(yǔ)法分析■構(gòu)造識(shí)別文法所有規(guī)范句型活前綴構(gòu)造識(shí)別文法所有規(guī)范句型活前綴 DFA的方法的方法課堂練習(xí)：課堂練習(xí)： 求文法求文法 G:S→( S)S|ε識(shí)別文法活前綴的識(shí)別文法活前綴的 DFA（ 1）拓廣文法并對(duì)每條規(guī)則編號(hào)；（ 2）求初始項(xiàng)目的項(xiàng)目閉包；（ 3）重復(fù)用狀態(tài)轉(zhuǎn)移函數(shù)求新的項(xiàng)目集，直到不產(chǎn)生新的項(xiàng)目集。S39。→SS→(S)SS→→ S→(S)SS→(S)SS→→ S→(S)SS→(S)SS→→ S39?！鶶S→(S)SS( )S((012S→(S)SS 34 5Date 62信息學(xué)院 孫麗云第 4章 語(yǔ)法分析■LR(0)分析表的構(gòu)造分析表的構(gòu)造若對(duì)于一個(gè)文法 G的拓廣文法 G’的 LR(0)項(xiàng)目集規(guī)范族中的每個(gè)項(xiàng)目集，不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目同時(shí)并存或多個(gè)歸約項(xiàng)目同時(shí)并存，則稱 G為 LR(0)文法。即 LR(0)文法中不能存在 移進(jìn)－歸約沖突 或者 歸約－歸約沖突 。E39?！鶨E→E+nE→nE→nE39?！鶨E→E+nE→E+nEn +n0 12 E→E+n 3 4根據(jù)右圖某文法識(shí)別活前綴的 DFA判斷該文法是否為L(zhǎng)R(0)文法Date 63信息學(xué)院 孫麗云第 4章 語(yǔ)法分析S39?！鶶S→(S)SS→→ S→(S)SS→(S)SS→→ S→(S)SS→(S)SS→→ S39?！鶶S→(S)SS( )S((012S→(S)SS 34 5根據(jù)下圖某文法識(shí)別活前綴的 DFA判斷該文法是否為 LR(0)文法Date 64信息學(xué)院 孫麗云第 4章 語(yǔ)法分析■LR(0)分析表的構(gòu)造分析表的構(gòu)造LR(0)分析表包含兩個(gè)子表： ACTION表 和 GOTO表假定 項(xiàng)目集規(guī)范族 C={I0,I1,…,I n}，令每個(gè)項(xiàng)目集 Ik的下標(biāo) k作為分析器的狀態(tài)，兩個(gè)子表的構(gòu)造過(guò)程如下：（ 1）若項(xiàng)目 A??.a?屬于 Ik且 GO(Ik,a)=Ij， a為終結(jié)符，則置 ACTION[k,a]為 ” sj” ；（ 2）若項(xiàng)目 A??.屬于 Ik，則對(duì)任何終結(jié)符 a（包括終結(jié)符 $），置 ACTION[k,a]為 ” rj” （注： j是產(chǎn)生式 A??的編號(hào)，而不是狀態(tài)集的狀態(tài)號(hào)）；（ 3）若項(xiàng)目 S’→S 屬于 Ik(S 表示整個(gè)句子已輸入并歸約結(jié)束 )，則置 ACTION[k,$]為 “ acc” ，表示接受。（ 4）若 GO[Ik,A]=Ij， A為非終結(jié)符，則置 GOTO[k,A]=j。（ 5）分析表凡不能用規(guī)則 (1)(4)填入的空白格均置為“ error” 。例： S?(S)|a狀態(tài)序號(hào) ACTION GOTO終結(jié)符和 $ 非終結(jié)符0……n分析表格式Date 65信息學(xué)院 孫麗云第 4章 語(yǔ)法分析例例 x：已知：已知 文法文法 G[S]， 求其求其 LR(0)的分析表。的分析表。S?aA|bBA?cA|dB?cB|dS??.cBB?.d解 :(1)識(shí)別文法活前綴的識(shí)別文法活前綴的 DFAA?d.A??.cAA?.dS?A?.cAA?.dB??.cBB?.dS??.SS?.aAS?.bBstartS??S.A?cA.S?aA.AddAcabSS?bB.B?cB.B?d.BddBccc01234567891011Date 66信息學(xué)院 孫麗云第 4章 語(yǔ)法分析狀態(tài)狀態(tài) actiongotoabcd$ SAB01234567891011s2s3accs5s6s8s9r1r1r1r1r1s5s6r4r4r4r4r4r2r2r2r2r2s8s9r6r6r6r6r6r3r3r3r3r3r5r5r5r5r51471011(2)LR(0)分析表分析表(1)識(shí)別文法活前綴的識(shí)別文法活前綴的 DFAA?d.A??.cAA?.dS?A?.cAA?.dS??.cBB?.dB??.cBB?.dS??.SS?.aAS?.bBstartS??S.A?cA.S?aA.AddAcabSS?bB.B?cB.B?d.BddBccc012367891011450S??S1S?aA2S?bB3A?cA4A?d5B?cB6B?dDate67信息學(xué)院 孫麗云第 4章 語(yǔ)法分析輸入：一個(gè)輸入串輸入：一個(gè)輸入串 w和文法和文法 G的一張的一張 LR分析表分析表 M。輸出：若輸出：若 w?L(G),輸出輸出 w的一個(gè)自底向上的分析；否則，輸出一個(gè)出的一個(gè)自底向上的分析；否則，輸出一個(gè)出錯(cuò)表示。錯(cuò)表示。方法：分別置放方法：分別置放 s0(初態(tài)初態(tài) )到棧中和到棧中和 w$（（ w為輸入串，為輸入串， $為界符）到輸入為界符）到輸入緩沖器中緩沖器中 。置置 ip指向指向 w$的第一個(gè)符號(hào)；的第一個(gè)符號(hào)；repeatforeverbegin令令 s是棧頂狀態(tài)且是棧頂狀態(tài)且 a是是 ip所指向的符號(hào)所指向的符號(hào)ifaction[s,a]=shifts?thenbegin將將 a和和 s?先后先后 壓入棧內(nèi)；壓入棧內(nèi)；使使 ip指向輸入串中的下一個(gè)符號(hào)；指向輸入串中的下一個(gè)符號(hào)；endelseifaction[s,a]=reduceA??thenbegin從棧頂彈出從棧頂彈出 2*|?|個(gè)符號(hào)；個(gè)符號(hào)；令令 s?是當(dāng)前是當(dāng)前 棧頂狀態(tài)；棧頂狀態(tài)；把把 A和和 goto[s?,A]先后入棧；先后入棧；輸出產(chǎn)生式輸出產(chǎn)生式 A??endelseifaction[s,a]=acceptthenreturnelseerror()end■LR(0)分析算法分析算法算法在教材 P79例：利用 LR(0)法分析上頁(yè)例 x中 acd是否是文法的句子。作業(yè)： P101并用 LR(0)方法分析a01是否為該文法的句子。Date 68信息學(xué)院 孫麗云第 4章 語(yǔ)法分析在進(jìn)行在進(jìn)行 LR語(yǔ)法分析過(guò)程中，可以發(fā)現(xiàn)當(dāng)前棧和輸入語(yǔ)法分析過(guò)程中，可以發(fā)現(xiàn)當(dāng)前棧和輸入串之間發(fā)生了間隔，在每種情況下，串之間發(fā)生了間隔，在每種情況下， 分析棧分析棧 的符號(hào)的符號(hào)序列被稱為右句型的序列被稱為右句型的 可行前綴（不含句柄之后的任可行前綴（不含句柄之后的任何符號(hào)）何符號(hào)） ?！鲇揖湫偷目尚星熬Y右句型的可行前綴 viableprefix（活前綴（活前綴 ））例例 x中，中， ε， a,ac,acA都是右句型都是右句型 acA的活前綴。的活前綴。Date 69信息學(xué)院 孫麗云第 4