1、第一章一填空題1編譯程序的工作過程一般可以劃分為詞法分析、語法分析、語義分析與中間代碼產生、優化和生成目標程序等幾個基本階段，同時還伴有符號表管理和出錯處理。2若源程序是用高級語言編寫的，目標程序是匯編或機器語言，則其翻譯程序稱為編譯程序。3編譯方式與解釋方式的根本區別在于運行目標程序時的控制權在解釋器而不是目標程序。4翻譯程序是這樣一種程序，它能將用甲種語言書寫的程序轉換成與其等價的乙種語言書寫的程序。5對編譯程序而言，輸入數據是高級語言（源）程序，輸出結果是低級語言（目標）程序。6運行編譯程序的計算機稱宿主機，運行編譯程序所產生目標代碼的計算機稱目標機。7當把編譯程序劃分成編譯前端和編譯后

2、端時，前端主要由與源語言有關但與目標機無關的部分組成，編譯后端包括編譯程序中與目標機有關的部分，編譯后端不依賴于源語言而僅僅依賴于中間語言。8描述詞法規則的有效工具是詞法分析器，通常使用語法分析器來描述語法規則，使用語義分析（與中間代碼產生）器描述語義規則。二綜合題（該答案僅供參考）1、給出C語言編譯程序對下面語句進行編譯時從詞法分析到目標代碼生成5個分析階段的分析過程。c=a+b*30; （1）給出每個階段的輸入和輸出代碼或其它數據形式。（2）給出符號表，說明在哪些階段會對符號表進行填寫或查找。（3）編譯過程是否進行了代碼優化？若有，請指出優化之處，并給出屬于哪種優化？答： 詞法分析：出入源

3、程序；輸出識別出的記號流。c=a+b*30 id1=id2+id3*30 語法分析器：輸入記號流，構造句子結構；輸出語法樹。 = id1 + id2 * id3 30 語義分析與中間代碼生成：出入語法樹，輸出中間代碼 變量 地址 數值 注：賦值階段會對符號表進行填寫或查找 1. id1 0 c （itr，30， ，t1） 2. id2 4 x （*，id3，t1，t2） 3. id3 8 y （+，id2，t2，t3） 4. t1 12 30 （=，t3， ，id1） 優化 ：1.（*，id3，30.0，t1） 2.（+，id2，t1，id1） 精簡掉多余的復寫傳播 目標代碼：mov id3，

4、r2 mulf #30.0，r2 mov id2，r1 sub r1，r2 mov r2，id1第二章一填空題1上下文無關文法包括以下四個組成部分：一組終結符號，一組非終結符號，一個開始符號，以及一組產生式。2如果一個文法存在某個句子對應兩棵不同的語法樹，則這個文法是二義文法。3消除文法的二義性的方法主要有：改寫二義文法為非二義文法；為文法符號規定優先順序和結合規則。二 簡答題1有文法G：EE+EE*E(E)id（1）給出(id* id)+ id的最左推導； E （E） （E+E） （E*E+E） （id*E+E） （id*id+E） （id*id+id）（2） 并給出該推導過程中的所有句型；

5、 見（1）,把箭頭去掉即可（3） 給出該文法的2個句子。 1*1+1 2*2+2第三章一 綜合題31 給出書中P48 圖3.5中所示有限自動機的狀態轉換矩陣和五元式，并說明該有限自動機可識別哪一類字符串。 狀態 a b ay6x541 0 1 2 空 空 a a 空 a 空 1 3 2 2 2 1 3 b b b 3 3 3 b (5,3,1,2,6,y） (5,4,1,2,6,y) 可識別相繼兩個a或相繼兩個b的字2 構造與正規式（ab）*a(ab) 或(0|1)*0(0|1)等價的狀態最少的確定有限自動機。（1）構造轉換系統如下圖所示。aaZCaBSAbb正則式（ab）*a(ab)的轉換系

6、統（2）NFA確定化為DFA的過程如下表所示：IIaIbS, A, BA, B, CA, BA, B, CA, B, C, ZA, B, ZA, BA, B, CA, BA, B, C, ZA, B, C, ZA, B, ZA, B, ZA, B, CA, B相應DFA的狀態圖如下所示a4a2aa1bab5bb3b正則式（ab）*a(ab)的DFA將DFA最小化：首先得到兩個子集K1 = 1,2,3 和 K2 = 4，5由于狀態1和狀態3輸入a都到達狀態2，輸入b都到達狀態3，而狀態2輸入a到達狀態4，輸入b到達狀態5，所以將K1分割成K11 = 1,3 和 K12 = 2又由于狀態4輸入b到

7、達K2，而狀態5輸入b到達K11,所以狀態4、5是可分的。這樣，將原狀態集合分割成以下子集：1，3，2，4，5所以最小化DFA的狀態圖如下所示，2aaaba41bbb5正則式（ab）*a(ab)的最小化DFA3 構造與正規式(a|ba)*等價的狀態最少的確定有限自動機。 i a b31 b (x,1) (1,y) (1,2) y1x 空 a (1,y) - - a a (1,2) (1,y) -22 b a4、P64:習題8（1）以01結尾的二進制數串（2）能被5整除的十進制整數第四章&第五章&第七章一填空題1自上而下語法分析中存在的主要問題是由左遞歸引起的無限循環問題和左公共

8、因子引起的無法確定產生式后選項問題。2自上而下語法分析的基本思想是，對任何輸入串，從文法的開始符號，即根結點出發，自上而下地為輸入串建立一顆語法樹。遞歸下降分析器采用的是 語法分析方法。3預測分析器模型是由總控程序（表驅動程序） ，預測分析表 和先進后出的語法分析棧 組成，預測分析器是一種下推自動機 。4自下而上語法分析的基本思想是，從輸入串開始，逐步進行歸約，直至規約到文法的開始符號，即從語法樹的末端開始，步步向上規約，直到葉結點為輸入符號串。二、綜合題一P81 :習題1（1）消去文法中的左遞歸二畫出下面表達式的DAG（1）a+a*(b-c)+(b-c)*d + + * * d a - b

9、c （2）a=b*(-c)+b*(-c) Assign A + * B uminus c三有文法G： （1）EE+T （2）ET （3）TT*F （4）TF （5）F(E) （6）Fi 書中P101圖5.5是LR分析表，以下程序是驅動器算法，loop s := top; a := ip; case actions，a is shift s': push(a); push(s'); next(ip); reduce by A: pop(2*|); s' := top; push(A); push(goto(s'，A); accept: return; others

10、: error; end case;end loop1完成表2中LR分析器利用LR分析表和驅動器對輸入串i1*i2+i3進行分析的過程：寫出棧中的內容和動作類型（移進或歸約，若為移進請指出轉向狀態，若為歸約請指出歸約采用的產生式）；2若在語法分析同時進行語義分析，請在有語義翻譯動作的步驟中標出。表1 文法G的LR分析表表2步驟棧內容當前輸入移進-規約動作翻譯動作1#i*i+i#移進#2#i*i+i#移進i3#F*i+i#規約F FiValtop=lexval4#T*i+i#規約T TFValtop=lexval5#T*i+i#移進*6#T*i+i#移進i7#T*F+i#規約F FiValtop

11、=lexval8#T+i#規約T TF9#E+i#規約E ET10#E+i#移進+11#E+ii#移進i12#E+F#規約F FiValtop=lexval13#E+T#規約T TFValtop=Valtop+Valtop+214#E#規約E ET第六章一填空題1、屬性文法是在上下文無關文法的基礎上，為每個文法符號配備若干相關的“值”，稱為屬性，屬性與變量一樣可以進行計算和傳遞，屬性加工的過程即是語義處理的過程，對文法的每個產生式配備的一組屬性的計算規則，叫語義規則，語義分析和中間代碼的產生就是根據該規則進行的，在自上而下或自下而上語法分析過程中，在適當的時候進行屬性的計算或其它語義動作（如查

12、填符號表、產生中間代碼、發布出錯信息）就可進行語法制導翻譯得到中間代碼，這就是語法制導翻譯的基本思想。2、屬性分為兩類，綜合屬性用于“自下而上”傳遞信息，_繼承_屬性用于“自上而下”傳遞信息。，第八章一填空題1、線性查找是構造符號表最簡單和最容易的辦法，但查找效率很低，為了提高查找速度可以采用對折查找和雜湊查找查找。2、編譯過程中編譯程序需要不斷匯集和反復查證出現在源程序中各種名字的屬性和特征等有關信息，這些信息通常記錄在一張或幾張符號表中。第九章一填空題1、不同的編譯程序關于數據空間的存儲分配策略會有所不同， 靜態分配策略在編譯是對所有數據對象分配固定的存儲單元，且在運行是始終保持不變；另外

13、還可采用的分配策略是棧式動態分配策略和堆式動態分配策略。二 簡答題(僅供參考）1、C語言的編譯系統應該采用哪種存儲分配策略，并簡述理由。2、Pascal語言的編譯系統應該采用哪種存儲分配策略，并簡述理由。像Pascal和C語言，由于它們允許遞歸過程，在編譯時刻無法預先確定哪些遞歸過程在運行時被激活，更難以確定它們的遞歸深度，而每次遞歸調用，都要為該過程中的每個數據對象分配一個新的存儲空間。由上可見，它們的編譯程序則不能采用靜態分配策略，只能采用在程序運行時動態地進行分配（棧式分配）。又如 Pascal和 C語言，還允許用戶動態地申請和釋放存儲空間，而且申請與釋放之間不一定遵守先申請后釋放或后申

14、請先釋放的原則，因此，需要采用一種更復雜的堆式動態分配策略。 第十章一填空題1、代碼優化可在編譯的各階段進行，其中主要的一類是在目標代碼之前生成的，這類優化不依賴于具體的計算機。2、代碼優化可在編譯的各階段進行， 有一類是在生成目標代碼時進行的，這類優化在很大程度上依賴于具體的計算機。3、窺孔優化是對目標代碼進行局部改進的簡單而有效的技術，一般可能需要對目標代碼掃描若干次進行窺孔優化。二 簡答題1、 簡述編譯過程中代碼優化必須遵循的原則 等價原則：經過優化后不應改變程序運行的結果； 有效原則：使優化后所產生的目標代碼運行時間較短，占用的存儲空間較小； 合算原則：應盡可能以較低的代價取得較好的優化效果。2、對中間代碼中基本塊的優化和循環優化都是與機器無關的代碼優化，請各給出2-3種優化方法。代碼外提強度消弱刪除歸納變量(變換循環控制條件)第十一章二 簡答題1、 目標代碼生成任務是什么？ 把語法分析后或優化后的中間代碼變換成目標代碼。2、目標代碼一般有哪幾種形式？ 目標代碼一般有以下三種形式：1.能夠立