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