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

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

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

4、般用一個四元式表示： G=(VT，VN，S，P)，其中VT：終結符集合(非空) VN：非終結符集合(非空)，且VT VN= S：文法的開始符號，SVN P：產生式集合(有限)。 （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型文法一定要牢記，不僅在概念題中有用，在下面的根據語言寫文法題中也有重要作用，

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

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

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

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

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

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

11、出(SdG)a的短語，直接（簡單）短語、句柄和最左素短語。分析：（1）推導和畫語法樹這些都很簡單，不再贅述。 （2）根據所畫出的語法樹，可以很快的找出短語，直接短語，句柄和最左素短語等，先講一個簡單子樹的概念，所謂簡單子樹是指僅具有單層分支的子樹。具體方法如下：短語：任一子樹的樹葉全體(具有共同祖先的葉節點符號串)皆為短語；直接短語：任一簡單子樹的樹葉全體(具有共同父親的葉節點符號串)皆為簡單短語；句柄：最左邊的直接短語；素短語：至少含有一個終結符的短語，并且除了自身外，不包含更小的素短語。 最左素短語：最左邊的素短語。答：（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對應文法SaS| a 如果是n=0則為SaS|(是空字)anbn | n0對應文法SaSb| ab下面這四道題目老是在試卷中重復出現，所以大家好好看看。考題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 用正規文法。ScA AaA|B BdC CbC|b(2)L2= 0na 1nbmcm| n0,m 0用二型文法。 SAB A0A1|0a1 BbBc|3、按指定的類型給出下列語言的文法（10 分）(1)L1= canbm| n0,m0 用正規文法。ScA AaA|B BbB|b(2)L2= 0na 1nbm| n0，m 0 用二型文法。SAB A0A1|0a1 BbB|4、按指定的類型給出下列語言的文法（10 分）(1) L1=anbmc|n=0,m0用正規文法SaS|A AbA|bB Bc(2)

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

15、制不再追溯。（2）注意優先級關系，閉包運算*最高，連接運算.次之，或運算|最低。 (3)考題1： 1）構造正則式a*b|(ab)*b對應的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是終態最小化DFA首先將集合分為A,B,D,F,G,C,E。A,B,D,G都有a,b作為條件輸出，F只有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 綜上所述：劃分的結果為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的狀態子集為DFA的終態,上例中的終態有B,C,E.題目中要求是確定化，沒有要求最小化，如若最小化，劃分的集合為S,A,B,CF,D,E然后再畫出最小化后的DFA這里不再贅述。考題3：構造奇數個0和奇數個1組成的自動機。（10分）狀態1：偶數個0 偶數個1 狀態2：奇數個0偶數個1狀態3：奇數個

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

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

19、TE E+TE | e TFT T *FT | e F(E) | i2)消除間接左遞歸這個請參見我期中整理的提綱篇幅較多，這里不再重復贅述，請參照下面的考題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)經分析發現文法GA并無直接左遞歸；(2)消除間接左遞歸：將A,B,C按照B,C,A排序（建議將A放在最后）由于出現CBg形式，將B代入C得：CdAg|Aeg

20、|fg|h又由于A出現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由于未在任何產生式的右部出現，所以是多余的。綜上所述:消除遞歸后的文法為：AdAaA|fa A|dAgb A |fgb A|hb A|c AAea A| egb A|e(4)LL(1)分析法1）含義：LL(1)分析方法（也叫預測分析法）：是指從左

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

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

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

24、終結符的First和Follow集合如下表所示非終結符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、所用產生式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)文法，若是請構造相應的LL(1)分析表，寫出aaabd的分析過程。SaH HaMd|d MAb|e AaM|e答：（1）可以判斷該文法無左遞歸。 （2）將文法分解為分解：SaH HaMd Hd MAb Me AaM Ae 求First和Follow集合非終結符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#的分析過程如下：步驟符號棧輸入串所用產生式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：構造LL(1)分析方法的總控流程圖6、構造遞歸下降識別程序這類題目首先看文法有無左遞歸和左公因子，有的話一定要消除，我期中給大家的答案錯了，考題1為更正后的答案。考題1：為文法GE： E V | V+E V N | NE N i構造遞歸下降識別程序（10分）解：（1）提取左公因子：EVE E +E|e

28、 V NV VE| e N i(3) 構造遞歸下降識別程序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構造遞歸下降識別程序解：（1）消除左遞

29、歸：ETE E+TE | e TFT T*FT | e F(E) | i (2)構造遞歸下降識別程序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）分析法注：自底向上分析法本質是從輸入串開始，逐步進行“歸約”，直到文法的開始符號,其關鍵問題是尋找句柄。自底向上分析法還有算符優先分析法，SLR(1),LR（1）等等，老師那天重點講了一道LR(0)分析法的題目，他說算符優先分析法A卷不考，但是補考的B卷會考，按照他的意思，這次期末考試LR(0)是考定的了，SLR(1),LR（1）應該不考，因為LR(0)分析法個人感覺也是所有題目中最繁的了，下面已老師講的題目為例這，也是一份試卷上的考題，首先介紹一些相關知識。（1） LR(0)項目：通俗點講，文法G中的任何一個產生式的右部的任何位置添

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

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

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

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

35、B （3）AcA （4） Ad （5）BcB （6）Bd分析：題中已經進行了推廣文法，所以第一步就不需要了，下面就是開始構造識別活前綴的DFA，然后構造出LR（0）分析表，最后在進行分析，實際上對于accd我們自己可以先推一下，EaAacAaccAaccd所以該句子符合文法，那么最終構造出的LR（0）分析表對該句子進行分析后必定得到“acc”（接受的意思），否則構造的LR(0)分析表出錯。答：（1）構造識別活前綴的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:注：實際上構造LR(0)分析表時這個圖沒有必要畫，根據上述計算結果即可填寫下表。（2）畫出LR(0)分析表注：至于怎么填這個表請參見上一頁中的PPT,這里不再贅述,Action表中si代表跳轉到第i個狀態，ri代表選擇文法中第i條規則進行歸約,acc代表接受，即分析成功。Goto表中數字i代表跳轉到第i個狀態。（3）對accd#進行分析步驟分析棧輸入串操作1#0accd#s22#0a2ccd#s53#0a2c5cd#s54#0a2c5c5d#s65#0a2c5c5d6#r46#0a2c5c5A10#r37#0a2c5A10#r38#0a2A4#r19#0E1#acc8、寫出表

38、達式或者程序的中間形式逆波蘭式和四元式是三地址代碼的兩種記錄表現形式，當然表示形式還有三元式、間接三元式等等，根據老師的意思應該不考，四元式和逆波蘭式必考。（1）逆波蘭表達式逆波蘭表達式即后綴表達式，就是中綴表達式（也就是我們一般看到的表達式形式）對應的后續遍歷結果，這個方法有很多，個人認為搞清楚運算優先級，觀察一下就可寫出，先算誰就將其對應的操作數寫出，運算符放在后面就行很簡單：例如：寫出下列各式的逆波蘭表示 （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）從左至右分別代表運算符，第一操作數，第二操作數,運算結果。如：A + B * ( C - D ) + E / ( C - D ) N 對應的四元式序列如下:四元式 : (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等等位存放結果的臨時變量。條件語句等四元式的表示（jnz , a ,- , p ) 表示 if

40、a goto p (jrop, x , y, p ) 表示 if x rop y goto p（rop代表關系運算符，如等等） (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、不能寫丟，否則一分沒有！上述四元式中第二第三個位置的“-”代表沒有元素。其實四元式就是對上述程序進行解釋，如果滿足則跳轉到哪里執行，不滿足則跳轉到哪里執行，大家自己分析一下，應該能夠看懂。考題：根據要求寫出下列表達式的中間形式。（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、參數傳遞這種題目很簡單，是送分題，一定要做對！參數傳遞方式分為三種，值傳遞，地址傳遞和傳名。值傳遞過程中形參值的改變不會影響實參值的改變，地址傳遞形參值的改變導致對應是實參值的改變，傳名傳遞類似于C語言中的宏展開，將實參原封不動的替換相應的形參（文字替換）。請看下題：(1) 高級語言程序中常用的參數傳遞方式有哪些？請根據這些傳遞方式寫出程序的運行結果。static int a=1;int p(int x,int y,i