編譯器最基本的功能就是把高級(jí)語言(例如C/Fortran)編寫的代碼轉(zhuǎn)化為機(jī)器指令(就是01串)，從這個(gè)角度來說它本質(zhì)上是個(gè)轉(zhuǎn)換過程。經(jīng)典的編譯過程主要包括：
1、詞法分析(Lexical Analysis)
詞法分析就是從輸入代碼中識(shí)別出各種記號(hào)(token)，例如對于C語言我們就需要知道if,else等是語言的關(guān)鍵字，myvar是個(gè)標(biāo)識(shí)，而123myvar不能被識(shí)別為一個(gè)標(biāo)識(shí)。負(fù)責(zé)實(shí)現(xiàn)詞法分析的模塊有時(shí)也稱為scanner。
詞法分析的關(guān)鍵當(dāng)然是語言定義的規(guī)則了，比如哪些是關(guān)鍵詞，哪些是合法的標(biāo)識(shí)等，這些規(guī)則一般是通過正則表達(dá)式(RE，Regular Expression)來給出，運(yùn)行時(shí)從輸入緩沖區(qū)中讀入一部分，然后看和哪個(gè)RE匹配就知道它到底是個(gè)什么token。
下一個(gè)問題就是正則表達(dá)式的匹配過程如何實(shí)現(xiàn)，經(jīng)典理論對此都會(huì)提到有限狀態(tài)機(jī)(FSM, Finite State Machine)。關(guān)于FSM在可行性計(jì)算里一般都會(huì)有不少篇幅分析，在編譯里談到的FSM和RE主要是如何從輸入的構(gòu)成出對應(yīng)的FSM。構(gòu)造的過程一般分為三個(gè)步驟，(1)根據(jù)Thompson構(gòu)造法從RE構(gòu)造出對應(yīng)的非確定性有限狀態(tài)機(jī)(NFA, Non-deterministic Automata)，(2)經(jīng)過不斷計(jì)算epison-閉包(也成為可到達(dá)集)構(gòu)造出確定性有限狀態(tài)機(jī)(DFA, deterministic Automata), (3)將DFA最小化，方法是增量式地合并不可區(qū)分(對于同一輸入的下一個(gè)狀態(tài)都一樣)的兩個(gè)狀態(tài)。
2、語法分析
語法分析的輸入是一連串的token(詞法分析的輸出)，根據(jù)語言的語法規(guī)則不斷解析最后得到一棵抽象語法樹(AST, Abstract Syntax Tree)，負(fù)責(zé)語法分析模塊通常也被叫做Parser。在詞法分析中，我們經(jīng)常使用正則表達(dá)式來表示語言所接受的token的規(guī)則，類似的，在語法分析中，我們使用文法(Grammar)來表示語言的語法規(guī)則，這也早期計(jì)算機(jī)語言設(shè)計(jì)中的研究熱點(diǎn)(同樣也是大學(xué)里學(xué)習(xí)編譯時(shí)最容易讓人頭暈的東西)。
編譯里常說的文法指的是一種上下文無關(guān)文法(Context-Free Grammar)，簡單地說文法里包含終結(jié)符(terminal，就是26個(gè)字符、數(shù)字等等)、非終結(jié)符(nonterminal，實(shí)際是一種抽象)和產(chǎn)生式(production)。上下文無關(guān)文法要求每個(gè)產(chǎn)生式的左邊必須恰好是一個(gè)非終結(jié)符，而右邊是0個(gè)或多個(gè)終結(jié)符與非終結(jié)符的組合，最后整個(gè)文法還必須有一個(gè)起始符(某個(gè)終結(jié)符)。文法里還有些很重要的基本概念，例如推導(dǎo)(derivation)、歸約(reduction)、二義性(ambiguity)、最左推導(dǎo)等等。
文法中最重要的基本概念是FIRST集和FOLLOW集的構(gòu)造。根據(jù)這兩個(gè)集合就可以很容易構(gòu)造出一個(gè)預(yù)測分析表，每個(gè)行的名字是一個(gè)非終結(jié)符，每個(gè)列的名字是一個(gè)終結(jié)符，如果每個(gè)表格內(nèi)沒有兩個(gè)以上的項(xiàng)，那么說明是一個(gè)LL(1)文法(Left-to-right parse, Leftmost-derivation, 1-symbol lookhead)，簡單地說就是向右邊看一個(gè)符號(hào)就能確定下一步動(dòng)作。當(dāng)原文法不是LL(1)文法時(shí)，可以嘗試通過消除左遞歸(Eliminate Left Recursion)和提取左因子(Left Factoring)對原文法進(jìn)行變形得到等價(jià)的LL(1)文法。
第二種文法就是LR(k)文法(Left-to-right parse, Rightmost derivation, k-token lookhead)。這種文法的解釋過程一般通過棧輔助實(shí)現(xiàn)，中間主要有兩種動(dòng)作：shift（就是將當(dāng)前輸入入棧）和reduce（選擇產(chǎn)生式并從棧中彈出符號(hào)執(zhí)行歸約操作）。LR(0)的構(gòu)成過程就是從起始符所在的產(chǎn)生式開始構(gòu)造item，然后對每個(gè)item針對每個(gè)可能的input構(gòu)造它的出邊(同樣還是一個(gè)item)，最終所有的item形成一個(gè)有限狀態(tài)機(jī)。接下來構(gòu)造有限狀態(tài)機(jī)，對于每個(gè)狀態(tài)，如果出邊是一個(gè)終結(jié)符，在對應(yīng)表格記入shift操作，如果是非終結(jié)符則記入goto操作。如果S->x.這種item集，那么對每個(gè)終結(jié)符r，都記入(S, r)位置處為shift操作。
第三種SLR文法與LR(0)非常相似，區(qū)別在于生成分析表格時(shí)，對于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看起來是沒問題的，因?yàn)閍和b都是合法的變量名，并且語法中支持變量間+這種操作。但是可能a是一個(gè)字符串，而b是一個(gè)浮點(diǎn)數(shù)，這兩者之間的+操作就不符合語義規(guī)范了，這種問題在這個(gè)階段都會(huì)被找出來。
(2)符號(hào)管理，最經(jīng)典的問題就是如何管理變量(變量的名字，類型，變量的作用域(scope)等)，在分析代碼時(shí)，符號(hào)管理肯定是被頻繁的搜索，因此它通常會(huì)使用hash來組織。
4、中間代碼(IR, intermediate Representation)生成
IR是非常非常重要的，它被引入的初衷是提高編譯器開發(fā)的效率。IR是編譯過程的一個(gè)匯聚點(diǎn)，在IR之前我們通常都認(rèn)為是編譯的前端，而IR之后是編譯的后端，這樣當(dāng)編譯器需要多支持一種高級(jí)語言時(shí)主要工作就是提供一個(gè)前端，而當(dāng)需要移植到一種新的平臺(tái)上時(shí)主要工作就是提供對應(yīng)的后端。關(guān)于IR的表示典型的有三地址碼。IR生成的過程就是將一棵抽象語法樹(這是編譯器前端對源代碼的理解和抽象)變成一串IR定義的代碼(IR指令種類簡單，這便于優(yōu)化)。這個(gè)轉(zhuǎn)換過程都是比較固定的套路，例如if-else，while/for等基本結(jié)構(gòu)如何轉(zhuǎn)都是一個(gè)固定的套路。
5、編譯優(yōu)化
這一部分是現(xiàn)代編譯器最核心所在，主要有兩類，一類是通用的優(yōu)化手段，比如死代碼刪除、循環(huán)不變量外提、強(qiáng)度削弱等，另一類就是體系結(jié)構(gòu)相關(guān)的，說白了就是某種體系結(jié)構(gòu)針對某類應(yīng)用提供了特殊指令，例如intel的MMX，SSE2等等。為支持優(yōu)化工作的開展，我們首先需要能夠比較方便的描述代碼。最基本的當(dāng)然是一條指令，但是這個(gè)太細(xì)微，于是往上抽象出基本塊(Basic Block)，這個(gè)基本上是所有優(yōu)化開展必備的工作，然后多個(gè)基本塊還可以構(gòu)成一個(gè)超級(jí)塊(region)。此外，經(jīng)典的方法還包括控制流分析和數(shù)據(jù)流分析，這里常用的包括d-u鏈等。最后一個(gè)經(jīng)典的topic就是寄存器分配。
6、目標(biāo)代碼生成
這里直接和具體平臺(tái)相關(guān)，這里的平臺(tái)同時(shí)包括軟件和硬件，例如哪種目標(biāo)文件格式(ELF, PE)，哪種平臺(tái)(指令集)。不過現(xiàn)在編譯器一般生成的是字符形式的匯編文件，所以前面一個(gè)問題基本不大，主要影響在后者。
聯(lián)系客服
