編譯器在經(jīng)過(guò)詞法分析、語(yǔ)法分析之后，就把源代碼變成了抽象語(yǔ)法樹(shù)（AST）。
接下來(lái)，編譯器的任務(wù)就是把AST變成機(jī)器碼。
AST，是一個(gè)表示代碼邏輯的樹(shù)形結(jié)構(gòu)，它是不能直接順序遍歷的，而只能遞歸遍歷。
遞歸遍歷的邏輯更復(fù)雜，不適合用在機(jī)器碼、匯編碼、字節(jié)碼上。
越是底層代碼越貼近數(shù)字電路，而數(shù)字電路不適合直接處理復(fù)雜的邏輯。
遞歸也屬于復(fù)雜的邏輯，
所以C語(yǔ)言的入門程序之一就是“漢諾塔”，而數(shù)學(xué)歸納法可以成為一種常用的證明方法。
AST的樹(shù)形結(jié)構(gòu)，肯定是不適合直接在CPU上運(yùn)行的，而要先把它變成機(jī)器碼。
AST是怎么變成機(jī)器碼的？
1，語(yǔ)義分析，
語(yǔ)義分析的作用有3個(gè)：
1）類型檢查，
2）常量表達(dá)式的計(jì)算，
3）函數(shù)重載，
如果不是OOP語(yǔ)言，語(yǔ)義分析時(shí)不需要考慮函數(shù)重載問(wèn)題。
語(yǔ)義分析最主要的作用還是類型檢查。
編譯器報(bào)出來(lái)的很多錯(cuò)誤或警告信息，都是類型檢查時(shí)給出來(lái)的，例如：
A* p = malloc(sizeof(A));
在C++中就會(huì)報(bào)錯(cuò)：從void指針到A的指針沒(méi)有加類型轉(zhuǎn)換（type cast）。
AST
賦值運(yùn)算符=兩邊的類型，是語(yǔ)義分析時(shí)首先要檢查的（其他運(yùn)算符也一樣）。
如果類型不匹配，在強(qiáng)類型語(yǔ)言的編譯器里就要給出錯(cuò)誤提示。
另外，sizeof(A) 都是常量表達(dá)式，也要在語(yǔ)義分析時(shí)計(jì)算出來(lái)。
把常量表達(dá)式提前在編譯時(shí)計(jì)算出來(lái)，可以提高運(yùn)行時(shí)的速度。
如果是腳本語(yǔ)言的解釋器的話，在語(yǔ)義分析之后，就可以直接在AST運(yùn)行了：
給每個(gè)運(yùn)算符節(jié)點(diǎn)定義一個(gè)處理函數(shù)，該調(diào)用哪個(gè)就調(diào)用哪個(gè)，就可以得出程序的結(jié)果；
if / while / for 等分支循環(huán)的關(guān)鍵字，也可以一樣看做是運(yùn)算符。
如果是編譯器或虛擬機(jī)，還需要繼續(xù)往下處理。
虛擬機(jī)也是運(yùn)行機(jī)器碼的，只是和CPU的機(jī)器碼不一樣：虛擬機(jī)的機(jī)器碼一般叫字節(jié)碼。
2，三地址碼的生成，
三地址碼，是編譯器的后端常用的中間代碼。
生成了三地址碼之后，就把AST的樹(shù)形結(jié)構(gòu)變成了順序結(jié)構(gòu)了，跟匯編碼、機(jī)器碼、字節(jié)碼一樣了。
struct A { int x, y; };
A* p = malloc(sizeof(A));
生成的三地址碼是這樣的：
call ret; malloc, 8
assign p; ret
第一個(gè)詞是三地址碼的指令（opcode），分號(hào)前面的是目的操作數(shù)（dst operand），分號(hào)后面的是源操作數(shù)列表（src operands list），多個(gè)源操作數(shù)之間以逗號(hào)分隔。
按照源代碼的執(zhí)行順序，把AST遍歷一遍，就可以生成三地址碼。
源代碼里分為順序語(yǔ)句、if else語(yǔ)句、while語(yǔ)句、for語(yǔ)句等等，每種語(yǔ)句類型生成的三地址碼是不一樣的。
if else語(yǔ)句的三地址碼會(huì)有分支跳轉(zhuǎn)：往函數(shù)的結(jié)尾方向跳轉(zhuǎn)。
while語(yǔ)句、for語(yǔ)句的三地址碼會(huì)有循環(huán)跳轉(zhuǎn)：往函數(shù)的開(kāi)頭方向跳轉(zhuǎn)。
for (i = 0; i < 10; i++) printf("%dn", i);
上述for循環(huán)的AST和三地址碼
從圖中可以看出來(lái)，三地址碼跟匯編碼的差異非常??！
匯編碼，是機(jī)器碼的人類閱讀版[呲牙]
生成了三地址碼之后，把它變成機(jī)器碼還是很容易的（如果不考慮運(yùn)行效率的話）。
編譯器后端的各種優(yōu)化，主要還是為了讓生成的機(jī)器碼運(yùn)行更快，而不僅僅是為了讓機(jī)器碼運(yùn)行正確。
編譯器的后端優(yōu)化是個(gè)無(wú)底洞，因?yàn)槌绦騿T對(duì)代碼的理解總是比編譯器更深刻。
畢竟程序員是個(gè)大活人，而編譯器有賴于程序員給它升級(jí)版本。
3，正確運(yùn)行相關(guān)的優(yōu)化，
加載（load）和保存（save）指令的位置，都是跟機(jī)器碼的正確運(yùn)行相關(guān)的優(yōu)化。
除非每條運(yùn)算指令都把結(jié)果寫到內(nèi)存，否則加載和保存指令的位置必須正確。
加載指令的位置在基本塊的開(kāi)頭，保存指令的位置在基本塊的末尾。
基本塊，指的是沒(méi)有跳轉(zhuǎn)指令的順序語(yǔ)句塊。
for (i = 0; i < 10; i++) printf("%dn", i);
還是以前面的for循環(huán)為例子：
assign i, 0
這就是第1個(gè)基本塊，因?yàn)榻酉聛?lái)就要比較 i < 10了，而且還可能從后面跳回來(lái)多次比較。
cmp i, 10
這是第2個(gè)基本塊，接下來(lái)會(huì)根據(jù)i < 10的比較結(jié)果進(jìn)行跳轉(zhuǎn)。
call printf, "%dn", i
inc i
這兩行是第3個(gè)基本塊，它們之間也沒(méi)有跳轉(zhuǎn)，而再往后就要跳轉(zhuǎn)回開(kāi)頭，再次檢查條件表達(dá)式。
跳轉(zhuǎn)的源位置和跳轉(zhuǎn)的目的位置，都是一個(gè)新的基本塊的開(kāi)始位置：
因?yàn)樗鼈儯ㄇ懊婊蚝竺妫┑拇a的執(zhí)行分支是可能變化的，所以要單獨(dú)劃到一個(gè)基本塊里。
for循環(huán)的流程圖
如果在某個(gè)基本塊里修改了某個(gè)變量，就要在末尾把它保存到內(nèi)存。
如果在某個(gè)基本塊里要使用某個(gè)變量，就要在開(kāi)頭把它加載到寄存器。
如上圖：
對(duì) i 賦值 0 之后要把它保存到內(nèi)存，見(jiàn)綠色的save i指令；
在比較i < 10之前要把它從內(nèi)存加載到寄存器，見(jiàn)綠色的load i指令。
這樣生成指令，就可以保證運(yùn)行結(jié)果的正確。
但為了讓它運(yùn)行的更快，一般會(huì)把循環(huán)內(nèi)的加載放到循環(huán)的開(kāi)頭，把循環(huán)內(nèi)的保存放到循環(huán)的末尾。
當(dāng)然，這么做的前提是：循環(huán)的出口和入口必須都是唯一的。
goto不受待見(jiàn)，從編譯器的層面來(lái)看，就是goto會(huì)導(dǎo)致循環(huán)的出口和入口有多個(gè)。
4，變量之間的沖突，
互相沖突的變量不能使用相同的寄存器，這是寄存器分配的原則。
怎么判斷變量之間互相沖突呢？
就是某個(gè)變量如果在后面還要用，那么它跟其他變量就是沖突的。
例如：
a = 1;
b = 2;
c = a + b;
那么a和b就是沖突的。
因?yàn)?strong>第3行代碼都要用到它們兩個(gè)，所以在第2行代碼的時(shí)候：a占用的寄存器不能騰出來(lái)，b必須找其他寄存器用。
第3行代碼之后，a和b都沒(méi)用了，c可以跟a或b的任何一個(gè)使用相同的寄存器。
所以上面的代碼翻譯成匯編，可以這樣：
mov eax, 1
mov ebx, 2
add eax, ebx
a和c都使用eax，b使用ebx。
但是a和b不能都使用eax，否則結(jié)果就是錯(cuò)的。
變量之間是否沖突，要從后往前看。
編譯器里在檢查變量的沖突時(shí)，都是從函數(shù)的末尾往開(kāi)頭反向遍歷每一條代碼，看看哪些變量之間是沖突的。
有興趣的可以看看我寫的scf編譯器框架的代碼，在文件scf_basic_block.c里。
5，寄存器的分配，
確定了變量之間的沖突情況之后，就可以給代碼里的變量分配寄存器了。
例如：
a = 2;
b = 3;
c = 4;
d = a + b + c;
這個(gè)例子的abc三者之間都是沖突的，因?yàn)樵诘?行同時(shí)用到了它們3個(gè)。
畫個(gè)變量的沖突圖如下：
變量的沖突圖
a, b, c之間是互相沖突的，每一對(duì)沖突的變量之間有一條連線，所以正好畫成一個(gè)三角形。
在分配寄存器時(shí)，abc互相之間不能分配相同的寄存器。
也就是說(shuō)，把寄存器的編號(hào)作為顏色的話，上圖三角形的3個(gè)頂點(diǎn)不能著同樣的顏色。
在變量的沖突圖上，每一條邊的兩個(gè)端點(diǎn)必須著不同的顏色。
這就是用于寄存器分配的圖的著色算法。
分配完寄存器之后就好辦了，按照每種CPU的手冊(cè)生成指令的機(jī)器碼就可以了。
例如：
給a, b, c分別分配eax, ebx, ecd，
d與a共用eax，
那么匯編指令就是：
mov eax, 2
mov ebx, 3
mov ecx, 4
add eax, ebx
add eax ecx.
x64的機(jī)器碼我實(shí)在記不住，但在匯編層面，我還是可以充當(dāng)個(gè)人形編譯器的[大笑]
有興趣的可以看看我的scf編譯器框架的源碼，非常的清晰。
編譯原理（龍書）確實(shí)沒(méi)怎么細(xì)說(shuō)后端是怎么寫的，只是提了一下圖的著色算法。
不過(guò)對(duì)于我來(lái)說(shuō)，我只要知道有這么個(gè)軟件，我就能把它寫出來(lái)！
求個(gè)贊賞[捂臉]
雖然重陽(yáng)一生不弱于人，但還是要靠九陰真經(jīng)來(lái)破解古墓派的武功啊。
