1、編譯原理期末復(fù)習鑒于編譯原理馬上就要期末考試，我將手中集中的一些資料上的題目進行了整理歸類，每種類型題目給出了所涉及到的基本知識，然后對每類題目中的第一道例題進行了做法進行了講解，剩下的例題請給大家作為練習，答案也都給出，希望對大家復(fù)習有所幫助，最后由于時間很緊，整理的有些倉促，整理中難免有遺漏或錯誤，請大家見諒。注：下面出現(xiàn)的字母中，若無特別說明，小寫英文字母為終結(jié)符，大寫英文字母為非終結(jié)符，希臘字母為終結(jié)符與非終結(jié)符的任意組合。1、簡答題（或者名詞解釋）下面涉及到的概念中，加下劃線的都是在以往一些試卷中出現(xiàn)的原題，務(wù)必掌握。注：這類題目老師說答案不會超過一百個字，否則寫的再多也不給分，有些

2、點到即可，不要重復(fù)啰嗦。 （1）簡述編譯程序的概念及其構(gòu)成答：1）編譯程序：它特指把某種高級程序設(shè)計語言翻譯成等價的低級程序設(shè)計語言的翻譯程序。2)構(gòu)成： （2）簡述詞法分析階段的主要任務(wù)（也有可能問語法分析階段主要任務(wù)）答：詞法分析的任務(wù)是輸入源程序，對源程序進行掃描，識別其中的單詞符號，把字符串形式的源程序轉(zhuǎn)換成單詞符號形式的源程序。 語法分析的主要任務(wù)是對輸入的單詞符號進行語法分析（根據(jù)語法規(guī)則進行推導或者歸約），識別各類語法單位，判斷輸入是不是語法上正確的程序(3) 簡述編譯程序的構(gòu)造過程（這個大家看看，是對（1）和（2）的綜合）答：1）構(gòu)造詞法分析器：用于輸入源程序進行詞法分析，輸出

3、單詞符號； 2）構(gòu)造語法分析器：對輸入的單詞符號進行語法分析，識別各類語法單位，判斷輸入是不是語法上正確的程序3）構(gòu)造語義分析和中間代碼產(chǎn)生器：按照語義規(guī)則對已歸約出的語法單位進行語義分析并把它們翻譯成中間代碼。4）構(gòu)造優(yōu)化器：對中間代碼進行優(yōu)化。 5) 構(gòu)造目標代碼生成器：把中間的代碼翻譯成目標程序。6) 構(gòu)造表格管理程序：登記源程序的各類信息和編譯各階段的進展情況。7)構(gòu)造錯誤處理程序：對出錯進行處理。(4) 說明編譯和解釋的區(qū)別：1)編譯要程序產(chǎn)生目標程序，解釋程序是邊解釋邊執(zhí)行，不產(chǎn)生目標程序； 2)編譯程序運行效率高而解釋程序便于人機對話。（5） 文法：描述語言語法結(jié)構(gòu)的形式規(guī)則，一

4、般用一個四元式表示： G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空) VN：非終結(jié)符集合(非空)，且VT VN= S：文法的開始符號，SVN P：產(chǎn)生式集合(有限)。 （6）二義性文法：一個文法中存在某個句子，它有兩個不同的最左（或者最右推導），則稱該文法是二義性的。例子如文法G：Sif expr then S |other Sif expr then S else S 句子if e1 then if e2 then s1 else s2是二義性的。（7）文法的形式（注：文法的形式一定要牢記，特別是2型和3型文法一定要牢記，不僅在概念題中有用，在下面的根據(jù)語言寫文法題中也有重要作用，

5、如果所寫的文法形式不對，一切都是無用功）1）0型文法(短語文法，圖靈機)：產(chǎn)生式形式為：a b ，其中：a (VT VN)*且至少含有一個非終結(jié)符；b (VT VN)* 2）1型(上下文有關(guān)文法，線性界限自動機)：產(chǎn)生式形式為:a b 其中：|a| |b|，僅 Se 例外，但是S不得出現(xiàn)在任何產(chǎn)生式右部。3）2型文法（上下文無關(guān)文法，非確定下推自動機)：產(chǎn)生式形式為：Pa， PVN， a (VT VN)* 。4）3型文法(正規(guī)文法，有限自動機)：右線性文法：產(chǎn)生式形如：A aB 或 A a其中：a VT*；A，BVN 左線性文法：產(chǎn)生式形如：A Ba 或 A a 其中：a VT*；A，BVN

6、例題：設(shè)G=(VT，VN，S，P)是一個上下文無關(guān)文法，產(chǎn)生集合P中的任一個產(chǎn)生式應(yīng)具有什么樣的形式？若G是1型文法呢？若G是正則文法呢？上下文無關(guān)文法， 產(chǎn)生式形式為：Pa， PVN， a (VT VN)* 。1型文法：產(chǎn)生式形式為:a b 其中：|a| |b|，僅 Se 例外，但是S不得出現(xiàn)在任何產(chǎn)生式右部。正則文法：右線性文法：產(chǎn)生式形如：A aB 或 A a其中：a VT*；A，BVN 左線性文法：產(chǎn)生式形如：A Ba 或 A a 其中：a VT*；A，BVN (8)什么是PDA(下推自動機)? 答：PDA是下推自動機，PDA M用一個七元組表示(K,f,H,h0,S,Z)K: 有窮狀

7、態(tài)集 S：輸入字母表(有窮) H:下推棧符號的有窮字母表h0 :H中的初始符號 f: K （e) H K H* S：屬于K是初始狀態(tài)。Z:包含于K，是終結(jié)狀態(tài)集合。(9) 什么是DFA（有窮狀態(tài)自動機）?自動機M是一個五元式M=(S, S, f, S0, F),其中：1）S: 有窮狀態(tài)集， 2） S：輸入字母表(有窮)，3） f: 狀態(tài)轉(zhuǎn)換函數(shù)，為SSS的單值部分映射，f(s，a)=s表示：當現(xiàn)行狀態(tài)為s，輸入字符為a時，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s。我們把s稱為s的一個后繼狀態(tài)。4） S0S是唯一的一個初態(tài)； 5） FS ：終態(tài)集(可空)。（10）推導：所謂推導就是對于一個含非終結(jié)符A的符號串，利

8、用規(guī)則A，把A替換成得到新符號串的過程。 最左推導：在推導的每一步，選擇符號串最左邊的非終結(jié)符進行替換。 最右推導：在推導的每一步，選擇符號串最右邊的非終結(jié)符進行替換。(11)歸約：歸約是推倒的逆過程，即用產(chǎn)生式的左部非終結(jié)符替換右部符號串。(12)什么是句型？什么稱為句子？什么是語言？ 句型：從文法的起始符號出發(fā)，經(jīng)過有限步的推導能夠推導出來的符號稱為句型。 句子：只由終結(jié)符構(gòu)成的句型稱為句子。語言：所有句子的集合構(gòu)成該文法描述的語言。(13)什么是短語？什么是直接短語（也稱為簡單短語）？什么是句柄？什么是素短語？什么是最左素短語？（以下幾個概念一定要理解，考試中肯定會考哪些是短語，直接短語

9、，句柄等，具體方法請參見后面的）短語：如果存在某個文法非終結(jié)符P,滿足S P,并且P則稱為句型相對于非終結(jié)符P的短語。直接短語：如果P,即從P出發(fā)一步推出，則稱為直接短語。句柄：一個句型的最左直接短語稱為該句型的句柄。素短語：至少含有一個終結(jié)符的短語，并且除了自身外，不包含更小的素短語。最左素短語：句型中最左邊的素短語。（14）自頂向下的語法分析方法中需要解決的主要問題什么？如何表示？答：1）主要需要解決回溯和左遞歸問題。 2）表示方式，回溯：文法中存在形如A1|2|n ,即產(chǎn)生式右部存在多個候選，導致推導時不能確定到底應(yīng)該選擇哪個候選式。 左遞歸：文法中存在形如PP的形式，推導時會導致推導過

10、程無休止的進行下去。注：解決方法，對回溯采取的是提取左公因子，對左遞歸使消除左遞歸（包括直接左遞歸和間接左遞歸）。(15)內(nèi)情向量：一般編譯程序?qū)?shù)組說明的處理是把數(shù)組的有關(guān)信息匯集在一個叫做“內(nèi)情向量”或“信息向量”的表格中，以便以后計算數(shù)組元素的地址時引用這些信息。每個數(shù)組有一個內(nèi)情向量。其中的信息包括，數(shù)組的類型，維數(shù)，各維的上、下界，以及數(shù)組的首地址。（16） C語言的活動記錄：2、最左最右推導，畫語法樹，找短語、直接短語、句柄等。這種題目很簡單，送分題，一定不能丟分！考題：1）文法GS為：SSdT | T TTG | G G(S) | a試給出句型(SdG)a的推導過程及語法樹，并找

11、出(SdG)a的短語，直接（簡單）短語、句柄和最左素短語。分析：（1）推導和畫語法樹這些都很簡單，不再贅述。 （2）根據(jù)所畫出的語法樹，可以很快的找出短語，直接短語，句柄和最左素短語等，先講一個簡單子樹的概念，所謂簡單子樹是指僅具有單層分支的子樹。具體方法如下：短語：任一子樹的樹葉全體(具有共同祖先的葉節(jié)點符號串)皆為短語；直接短語：任一簡單子樹的樹葉全體(具有共同父親的葉節(jié)點符號串)皆為簡單短語；句柄：最左邊的直接短語；素短語：至少含有一個終結(jié)符的短語，并且除了自身外，不包含更小的素短語。 最左素短語：最左邊的素短語。答：（1）ST TG GG(S)G(SdT)G(SdG)G(SdG)a語法

12、樹：（2）短語：G，SdG, (SdG), a, (SdG)a 直接短語：G，a 句柄：G 最左素短：SdG注:還有一份試卷將句型改為adT(S)，與這個類似，大家自己做做，答案是短語：a,(S),T(S),adT0對應(yīng)文法SaS| a 如果是n=0則為SaS|(是空字)anbn | n0對應(yīng)文法SaSb| ab下面這四道題目老是在試卷中重復(fù)出現(xiàn)，所以大家好好看看。考題1、按指定類型給出下列語言的文法,并指出語言的類型。（10 分）(1)L1=anbmcn| n0,m0 二型文法：SaSc|B BbB|b(2) L2= 0na1nbmcm| n0，m 0 二型文法：SAB A0A1|0a1 B

13、bBc|2、按指定類型給出下列語言的文法。（10 分）(1)L1= candbm| n0,m0 用正規(guī)文法。ScA AaA|B BdC CbC|b(2)L2= 0na 1nbmcm| n0,m 0用二型文法。 SAB A0A1|0a1 BbBc|3、按指定的類型給出下列語言的文法（10 分）(1)L1= canbm| n0,m0 用正規(guī)文法。ScA AaA|B BbB|b(2)L2= 0na 1nbm| n0，m 0 用二型文法。SAB A0A1|0a1 BbB|4、按指定的類型給出下列語言的文法（10 分）(1) L1=anbmc|n=0,m0用正規(guī)文法SaS|A AbA|bB Bc(2)

14、L2=a0n1nbdm|n0,m0用二型文法SAB AaT T0T1|01 BbD DdD|d這是書P36 第11題的答案如下：大家作為練習，可以發(fā)現(xiàn)比上述題目簡單的多了。G4:S1S0|AA0A1|G3:SABAaAb|BaAb|G2:SABAaA|BbBc|bcG1:SACAaAb|abCcC|或者 G4:4、詞法分析正規(guī)式、NFA和DFA之間的轉(zhuǎn)化：（1）這類題目一般是三者之間的轉(zhuǎn)換，正規(guī)式NFA確定化的DFA最小化的DFA，有時已經(jīng)給出NFA了，則只需要確定化為DFA和最小化就行了，一般每一步都是五分。具體怎么轉(zhuǎn)換請參照我期中考試時整理的提綱，主要就是下面這幅關(guān)系對照圖，因時間和篇幅限

15、制不再追溯。（2）注意優(yōu)先級關(guān)系，閉包運算*最高，連接運算.次之，或運算|最低。 (3)考題1： 1）構(gòu)造正則式a*b|(ab)*b對應(yīng)的DFA。（15分） 畫出NFA 確定化DFAXIaIbX,1,2,3,41,2,5Y1,2,51,23,4,YY-1,21,2Y3,4,Y5Y5-3,43,45YXIaIbABCBDEC-DDCEFCF-GGFC注：C和E是終態(tài)最小化DFA首先將集合分為A,B,D,F,G,C,E。A,B,D,G都有a,b作為條件輸出，F(xiàn)只有b輸出，所以分為A,B,D,G和F 同理C,E分為C,E。A,B,Da=B,D Ga=F所以A,B,D,G分為A,B,D和G。Ab=C

16、B,Da=D所以分為A B,D 綜上所述：劃分的結(jié)果為A,B,D,C,E,G.考題2： 將NFA確定化為DFA(10分)abSABAACBECDEDFEFDENFA: DFA:IaIbX,0,1,30,2,1,33,Y0,2,1,30,2,1,31,3,Y3,YY1,3,Y2Y21,3Y1,32Y含有Y的狀態(tài)子集為DFA的終態(tài),上例中的終態(tài)有B,C,E.題目中要求是確定化，沒有要求最小化，如若最小化，劃分的集合為S,A,B,CF,D,E然后再畫出最小化后的DFA這里不再贅述。考題3：構(gòu)造奇數(shù)個0和奇數(shù)個1組成的自動機。（10分）狀態(tài)1：偶數(shù)個0 偶數(shù)個1 狀態(tài)2：奇數(shù)個0偶數(shù)個1狀態(tài)3：奇數(shù)個

17、0 奇數(shù)個1 狀態(tài)4：偶數(shù)個0奇數(shù)個1如果題目改成偶數(shù)個0，奇數(shù)個1，只要將狀態(tài)4轉(zhuǎn)換成終態(tài)即可，其他類似。5、語法分析自頂向下分析法（LL（1）分析法和遞歸向下構(gòu)造子程序法）注：自頂向下分析法本質(zhì)是由開始符號，按照產(chǎn)生式逐步推導看能否產(chǎn)生需要分析的句子。（1）自頂向下分析中存在的問題左遞歸和回溯（具體請參見簡答題中的第（14）題）（2）消除回溯提取公因子法提取公共左因子:假定關(guān)于A的規(guī)則 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm(其中，每個g 不以d開頭) 那么，可以把這些規(guī)則改寫成AdA | g 1 | g 2 | | g m Ab 1 | b 2

18、| | b n （3）消除左遞歸1)消除直接左遞歸：直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為PPa | b ，其中b不以P開頭。 我們可以把P的規(guī)則等價地改寫為如下的非直接左遞歸形式：PbP PaP|e 注：一般而言，假定P關(guān)于的全部產(chǎn)生式是PPa1 | Pa2 | | Pam | b1 | b2|bn 其中，每個a都不等于e，每個b都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： Pb1P | b2P | | bnP Pa1P | a2P | | amP | e 例：文法G(E):EET | T TT*F | F F(E) | i 經(jīng)消去直接左遞歸后變成： E

19、TE E+TE | e TFT T *FT | e F(E) | i2)消除間接左遞歸這個請參見我期中整理的提綱篇幅較多，這里不再重復(fù)贅述，請參照下面的考題2。考題1：將文法GS改寫為等價的GS,使得GS不含左遞歸和左公因子。SA AB|AS BaB|a答：消除左遞歸和左公因子后的文法為：SA A BA A S A| e BaB B B| e考題2：寫出文法GA: ABa|Cb|c BdA|Ae|f CBg|h消除左遞歸后的文法。答：(1)經(jīng)分析發(fā)現(xiàn)文法GA并無直接左遞歸；(2)消除間接左遞歸：將A,B,C按照B,C,A排序（建議將A放在最后）由于出現(xiàn)CBg形式，將B代入C得：CdAg|Aeg

20、|fg|h又由于A出現(xiàn)ABa ACb將B,C帶入A得到：AdAa|Aea|fa|dAgb|Aegb|fgb|hb|c等價于AAea|Aegb |dAa|fa|dAgb |fgb|hb|c將A消除直接左遞歸AdAaA|fa A|dAgb A |fgb A|hb A|c A Aea A| egb A|e此時，對于BdA|Ae|f，CdAg|Aeg|fg|h由于未在任何產(chǎn)生式的右部出現(xiàn)，所以是多余的。綜上所述:消除遞歸后的文法為：AdAaA|fa A|dAgb A |fgb A|hb A|c AAea A| egb A|e(4)LL(1)分析法1）含義：LL(1)分析方法（也叫預(yù)測分析法）：是指從左

21、到右掃描、最左推導(LL)和只查看一個當前符號（括號中的 1）。2）判斷一個文法是否是LL(1)文法的充要條件：1. 文法不含左遞歸，2. 對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若Aa 1|a 2|a n 則 FIRST(a i)FIRST(a j)f (ij)3. 對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含e，則FIRST(a i)FOLLOW(A)=f i=1,2,.,n如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。(5)LL(1)文法分析表的構(gòu)造與運用這類題目，主要就是判斷文法是否滿足LL(1)文法的三個充要條件，分為以下幾步：1）首先將

22、文法分解，判斷是否有左遞歸好，有的話肯定不是LL(1)文法；2）算非終結(jié)符的First集合和Follow集合，具體方法請參見期中考試的提綱，其實最本質(zhì)的要抓住first集合是Ua，F(xiàn)ollow集合石 Ua即可。3）算Select集合，書上沒有提到Select集合，計算Select集合實質(zhì)就是計算First(a)，當然考試時不一定非要寫成Select集合形式，可以直接計算First(a)來判斷交集是否為空，從而是否為LL(1)文法，請看考題1。4）至于判斷一個句子的分析過程，大家注意一下，所給的句子不一定是能通過該文法分析出來的，實際上在分析之前可以自己根據(jù)文法推推看，請看考題1.5）分析表中沒

23、有填的空格代表出錯，如果分析時遇到了代表該句子不符合該文法。考題1：判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表并分析句子aabe的分析過程。（15分）SaD DSTe| TbM MbH HM|分析：判斷一個文法是否為LL(1)文法是否為LL(1)文法，主要就是判斷是否滿足LL(1)文法的充要條件，有一個不滿足就不是LL(1)文法。對于aabe根據(jù)文法SaDaSTeaaDTeaaTeaabMe由于M不能為空字，所以最后肯定推不出來，也就是該句子不能由該文法推出，出錯。當然一般題目都是LL(1)文法，否則題目就不好往下做，沒有意義。答：(1)經(jīng)分析該文法無左遞歸；(2)非

24、終結(jié)符的First和Follow集合如下表所示非終結(jié)符XFirst(X)Follow(X)Sa# bD a# bTbe Mbe H be 將文法分解為：SaD DSte D TbM MbH HM H依次計算：First(aD)=a First(Ste)=aFollow(D)=# b First(bM)=bFirst(bH)=b First(M)=b Follow(H)= e First(Ste)Follow(D)= First(M)Follow(H)=該文法是LL(1)文法LL(1)分析表如下：abe#SSaDDDSTeDDTTbMMMbHHHMH(3)aabe的分析過程如下：步驟符號棧輸入串

25、所用產(chǎn)生式0#Saabe#1#Daaabe #SaD2#D abe#3#eTS abe#DSTe4#eTDa abe#5#eTD be#6#eT be#D7#eMb be#TbM8#eM e# 出錯考題2：判斷下面文法是不是LL(1)文法，若是請構(gòu)造相應(yīng)的LL(1)分析表，寫出aaabd的分析過程。SaH HaMd|d MAb|e AaM|e答：（1）可以判斷該文法無左遞歸。 （2）將文法分解為分解：SaH HaMd Hd MAb Me AaM Ae 求First和Follow集合非終結(jié)符XFirst(X)Follow(X)Sa#Ha,d#Me, a,ed,bAa,eb求Select集合Sel

26、ect(SaH)=First(aH)=a Select(HaMd)=First(aMd)=a Select(Hd)=d Select(MAb)=First(Ab)=a,e Select(Me)=First(e)UFollow(M)= Follow(M)=d,b Select(AaM)=FirstaM=a Select(Ae)=First(e)=eSelect(HaMd) Select(Hd)= Select(MAb) Select(Me)= Select(AaM) Select(Ae)= 該文法是LL(1)文法。（3）LL(1)分析表如下：adbeSSaHHHaMdHdMMAbMeMeMAbA

27、AaMAeaaabd#的分析過程如下：步驟符號棧輸入串所用產(chǎn)生式0#Saaabd#1#Haaaabd #SaH2#H aabd#3#dMa aabd#HaMd4#dM abd#5#dbA abd#MAb6#dbMa abd#AaM7#dbM bd#8#db bd#Me9#d d#10# #考題3：構(gòu)造LL(1)分析方法的總控流程圖6、構(gòu)造遞歸下降識別程序這類題目首先看文法有無左遞歸和左公因子，有的話一定要消除，我期中給大家的答案錯了，考題1為更正后的答案。考題1：為文法GE： E V | V+E V N | NE N i構(gòu)造遞歸下降識別程序（10分）解：（1）提取左公因子：EVE E +E|e

28、 V NV VE| e N i(3) 構(gòu)造遞歸下降識別程序PROCEDURE E；BEGIN V; EEND;PROCEDURE E；IF SYM=+ THEN BEGINADVANCE； EENDPROCEDURE ；BEGIN N;VEND;PROCEDURE F；IF SYM= THEN BEGINADVANCE;E；IF SYM= THEN ADVANCEELSE ERROREND ELSE ERROR;PROCEDURE N；IF SYM=i THEN ADVANCEELSEERROR;考題2：為文法GE:EE+T|T TT*F|F F(E)|i構(gòu)造遞歸下降識別程序解：（1）消除左遞

29、歸：ETE E+TE | e TFT T*FT | e F(E) | i (2)構(gòu)造遞歸下降識別程序PROCEDURE E；BEGIN T；E END；PROCEDURE T；BEGIN F；T ENDPROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THENBEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR ENDELSE ERROR;PROCEDURE E； IF SYM=+ THEN BEGINADVANCE； T；E ENDPROCEDURE T； IF SYM=* THEN BEGIN

30、ADVANCE； F；T END7、自底向上分析法LR（0）分析法注：自底向上分析法本質(zhì)是從輸入串開始，逐步進行“歸約”，直到文法的開始符號,其關(guān)鍵問題是尋找句柄。自底向上分析法還有算符優(yōu)先分析法，SLR(1),LR（1）等等，老師那天重點講了一道LR(0)分析法的題目，他說算符優(yōu)先分析法A卷不考，但是補考的B卷會考，按照他的意思，這次期末考試LR(0)是考定的了，SLR(1),LR（1）應(yīng)該不考，因為LR(0)分析法個人感覺也是所有題目中最繁的了，下面已老師講的題目為例這，也是一份試卷上的考題，首先介紹一些相關(guān)知識。（1） LR(0)項目：通俗點講，文法G中的任何一個產(chǎn)生式的右部的任何位置添

31、加一個圓點就成了LR(0)項目，比如AAb是產(chǎn)生式，則AAb AAb AAb都是該產(chǎn)生式對應(yīng)的全部項目。項目動態(tài)的表示歸約的一個階段：對于項目AAb，可以這樣理解它：“”之前的A表示的是在識別Ab過程中已輸入到棧終的部分；“”之后的表示在識別Ab過程中期望出現(xiàn)的部分；“”表示則是在識別Ab過程中當前的識別進度的定位。項目AAb已經(jīng)具備了識別Ab的一切條件，因此被稱為歸約項目。項目可以分為以下四類：Pa稱為移進項目其中, PX稱為待約項目，其中X為非終結(jié)符，P 稱為歸約項目，S S稱為接收項目（2）LR(0)的分析棧可以看成兩部分狀態(tài)棧 LR分析器的核心是一張分析表：ACTIONs，a：當狀態(tài)s

32、面臨輸入符號a時，應(yīng)采取什么動作.GOTOs，X：狀態(tài)s面對文法符號X時，下一狀態(tài)是什么.下面幾張PPT大家看看，對基本概念有個印象：這一章的概念較多較抽象，我一時半會也講不完講不清楚，這里不再贅述，直接看題目，知道怎么做就行，下面以一道考題這也是老師講的原題為例講解如何做這類題目，首先一般這種題目分三步走：(1)拓廣文法：假定文法G是一個以S為開始符號的文法，我們構(gòu)造一個G，它包含了整個G，但它引進了一個不出現(xiàn)在G中的非終結(jié)符S，并加進一個新產(chǎn)生式SS，而這個S是G的開始符號。那么，我們稱G是G的拓廣文法。這樣，便會有一個僅含項目SS.的狀態(tài)，這就是唯一的“接受”態(tài)。（2）構(gòu)造識別文法活前綴

33、的DFA:對于任意的項目即I,其閉包CLOSURE(I)計算方法如下，I中的所有項目都屬于CLOSURE(I);如果PX,并且X為非終結(jié)符，則所有形如X的項目也屬于ClOSURE(I)定義函數(shù)GO(I,X)，其中I是項目集，X是任意的文法符號（終結(jié)符，非終結(jié)符都可以），GO(I，X)=CLOSURE(J).J是從I中項目出發(fā)后讀取X后到達的后繼項目,即J=PX| PXI 有了上述CLOSURE和GO的定以后，從CLOSURE(SS)出發(fā)，利用GO函數(shù)，產(chǎn)生出它在每個可能的文法符號下，要轉(zhuǎn)移的項目集，再對新產(chǎn)生的項目集采取同樣的方法直到?jīng)]有新產(chǎn)生的項目集未被處理為止。(4) 根據(jù)計算出的項目集之

34、間的關(guān)系畫出DFA和LR(0)分析表，其中LR(0)構(gòu)造方法如下:(5) 對具體的句子運用LR(0)分析的方法如下：每一項ACTIONs，a所規(guī)定的四種動作:1. 移進 把(s，a)的下一狀態(tài)s和輸入符號a推進棧，下一輸入符號變成現(xiàn)行輸入符號.2. 歸約 指用某產(chǎn)生式A進行歸約. 假若的長度為r， 歸約動作是， 去除棧頂r個項，使狀態(tài)sm-r變成棧頂狀態(tài)，然后把(sm-r, A)的下一狀態(tài)s=GOTOsm-r, A和文法符號A推進棧.3. 接受（即acc） 宣布分析成功，停止分析器工作.4. 報錯考題：構(gòu)造文法GE的LR(0)分析表，并給出accd的分析過程。（0）SE（1）EaA （2）Eb

35、B （3）AcA （4） Ad （5）BcB （6）Bd分析：題中已經(jīng)進行了推廣文法，所以第一步就不需要了，下面就是開始構(gòu)造識別活前綴的DFA，然后構(gòu)造出LR（0）分析表，最后在進行分析，實際上對于accd我們自己可以先推一下，EaAacAaccAaccd所以該句子符合文法，那么最終構(gòu)造出的LR（0）分析表對該句子進行分析后必定得到“acc”（接受的意思），否則構(gòu)造的LR(0)分析表出錯。答：（1）構(gòu)造識別活前綴的DFA:I0=Closure(SE )= SE, EaA, EbB I1=GO(I0,E)=Closure(SE)= SE I2=GO(I0,a)=Closure( EaA )= E

36、aA，AcA ，Ad I3=GO(I0,b)=Closure( EbB )=EbB, BcB ，Bd （為了方便，下面計算中的Closure不再寫了，直接給出答案,考試時可以不寫，當然計算I0是必須要的）I4=GO(I2,A)= EaA I5=GO(I2,c)= AcA，AcA ，Ad I6= GO(I2,d)= Ad I7=GO(I3,B)= EbBI8= GO(I3,c)= BcB，BcB ，Bd I9= GO(I3,d)= BdI10= GO(I5,A) = AcA GO(I5,c)=I5 GO(I5.d)=I6I11= GO(I8,B) BcB GO(I8,c)=I8 GO(I8.d)

37、=I9畫出DFA:注：實際上構(gòu)造LR(0)分析表時這個圖沒有必要畫，根據(jù)上述計算結(jié)果即可填寫下表。（2）畫出LR(0)分析表注：至于怎么填這個表請參見上一頁中的PPT,這里不再贅述,Action表中si代表跳轉(zhuǎn)到第i個狀態(tài)，ri代表選擇文法中第i條規(guī)則進行歸約,acc代表接受，即分析成功。Goto表中數(shù)字i代表跳轉(zhuǎn)到第i個狀態(tài)。（3）對accd#進行分析步驟分析棧輸入串操作1#0accd#s22#0a2ccd#s53#0a2c5cd#s54#0a2c5c5d#s65#0a2c5c5d6#r46#0a2c5c5A10#r37#0a2c5A10#r38#0a2A4#r19#0E1#acc8、寫出表

38、達式或者程序的中間形式逆波蘭式和四元式是三地址代碼的兩種記錄表現(xiàn)形式，當然表示形式還有三元式、間接三元式等等，根據(jù)老師的意思應(yīng)該不考，四元式和逆波蘭式必考。（1）逆波蘭表達式逆波蘭表達式即后綴表達式，就是中綴表達式（也就是我們一般看到的表達式形式）對應(yīng)的后續(xù)遍歷結(jié)果，這個方法有很多，個人認為搞清楚運算優(yōu)先級，觀察一下就可寫出，先算誰就將其對應(yīng)的操作數(shù)寫出，運算符放在后面就行很簡單：例如：寫出下列各式的逆波蘭表示 （1） -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F 解： （1） abc*cd-/ba*+ - （2） ABCDE/*F/+ 注：代表負號“-

39、”（2）四元式四元式形式如下（op,arg1,arg2,Result）從左至右分別代表運算符，第一操作數(shù)，第二操作數(shù),運算結(jié)果。如：A + B * ( C - D ) + E / ( C - D ) N 對應(yīng)的四元式序列如下:四元式 : (1) ( - ,C ,D,T1 ) (2) ( * ,B,T1,T2) (3) ( + ,A,T2,T3) (4) ( - ,C,D,T4)(5) ( ,T4,N,T5) (6)( / ,E ,T5,T6) (7) ( + ,T3 ,T6 ,T7) 注：T1,T2等等位存放結(jié)果的臨時變量。條件語句等四元式的表示（jnz , a ,- , p ) 表示 if

40、a goto p (jrop, x , y, p ) 表示 if x rop y goto p（rop代表關(guān)系運算符，如等等） (j , -, - , p ) 表示 goto p 例如：寫出條件語句 IF a0 THEN x:=x+1 ELSE x:=4*( x- 1) 四元式序列 解： (1)( j , a ,0 ,(3)(2)( j , -, -,(6)(3)(+,x , 1 , T1)(4)( := , T1,-, T2 )(5)(j ,-, -,(9)(6)( -, x,1, T3)(7) (*, 4 ,T3 ,T4 )(8) ( := , T4 ,-,x)(9) 注意：（5）和（9）

41、不能寫丟，否則一分沒有！上述四元式中第二第三個位置的“-”代表沒有元素。其實四元式就是對上述程序進行解釋，如果滿足則跳轉(zhuǎn)到哪里執(zhí)行，不滿足則跳轉(zhuǎn)到哪里執(zhí)行，大家自己分析一下，應(yīng)該能夠看懂。考題：根據(jù)要求寫出下列表達式的中間形式。（1）5+6*（a+b）寫出表達式的逆波蘭式 逆波蘭表達式為：56ab+*+（2）答案（1）答案（2）if x y then y:=y-1;x：=y*z+10else x:= z + y寫出上述代碼的四元式或者三址碼。（有的試卷上問法是寫出下列表達式三地址形式的中間表示，答案一樣）(0)(j,x,y,(2)(1)(j,-,-,(8)(2)(-,y,1,T1)(3)(:=

42、,T1,-,y)(4)(*,y,z,T2)(5)(+,T2,10,T3)(6)( :=,T3,-,x)(7)(j,-,-,(10)(8)(+,z,y,T4)(9)( :=,T4,-,x)(10)100:if xy goto 102101:goto 108102:T1:=y-1103:y:=T1104: T2:=y*z105: T3:=T2+10106: x:=T3107: goto 110108: T4:=z+y109: x:=T4110:注意：同上題，本題答案加紅色的部分此外上述編號隨意，從0開始也行從100開始也行。不能丟，否則一分沒有！ 9、參數(shù)傳遞這種題目很簡單，是送分題，一定要做對！參數(shù)傳遞方式分為三種，值傳遞，地址傳遞和傳名。值傳遞過程中形參值的改變不會影響實參值的改變，地址傳遞形參值的改變導致對應(yīng)是實參值的改變，傳名傳遞類似于C語言中的宏展開，將實參原封不動的替換相應(yīng)的形參（文字替換）。請看下題：(1) 高級語言程序中常用的參數(shù)傳遞方式有哪些？請根據(jù)這些傳遞方式寫出程序的運行結(jié)果。static int a=1;int p(int x,int y,i