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