編譯原理實驗課程教案

1、實驗課程教案課程名稱編譯原理課程屬性專業(yè)基礎(chǔ)開課學(xué)年開課學(xué)期年級專業(yè)主講教師課程所屬院系部計算機科學(xué)與技術(shù)學(xué)院課程所屬系（教研室）實驗一名稱ChomskyN.Chomsky1956年，N.ChomskyN.Chomsky定種類的自動機那樣的識別器聯(lián)系起來。,Chomsky0型文法（短語文法）u:=v其中u口M,v口V*,定種類的自動機那樣的識別器聯(lián)系起來。,Chomsky0型文法（短語文法）u:=v其中u口M,v口V*,則稱該文法0G為0,0對計算機PSG。L0。這種,任何1型文法因此0,Turning）來識別。故0（上下文有關(guān)文法）xUy:=xuyx,y口V*,則稱該文法x,y口V*,則稱該

2、文法1,1,1u替換CSG。U和右部的uU,必須在前面有x和后面有x和下文y,利用該規(guī)y,1型語言L1,12型文法（上下文無關(guān)文法）U:=u其中U口VN；u口M,則稱該文法G為2,為CFG。按照這條規(guī)則，對于上下文無關(guān)文法，利用該規(guī)則進行推導(dǎo)時，無需考慮非終結(jié)符U所在的上下文，總能用u替換U，或者將u歸約為U，顯示了上下文無關(guān)的特點。2型文法所確定的語言為2型語言L2，2型語言可由非確定的下推自動機來識別。一般定義程序設(shè)計語言的文法是上下文無關(guān)的。如C語言便是如此。因此，上下文無關(guān)文法及相應(yīng)語言引起了人們較大的興趣與重視。3型文法(正則文法，線性文法)如果對于某文法G，P中的每個規(guī)則具有下列形

3、式：U:=T或U:=WT其中TVt；U,WVn，則稱該文法G為左線性文法。如果對于某文法G,P中的每個規(guī)則具有下列形式：U:=T或U:=TW其中TVt；U,WVN，則稱該文法G為右線性文法。左線性文法和右線性文法通稱為3型文法或正則文法，有時又稱為有窮狀態(tài)文法，簡寫為RG。按照定義，對于正則文法應(yīng)用規(guī)則時，單個非終結(jié)符號只能被替換為單個終結(jié)符號，或被替換為單個非終結(jié)符號加上單個終結(jié)符號，或者被替換為單個終結(jié)符號加上單個非終結(jié)符號。3型文法所確定的語言為3型語言L3,3型語言可由確定的有窮狀態(tài)自動機來識別。在常見的程序設(shè)計語言中，多數(shù)與詞法有關(guān)的文法屬于3型文法。可以看出，上述4類文法，從0型到

4、3型，產(chǎn)生式限制越來越強，其后一類都是前一類的子集，而描述語言的功能越來越弱，四類文法及其表示的語言之間的關(guān)系可表示為：0型1型2型3型；即L0L1L2L3四、注意事項文法的輸入應(yīng)簡便。指明是哪一類Chomsky文法，并給出相應(yīng)的四元組形式：G=(VN,VT,P,S)。說明：簡單起見，可以不考慮0型文法類。實驗二名稱名稱,:1）給定一個文法，就能從結(jié)構(gòu)上惟一地確定其語言，即GLG）2）給出文法后，語言也就相應(yīng)地確定了，其語言可以是有窮的，也可以是無限的。：3U:=T其中U:=T其中T口VT；U:=T其中T口VT；G,P：或U:=WTU,W口VN，則稱該文法G,P：或U:=TWU,W口VN，則稱

5、該文法G,RG。按照定義，,結(jié)符號，,33型語言來識別。,描述如下：:=/,:,易；,4),例如，文獻目錄檢索系統(tǒng)以及正文編輯程序等。正則表達式和正則集：和都是,和,其中是空口，是空集；(2)任意的a,a；(3)如果e1和e2是,Lej和L(e2),則：e1/e2,口e1/e2)口e1)口e2)。e1e2,L(e1e2)口L(e1)L(e2)。(e1)*,L(e1)*)口L(e1)*。(1)和(2)定義了原子正則表達式，而(3)則表明字母表上的正正則表達式的性質(zhì)e1和e2,eje2。正則表達式與正則文法的關(guān)系,除了符號外,n為止。存在產(chǎn)生式。FOLLOW集合a口a口VT。GS的所有句型中，緊跟

6、在非FOLLOW設(shè)文法GSD(VN,VT，P,S),則FOLLOW(A)口aISAa*A,#FOLLOW(A)。,FOLLOW!A)是指在文法終結(jié)符AFOLLOW：1)對于文法GS的開始符號S,有#FOLLOW(S)；2)若文法GS中有形如B口xAy,x,y口V*，則FIRST(y)FOLLOW(A)；若文法GS中有形如B口xA,B口xAy的規(guī)則且FIRST(y),其中x,y口V*，則FOLLOW(B)口FOLLOW(A)；.計算每個產(chǎn)生式A口a的SELECT(A口a)集按定義計算SELECT(A口a)：(1)若a永遠推導(dǎo)不出，則SELECT(ADa)=FIRST(a)(2)0a可能推導(dǎo)出，則

7、SELECT(A口a)=(FIRST(a)-)口FOLLOW(A).一個上下文無關(guān)文法G是LL文法，當且僅當對G中每個非終結(jié)符A的任何兩個不同的規(guī)則A口aIB，滿足SELECT(A口a州SELECT(AD0)=0，其中a口000000一個能推出口。微機()能處理含；first集合、followLL1),：非終結(jié)符firstfollow判定結(jié)論實驗六名稱自動生成LR(0)分析表LR(K)分析方法是1965年Knuth,L,R,KLRK)“移進-歸K(Kb0)個符號，就能惟,-,柄。LR串的KK口0)符號就可惟一地確定分析器的動作是移進還是歸口以及用哪,LR,LRLR,符號這3,LR,因此，“歷史

8、”,，但是，,LRLL,也就是說，LR,LR,LR,LR,：LR(0)分析表。對于LR,LRLR分析表，我們需要定義一個重要概念一一文法的規(guī)范句型“活前綴”。這種句柄之后不含任何符號的前綴稱為活前綴。在LR分析工作過程中的任何時候，棧里的文法符號(自棧底而上)X1X2X應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型(如果整個輸入串確實構(gòu)成一個句子)。因此，只要輸入串的已掃描部分保持可歸約成一個活前綴，那就意味著所掃描過的部分沒有錯誤。對于一個文法G,我們可以構(gòu)造一個有窮自動機，它能識別G的所有活前綴，然后把這個自動機轉(zhuǎn)變成LR分析表，按照該LR分析表進行LR分析，就能保證在分析的過

9、程中，如果分析的句子是正確的，棧里的文法符號(自棧底而上)始終構(gòu)成活前綴。假若一個文法G的拓廣文法的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下述情況：(1)既含移進項目又含歸約項目；(2)含有多個歸約項目，則稱G是一個LR(0)文法。該自動機的狀態(tài)集合即為該文法的LR(0)項目集規(guī)范族。構(gòu)造識別文法活前綴DFA有3種方法：(1)根據(jù)形式定義求出活前綴的正則表達式，然后由此正則表達式構(gòu)造NFA再確定為DFA；(2)求出文法的所有項目，按一定規(guī)則構(gòu)造識別活前綴的NFA再確定化為DFA；(3)使用閉包函數(shù)(CLOSURE)和轉(zhuǎn)向函數(shù)90(1不)構(gòu)造文法fiLR(0)的項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建

10、立狀態(tài)之間的連接關(guān)系來得到識別活前綴的DFA。符號串的前綴是指該符號串的任意首部，包括空串。例如，對于符號串a(chǎn)bc,其前綴有,a,ab,abc。如果輸入串沒有錯誤的話，一個規(guī)范句型的活前綴是該句型的一個前綴，但它不含句柄之后的任何符號。之所以稱為活前綴，是因為在該前綴后聯(lián)接尚未輸入的符號串可以構(gòu)成一個規(guī)范句型?；钋熬Y與句柄的關(guān)系如下：(1)活前綴已含有句柄的全部符號，表明產(chǎn)生式A-P的右部B已出現(xiàn)在棧頂。(2)活前綴只含句柄的一部分符號，表明AB涓2的右部子串B1已出現(xiàn)在棧頂，期待從輸入串中看到B2推出的符號。(3)活前綴不含有句柄的任何符號，此時期望A-B的右部所推出的符號串。在文法G的每個

11、產(chǎn)生式的右部(候選式)的任何位置上添加一個圓點，所構(gòu)成的每個產(chǎn)生式稱為LR(0)項目。如產(chǎn)生式A-xyz有如下項目：A-.xyz,Ax.yz,A-xy.z,A-xyz.。為刻劃分析過程中的文法的每一個產(chǎn)生式的右部符號已有多大一部分被識別(出現(xiàn)在棧頂)，可以用這種標有圓點的產(chǎn)生式來確定。A-B.刻劃產(chǎn)生式A-B的右部B已出現(xiàn)在棧頂。A-B1.B2刻劃A-B1B2的右部子串B1已出現(xiàn)在棧頂，期待從輸入串中看到B2推出的符號。A-.B刻劃沒有句柄的任何符號在棧頂，此時期望A-B的右部所推出的符號串。(4)對于Af的匕口(0)項目只有Af.。設(shè)文法G=(VT,VN,S,P)是一個上下文無關(guān)文法，若存在

12、一個規(guī)范推導(dǎo)S*BwHICw(其中AH1IRBP),則稱項目八B1時對活前綴=是有rmrm效的，即LR(0)有效項目。從直觀意義上講，一個匕口(0)項目指明了在分析過程中的某一步我們看到產(chǎn)生式的多大部分被識別，匕口(0)項目中的圓點可看成是分析棧棧頂與輸入串的分界線，圓點左邊為已進入分析棧的部分，右邊是當前輸入或繼續(xù)掃描的符號串。不同的匕口(0)項目，反映了分析棧頂?shù)牟煌闆r。我們根據(jù)匕口(0)項目的作用不同，將其分為四類：(1)歸約項目：表現(xiàn)形式：Afa.這類匕口(0)項目表示句柄a恰好包含在棧中，即當前棧頂?shù)牟糠謨?nèi)容構(gòu)成了所期望的句柄，應(yīng)按Afa進行歸約。(2)接受項目：表現(xiàn)形式：Sfa.

13、其中S是文法惟一的開始符號。這類匕口(0)項目實際是特殊的歸約項目，表示分析棧中內(nèi)容恰好為a,用Sfa進行歸約，則整個分析成功。(3)移進項目：表現(xiàn)形式：Afa.b(bVT)這類匕口(0)項目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句柄的活前級，需將b移進分析棧。(4)待約項目：表現(xiàn)形式：Afa.Bp(BVN)這類匕口(0)項目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句柄的活前綴，應(yīng)把當前輸入字符串中的相應(yīng)內(nèi)容先歸約到B。在給出匕口(0)項目的定義和分類之后，我們從這些匕口(0)項目出發(fā)，來構(gòu)造能識別文法所有前綴的有窮自動機。其步驟是：首先構(gòu)造能識別文法所有活前綴的非確定的

14、有窮自動機，再將其確定化和最小化，最終得到所需的確定的有窮自動機。由文法G的LR(0)項目構(gòu)造識別文法G的所有活前綴的非確定有窮自動機的方法：(1)規(guī)定含有文法開始符號的產(chǎn)生式(設(shè)SAA)的第一個匕口(0)項目(即SA.A)為NFA的惟一初態(tài)。(2)令所有匕口(0)項目分別對應(yīng)NFA的一個狀態(tài)且匕口(0)項目為歸約項目的對應(yīng)狀態(tài)為終態(tài)。(3)若狀態(tài)i和狀態(tài)j出自同一文法G的產(chǎn)生式且兩個狀態(tài)匕口(0)項目的圓點只相差一個位置，即：若i為XfX1X2Xi-1XiXn，j為XfXiX2XiXi+iXn，則從狀態(tài)i引一條標記為X.的弧到狀態(tài)j。(4)若狀態(tài)i為待約項目(設(shè)XfaAP)，則從狀態(tài)i引弧到

15、所有Afr的狀態(tài)。GGGG它包含了整假定文法G是一個以S,個G,但它引進了一個不出現(xiàn)在GS,SS,以SSG開始符號。那么，我們稱GG,SS,CLOSURE(I)如下:B口.項目也屬于如果I是文法GCLOSURE(I)如下:B口.項目也屬于1)I的項目都在CLOSURE中。2)若A口B于CLOSURE(I),則每一形如CLOSURE(I)。(3)2)直到CLOSURE(I)不再擴大。：GO(I,X)=CLOSURE(J)其中：I為包含某一項目集的狀態(tài)，X為一文法符號，J=A口HX.IA口HXmI。,S口口.S,因此用GOTO(I,X)狀態(tài)轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)閉口項目集的核。(CLOSUR

16、E)和轉(zhuǎn)換函數(shù)(GO(I,X)構(gòu)造文法G的LR(0)的項,：置項目S口.S,CLOSURE(S.S)得到初態(tài)的閉口項目集。對初態(tài)集或其他所應(yīng)用轉(zhuǎn)換函數(shù)GO(I,X)=CLOSURED出口狀態(tài)J的閉口項目集。(3)(2)直到不出現(xiàn)新的項目集為止。計算LR(0)項目集規(guī)范族C=I0，I1,.In：roedreiteet(G);BeinC=CLOSURE(S.S)RepeatForCI和每一文法符號XDoifGO(I,X)CThen把GO(I,X)放入CDUntilC不再增大End;,則稱移進-歸約,-子：DFA建立LR,究這個DFA()ADP1p2對口前綴aP1,S*.,(12)是有效的，則它告訴

17、我們應(yīng)把符號串)是有效的，則它告訴我們應(yīng)把符號串1若移進項目ADP1.P2對口前綴歸約為A,1是有效的，則它告訴我們,句柄尚未形成,ADP1.對口前綴變成aA。1因此，下一步動作應(yīng)是移進。但是，可能存在這樣的情形，對同一活前綴，存在若干項目對它都是有效的。而且它們告訴我們應(yīng)做的事情各不相同，互相沖突。這種沖突通過向前多看幾個輸入符號，或許能夠獲得解決。對于每個活前綴，我們可以構(gòu)造它的有效項目集。實際上，一個活前綴Y的有效項目集正是從上述的DFA的初態(tài)出發(fā)，經(jīng)讀出Y后而到達的那個項目集（狀態(tài)）。換言之，在任何時候，分析棧中的活前綴X1X2X的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。這是LR分

18、析理論的一條基本定理。實際上，棧頂?shù)捻椖考顟B(tài)）體現(xiàn)了棧里的一切有用信息一歷史。前面我們已經(jīng)對LR（0）文法進行了定義，下面我們來看一下LR（0）分析表是如何構(gòu)造的。對于LR（0）文法，我們可以直接從它的項目集規(guī)范族C和活前綴識別自動機的狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出LR分析表。下面是構(gòu)造LR（0）分析表的算法。假定C=I0,I1,，In，令每個項目集人的下標k為分析器的一個狀態(tài)，因此，G的LR（0）分析表含有狀態(tài)0，1，n。令那個含有項目Sf.S的1k的下標k為初態(tài)。ACTION子表和GOTO子表可按如下方法構(gòu)造：（1）若項目Afa.ap屬于Ik且GO（Ik,a）=Ij,a為終結(jié)符，則置ACTIONk,a為“把狀態(tài)j和符號a移進?！保営洖椤皊j”；（2）若項目A-。.屬于Ik，那么，對任何終結(jié)徐，置ACTIONk，a為“用產(chǎn)生式Afa進行規(guī)約”，簡記為“r”；其中，假定A-a為文法G的第j個產(chǎn)jJ生式；（3）若項fS.屬于Ik,則置ACTIONk,#為“接受”，簡記為“acc”；（4）若GO（Ik,A）=Ij,A為非終結(jié)符，則置GOTOk,A=j；（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出錯標志”。按上述算法構(gòu)造的含有ACTION和G