編譯器最基本的功能就是把高級語言(例如C/Fortran)編寫的代碼轉(zhuǎn)化為機器指令(就是01串)，從這個角度來說它本質(zhì)上是個轉(zhuǎn)換過程。經(jīng)典的編譯過程主要包括：

1、詞法分析(Lexical Analysis)
詞法分析就是從輸入代碼中識別出各種記號(token)，例如對于C語言我們就需要知道if,else等是語言的關(guān)鍵字，myvar是個標識，而123myvar不能被識別為一個標識。負責(zé)實現(xiàn)詞法分析的模塊有時也稱為scanner。
詞法分析的關(guān)鍵當然是語言定義的規(guī)則了，比如哪些是關(guān)鍵詞，哪些是合法的標識等，這些規(guī)則一般是通過正則表達式(RE，Regular Expression)來給出，運行時從輸入緩沖區(qū)中讀入一部分，然后看和哪個RE匹配就知道它到底是個什么token。
下一個問題就是正則表達式的匹配過程如何實現(xiàn)，經(jīng)典理論對此都會提到有限狀態(tài)機(FSM, Finite State Machine)。關(guān)于FSM在可行性計算里一般都會有不少篇幅分析，在編譯里談到的FSM和RE主要是如何從輸入的構(gòu)成出對應(yīng)的FSM。構(gòu)造的過程一般分為三個步驟，(1)根據(jù)Thompson構(gòu)造法從RE構(gòu)造出對應(yīng)的非確定性有限狀態(tài)機(NFA, Non-deterministic Automata)，(2)經(jīng)過不斷計算epison-閉包(也成為可到達集)構(gòu)造出確定性有限狀態(tài)機(DFA, deterministic Automata), (3)將DFA最小化，方法是增量式地合并不可區(qū)分(對于同一輸入的下一個狀態(tài)都一樣)的兩個狀態(tài)。

2、語法分析

語法分析的輸入是一連串的token(詞法分析的輸出)，根據(jù)語言的語法規(guī)則不斷解析最后得到一棵抽象語法樹(AST, Abstract Syntax Tree)，負責(zé)語法分析模塊通常也被叫做Parser。在詞法分析中，我們經(jīng)常使用正則表達式來表示語言所接受的token的規(guī)則，類似的，在語法分析中，我們使用文法(Grammar)來表示語言的語法規(guī)則，這也早期計算機語言設(shè)計中的研究熱點(同樣也是大學(xué)里學(xué)習(xí)編譯時最容易讓人頭暈的東西)。

編譯里常說的文法指的是一種上下文無關(guān)文法(Context-Free Grammar)，簡單地說文法里包含終結(jié)符(terminal，就是26個字符、數(shù)字等等)、非終結(jié)符(nonterminal，實際是一種抽象)和產(chǎn)生式(production)。上下文無關(guān)文法要求每個產(chǎn)生式的左邊必須恰好是一個非終結(jié)符，而右邊是0個或多個終結(jié)符與非終結(jié)符的組合，最后整個文法還必須有一個起始符(某個終結(jié)符)。文法里還有些很重要的基本概念，例如推導(dǎo)(derivation)、歸約(reduction)、二義性(ambiguity)、最左推導(dǎo)等等。

文法中最重要的基本概念是FIRST集和FOLLOW集的構(gòu)造。根據(jù)這兩個集合就可以很容易構(gòu)造出一個預(yù)測分析表，每個行的名字是一個非終結(jié)符，每個列的名字是一個終結(jié)符，如果每個表格內(nèi)沒有兩個以上的項，那么說明是一個LL(1)文法(Left-to-right parse, Leftmost-derivation, 1-symbol lookhead)，簡單地說就是向右邊看一個符號就能確定下一步動作。當原文法不是LL(1)文法時，可以嘗試通過消除左遞歸(Eliminate Left Recursion)和提取左因子(Left Factoring)對原文法進行變形得到等價的LL(1)文法。

第二種文法就是LR(k)文法(Left-to-right parse, Rightmost derivation, k-token lookhead)。這種文法的解釋過程一般通過棧輔助實現(xiàn)，中間主要有兩種動作：shift（就是將當前輸入入棧）和reduce（選擇產(chǎn)生式并從棧中彈出符號執(zhí)行歸約操作）。LR(0)的構(gòu)成過程就是從起始符所在的產(chǎn)生式開始構(gòu)造item，然后對每個item針對每個可能的input構(gòu)造它的出邊(同樣還是一個item)，最終所有的item形成一個有限狀態(tài)機。接下來構(gòu)造有限狀態(tài)機，對于每個狀態(tài)，如果出邊是一個終結(jié)符，在對應(yīng)表格記入shift操作，如果是非終結(jié)符則記入goto操作。如果S->x.這種item集，那么對每個終結(jié)符r，都記入(S, r)位置處為shift操作。

第三種SLR文法與LR(0)非常相似，區(qū)別在于生成分析表格時，對于S->x.這種item集，僅僅對于r輸入FOLLOW(S)才在(S, r)位置處記入shift操作。

最后一種LALR(1)相對于LR(0)而言引入了活前綴，構(gòu)造思路仍與LR(0)類似，但是構(gòu)造出來的預(yù)測分析表更大。

綜合起來，各文法表述能力：LL(0)<LR(0)<SLR<LALR(1)<LR(1)<LR(k)，LL(1)<LR(1)

3、語義分析(Sematic Analysis)
語義分析包括一些經(jīng)典的問題。
(1)類型檢查(Type Checking)，例如在語法樹上a+b看起來是沒問題的，因為a和b都是合法的變量名，并且語法中支持變量間+這種操作。但是可能a是一個字符串，而b是一個浮點數(shù)，這兩者之間的+操作就不符合語義規(guī)范了，這種問題在這個階段都會被找出來。
(2)符號管理，最經(jīng)典的問題就是如何管理變量(變量的名字，類型，變量的作用域(scope)等)，在分析代碼時，符號管理肯定是被頻繁的搜索，因此它通常會使用hash來組織。

4、中間代碼(IR, intermediate Representation)生成
              IR是非常非常重要的，它被引入的初衷是提高編譯器開發(fā)的效率。IR是編譯過程的一個匯聚點，在IR之前我們通常都認為是編譯的前端，而IR之后是編譯的后端，這樣當編譯器需要多支持一種高級語言時主要工作就是提供一個前端，而當需要移植到一種新的平臺上時主要工作就是提供對應(yīng)的后端。關(guān)于IR的表示典型的有三地址碼。IR生成的過程就是將一棵抽象語法樹(這是編譯器前端對源代碼的理解和抽象)變成一串IR定義的代碼(IR指令種類簡單，這便于優(yōu)化)。這個轉(zhuǎn)換過程都是比較固定的套路，例如if-else，while/for等基本結(jié)構(gòu)如何轉(zhuǎn)都是一個固定的套路。

5、編譯優(yōu)化
              這一部分是現(xiàn)代編譯器最核心所在，主要有兩類，一類是通用的優(yōu)化手段，比如死代碼刪除、循環(huán)不變量外提、強度削弱等，另一類就是體系結(jié)構(gòu)相關(guān)的，說白了就是某種體系結(jié)構(gòu)針對某類應(yīng)用提供了特殊指令，例如intel的MMX，SSE2等等。為支持優(yōu)化工作的開展，我們首先需要能夠比較方便的描述代碼。最基本的當然是一條指令，但是這個太細微，于是往上抽象出基本塊(Basic Block)，這個基本上是所有優(yōu)化開展必備的工作，然后多個基本塊還可以構(gòu)成一個超級塊(region)。此外，經(jīng)典的方法還包括控制流分析和數(shù)據(jù)流分析，這里常用的包括d-u鏈等。最后一個經(jīng)典的topic就是寄存器分配。

6、目標代碼生成
這里直接和具體平臺相關(guān)，這里的平臺同時包括軟件和硬件，例如哪種目標文件格式(ELF, PE)，哪種平臺(指令集)。不過現(xiàn)在編譯器一般生成的是字符形式的匯編文件，所以前面一個問題基本不大，主要影響在后者。