【文章內容簡介】 碼，這樣可以將與機器相關的某些實現細節(jié)置于代碼生成階段仔細處理，并且可以在中間代碼一級進行優(yōu)化工作，使得代碼優(yōu)化比較容易實現。何謂中間代碼：源程序的一種內部表示，不依賴目標機的結構，易于代碼的機械生成。為何要轉換成中間代碼邏輯結構清楚；利于不同目標機上實現同一種語言。便于移植，便于修改，便于進行與機器無關的優(yōu)化。中間代碼的幾種形式：逆波蘭記號 ，三元式和樹形表示 ，四元式 逆波蘭記號：把運算分量(操作數)寫在前面，把運算符寫在后面的表示法，又稱后綴表示法。中綴表達式向逆波蘭表達式轉換第十章：運行時的存儲區(qū)為了使目標程序能夠運行，編譯程序要從操作系統(tǒng)中得到一塊存儲區(qū)，以使目標程序能夠在其上運行。運行時的存儲區(qū)劃分目標區(qū)：存放目標代碼。代碼區(qū)（code）靜態(tài)數據區(qū)（static data）：編譯時能確定所占用空間的數據。棧區(qū)和堆區(qū)（stack and heap）：可變數據及管理過程活動的控制信息。存儲分配方案策略：靜態(tài)存儲分配；動態(tài)存儲分配：棧式、 堆式。 靜態(tài)存儲分配基本策略在編譯時就安排好目標程序運行時的全部數據空間，并能確定每個數據項的單元地址。適用的分配對象：子程序的目標代碼段；全局數據目標（全局變量）靜態(tài)存儲分配的要求：不允許遞歸調用，不含有可變數組。FORTRAN程序是段結構，不允許遞歸，數據名大小、性質固定。 是典型的靜態(tài)分配動態(tài)存儲分配 如果一個程序設計語言允許遞歸過程、可變數組或允許用戶自由申請和釋放空間，那么，就需要采用動態(tài)存儲管理技術。兩種動態(tài)存儲分配方式：棧式，堆式棧式動態(tài)存儲分配分配策略：將整個程序的數據空間設計為一個棧。 【例】在具有遞歸結構的語言程序中，每當調用一個過程時，它所需的數據空間就分配在棧頂，每當過程工作結束時就釋放這部分空間。過程所需的數據空間包括兩部分一部分是生存期在本過程這次活動中的數據對象。如局部變量、參數單元、臨時變量等；另一部分則是用以管理過程活動的記錄信息(連接數據)。活動記錄（AR） 一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū) (塊)叫做一個活動記錄。構成臨時工作單元；局部變量；機器狀態(tài)信息；存取鏈；控制鏈；實參；返回地址第十一章：什么是代碼優(yōu)化所謂優(yōu)化，就是對代碼進行等價變換，使得變換后的代碼運行結果與變換前代碼運行結果相同，而運行速度加快或占用存儲空間減少。優(yōu)化原則：等價原則：經過優(yōu)化后不應改變程序運行的結果。 有效原則：使優(yōu)化后所產生的目標代碼運行時間較短，占用的存儲空間較小。 合算原則：以盡可能低的代價取得較好的優(yōu)化效果。優(yōu)化分類：局部優(yōu)化，循環(huán)優(yōu)化，全局優(yōu)化常見的優(yōu)化技術(1) 刪除多余運算(刪除公共子表達式) (2) 代碼外提:是針對循環(huán)的(3)強度削弱。 把執(zhí)行時間較長的運算替換為執(zhí)行時間較短的運算(4)變換循環(huán)控制條件 (5)合并已知量與復寫傳播 (6)刪除無用賦值基本塊定義程序中只有一個入口和一個出口的一段順序執(zhí)行的語句序列，稱為程序的一個基本塊。對四元式序列，各個基本塊的入口語句是：(1)代碼序列的第一個語句。 (2)轉移語句的目標語句。 (3)轉移語句的下一條語句。例子：(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt必經結點在程序流圖中，對任意結點m和n，如果從流圖的首結點出發(fā)，到達n的任一通路都要經過m，則稱m是n的必經結點，記為m DOM n。必經結點集：流圖中結點n的所有必經結點的集合稱為結點n的必經結點集，記為D(n)?；剡叄杭僭Oa→ b是流圖中一條有向邊，如果b DOM a，則稱a→b是流圖中的一條回邊。循環(huán)(依據回邊判斷)給出一個回邊 n174。d，定義這個邊的(自然)循環(huán)是d加上所有不經過d能到達n的結點；d是這個循環(huán)的首結點。 【 例 】 求出左圖的所有回邊?！窘獯稹?1) 6→6，因為D(6)={1,2,4,6}， 所以6 DOM 6，故6→6是回邊； (2) 7→4，因為D(7)={1,2,4,7}， 所以4 DOM 7，故7→4是回邊； (3) 4→2，因為D(4)={1,2,4}， 所以2 DOM 4，故4→2是回邊。容易看出，其它有向邊都不是回邊。 例二：求回邊和循環(huán) 回邊4 → 3（3 DOM 4） 循環(huán)：{3,4,5,6,7,8,10}回邊7 → 4（ 4 DOM 7 ） 循環(huán)：{4,5,6,7,8,10}回邊10→7 （ 7 DOM 10 ） 循環(huán)： {7，8，10}回邊8 → 3 （3 DOM 8） 循環(huán)：{3,4,5,6,7,8,10} 一、填空題（每空2分，共20分）1．編譯程序首先要識別出源程序中每個單詞，然后再分析每個句子并翻譯其意義。 2．編譯器常用的語法分析方法有自底向上和自頂向下兩種。3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的分析，中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的綜合。4．程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即靜態(tài)存儲分配方案和動態(tài)存儲分配方案。5．對編譯程序而言，輸入數據是源程序，輸出結果是目標程序。1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。 2．掃描器是詞法分析器，它接受輸入的源程序，對源程序進行詞法分析并識別出一個個單詞符號，其輸出結果是單詞符號，供語法分析器使用。3．自下而上分析法采用移進、歸約、錯誤處理、接受等四種操作。4．一個LL（1）分析程序需要用到一張分析表和符號棧。5．后綴式abc/所代表的表達式是a/(bc)。 二、單項選擇題（每小題2分，共20分）1．詞法分析器的輸出結果是__C?！． 單詞的種別編碼 　　　　　　B． 單詞在符號表中的位置C． 單詞的種別編碼和自身值 　　D． 單詞自身值2． 正規(guī)式 M 1 和 M 2 等價是指__C_。 　A． M1和M2的狀態(tài)數相等 　 　B． M1和M2的有向邊條數相等C． M1和M2所識別的語言集相等 　 D． M1和M2狀態(tài)數和有向邊條數相等 3． 文法G：S→xSx|y所識別的語言是_C____?！． xyx 　 B． (xyx)* C． xnyxn(n≥0) D． x*yx* 4．如果文法G是無二義的，則它的任何句子α_A____。　A．最左推導和最右推導對應的語法樹必定相同 　　B．最左推導和最右推導對應的語法樹可能不同 　　　C．最左推導和最右推導必定相同 　　 　D．可能存在兩個不同的最左推導，但它們對應的語法樹相同 5．構造編譯程序應掌握____D__?！．源程序　　　B．目標語言 C． 編譯方法 D．以上三項都是 6．四元式之間的聯(lián)系是通過__B___實現的。 　A．指示器 　　B．臨時變量