一篇文章理解編譯全過程
https://www.cnblogs.com/fisherss/p/13905395.html
編譯過程
編譯目標
目標：把源代碼變成目標代碼
1.如果源代碼在操作系統(tǒng)上運行：目標代碼就是“匯編代碼”。再通過匯編和鏈接的過程形成可執(zhí)行文件，然后通過加載器加載到操作系統(tǒng)執(zhí)行。
2.如果源代碼在虛擬機(解釋器)上運行：目標代碼就是“解釋器可以理解的中間形式的代碼”，比如字節(jié)碼(中間代碼)IR、AST語法樹。
編譯過程可以分為這幾個階段，每個階段做了一定的任務(wù)，層級的讓下一個階段進行。
詞法分析
編譯器讀入源代碼，經(jīng)過詞法分析器識別出Token，把字符串轉(zhuǎn)換成一個個Token。
Token的類型包括：關(guān)鍵字、標識符、字面量、操作符、界符等
比如下面的C語言代碼源文件，經(jīng)過詞法分析器識別出的token有：int、foo、a、b、=、+、return、(){}等token
int foo(int a){
int b = a + 3;
return b;
}
為什么要這樣做呢，把代碼里的單詞進行分類，編譯器后面的階段不就更好處理理解代碼了嘛！
語法分析
每一個程序代碼，實際上可以通過樹這種結(jié)構(gòu)表現(xiàn)出其語法規(guī)則。
語法分析階段把Token串，轉(zhuǎn)換成一個體現(xiàn)語法規(guī)則的、樹狀數(shù)據(jù)結(jié)構(gòu)，即抽象語法樹AST。
AST樹反映了程序的語法結(jié)構(gòu)。
比如下面對應(yīng)的一段C語言代碼，對應(yīng)的AST抽象語法樹如下所示：
int foo(int a){
int b = a + 3;
return b;
}
AST抽象語法樹
AST樹長成什么樣，由語法的結(jié)構(gòu)有關(guān)。
比如 上面C語言代碼中對函數(shù)的語法定義如下：語法分析器就按照語法定義進行解析，就是從上到下匹配的過程。
也就是先匹配function的規(guī)則，匹配函數(shù)類型type、函數(shù)名name、函數(shù)參數(shù)parameters、函數(shù)體
當匹配函數(shù)參數(shù)時，就去匹配parameters的規(guī)則
當匹配函數(shù)體時，函數(shù)體由一個個語句組成，就去匹配各個語句stmt的規(guī)則。
function := type name parameters functionBody
parameters:= parameter*
functionBody:= stmt returnStatement
生成 AST 以后，程序的語法結(jié)構(gòu)就很清晰了，但這棵樹到底代表了什么意思，我們目前仍然不能完全確定，要在語義分析階段確定。
為什么要把程序轉(zhuǎn)換成AST這么一顆樹，因為編譯器不像人能直接理解語句的含義，AST樹更有結(jié)構(gòu)性，后續(xù)階段可以針對這顆樹做各種分析！
語義分析
語義分析階段的任務(wù)：理解語義，語句要做什么。
比如+號要執(zhí)行加法、=號要執(zhí)行賦值、for結(jié)構(gòu)要去實現(xiàn)循環(huán)、if結(jié)構(gòu)實現(xiàn)判斷。
所以語義階段要做的內(nèi)容有：上下文分析（包括引用消解、類型分析與檢查等）
引用消解：找到變量所在的作用域，一個變量作用范圍屬于全局還是局部。
類型識別：比如執(zhí)行a+3，需要識別出變量a的類型，因為浮點數(shù)和整型執(zhí)行不一樣，要執(zhí)行不同的運算方式。
類型檢查：比如int b = a + 3，是否可以進行定義賦值。等號右邊的表達式必須返回一個整型的數(shù)據(jù)、或則能夠自動轉(zhuǎn)換成整型的數(shù)據(jù)，才能夠?qū)︻愋蜑檎偷淖兞縝進行復制。
比如之前的一段C語言代碼，經(jīng)過語義分析后獲得的信息（引用消解信息、類型信息），可以在AST上進行標注，形成下面的“帶有標注的語法樹”，讓編譯器更好的理解程序的語義。
也會將這些上下文信息存入“符號表”結(jié)構(gòu)中，便于各階段查詢上下文信息。
符號表是有層次的結(jié)構(gòu)：我們只需要逐級向上查找就能找到變量、函數(shù)等的信息(作用域、類型等)
接下來就可以 解釋執(zhí)行：實現(xiàn)一門解釋型的語言
Tip:編譯型語言需要生成目標代碼，而解釋性語言只需要解釋器去執(zhí)行語義就可以了。
實現(xiàn)AST的解釋器：在語法分析后有了程序的抽象語法樹，在語義分析后有了“帶有標注的AST”和符號表后，就可以深度優(yōu)先遍歷AST，并且一邊遍歷一邊執(zhí)行結(jié)點的語義規(guī)則。整個遍歷的過程就是執(zhí)行代碼的過程。
舉一個解釋執(zhí)行的例子，比如執(zhí)行下面的語義：
遇到語法樹中的add “+”節(jié)點：把兩個子節(jié)點的值進行相加，作為“+”節(jié)點的值。
遇到語法樹中的變量節(jié)點(右值)：就取出變量的值。
遇到字面量比如數(shù)字2：返回這個字面量代表的數(shù)值2。
中間代碼生成
在編譯前端完成后(編譯器已經(jīng)理解了詞法和語義)，編譯器可以直接解釋執(zhí)行、或則直接生成目標代碼。對于不同架構(gòu)的CPU，還需要生成不同的匯編代碼，如果對每一種匯編代碼做優(yōu)化就很繁瑣了。所以我們需要增加一個環(huán)節(jié)：生成中間代碼IR，統(tǒng)一優(yōu)化后中間代碼，再去將中間代碼生成目標代碼。
中間代碼IR的兩個用途：解釋執(zhí)行 、代碼優(yōu)化
解釋執(zhí)行：解釋型語言，比如Python和Java，生成IR后就能直接執(zhí)行了，也就是前面舉出的例子。
優(yōu)化代碼：比如LLVM等工具；在生成代碼后需要做大量的優(yōu)化工作，而很多優(yōu)化工作沒必要使用匯編代碼來做(因為不同CPU體系的匯編語言不同)，而可以基于IR用統(tǒng)一的算法來完成，降低編譯器適配不同CPU的復雜性。
代碼優(yōu)化
一種方案：基于基本塊作代碼優(yōu)化
分類：本地優(yōu)化、全局優(yōu)化、過程間優(yōu)化
本地優(yōu)化：可用表達式分析、活躍性分析
全局優(yōu)化：基于控制流圖CFG作優(yōu)化。
控制流圖CFG ：是一種有向圖，它體現(xiàn)了基本塊之前的指令流轉(zhuǎn)關(guān)系，如果從BLOCK1的最后一條指令是跳轉(zhuǎn)到 BLOCK2， 就連一條邊，如果通過分析 CFG，發(fā)現(xiàn)某個變量在其他地方?jīng)]有被使用，就可以把這個變量所在代碼行刪除。
過程間優(yōu)化：跨越函數(shù)的優(yōu)化，多個函數(shù)間作優(yōu)化
優(yōu)化案例：
代數(shù)優(yōu)化：
比如刪除“x:=x+0 ”，乘法優(yōu)化掉“x:=x乘以0” 可以簡化成“x:=0”，乘法優(yōu)化成移位運算：“x:=x*8”可以優(yōu)化成“x:=x<<3”。
常數(shù)折疊：
對常數(shù)的運算可以在編譯時計算，比如 “x:= 20 乘以 3 ”可以優(yōu)化成“x:=60”
刪除公共子表達式：作“可用表達式分析”
x := a + b
y := a + b //優(yōu)化成y := x
拷貝傳播：作“可用表達式分析”
x := a + b
y := x
z := 2 * y //優(yōu)化成z:= 2 * x
常數(shù)傳播：
x := 20
y := 10
z := x + y//優(yōu)化成z := 30
死代碼刪除：作變量的“活躍性分析”
活躍性分析（優(yōu)化刪除死代碼，沒用到的變量） 數(shù)據(jù)流分析：使用“半格理論”解決多路徑的V值計算集合問題，不在代碼下面集合的變量就是死代碼。
目標代碼生成
目標代碼生成，也就是生成虛擬機執(zhí)行的字節(jié)碼，或則操作系統(tǒng)執(zhí)行的匯編代碼
代碼生成的過程，其實很簡單，就是將中間代碼IR逐個翻譯成想要的匯編的代碼
那么目標代碼生成階段的任務(wù)就有：
選擇合適指令，生成性能最高的代碼。
優(yōu)化寄存器的分配，讓頻繁訪問的變量，比如循環(huán)語句中的變量放到寄存器中，寄存器比內(nèi)存快
在不改變運行結(jié)果下，對指令做重排序優(yōu)化，從而充分運用CPU內(nèi)部的多個功能部件的并行能力
點個『在看』支持下?