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