“手把手教你構(gòu)建 C 語(yǔ)言編譯器” 這一系列教程將帶你從頭編寫一個(gè) C 語(yǔ)言的編譯器奏瞬。希望通過(guò)這個(gè)系列吸祟，我們能對(duì)編譯器的構(gòu)建有一定的了解，同時(shí)，我們也將構(gòu)建出一個(gè)能用的 C 語(yǔ)言編譯器恩沽，盡管有許多語(yǔ)法并不支持。
在開始進(jìn)入正題之前切心，本篇是一些閑聊飒筑，談?wù)勥@個(gè)系列的初衷。如果你急切地想進(jìn)入正篇绽昏，請(qǐng)?zhí)^(guò)本章协屡。
前言
為什么要學(xué)編譯原理
如果要我說(shuō)計(jì)算機(jī)專業(yè)最重要的三門課，我會(huì)說(shuō)是《數(shù)據(jù)結(jié)構(gòu)》全谤、《算法》和《編譯原理》肤晓。在我看來(lái)，能不能理解“遞歸”像是程序員的第一道門檻认然，而會(huì)不會(huì)寫編譯器則是第二道补憾。
（當(dāng)然，并不是說(shuō)是沒(méi)寫過(guò)編譯器就不是好程序員卷员，只能說(shuō)它是一個(gè)相當(dāng)大的挑戰(zhàn)吧）
以前人們會(huì)說(shuō)盈匾，學(xué)習(xí)了編譯原理，你就能寫出更加高效的代碼毕骡，但隨著計(jì)算機(jī)性能的提升削饵，代碼是否高效顯得就不那么重要了岩瘦。那么為什么要學(xué)習(xí)編譯原理呢？
原因只有一個(gè)：裝B窿撬。
好吧启昧，也許現(xiàn)在還想學(xué)習(xí)編譯原理的人只可能是因?yàn)榕d趣了。一方面想了解它的工作原理劈伴；另一方面希望挑戰(zhàn)一下自己密末，看看自己能走多遠(yuǎn)。
理論很復(fù)雜跛璧，實(shí)現(xiàn)也很復(fù)雜严里？
我對(duì)編譯器一直心存敬佩。所以當(dāng)學(xué)校開《編譯原理》的課程后赡模，我是抱著滿腔熱情去上課的田炭，但是兩節(jié)課后我就放棄了师抄。原因是太復(fù)雜了漓柑，聽不懂。
一般編譯原理的課程會(huì)說(shuō)一些：
1叨吮、如何表示語(yǔ)法（BNF什么的）
2辆布、詞法分析，用什么有窮自動(dòng)機(jī)和無(wú)窮自動(dòng)機(jī)
3茶鉴、語(yǔ)法分析锋玲，遞歸下降法，什么 LL(k)涵叮，LALR 分析惭蹂。
4、中間代碼的表示
5割粮、代碼的生成
6盾碗、代碼優(yōu)化
我相信絕大多數(shù)（98％）的學(xué)生頂多學(xué)到語(yǔ)法分析就結(jié)束了。并且最重要的是舀瓢，學(xué)了這么多也沒(méi)用廷雅！依舊幫助不了我們學(xué)習(xí)編譯器！這其中最主要的原因是《編譯原理》試圖教會(huì)我們的是如何構(gòu)造“編譯器生成器”京髓，即構(gòu)造一個(gè)工具航缀，根據(jù)文法來(lái)生成編譯器（如 lex/yacc）等等。
這些理論試圖教會(huì)我們?nèi)绾斡猛ㄓ玫姆椒▉?lái)自動(dòng)解決問(wèn)題堰怨，它們有很強(qiáng)的實(shí)際意義芥玉，只是對(duì)于一般的學(xué)生或程序員來(lái)說(shuō)，它們過(guò)于強(qiáng)大备图，內(nèi)容過(guò)于復(fù)雜灿巧。如果你嘗試閱讀 lex/yacc （或 flex/bison）的代碼皇型，就會(huì)發(fā)現(xiàn)太可怕了。
然而如果你能跟我一樣砸烦，真正來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的編譯器弃鸦，那么你會(huì)發(fā)現(xiàn)，比起可怕的《編譯原理》幢痘，這點(diǎn)復(fù)雜度還是不算什么的（因?yàn)楹枚嗬碚摳居貌簧希?/p>
項(xiàng)目的初衷
有一次在 Github 上看到了一個(gè)項(xiàng)目（當(dāng)時(shí)很火的）唬格，名叫 c4，號(hào)稱用 4 個(gè)函數(shù)來(lái)實(shí)現(xiàn)了一個(gè)小的 C 語(yǔ)言編譯器颜说。它最讓我震驚的是能夠自舉购岗，即能自己編譯自己。并且它用很少的代碼就完成了一個(gè)功能相當(dāng)完善的 C 語(yǔ)言編譯器门粪。
一般的編譯器相關(guān)的教程要么就十分簡(jiǎn)單（如實(shí)現(xiàn)四則運(yùn)算）喊积，要么就是借助了自動(dòng)生成的工具（如 flex/bison）。而 c4 的代碼完全是手工實(shí)現(xiàn)的玄妈，不用外部工具乾吻。可惜的是它的代碼初衷是代碼最小化拟蜻，所以寫得很亂绎签，很難懂。所以本項(xiàng)目的主要目的：
1酝锅、實(shí)現(xiàn)一個(gè)功能完善的 C 語(yǔ)言編譯器
2诡必、通過(guò)教程來(lái)說(shuō)明這個(gè)過(guò)程。
c4 大致500+行搔扁。重寫的代碼歷時(shí)一周爸舒，總共代碼加注釋1400行。項(xiàng)目地址: Write a C Interpreter稿蹲。
聲明：本項(xiàng)目中的代碼邏輯絕大多數(shù)取自 c4 扭勉，但確為自己重寫。
預(yù)警
在寫編譯器的時(shí)候會(huì)遇到兩個(gè)主要問(wèn)題：
1场绿、麻煩剖效，會(huì)有許多類似的代碼，寫起來(lái)很無(wú)聊焰盗。
2璧尸、難以調(diào)試，一方面沒(méi)有很好的測(cè)試用例熬拒，另一方面需要對(duì)照生成的代碼來(lái)調(diào)試（遇到的時(shí)候就知道了）爷光。
所以我希望你有足夠的耐心和時(shí)間來(lái)學(xué)習(xí)，相信當(dāng)你真正完成的時(shí)候會(huì)像我一樣澎粟，十分有成就感蛀序。
雖然標(biāo)題是編譯器欢瞪，但實(shí)際上我們構(gòu)建的是 C 語(yǔ)言的解釋器，這意味著我們可以像運(yùn)行腳本一樣去運(yùn)行 C 語(yǔ)言的源代碼文件徐裸。這么做的理由有兩點(diǎn)：
1遣鼓、解釋器與編譯器僅在代碼生成階段有區(qū)別，而其它方面如詞法分析重贺、語(yǔ)法分析是一樣的骑祟。
2、解釋器需要我們實(shí)現(xiàn)自己的虛擬機(jī)與指令集气笙，而這部分能幫助我們了解計(jì)算機(jī)的工作原理次企。
編譯器的構(gòu)建流程
一般而言，編譯器的編寫分為 3 個(gè)步驟：
1潜圃、詞法分析器缸棵，用于將字符串轉(zhuǎn)化成內(nèi)部的表示結(jié)構(gòu)。
2谭期、語(yǔ)法分析器堵第，將詞法分析得到的標(biāo)記流（token）生成一棵語(yǔ)法樹。
3崇堵、目標(biāo)代碼的生成型诚，將語(yǔ)法樹轉(zhuǎn)化成目標(biāo)代碼。
已經(jīng)有許多工具能幫助我們處理階段1和2鸳劳，如 flex 用于詞法分析，bison 用于語(yǔ)法分析纵搁。只是它們的功能都過(guò)于強(qiáng)大崔赌，屏蔽了許多實(shí)現(xiàn)上的細(xì)節(jié)狠鸳，對(duì)于學(xué)習(xí)構(gòu)建編譯器幫助不大。所以我們要完全手寫這些功能幔摸。
所以我們會(huì)根據(jù)下面的流程：
1、構(gòu)建我們自己的虛擬機(jī)以及指令集颤练。這后生成的目標(biāo)代碼便是我們的指令集既忆。
2、構(gòu)建我們的詞法分析器
3嗦玖、構(gòu)建語(yǔ)法分析器
編譯器的框架
我們的編譯器主要包括 4 個(gè)函數(shù)：
1患雇、next() 用于詞法分析，獲取下一個(gè)標(biāo)記宇挫，它將自動(dòng)忽略空白字符苛吱。
2、program() 語(yǔ)法分析的入口器瘪，分析整個(gè) C 語(yǔ)言程序翠储。
3绘雁、expression(level) 用于解析一個(gè)表達(dá)式。
4援所、eval() 虛擬機(jī)的入口庐舟，用于解釋目標(biāo)代碼。
這里有一個(gè)單獨(dú)用于解析“表達(dá)式”的函數(shù) expression 是因?yàn)楸磉_(dá)式在語(yǔ)法分析中相對(duì)獨(dú)立并且比較復(fù)雜住拭，所以我們將它單獨(dú)作為一個(gè)模塊（函數(shù)）继阻。
因?yàn)槲覀兊脑创a看起來(lái)就像是：
#include
#include
#include
#include
int token; ? ? ? ? ? ?// current token
char *src, *old_src; ?// pointer to source code string;
int poolsize; ? ? ? ? // default size of text/data/stack
int line; ? ? ? ? ? ? // line number
void next() {
? ? token = *src++;
? ? return;
}
void expression(int level) {
? ? // do nothing
}
void program() {
? ? next(); ? ? ? ? ? ? ? ? ?// get next token
? ? while (token > 0) {
? ? ? ? printf("token is: %c\n", token);
? ? ? ? next();
? ? }
}
int eval() { // do nothing yet
? ? return 0;
}
int main(int argc, char **argv)
{
? ? int i, fd;
? ? argc--;
? ? argv++;
? ? poolsize = 256 * 1024; // arbitrary size
? ? line = 1;
? ? if ((fd = open(*argv, 0)) < 0) {
? ? ? ? printf("could not open(%s)\n", *argv);
? ? ? ? return -1;
? ? }
? ? if (!(src = old_src = malloc(poolsize))) {
? ? ? ? printf("could not malloc(%d) for source area\n", poolsize);
? ? ? ? return -1;
? ? }
? ? // read the source file
? ? if ((i = read(fd, src, poolsize-1)) <= 0) {
? ? ? ? printf("read() returned %d\n", i);
? ? ? ? return -1;
? ? }
? ? src[i] = 0; // add EOF character
? ? close(fd);
? ? program();
? ? return eval();
}
上面的代碼看上去挺復(fù)雜，但其實(shí)內(nèi)容不多废酷，就是讀取一個(gè)源代碼文件瘟檩，逐個(gè)讀取每個(gè)字符，并輸出每個(gè)字符澈蟆。這里重要的是注意每個(gè)函數(shù)的作用墨辛，后面的文章中，我們將逐個(gè)填充每個(gè)函數(shù)的功能趴俘，最終構(gòu)建起我們的編譯器睹簇。
本節(jié)的代碼可以在 Github 上下載，也可以直接 clone
git clone -b step-0 https://github.com/lotabout/write-a-C-interpreter
這樣我們就有了一個(gè)最簡(jiǎn)單的編譯器：什么都不干的編譯器寥闪，下一章中太惠，我們將實(shí)現(xiàn)其中的eval函數(shù)，即我們自己的虛擬機(jī)疲憋。
參考資料
最后想介紹幾個(gè)資料：
1凿渊、Let’s Build a Compiler 很好的初學(xué)者教程，英文的缚柳。
2埃脏、Lemon Parser Generator，一個(gè)語(yǔ)法分析器生成器秋忙，對(duì)照《編譯原理》觀看效果更佳彩掐。
祝你學(xué)得愉快。
