編譯原理相關的書籍資料五花八門，大多偏理論為主，實用性高的寥寥無幾；而講實踐的書，相關的理論太少，難以提煉出一套方法論。并且教科書通常只實現了一些語言的子集，很多基本的特性都有所閹割，對一些新的語言特性要么只字不提，要么一筆帶過。最近筆者實現了從支持面向對象、函數式、閉包等特性的源語言-中間代碼-目標代碼-到寄存器式虛擬機上的解釋執(zhí)行，這篇博客主要寫一下工程實踐中的一些思路，盡量的撇開細枝末節(jié)。
說點與主題無關的，對于學習階段而言，編譯器的實現盡量選用自己熟悉的特性較為豐富的高級語言，原因在于主要目的是要了解編譯與運行時相關的理論與實踐，重點在于把這一塊領域知識串起來，所以過程中最好排除與之無關的干擾信息，也就是抓住主要矛盾。既然要實現語言的編譯器/解釋器，首先要知道該語言是怎樣的一門語言，大概要支持哪些基本特性，首先談談程序與語言。
程序，實際是我們給計算機所讀取的一套解決某個可計算問題的指令集合。但機器能直接讀取的二進制指令對人來說可讀性太差了，更別說用它來寫程序。于是人們想出了用一些語義化的文本來表示某個指令，如 0x10 0x1 0x2 0x3 換成文本表示 add r1,r2,r3 這樣通過文本就能一眼看出該條指令的含義-將r1和r2的數值相加，結果再放入r3，這個表示的文本也就是 匯編語言 。但這些文本機器不能識別，所以又需要一個程序來將這些文本轉換為機器指令，這個轉換程序稱為 匯編器 。匯編器用什么來寫呢？用匯編語言、或者高級語言都可以，但前提是已經有程序能將這些東西轉換成二進制機器碼程序。所以可想而知，最早匯編器就是直接用機器碼寫的。
同樣的，匯編語言基本與機器碼一一對應，還是太繁瑣了，本來只想寫個簡單的程序，還要關注太多硬件的細節(jié)。于是前人又嘗試設計一種更為高級的語言，目的就是為了去除這些無關的細節(jié)，讓同樣的文本有更強的表達能力。當然，最后還是需要轉換成低級語言，如匯編，那么將這個高級語言轉換為低級語言的程序稱為 編譯器 。
再回到現代計算機，實際上我們現在的程序都是運行在操作系統(tǒng)上的，這里說的程序實際不是 純二進制程序 ，純二進制程序是除了指令與數據外不包含額外的信息，但一般運行的程序都是對應操作系統(tǒng)定義了在它上面運行的程序文件的格式，運行時由 程序加載載器 來將固定格式的文件解析、分配內存、裝載程序指令與數據。所以如果是純二進制程序，其實是只與硬件支持的指令集有關。但我們的程序不是在裸機器上運行的，一般跟隨著操作系統(tǒng)提供的有匯編器、鏈接器、程序裝載器，這才有了Intel和AT&T兩種不同風格的匯編指令。由編譯器生成匯編指令后，再由匯編器生成目標文件，最后由鏈接器生成操作系統(tǒng)支持的可執(zhí)行文件。
當然，程序語言的設計是單獨的一個領域了，只有對各個語言的構成都有過研究，才可能設計出一個好的語言，編譯器只是一個實現語言所表達含義的工具。
其實編譯器與解釋器沒有太嚴格的界限，一般是按照最后生成的目標代碼是否是操作系統(tǒng)對應的匯編指令來決定。光是解釋器有好幾種，可以直接在語法樹上進行解釋執(zhí)行，可以對生成的中間代碼解釋執(zhí)行，或者給最后生成的指令提供一個虛擬機來執(zhí)行。前兩者通常是直接通過在內存的數據結構，后者可以直接輸出一個文件，然后下次運行直接按照定義的格式解析加載后執(zhí)行，無需再進行編譯。所以可以看到，對于編譯器與解釋器更好的說法是是否進行了完善的語義分析、并產生了新的可執(zhí)行的文件。至于直接的執(zhí)行者是CPU，還是虛擬機程序就無關緊要了。平時有人愛說某某語言是編譯型/解釋型語言其實并不準確，程序語言本身與它怎么運行的無關，關鍵在于編譯器是如何實現的，對于C/C++這種也可以直接解釋執(zhí)行。
再來看看編譯器完整的流程
分為以下幾步
常規(guī)的流程基本大同小異，額外的一些比如編譯過程中加入的優(yōu)化、根據與源語言的接近程度設計不同級別的中間代碼、編譯后交給匯編器、鏈接器生成目標平臺的可執(zhí)行程序... 當然，還有很多編譯器不按流程走，不顯式生成抽象語法樹或者中間代碼，直接在語法分析的時候完成一切工作。下面看看具體的流程
Lexer(詞法分析器)，顧名思義就是將輸入的一個個字符變成一個個Token(單詞)。token一般保存了單詞的類型、文本內容、在源代碼的行號、列號。自然的可以定義如下的結構
class Token { int tokenType; String text; int line, column;}要完成詞法分析，首先需要定義一套詞法規(guī)則，如:支持哪些關鍵字與基本的運算符？標識符的命名規(guī)則是怎樣的？整數、小數、字符串等字面量的可以有哪幾種表示。常用的規(guī)則基本類似，那么單詞如何識別呢？一般編譯原理的書籍都會把詞法分析和有窮自動機(Finite Automata)理論放到一起，但二者其實并無關系，首先來簡單說一下有窮自動機
有窮自動機作為一個數學模型，表示 一個內部有有限個狀態(tài)的系統(tǒng)，系統(tǒng)會有一個初始狀態(tài)，并能根據新的輸入，去改變當前的狀態(tài)，直到轉移到某個終止狀態(tài)為止 。所以可以知道，一個有窮自動機包含一下幾部分:
那么如何使用這個模型呢？以變量名與數字字面量的識別為例,假設變量名允許的命名規(guī)則為大小寫字母開頭，后續(xù)可以接任意字母或者數字，那么可以畫出如下的狀態(tài)轉移圖
雙圓環(huán)表示終止狀態(tài)。其中1為初始狀態(tài)，根據輸入的字符，如果是數字則轉移到狀態(tài)3，直到輸入的字符不是數字為止；狀態(tài)1如果輸入是字母，則轉移到狀態(tài)2，接著接受的字符如果是字母或數字則一直接收，直到不滿足條件而終止。根據狀態(tài)機模型，可以很快的編碼來解決這么一個問題。首先根據初始狀態(tài)+輸入字符，得到要轉移的狀態(tài)
int state = 1;if (isLetter(ch)) { state = 2 append(ch)} else if (isDigit(ch)) { state = 3 append(ch)}接著根據當前狀態(tài)+輸入字符
while (has next ch) { switch (state) { case 2: if (isLetter(ch) || isDigit(ch)) { append(ch) } else { appendToken() initState() } break; case 3: if (isDigit(ch)) { append(ch) } else { appendToken() initState() } break; }}換個角度，其實狀態(tài)機的這整個流程和我們按照正常處理的邏輯其實是差不多的，即使不使用狀態(tài)機相關的理論，依然可以快速的解決問題。如下述偽代碼
while (has next ch) { if (isLetter(ch)) { processId() } else if (isDigit(ch)) { processNum() }}所以要清楚有窮自動機模型只是一個可以解決字符串匹配的工具，但實際不必非得這樣做，一是當要匹配的的單詞規(guī)則過多時，狀態(tài)也會大量增加，會增加很多不必要的狀態(tài)維護；二是完全使用狀態(tài)機模型去編碼，狀態(tài)過多，并且又沒有狀態(tài)轉移圖的情況下，代碼可讀性很差。當然，對于詞法分析完全是可以使用正則表達式來進行匹配的，而正則表達式引擎本身也是由有窮自動機相關的理論實現的。
直接按照正常的思路事半功倍，比如關鍵字與標識符的識別，關鍵字一般是標識符的子集，所以比較好的方式是單獨建立一個哈希表存放關鍵字，詞法分析時統(tǒng)一識別成標識符，完成后再去查詢關鍵字表來最終決定token的類型，而不必去維護多個中間狀態(tài)。
Parser(語法分析器)，目標是將詞法分析器得到的token流變成按照語法規(guī)則來組織的數據結構，通常情況下樹是一個好的選擇，一般生成的語法樹稱為AST(abstract syntax tree)。同樣，首先要做的是設計語言的文法規(guī)則。與自然語言一樣，程序語言肯定也是某種固定的結構。既然要表示語句，必然要采用一種大家都約定俗成的表達方式，一般采用EBNF(擴展的巴科斯范式)，當然只要能準確表達，不用死扣具體規(guī)范。一般語句的組成有非終結符與終結符，前者表示抽象的一類事物，所以可以繼續(xù)推導；反之，后者表示具體的事物。以漢語為例，一般句子由主、謂、賓結構組成，其中主語謂語可以用人稱代詞、名詞表示，謂語用動詞表示?？梢缘玫饺缦率阶?/span>
句子 -> 主語 謂語 賓語主語 -> 人稱代詞 | 名詞謂語 -> 走 | 跑 | 吃 | 打...賓語 -> 人稱代詞 | 名詞人稱代詞 -> 你 | 我 | 他...名詞 -> 事物具體名稱其中句子左邊是規(guī)則名稱，右邊是產生式，即產生句子的規(guī)則。以解析句子 “小明吃飯”為例，最終可以得到這么一顆語法樹。
終結符與非終結符分別用不同顏色標出了?？梢钥吹?，用語法樹表示時，在葉子節(jié)點的為終結符，不可再繼續(xù)推導。程序語言與之類似，語法分析最終的目的也是得到這么一顆語法樹。語法分析階段依賴的文法稱 上下文無關文法 ，也就是意味著，該階段只能檢查出句子的語法結構上有沒有錯誤，而不能識別出邏輯的錯誤。如'一個字符串減去另一個字符串'，表達式的語法結構是沒有問題的，但語義上一般語言都是不支持的。接下來看看編程語言
以while循環(huán)語句為例
stmt -> expr | '{' stmt '}' | if_stmt | while_stmtwhile_stmt -> WHILE '(' expr ')' stmtstmt包括表達式、用花括號包裹的語句塊、if語句、while語句，其中while語句由終結符WHILE，左右小括號，表達式，語句組成。既然語法規(guī)則也是固定的結構，那么能不能用正則表達式直接去進行匹配呢？答案是不可以，仔細觀察能發(fā)現，正則文法實際上沒辦法處理遞歸定義的情況。根據這個語法結構很自然的能想到用遞歸的方式去進行語法分析，如下偽代碼
void parseStmt() { if (curToken is '{') { parseStmt() } else if (curToken is IF) { parseIfStmt() } else if (curToken is WHILE) { parseWhileStmt() } else { parseExpr() }}void parseWhileStmt() { match(WHILE) match('(') parseExpr() match(')') parseStmt()}整體邏輯還是挺清晰的，實際上也就是使用 遞歸下降算法 進行語法分析，一般提前實現好token流匹配相關的函數即可。語法分析的算法也有好幾種，手工構造的詞法分析器，遞歸下降也是比較常用的，這里也本著夠用就行的原則。再來看看，使用遞歸下降進行語法分析的主要一個問題在于表達式的優(yōu)先級處理。
以表達式1+2*3為例，最終得出的語法樹應該是這個樣子
這樣根據語法樹進行后序遍歷，就能計算出正確的結果。處理表達式優(yōu)先級，實際上就是將優(yōu)先級高的子表達式先計算，對應到語法樹就是 優(yōu)先級越高的運算符在語法樹上所處的層級越低 ?？梢缘贸鲞@樣的產生式
expr -> addadd -> add + mul | mulmul -> mul * pri | pripri -> Id | Literal不過這樣的產生式導致了左遞歸的問題, 匹配邏輯大概是
void parseAdd() { parseAdd() match('+') parseMul()}實際會在parseAdd一直無限地遞歸下去，式子add遞推下去(不斷將產生式的非終結符進行替換)就是
add + mul + mul + mul + ...可以看到，既然先parseAdd()導致左遞歸問題，那么換成先parseMul()不就好了。實際上這也是教科書標準的解決辦法，即 將左遞歸產生式改寫為右遞歸 ，可以這樣寫
add -> mul add'add' -> + mul add' | ε寫成偽代碼如下
void parseAdd() { parseMul() if (next is '+') { parseAdd_() }}void parseAdd_() { match('+') parseMul() if (next is '+') { parseAdd_() }}使用右遞歸的方式進行解析又會產生結合性問題，正常情況下表達式應該是左結合的，但右遞歸導致右結合，以表達式1+2+3為例，如下所示
左邊是從左到右的結合，右邊是從右到左結合，這么一看好像沒問題，但如果換成減法1-2-3，從左至右運算實際含義是1-(2+3)，而從右向左運算是1-(2-3)，實際含義都變了，那么肯定要想辦法解決這個問題，先如下方式改寫產生式
add -> mul('+'mul)*這樣與右遞歸描述的規(guī)則其實是一樣的，但這樣寫在邏輯上可以變遞歸為循環(huán)來實現
void parseAdd() { c1 = parseMul() while (next is '+') { match('+') c2 = parseMul() c3 = new Expr('+', c1, c2) c1 = c3 }}通過將新建的節(jié)點變成下一次匹配到的二元表達式的左孩子，這樣就解決了結合性問題。大多數運算都是從左到右結合，但還是存在從右到左結合的情況，如賦值表達式
x = y = z = 1解決辦法是在解析一個完整的表達式后再將二叉樹的節(jié)點重組，以表達式x = y = 1為例，如圖
實際得到的是左邊的，但按照語義是要得到右邊的語法樹。所以直接將左子樹的右節(jié)點斷開，變成當前節(jié)點的左孩子，接著再將原先的左子樹的右孩子變成當前節(jié)點即可，可以觀察到的規(guī)律是 賦值運算符的左孩子不能是賦值運算符 ，因此對于多個連續(xù)的賦值表達式直接按照上述規(guī)則一直循環(huán)處理當前節(jié)點的左孩子，直到不滿足條件為止。如下偽代碼
while (node.left != null && node.left is assignExpr) { oldLeft = node.left leftRight = oldLeft.right oldLeft.right = node node.left = leftRight node = oldLeft}解決這些問題，語法分析基本只是堆積的工作了。接下來看看語義分析
語義分析是編譯過程中比較重要的一步，所謂語義實際就是分析程序所表達的意思。因為程序最終的結果還是要執(zhí)行某種計算，所以進行好語義分析后才方便進行目標代碼的生成。前面說的語法分析是上下文無關的，而語義就是上下文相關的分析。語義分析階段的工作一般包括類型推導、類型消解、類型檢查、引用消解、語義校驗、閉包分析等。下面介紹比較該階段常見的幾部分工作
建立類型系統(tǒng)的目的是將具有某類共同性質的值進行劃分，以準確規(guī)定與預測程序的行為，既保證了程序的安全，又能提高運行時的效率。那么一般類型系統(tǒng)如何構成呢？ 首先，要確定的就是該程序語言提供哪幾種基礎類型，一般包括整數、浮點數、字符、布爾值。直接通過字面量文本就可以確定好該字面量的基本數據類型。另外，主流的語言都支持定義新的組合類型，如字符串、數組、C語言的結構體、指針、面向對象語言的class，以及將函數作為一等公民的語言還包括函數類型，對于新類型的定義也要提供一套對應的規(guī)則，定義的類型支持哪些基本的運算。
建立類型系統(tǒng)后，語義分析的過程中就要確定所有的變量、常量、字面量、表達式的類型，這個視具體的語言而定，需要顯示聲明變量類型的語言，如C/C++、Java系
int a = 1通過語法樹的左孩子對應的關鍵字 'int'，就可以確定出變量a的類型；有些語言不需要顯式聲明變量類型的
var a = 1就可以根據變量聲明語句語法樹中最右邊的孩子整數字面量 '1' 從而確定出變量a的類型也為整形。這里只是拿基本類型舉例，對于組合類型而言，比如數組取值的表達式，取值表達式是幾維，就看數組去掉幾維后它的類型是什么，如
int[] a; // a[0]的類型為去掉1維, 即intint[][] a1; // a1[0]的類型為去掉1維, 即int[]對于函數調用，則去查看函數對應的返回值類型來確定該表達式的類型。而對于二元表達式，則根據左右孩子的類型來推導出父親節(jié)點的類型。該過程通常又會涉及到類型轉換。
類型系統(tǒng)也要規(guī)定不同數據類型的數值之間的轉換規(guī)則。如整形與浮點數類型的值進行運算，得到的結果應該為浮點型；任何類型的數值與字符串進行運算，得到的結果都為字符串類型。如
1 + 2.0 // 該表達式類型為浮點型1 + 'abc' // 該表達式類型為字符串類型一般情況下，如果是直接顯式的將不同類型的數值進行賦值，也要顯式進行轉換；如果是表達式，就要進行隱式的類型轉換，也就是在語義分析階段單獨添加新的類型轉換的語法樹節(jié)點。
這里簡單說下強類型與弱類型的區(qū)別，指一個變量的類型聲明后是否還能改變，能改變說明該語言是弱類型的語言。一般的腳本語言通常就沒有嚴格的類型限制，在運行期變量的類型可以任意改變，這樣其實就杜絕了在編譯期進行嚴格的安全檢查，如下列代碼
var a = 1, b = 2var c = input()if (c == '1') { a = 'sass'} else if (c == '2') { a = 5} else { ...}println(a - b)這里對于表達式a - b，如果a為字符串的話，表達式肯定是不合法的，但a的類型實際沒辦法在編譯期就確定。所以弱類型的語言運行期還要進行較多額外的類型檢查與轉換。
一般強類型的語言就要做較為完善的類型檢查，通常包括
引用消解的目的是給程序中引用的變量、函數等找到正確的定義，以及找出同一作用域下存在的變量名的重復定義。整個過程中肯定要查找聲明的變量、函數、類、作用域等相關的信息，因此必然要有一個中間結構保存這些信息，這個結構稱為 符號表 ，后面再單獨介紹符號表的設計。對變量進行引用消解基本是按以下幾步進行
可以看到，如果要達到“先使用后聲明”的效果，如下
void test() { println(a) T t = T() println(t.a)}int a = 1class T { int a = 1}這里變量a，以及類T的定義都在使用后面，但處理函數test時仍能找到正確的引用。比較好的做法是多階段掃描，首先單獨的將聲明的類、變量、函數等加入符號表，后續(xù)進引用消解時就可以直接從符號表中查找到引用的定義。
程序源文件的內容對于計算機來說全部都是符號，那么確定這些符號表達的含義，把這些符號用某種結構組織起來就是編譯器做的事情。主要保存符號的名稱、類型、作用域等相關的信息，基本貫穿編譯過程中的大部分階段，所以重要性可見一斑。符號表作為一種中間結構，也沒有規(guī)定具體的實現，但它本身是為了方便進行編譯過程中符號所表示的信息的獲取。一般的符號包括名稱、可見性、是否是靜態(tài)、以及所屬作用域等，所以對于一個基本的符號可以這樣設計
class Symbol { string name int visibility boolean isStatic Scope enclosingScope AST ast}另外，符號對應的ast節(jié)點也需要進行存儲，ast節(jié)點會與token關聯(lián)起來，所以主要目的是發(fā)現語義錯誤時，方便直接定位到錯誤所處的列號與行號。而Scope表示一個作用域，作用域其實是符號保存的一個位置，所以不同的作用域肯定有單獨的一張符號表。于是作用域可以這樣表示
class Scope extends Symbol { Symbol[] symbols = Symbol[1024] int idx = 0 void addSymbol(Symbol symbol) { symbols[idx] = symbol idx += 1 } Symbol findSymbolByName(string name) { Symbol result = null for (int i = 0;i < symbols.length;i+=1) { if (symbol.name == name) { result = symbol break } } if (result == null && enclosingScope != null) { result = enclosingScope.findSymbolByName(name) } return result } ...}一般編譯器會針對不同的作用域設計不同的符號表，如全局符號表、局部符號表，其實也只是因為不同作用域符號的生命周期不同，方便后期代碼的生成。其實通過這種簡單的鏈式結構能很好的處理，當某個作用域沒有父作用域時，肯定就是全局作用域了。其它的不同符號都可以在基本結構上擴展，如變量、類、函數0等
class Variable extends Symbol { Type type}class Class extends Scope { Class parentClass}class Function extends Scope { Variable[] formalParams Type returnType}...根據這些結構，基本能將各個符號相關的信息清楚的表示出來，前面說語義分析是為了得到帶注釋的抽象語法樹，進而方便進行后續(xù)的工作。其實不必拘泥于概念，可以直接在原來的ast節(jié)點上進行擴展符號信息，但工程上的實現也是分步進行的，所以可以的話盡量前面的步驟不要依賴后面的實現，這樣能保證整體邏輯的清晰，其實直接用一個hash表存儲，建立起ast節(jié)點與其對應的類型，以及符號信息的映射即可。
前面說過，語法分析階段建立了語法樹。語法樹的好處在于，通過簡單的樹遍歷，就可以實現語義分析。如二元表達式的類型推導，實際就可以根據樹的后序遍歷，遍歷到根節(jié)點時，左右孩子肯定已經處理完，就可以直接根據左右孩子的類型信息，來標注根節(jié)點的類型，以此類推，直到處理完整課語法樹。
接下來看看中間代碼生成
完成語義分析后可以直接生成目標代碼，但編譯器通常會先生成中間代碼，目的是為了進行平臺無關的優(yōu)化以及簡化目標代碼的生成。 要清楚，即使進行了語義分析，對于源程序中的一些高級概念，如控制流語句語句、函數調用、多維數組、復合表達式...這些東西直接轉換成目標代碼要做不少工作，生成中間代碼后，這些概念基本被消除了，中間代碼通?？拷凑Z言又接近目標代碼，能極大簡化最終代碼的生成。并且如果將不同的語言轉換成同一中間表示的話，就能讓多個不同的程序語言共用相同的編譯器后端，最終編譯成同一平臺的目標代碼。實際上llvm、方舟編譯器就是這樣做的，定義了一種IR，不同的編譯器前端只需要生成指定格式的IR即可。
現在比較常見的是一種線性IR-三地址碼(Three Address Code)，即用四元組形式來表示
z = x op y其中x、y表示操作數，op表示操作符，z表示運算結果存儲的位置。當然，四元組不是說非得要用四個符號來表示，而是最多使用四個?？梢栽O計這么一個結構
class TAC { Symbol result string op Symbol arg1 Symbol arg2}因為中間代碼要將復合的表達式進行分解，不可避免的要產生許多臨時變量來存儲中間結果。如
// 源程序x = 1 * 2 * 3// irv1 = 1 * 2v2 = v1 * 3// x = v2v0 = v2既然要產生中間變量，不如直接將原先所有變量都重新分配新的名稱，用hash表做映射，這樣也是能方便后續(xù)生成目標代碼時進行內存的分配。接下來再簡單介紹幾種高級語言的語法結構翻譯成的中間表示
以while循環(huán)為例
int i = 0while (i < 100) { i += 1}中間表示如下
v0 = 0L0:v1 = v0 < 100jumpz v1 L1v2 = v0 + 1v0 = v2GOTO LOL1:...可以看到，要把源程序的語義表達出來，需要插入額外的輔助標簽。這里jumpz表示如果v1為false，則跳轉到L1所處的位置。一般涉及到控制流語句的，就要插入標號占位，將來生成目標代碼時再替換成內存實際的位置。這里需要注意的一個問題是，源程序是至上而下翻譯的，要跳轉到的位置在當前程序后面時，沒辦法馬上獲取到要跳轉到的標號,所以對于循環(huán)、分支等語句通常要進行 標號回填 。見如下偽代碼
void translateWhileStmt(AST ast) { // 生成開始標簽 TAC start = genLabel() // 翻譯while循環(huán)的條件表達式 Symol res = translateExpr(ast.condition()) // 生成jumpz指令，標號暫時為空 TAC jumpTAC = genJumpZTAC(res, null) // 翻譯語句塊 translaBlockStmt() // 生成goto指令跳轉到循環(huán)開始的位置 genGoto(start) // 標號回填 TAC end = genLabel() jumpTAC.setArg1(end)}以if語句為例，如下
if (flag) { i = 1} else { i = 2}翻譯成的中間表示
jumpz v0 L0v1 = 1GOTO L1L0:v1 = 2GOTO L1L1:...if語句同樣要進行標號回填，并且會在每個分支塊的結尾生成直接跳轉到整個分支語句后面位置的指令。
break與continue語句分別用來表示結束、跳過當前的這次循環(huán)?？梢韵氲剑隙ㄊ且彩欠g成goto語句，但關鍵是如何確定跳轉的位置呢？前面的循環(huán)和分支語句，是因為可以確定語句開始與結束的位置，所以方便回填。對于break與continue，可能出現在循環(huán)的任意位置，并且如果處于多層嵌套的情況下，應該只退出或跳過最內層循環(huán)，解決辦法是使用一個棧存儲標號即可。 對于break，使用單獨的棧存儲最新進入循環(huán)語句的結束標號，退出該循環(huán)語句塊時則將棧頂的標號出棧。所以碰到break，直接獲取當前棧頂標號即可；同理，對于continue，使用單獨的棧存儲最新進入的循環(huán)語句的開始標簽，遇到該關鍵字也直接獲取棧頂標號。
對于更多的指令，直接參考現成的或自己制定即可，反正最終目的是要生成的代碼符合程序的邏輯，至于具體的表現不是重點。還有需要清楚的一個問題是，代碼生成過程中有很多特殊情況需要處理。比如引用的變量所屬作用域的問題，該變量是局部變量、還是類的成員、或是全局變量，支持閉包的話還要判斷是否是自由變量。對于不同作用域的變量在內存中存儲的位置肯定是不一樣的，這個可以在目標代碼生成的時候去處理。但在中間代碼處理完更好，一般針對不同作用域的變量需要生成不同的指令。
編譯器的目的是最終生成能在目標平臺上運行的指令，所以為了正確的生成指令還需清楚程序運行的機制是怎樣的。說運行時，主要了解的是程序運行的環(huán)境與運行的過程。
程序最終是運行在目標平臺上，這個平臺可能是實際機器，可能是虛擬機。對于實際的機器，主要就是跟CPU和內存這兩個硬件進交互。首先得了解的是計算機硬件的基本組成，而現代的計算機基本都是馮諾依曼結構的，邏輯上包含五部分:輸入設備、輸出設備、存儲設備、運算器、控制器。對應到實際的機器，CPU的負責的實際就是運算與控制，而內存、硬盤等實際上又是輸入、輸出還是存儲設備，但由于不同的設備讀寫速度差異過大，直接與CPU打交道的通常是內存。CPU內部有寄存器與高速緩沖區(qū)，但容量有限，所以內存成為程序指令與數據主要存儲的位置。
程序按照運行的平臺可分為3類。
直接運行在機器上的的程序，由自己完成內存的劃分與分配；運行在操作系統(tǒng)里的程序，由操作系統(tǒng)來完成運行期內存的劃分，操作系統(tǒng)通常使用的是虛擬內存，通過內存分頁以及頁表來建立虛擬內存到物理內存的映射。前兩者，實際的運行時都是直接由硬件或操作系統(tǒng)完成的，只需按照平臺的約定生成符合規(guī)范的程序即可。而運行在虛擬機上的程序就要虛擬機的實現者自己完成程序的裝載、內存區(qū)域的劃分、動態(tài)內存的分配等工作。
對于后者，可以完全模擬實際的硬件，但可以表示的是可選項，不必局限于此。因此，一般的腳本語言有豐富的特性，就是因為它運行時平臺的可定制性與靈活性高，所以去實現高級的語言特性時非常方便，可以把很多特性推遲到運行時來處理。反之，一般直接編譯成真實目標平臺上的匯編指令集的語言，因為硬件的限制，所以實現同樣的功能要在編譯期間花費較多額外的工作。
通常情況下，內存區(qū)域都會使用類似的劃分方式。一般可分為代碼區(qū)、棧、靜態(tài)數據區(qū)、堆。
程序開始運行，也就是程序文件的內容從硬盤裝載到內存，CPU從入口地址開始執(zhí)行指令。正常情況下是沿著指令起始地址，一直往后執(zhí)行，直到遇見跳轉語句，則需要定位到將要跳轉的位置。直接跳轉無需考慮其它，對于函數調用指令，要跳轉到函數的起始地址執(zhí)行，并且執(zhí)行完后需要返回原來函數調用的下一條指令的地址。另外，函數調用時還包括參數的傳遞以及返回值的獲取，所以這些信息必須要有地方進行保存，通常是保存在棧中。
一般把一次函數調用稱為一次活動，每個活動對應著一個活動記錄，活動記錄實際就保存了上述的信息，通常情況下基于棧來管理內存，所以活動記錄也被稱為棧幀。注意棧幀只是邏輯上的一個概念，只是為了方便描述當前的運行環(huán)境，不是說真的存在這么一個東西。當前棧幀通常還需要保存上一棧幀的鏈接地址(對于直接在實際計算機運行的程序，通常是棧基址寄存器)，調用過程中需要保存的寄存器等 ，這樣在函數執(zhí)行完回收棧幀時還能恢復之前的位置，或者某些情況下需要引用上一棧幀的變量，就可以沿著調用鏈進行查找。
同內存區(qū)域一樣，對于棧幀的實現如果是虛擬機需要自己來實現運行時的時候，可以完全參照實際機器的概念進行模擬，也可以真的顯式地使用新的數據結構來存儲以及鏈接。
運行時相關的東西，光看概念很難清晰，動手實踐一下就柳暗花明了。
接下來描述語言的設計中一些常見的特性。
基于面向對象的方式編程更接近現實生活的邏輯，所以對面向對象相關特性的支持基本是現在主流的語言必備的。通常包括的概念有類、對象、繼承、多態(tài)，這里就來簡單的說一下為了支持這些特性編譯器要做的工作。首先對于類，類似C語言中的結構體，同樣是屬于可以由用戶自定義的類型，不過類可以包括屬性與方法(C結構體用函數指針同樣可以模擬)，設計類這樣一個概念主要是方便融入語言的類型系統(tǒng)，通過類型來檢查對象可以訪問的字段與方法。
在面向對象的語言中，類是對象的模板，對象是類的實例。那么在運行期間，對象的具體表現是什么樣呢？首先對于類的字段，每個不同的對象應該都是單獨的一份；而類方法，每個實例對象調用的都是相同的方法，因此只用保存一份。所以對于一個對象，保存的基本信息至少應該有所屬的類，以及存放字段的容器?？梢赃@樣定義
class Object { Type type Slot[] slots}對于自己實現運行時的語言來說，一般會在內存區(qū)域里劃分一個元數據區(qū)，類、字段、方法相關的信息就可以保存在這里，在程序運行期去查找對應的元信息，來確定正確的操作。如數據類型，不管是整形、浮點數還是布爾值，到實際的存儲時都是二進制數字，關鍵在于運行期如何針對不同的類型進行數據處理。取值，是整數直接從內存里取就好，浮點數則需要將取出來的整數根據設定的規(guī)則轉換成浮點數；賦值時，則相反。當然，對于數據類型的問題同樣可以通過將指令變成操作某種確定數據類型的，這樣會增加很多多余的指令，但運行期不用再去查詢元信息，執(zhí)行效率能有一定的改善。
對于類的字段，類定義后，字段的相對順序不會改變，所以可以直接在編譯期給字段編號，翻譯的目標代碼直接按標號訪問對應的內存單元即可，內存單元可以固定為4字節(jié)，要存儲更大的數就用更多的內存單元來存儲。自己實現運行時確實比較靈活，對于C++這種直接編譯成硬件平臺匯編指令的，和結構體處理的方式類似，對于不同的數據類型要考慮字節(jié)對齊(同樣可以直接固定內存單元的大小)，字段的訪問翻譯后就是基于對象基址的偏移。
一般對于類來說，成員通常包括普通成員與靜態(tài)成員，前者屬于對象，后者屬于類。在運行期，實際可以將靜態(tài)成員直接當作全局變量來處理，用類簽名拼接上成員簽名，就可以唯一確定到一個靜態(tài)成員。
最后，對象的內存分配一般是在堆中動態(tài)分配，動態(tài)分配的內存回收是個問題。所以現代的編譯器通常會考慮，如果對象只是在局部使用的話，可以在棧里分配空間，這樣用完就可以直接回收了。
繼承是為了實現數據和邏輯的重用以及實現多態(tài)，但對于重用不一定要使用繼承，很多情況下更推薦使用組合，因為繼承增加了代碼的耦合性。這里主要說下編譯器如何處理繼承的。只需要在類的信息中設置繼承的父類即可，在引用消解時直接從當前類查找不到就去父類查找，類型檢查時也需要根據繼承關系來判斷是否合法。
對于類字段，如果當前類有父類直接從父類最后一個字段的編號后面開始編號，所以最后類的實例對象的內存布局實際是這樣的。
對象頭保存了當前對象的實際類類型，然后父類、子類字段依次排列。
在運行期，對于類方法，子類可以重寫父類的同名方法，而在編譯器期間可能無法確定對象的實際類型是什么。如下
void test(T t) { t.f()}class T { void f()}class T1 extends T { void f() { println('t1...') }}class T2 extends T { void f() { println('t2...') }}編譯期間對test()方法進行處理，消解的方法f()是父類T的，沒有具體的實現。傳的實際參數是哪個子類對象，根本不知道，所以只能在運行期根據對象t所屬的實際類型，來根據方法簽名查找到方法的位置，這個過程一般被稱為 動態(tài)綁定 。同樣，對于自己實現運行時，類、方法都有直接的數據結構來保存元信息，這個過程比較靈活，但如果是C++這種，方法的動態(tài)綁定如何處理呢？實際上，C++對象頭里面有一個指針，指向一個表格，表格保存的就是當前對象所屬類的實際方法的入口地址，這個表格被稱為 虛函數表 。在編譯期間就可以確定表格的大小，所以在生成目標代碼時，知道對象的入口地址，也能知道表格的地址，調用對象的實例方法就直接翻譯成調用根據表格首地址的偏移處存放的函數地址。
this與super關鍵字一般也是必備的，前者用來訪問當前實例對象所屬類的字段或方法，super關鍵字用來訪問父類字段或方法。前面說過，在運行期間，沒有什么父類的概念，所有的父類字段都排列在子類的實例中，所以 this和super實際表示的都是當前對象實例 ，super其實只是一個子類訪問父類成員的語法糖。那么在類的方法里面，怎么獲取到 當前對象實例 呢？要知道，方法是被所有類的實例共享的，所以肯定對于不同的實例this的實際引用也不同，而方法的邏輯又是一樣的，很自然的能想到，把實例對象當作它所調用方法的參數傳遞進去，一般放在第一個參數的位置。而對于靜態(tài)方法，是屬于類的，就和常規(guī)的函數一樣翻譯即可。
還需要考慮的一個問題是，類字段的初始化值在什么時候進行，如下
class A { int a = 1}類字段同普通的變量聲明一樣，普通的變量聲明在運行到聲明的位置就直接賦值了。字段在編譯期的處理，只是引用消解、進行編號后為運行期創(chuàng)建類實例做準備，字段的值可以是復合表達式，可能產生多個中間臨時變量，并且對于普通字段每個實例對象都要進行重新賦值，靜態(tài)類只用賦值一次，一個辦法就是在語法分析階段生成AST時，創(chuàng)建一個初始化方法聲明節(jié)點，方法的實際內容就是給成員賦值，這樣多少臨時變量占用的空間在方法執(zhí)行完后都被回收了。只需要在類創(chuàng)建實例時先執(zhí)行這個隱藏的方法。對于編譯期處理后實際代碼邏輯是這個樣
class A { int a A() { _init_() ... } _init_() { this.a = 1 }}在類的構造方法里調用該init方法即可。對于靜態(tài)字段，也可以用同樣的方式，在第一次引用時進行賦值，讓類使用一個標志位判斷是否已經初始化過即可。
同面向對象，函數式也是一種編程范式，現在很多語言如Python、JavaScript實際都支持多范式的編程風格，至于哪種更好就見仁見智了，這不是討論的點。
平時我們寫程序一般是命令式編程， 命令式編程關心的主要是解決問題的步驟，而函數式編程關心的是數據的映射關系 。這里所說的函數式編程中的函數其實等同于數學里面的函數。在程序中也有函數這種說法，原因在于最開始搞計算機的那一批人實際也是從搞數學的那里轉過來的，于是沿用了這個概念，但程序中的函數說成是子程序更加準確一點，這里來說明一下。
對于函數f(x)=ax+b，假設把x看作輸入，ax+b的結果看成輸出?？梢灾罃祵W里面的函數有這么兩個特點，一是 對于相同的輸入一定會得到相同的輸出 ；二是 輸入的值不會在計算過程中改變 ，并且輸入的x即可以是普通的數值，也可以是一個函數。由這些特點，可以推廣到程序語言中。程序語言中的函數可以引用全局、類成員變量等外部的數據，所以如果前面的計算改變了外部環(huán)境的數據，那么函數最終的輸出就可能發(fā)生變化。因此根據數學中的函數，程序語言的函數式編程主要強調以下幾點
函數式編程的好處在于，因為不需要引用和改變外部的環(huán)境，所以對于函數的執(zhí)行結果實際是可以預測的，并且由于不存在共享變量，因此也不會產生并發(fā)的問題。舉個簡單例子
var list = [1,2,3,4]// function f(x) { return x * x}var f = x => x * xlist.map(f)// 輸出: [1, 4, 9, 16]注意變量ｆ后面的是lambda表達式，實際就是普通函數定義的語法糖。對比看看，這個就是滿足了函數式編程的幾點要求。
前兩點實際都是編程規(guī)范的遵守，而第三點就是編譯器需要實現的。接下來看看如果語言要支持該特性，編譯器要做哪些工作。首先，函數應該也作為一種新的類型加入語言的類型系統(tǒng)，函數類型由參數類型、返回值類型組成，聲明的函數本身也屬于函數類型。對于函數類型的變量可以這樣定義與賦值
void test(int a, float b) { println('函數測試: a=' + a + ', b=' + b)}function void(int,float) a = test// 函數 名稱()表示調用該函數 名稱表示直接引用該函數本身表示聲明了一個變量a，返回值為void，傳入兩個參數，類型分別為int、float。對于每個新聲明的函數，確定一個函數類型，這里將同樣簽名的函數test賦值給了變量a。然后在語義分析時，先根據函數名正確的進行引用消解，接著函數類型變量的賦值以及作為函數參數、返回值等都要進行類型檢查，也就是分別檢查參數與返回值類型是否兼容。
變量a被賦值函數test了后，可以直接調用
a(1, 1.0)// 輸出: 函數測試: a=1, b=1.0前面說過，函數是一個子程序，翻譯后就是一堆指令的集合。那么這個函數變量賦值的運行時表現是怎樣的呢？函數賦值時，直接將函數生成一個不含數據的對象，在對象頭部保存原函數的引用即可，在運行期間根據函數對象頭部找到函數的具體位置。函數變量之間同樣可以相互賦值
function void(int,float) a1 = aa1(1, 1.0f)// 輸出: 函數測試: a=1, b=1.0變量賦值時實際都是函數對象引用的傳遞，只有直接將函數直接賦值時才會創(chuàng)建新的函數對象。
閉包通常是在實現了將函數作為一等公民的情況下，再繼續(xù)進行擴展的，與前面所說的函數式編程所提的純函數的概念相反，閉包解決的主要就是內部環(huán)境引用外部環(huán)境變量的問題。閉包實際就是函數+存放外部變量的環(huán)境?？匆粋€簡單的示例
function int() outer() { int i = 0 int inner() { int a = i + 1 return a } return inner}function int() a = outer()上述代碼中內部函數inner引用了外部函數的局部變量i，并且外部函數最終返回的值是內部函數。對于函數的局部變量，內存通常分配在棧里，生命周期較短，在函數執(zhí)行完后就被回收了。函數內部引用的外部變量通常也稱為 自由變量 ，對于上述示例，如果在outer函數執(zhí)行完，引用的自由變量i應該也被回收了，但內部函數作為outer執(zhí)行的返回值賦值給了函數變量a，所以可以直接通過變量a調用該函數。那么執(zhí)行變量a實際指向的函數inner時，自由變量i從何處來呢？
這個問題也就是閉包需要解決的，當引用了自由變量的函數被作為返回值或者直接給函數變量進行賦值時，需要打包當前的運行環(huán)境，也就是將當前棧內存中自由變量的值一起打包給接收者，接收者再執(zhí)行該函數時就能正常訪問該自由變量。實際上，是原先處于棧內存的自由變量，被拷貝后放到了生命周期更加長的堆內存。
而編譯器需要做的是，在編譯期間分析出哪些變量是自由變量，實際就是看函數作用域內引用的哪些變量不是屬于當前作用域，并且也不是全局變量或類成員變量。對于一個自由變量，要運行期間在棧中找到正確的位置，然后才能拷貝打包。首先要確定閉包的創(chuàng)建時機，思考一下，能發(fā)現創(chuàng)建閉包的指令其實是位于 閉包函數所處的父作用域的指令流中 。這就意味著，實際上是在執(zhí)行閉包函數父作用域的指令時創(chuàng)建閉包，那么 自由變量實際的位置也就是該變量在當前函數的局部變量所處的位置 。而知道當前局部變量所處的位置，就可以根據當前棧幀中的?；穪磉M行偏移得到最終的內存地址。
因此在進行閉包分析時，肯定要記錄自由變量在外部作用域中局部變量所處的位置。另外，上述示例引用的變量就是直接外層，實際上內部函數可以引用外部的任意層的局部變量，就可能出現直接外層沒引用該變量，但內部函數又引用了。解決辦法是， 對引用的自由變量中間所有層都加上該變量的拷貝 ，因為創(chuàng)建閉包是直接外層的指令，所以創(chuàng)建一個閉包時外層的閉包環(huán)境肯定已經創(chuàng)建了，所以自由變量從直接外層拿即可。最后同樣打包成一個對象，對象頭里存放了函數，而內容就是自由變量的環(huán)境。
對于自己實現運行時很靈活，自由變量的查找都可以推遲到運行期。對于Go語言這種直接編譯成目標平臺匯編指令的語言，也支持閉包。它在編譯期會直接將閉包函數+引用的自由變量打包成一個結構體，然后給結構體在堆上分配內存，并從當前運行的棧內存中將值拷貝到新分配的內存(根據棧基址寄存器ebp+局部變量的偏移)。對于閉包函數的調用，直接根據結構體指針的地址+偏移量得到，而對于函數所引用的自由變量同樣，執(zhí)行函數時將該結構體的指針放到寄存器，引用變量時直接根據寄存器存放的地址來獲取。
目標代碼也就是語言最終要運行的平臺所支持的指令集，所以要正確的生成代碼需要先清楚目標平臺的體系結構。計算機體系結構也是單獨的研究領域了，但對于生成可用的目標代碼需要的知識并不算多。
對于目標代碼，一種是生成實際的目標平臺的匯編指令，如Linux下的AT&T風格的x86匯編、Windows下的Intel風格的x86匯編指令，兩種風格的匯編代碼最后經過匯編器、鏈接器生成的都是同樣一套機器指令，但程序的運行需要依賴運行時庫，而現在程序常見的功能：網絡、磁盤IO等實際都是操作系統(tǒng)提供的運行時庫來實現的。最后生成的可執(zhí)行程序文件格式也不一樣，但即使在Linux下按照Windows程序的格式來解析裝載(wine就是這么做的)，也難以正常運行，還需要解決的是對于同樣的功能所依賴的運行時庫也需要轉換成當前平臺的。另一種，就是運行在虛擬機上的，通常包括寄存器式虛擬機和棧式虛擬機，前者典型的有Lua虛擬機、安卓的Dalvik虛擬機，后者有Java虛擬機、Python虛擬機，這里就以生成寄存器式虛擬機上的指令(通常也稱字節(jié)碼)為例。
首先的問題是如何設計一套字節(jié)碼將所有源代碼(可以是中間代碼)的操作正確表達出來。最開始從高級語言生成中間代碼的時候也經常需要為后續(xù)目標代碼的生成作考慮，同樣從中間代碼生成目標代碼時，必須得考慮運行期間數據是如何組織的，硬件之間是怎樣協(xié)作的，才好針對性的設計需要的指令。對于目標代碼，實現同樣的功能，可以有多種方式，就有一個問題：對于同樣的功能如何使用盡量少的指令或者盡量少的內存訪問次數？因此指令選擇也是優(yōu)化的一部分，不過在設計一套自圓其說的系統(tǒng)之初不必考慮這些，用盡量少的指令讓系統(tǒng)運行起來再說。所以目標代碼可以模仿 RISC (Reduced Instruction Set Computing)精簡指令集來設計，提供基本的指令，復雜一點的功能就用多條指令進行組合。
對于基于寄存器的虛擬機，一般是先將內存數據加載到寄存器，然后從寄存器里面取值運算，最終結果也存放到寄存器。當然這里的寄存器實際也是內存模擬的，寄存器包括特定目的寄存器與一些通用寄存器。根據指令的功能，一般可以分為這幾類
這里只是列舉了基本的幾類指令，要支持面向對象等高級特性，通常還要包括面向對象相關的操作指令，如創(chuàng)建實例對象、調用實例方法、獲取字段等；數組相關的，如創(chuàng)建新的數組、獲取指定位置的數組元素，數組元素賦值、獲取數組長度等。當然，也可以不需要上述的指令，對于某些實現了運算符重載的語言，會這樣翻譯代碼
1 + 2 => 1.add(2)也就是所有的基本運算經過編譯器都轉換成了函數調用，默認情況下直接通過內建函數來進行運算了。
還需要考慮的問題，如果運行期希望盡可能少的依賴類、字段等元信息，可以對同一個運算設計不同類型的操作指令，如下
// 將寄存器r1和r2里的int類型數字進行加法運算，結果存到r3iadd r1,r2,r3// 將寄存器r1和r2里的float類型數字進行加法運算，結果存到r3fadd r1,r2,r3生成目標代碼時直接根據類型信息生成不同的指令。對于指令的設計還有幾個需要考慮的問題，一是每條指令占用的空間是多少？ 每條指令包括了操作碼和操作數 ，操作碼表示的是指令具體的含義，如進行加法運算。對于操作碼，用1字節(jié)來存儲，可以包含256類不同的指令，肯定用不到這么多，留作擴展。然后看操作數，操作數通常包括寄存器、立即數、偏移量等，要知道操作數占用多少字節(jié)，通常需要考慮 尋址模式 ，也就是指令通過怎樣的方式訪問、存儲數據。一般對于所有的指令，可以歸類到幾種尋址模式。然后對于具體的操作數，寄存器用１字節(jié)存儲，立即數暫時只支持較小的數，也用1字節(jié)存儲，偏移量用兩字節(jié)存儲。
前兩者不用多說，這里看看偏移量，在不同的環(huán)境下含義不同，舉例說明。參考真實的計算機，CPU一般會設置一些寄存器，用作特殊目的，如BP寄存器存放?；?，SP寄存器存放當前棧頂地址，PC寄存器存放下一要運行的指令，對于局部變量的訪問通常就翻譯成當前?；A地址+偏移量；對于不存放在棧中的全局變量或者常量，也同樣要有個起始地址+偏移量，小的數可以直接當做立即數編碼到指令中，數值較大的數就可以存放到常量池。指令里面存放的是常量池偏移，運行期再從常量池加載到寄存器中，這樣做還有一個好處，對于代碼中引用的所有常量都只在常量池存放一份，實際減少了最終程序文件的大??；偏移量還可作為發(fā)生跳轉時，目標指令在代碼段中的偏移地址。
所以根據操作碼以及尋址模式，可以確定每條指令占用的字節(jié)數。機器執(zhí)行代碼時通常按取指、譯碼、執(zhí)行的順序。在對目標代碼譯碼時，直接根據操作碼及尋址模式，去取對應大小的操作數，并可以確定哪幾字節(jié)的操作數是什么。所以操作碼可以這樣設計
class Opcode { // 操作碼 byte opcode // 尋址模式 int addressingMode static Opcode get(byte opcode) { return opcodeMap.get(opcode) }}這個只是內存的結構，將程序編譯后實際輸出外部文件時，只需要1字節(jié)操作碼。對于一條指令，可以這樣表示
class Instruction { // 操作碼對象 Opcode opcode // 操作數 Operand[] operands // 將指令解碼 Instruction decode(ByteReader reader) { byte code = reader.readByte() Opcode opcode = Opcode.get(code) Operands[] operands switch(opcode.addressingMode) { case MODE1: operands = Operand[2] operands[0] = Operand(code.readByte()) operands[1] = Operand(code.readShort()) break case MODE2: ... } return Instruction(opcode, operands) } // 指令編碼 byte[] encode() { int len = getInsLength() byte[] bytes = byte[len] bytes[0] = opcode.opcode switch(opcode.addressingMode) { case MODE1: bytes[1] = operands[0].getVal() int val = operands[1].getVal() bytes[2] = (val >> 8) & 0xff bytes[3] = val & 0xff break case MODE2: ... } return bytes }}上述同樣給出了對于指令編解碼的偽代碼，解碼時根據讀取的1字節(jié)內容去獲取到對應的操作碼對象，再根據尋址模式繼續(xù)取操作數；要輸出外部文件時直接將所有指令對象編碼轉換為字節(jié)數組并合并。需要注意的是，存儲與讀取的字節(jié)序需要保持一致。這里這樣設計是為了同時方便代碼生成和運行期虛擬機進行解碼執(zhí)行。
調用約定描述了當發(fā)生函數調用時，參數是怎樣傳遞的、調用如何返回、以及過程中分配的堆棧是由調用方還是被調用方來清理，這些問題是生成目標代碼時必須考慮的。
對于參數傳遞，現代編譯器普遍的做法是優(yōu)先使用寄存器傳遞，參數個數較多時改用棧傳遞，這里不考慮寄存器分配的問題，統(tǒng)一采用棧傳遞。通常是從右向左將參數入棧，因為對于實際的計算機，棧是從高地址到低地址的方式增長，傳遞參數時通常還在上一棧的棧幀(內存地址較高的位置)，函數調用時已經位于新的棧幀了(內存較低的位置)，函數內的指令要訪問參數，就得根據當前棧幀的起始地址+偏移量得到。
除了參數傳遞，發(fā)生函數調用時，還有以下幾個問題。
這個在編譯期間就能確定，函數調用開始時，直接將棧頂指針向下移動指定大小即可。
發(fā)生函數調用時，將下一條指令的地址放入當前棧幀，函數調用遇到返回指令時直接將棧幀中保存的地址放入PC寄存器；對于返回值，直接使用一個固定的寄存器存放即可。
這個也是，早生成目標代碼時，直接在函數調用指令后面插入回收參數所占用空間的大小的指令即可。
整個過程舉個簡單的例子，如下
int add(int a, int b) { int c = 3, d = 4 return a + b }add(1, 2)編譯器最終會轉換成如下形式的代碼
# function add:// 函數開始序言push bpmove sp,bpdec sp,0// 給當前函數的局部變量賦值store 3,bp,-1store 4,bp,-2// 從當前運行棧加載參數到寄存器load bp,3,r1load bp,4,r2iadd r1,r2,r3// 函數尾聲move bp,sppop bpmove r3,rvret// 函數調用push 2push 1call add// 回收?？臻ginc sp,2解釋一下，bp、sp分別表示?；?、棧頂指針寄存器，r1、r2、r3都是通用寄存器，rv寄存器專門用來存放函數返回值。push指令表示將值壓入當前棧頂，棧頂指針會向下移動，pop指令則將棧頂的值彈出到寄存器，棧頂指針向上移動。call指令表示調用指定的函數(子程序)，call指令會把下一條指令的地址保存到當前棧內存，ret指令會將該地址彈出放入pc寄存器。函數開始時，會將當前?；反娣诺綏Ｖ?，并把當前的棧頂作為下一幀的棧底。函數調用結束時則將當前棧底又變回棧頂，并從內存中將上一幀的棧底地址取出。內存布局見下圖
根據上圖，對照代碼一目了然，如函數內部訪問參數，第一個參數實際上就是當前bp+3, 第二參數是當前bp+4。兩個參數，在執(zhí)行完后需要回收?？臻g。r
可以注意到的是，函數開始和結束的邏輯是固定的，在生成目標代碼時需要給每個函數插入序言和尾聲。即如下兩部分
// 序言push bpmove sp,bp // bp=spdec sp,函數局部變量占用空間// 尾聲move bp,sp // sp=bppop bp其實對于函數局部變量大小的空間不用考慮，因為函數結束時直接將當前bp變成了棧頂，不過手動清空更好一點，否則可能出現下次函數調用如果使用到這塊空間，對于沒初始化的變量獲取到意外的值。
這篇博客編譯器的前端、后端到運行時以及一些語言特性的實現方式均有涉獵，不過編譯原理相關的知識點確實多而雜。特別是寫后端時發(fā)現不怎么好組織，前端部分有比較固定的套路，后端不同的編譯器、運行時的實現差別太大。細心的讀者能注意到，通篇充滿“可以”、“一般”、“通?！边@樣的詞，是因為走出書本的理論，工程上的實現靈活性很大，所以不必拘泥于死的理論，多多實踐，這篇博客就先到這里了。
聯(lián)系客服
