1.
前言
在你看到這篇文章的時候，你一定在想，編譯器啊，真是個麻煩的東西。呃，沒有錯，在撰寫此文的時候，我也一直有著這樣的念頭。本文不能將你從編譯器的苦海里救出來，只是希望它能夠讓你少游一會兒，以盡可能的少喝水。
與一般的文章不同，本文不會涉及到有關(guān)于編譯原理的理論細節(jié)，NFA，DFA，遞歸下降，文法，語法制導(dǎo)翻譯等等概念，都不會深入的追究。但是希望你能有這方面的概念，這樣在討論到一些算法及其實現(xiàn)的時候，不至于理解的太過費力。
本文重點在于利用現(xiàn)有各式各樣的編譯器前端或后端技術(shù)和庫，以可控制和漸增的方式，將我們的編譯器從無到有，從小到大，從簡單到復(fù)雜，從低效到高效的實現(xiàn)出來。本文的寫作目標(biāo)是，我們將編寫編譯器的任務(wù)，分解成多個迭代的階段，其中的大部分階段，你都能夠在理解它之后，在一個小時到一天不等的時間內(nèi)達到預(yù)計的目標(biāo)。這樣我們才有動力進行下去，不是嗎？
唔，自然，這樣的文章需要一個完整的實例貫穿前后。我們決定采用SoftArt項目內(nèi)最復(fù)雜的一個子項目 SoftArt Shader Language作為一個導(dǎo)引，你所看到的行文過程，就是SoftArt
Shader Language的開發(fā)過程。SoftArt開發(fā)到哪里，這篇博文就寫到哪里，我們對SVN發(fā)誓，我們所經(jīng)歷的，你都能看得到。
SoftArt的項目主頁http://code.google.com/p/softart
SoftArt項目介紹頁http://www.shnenglu.com/lingjingqiu/archive/2009/12/07/102698.html
換句話說，我們所走的彎路，你一樣得走（哈哈，被我們坑的），我們所路過的捷徑，一樣也會成為你的捷徑。祝大家好運。
2.
本文的使用說明
在閱讀本文的時候，我們希望您能有以下的基礎(chǔ)：
-
熟悉至少一門高級語言
- 能閱讀帶模板的C++（我們的示例代碼用此所寫）
- 會使用正則表達式
- 了解計算機的工作原理，能閱讀匯編
- 對LL和LR文法有一定的了解
- 掌握基本的數(shù)據(jù)結(jié)構(gòu)和算法
如果您符合以下描述，那么恭喜您，本文就是為您而寫的：
-
需要快速開發(fā)編譯器
- 對編譯原理了解不深
- 對編譯速度和編譯后的程序在性能上要求不甚苛刻
如果您具有以下特征之一，那么本文可能會給您帶來不適，請諒解我們的工作：
- 天然噴
- 紫禁之巔的高手
- 車輪黨
- 反模板聯(lián)盟
3.
一個迷你的虛擬機
哈，我想你一定會問，不是說編譯器么，為什么要先說虛擬機呢？唔……用一句話來回答就是，因為它必要而簡單。還記得編譯原理中描述的一個語言是如何被分析、解釋并執(zhí)行的么？
在詞法分析->低級代碼生成四個階段里，每個階段的輸出都作為下一個階段的輸入。這些輸出通常都是規(guī)范化的，而且都以計算機容易識別的形式保存。依據(jù)這些階段的輸出來判斷程序運作的正常與否，是需要很多經(jīng)驗的。這顯然不是我們所希望的。
那么最后一個階段，低級代碼的執(zhí)行，便成為了最容易實現(xiàn)，也最容易檢驗的階段。在這一階段，我們只需要設(shè)計一個虛擬機便可以達到目的。
唔，虛擬機。是個很可怕的名詞，不是么？沒關(guān)系，對我們的實現(xiàn)來說，虛擬機最大的好處，就在于它可大可小。我們可以實現(xiàn)一個x86一樣指令集的龐然大物，也可以實現(xiàn)一個只有幾條到幾十條我們所需要的指令構(gòu)成的小小玩具。
不過，既然叫虛擬機，那麻雀雖小，五臟俱全。咱們這只小麻雀，看中了誰的五臟呢？一個大家都學(xué)過的典范，8086。還是覺得復(fù)雜了，是嗎？沒關(guān)系，我們先來看看，8086的哪些部分是最必要的，我們只要實現(xiàn)了這一部分，就能讓虛擬機跑起來。
嗯……我們來看看，8086里面，要做一個1+1=2的運算，需要哪些最基礎(chǔ)的設(shè)施呢？通用寄存器，棧，指令寄存器，指令槽，當(dāng)然還有最重要的執(zhí)行引擎。好吧，其余的什么段啊，分頁啊，中斷啊，我們一概不需要。
好，那么我們便用最直截了當(dāng)?shù)姆绞剑堰@些我們需要的設(shè)施拼湊成我們的虛擬機。
class vm{
vector<instruction>
code_buffer;
vector<byte>
stack;
int r[16];
intptr_t
eip;
bool execute(const
instruction& ins);
};
|
唔，有了這些基本的設(shè)備之后，我們得讓它運轉(zhuǎn)起來。我們先設(shè)計一個最簡單的驅(qū)動代碼，這個代碼依次讀入code_buffer里eip位置上的指令，然后執(zhí)行這條指令，執(zhí)行完后，移向下一條，知道指令槽空為止。
class vm{
bool call(){
eip = 0;
while ( eip < code_buffer.size() ){
if( execute(code_buffer[eip]) ){
++eip;
} else {
break;
}
}
}
};
|
知道這個虛擬機怎么去執(zhí)行指令后，還得要定義有哪些指令可以執(zhí)行，每條指令執(zhí)行后會產(chǎn)生什么效果。這些能夠執(zhí)行的指令的集合，就稱為虛擬機的指令集。而后者，需要在我們的執(zhí)行引擎里，編寫實際的執(zhí)行代碼來達到每個指令的效果。
什么？你說要實現(xiàn)x86的指令集？天哪，那些指令僅僅是讀就夠你讀上半天的。一開始，我們只需要實現(xiàn)最基本的幾條指令，告訴我們，這個虛擬機可以works，這個就OK了。我想大家的數(shù)學(xué)都是從1+1=2開始的，這里，我們也用加法運算做為開始。由于咱們這個虛擬機是仿照x86的，所以所有的運算都要在寄存器里完成。所以我們只需要兩條指令便可以完成運算：讀入數(shù)據(jù)到寄存器的指令和在寄存器里執(zhí)行加法的指令，咱們的數(shù)據(jù)類型，只有萬年的32位有符號整數(shù)，簡稱int。
明確了我們需要什么指令，就要設(shè)計指令的格式了。本著抄襲……啊，不，是借鑒x86的精神，我們也將指令設(shè)計成三元組的形式：指令碼，操作數(shù)1，操作數(shù)2
夠用嗎？這個你去問x86，它會告訴你，歷史證明，三元組基本夠用。當(dāng)然，其實我覺得四元組更好使……也許我會把它改成4元組的。唔，咱們不YY，先來看三元組的數(shù)據(jù)結(jié)構(gòu)，簡單明了。
struct instruction{
op_code op;
int arg0;
int arg1;
};
|
真沒啥想頭的，不是嘛？嗯，有了指令的數(shù)據(jù)結(jié)構(gòu)，咱們就可以設(shè)計指令了。
在instruction里，op_code是一個指令碼的枚舉
enum op_code{
op_add,
op_loadrc
};
|
op_add執(zhí)行的是寄存器之間的加法，arg0是目標(biāo)寄存器號（實際上就是寄存器數(shù)組r的下標(biāo)），arg1是源寄存器號；該指令將arg1中的值加到arg0中。
op_loadrc將一個數(shù)值讀入到寄存器中。Arg0是寄存器號，arg1是數(shù)值。
然后在execute里面實現(xiàn)這兩條指令
bool execute (op_code op, int
arg0, int arg1){
switch (op) {
case op_add:
r[arg0]
+= r[arg1]; break;
case op_loadrc: {
int& reg( r[arg0] );
int val = arg1;
reg
= val;
break;
}
}
return true;
}
|
最后，再添上一些輔助性的代碼，這個虛擬機就能夠正常的工作了。不信？咱們可以試試：
int _tmain(int argc, _TCHAR*
argv[])
{
code_generator
cg;
cg
//讀取兩個常量
.op(
op_loadrc, r0, 10 )
.op(
op_loadrc, r1, 67 )
.op(
op_add, r0, r1) //執(zhí)行加法
;
vm machine;
int result = machine.raw_call( cg.codes() );
std::cout
<< result << endl;
system("pause");
return 0;
}
|
呵呵，Run起來吧~
