編譯器的前端技術
- 詞法分析是把程式分割成一個個 Token 的過程，可以通過構造有限自動機來實作。
- 文法分析是把程式的結構識别出來，并形成一棵便于由計算機處理的抽象文法樹。可以用遞歸下降的算法來實作。
- 語義分析是消除語義模糊，生成一些屬性資訊，讓計算機能夠依據這些資訊生成目标代碼。
詞法分析
手工打造詞法分析器的過程，就是寫出正規表達式，畫出有限自動機的圖形，然後根據圖形直覺地寫出解析代碼的過程。
文法分析
文法分析的結果是生成 AST。算法分為自頂向下和自底向上算法，其中，遞歸下降算法是一種常見的自頂向下算法。
首先把變量聲明語句（int a = 45）的規則，用形式化的方法表達一下。它的左邊是一個非終結符（Non-terminal），右邊是它的産生式（Production Rule）。
在文法解析的過程中，左邊會被右邊替代。如果替代之後還有非終結符，那麼繼續這個替代過程，直到最後全部都是終結符（Terminal），也就是 Token。隻有終結符才可以成為 AST 的葉子節點。這個過程，也叫做推導（Derivation）過程。
帶有預測的自頂向下算法，它能減少回溯的次數。
上級文法嵌套下級文法，上級的算法調用下級的算法。表現在生成 AST 中，上級算法生成上級節點，下級算法生成下級節點。這就是“下降”的含義。
程式結構基本上是跟文法規則同構的。這就是遞歸下降算法的優點，非常直覺。
解析算術表達式的時候，會遇到更複雜的情況，這時，正則文法不夠用，我們必須用上下文無關文法來表達。
通過文法的嵌套，實作對運算優先級的支援。
正則文法是上下文無關文法的一個子集。它們的差別是上下文無關文法允許遞歸調用，而正則文法不允許。
左遞歸是遞歸下降算法無法處理的，這是遞歸下降算法最大的問題。
對于左結合的運算符，遞歸項要放在左邊；而右結合的運算符，遞歸項放在右邊。
針對優先級、結合性和左遞歸這三個問題做了更系統的研究：
- 優先級 是通過在文法推導中的層次來決定的，優先級越低的，越先嘗試推導。
- 結合性 是跟左遞歸還是右遞歸有關的，左遞歸導緻左結合，右遞歸導緻右結合。
- 左遞歸 可以通過改寫文法規則來避免，而改寫後的文法又可以表達成簡潔的 EBNF 格式，進而啟發我們用循環代替右遞歸。
了解遞歸下降算法中的回溯：嘗試一個規則不成功之後，恢複到原樣，再去嘗試另外的規則，這個現象就叫做“回溯”。
語義分析
語義分析的相關知識：
- 語義分析的本質是對上下文相關情況的處理，能做詞法分析和文法分析所做不到的事情。
- 了解引用消解，左值和右值的場景，可以增加對語義分析的直覺了解。
- 掌握屬性計算和屬性文法，可以使我們用更加形式化、更清晰的算法來完成語義分析的任務。
4.1 類型系統
類型系統最大的好處，就是可以通過類型檢查降低計算出錯的機率。是以，現代計算機語言都會精心設計一個類型系統，而不是像彙編語言那樣完全不區分類型。
根據類型檢查是在編譯期還是在運作期進行的，我們可以把計算機語言分為兩類：
- 靜态類型語言（全部或者幾乎全部的類型檢查是在編譯期進行的）
- 動态類型語言（類型的檢查是在運作期進行的）
再延伸一下，跟靜态類型和動态類型概念相關聯的，還有強類型和弱類型。強類型語言中，變量的類型一旦聲明就不能改變，弱類型語言中，變量類型在運作期時可以改變。二者的本質差別是，強類型語言不允許違法操作，因為能夠被檢查出來，弱類型語言則從機制上就無法禁止違法操作，是以是不安全的。
下面表達式在不同的情況下會有不同的運作結果：
a = b + 10; - 如果 b 是一個浮點型，b+10 的結果也是浮點型。如果 b 是字元串型的，有些語言也是允許執行 + 号運算的，實際的結果是字元串的連接配接。這個分析過程，就是類型推導（Type Inference）。
- 當右邊的值計算完，指派給 a 的時候，要檢查左右兩邊的類型是否比對。這個過程，就是類型檢查（Type Checking）。
- 如果 a 的類型是浮點型，而右邊傳過來的是整型，那麼一般就要進行預設的類型轉換（Type Conversion）。
4.2 引用消解
語義分析的本質，就是針對上下文相關的情況做處理。
當使用變量 a 時，我們需要知道它是全局變量 a，還是 fun() 函數中的本地變量 a。因為不同作用域裡可能有相同名稱的變量，是以必須找到正确的那個。這個過程，可以叫引用消解。
做引用消解可能會産生幾個結果：
- 解析出了準确的引用關系。
- 重複定義（在聲明新的符号的時候，發現這個符号已經被定義過了）。
- 引用失敗（找不到某個符号的定義）。
- 如果兩個不同的命名空間中都有相同名稱的符号，程式設計者需要明确指定。
4.3 左值與右值
左值（L-value）最早是在 C 語言中提出的，通常出現在表達式的左邊，如指派語句的左邊。左值取的是變量的位址（或者說變量的引用），獲得位址以後，我們就可以把新值寫進去了。
與左值相對應的就是右值（R-value），右值就是我們通常所說的值，不是位址。
4.4 屬性文法與屬性計算
在語義分析階段我們要了解的是屬性文法（Attribute Grammar），屬性計算需要用到屬性文法。
比如，針對求左值場景中的 primary 節點，它需要計算的屬性包括：
- 它的變量定義是哪個（這就引用到定義該變量的 Symbol）。
- 它的類型是什麼?
- 它的作用域是什麼？
- 這個節點求值時，是否該傳回左值？能否正确地傳回一個左值？
- 它的值是什麼？
從屬性計算的角度看，對表達式求值，或運作腳本，隻是去計算 AST 節點的 Value 屬性，Value 這個屬性能夠計算，其他屬性當然也能計算。
屬性計算的特點：它會基于文法規則，增加一些與語義處理有關的規則。
是以，我們也把這種語義規則的定義叫做文法制導的定義（Syntax directed definition，SDD）。如果變成計算動作，就叫做文法制導的翻譯（Syntax directed translation，SDT）。
屬性計算，可以伴随着文法分析的過程一起進行，也可以在做完文法分析以後再進行。這兩個階段不一定完全切分開。甚至，我們有時候會在文法分析的時候做一些屬性計算，然後把計算結果回報回文法分析的邏輯，幫助文法分析更好地執行（這是在工程實踐中會運用到的一個技巧）。
我們沒必要在文法分析階段把屬性全都計算出來，等到文法分析完畢後，再對 AST 周遊一下就好了。這時所有節點都有了，計算屬性也就不是難事了。
4.5 語義分析過程
第 1 遍：類型和作用域解析。
把自定義類、函數和和作用域的樹都分析出來。這麼做的好處是，你可以使用在前，聲明在後。比如你聲明一個 Mammal 對象，而 Mammal 類的定義是在後面才出現的；在定義一個類的時候，對于類的成員也會出現使用在聲明之前的情況，把類型解析先掃描一遍，就能友善地支援這個特性。
在寫屬性計算的算法時，計算的順序可能是個最重要的問題。因為某屬性的計算可能要依賴别的節點的屬性先計算完。我們讨論的 S 屬性、I 屬性和 L 屬性，都是在考慮計算順序。像使用在前，聲明在後這種情況，就更要特殊處理了。
第 2 遍：類型的消解。
把所有出現引用到類型的地方，都消解掉，比如變量聲明、函數參數聲明、類的繼承等等。做完消解以後，我們針對 `Mammal m;` 這樣語句，就明确的知道了 m 的類型。這實際上是對 I 屬性的類型的計算。
第 3 遍：引用的消解和 S 屬性的類型的推導。
這個時候，我們對所有的變量、函數調用，都會跟它的定義關聯起來，并且完成了所有的類型計算。
第 4 遍：做類型檢查。
比如當指派語句左右兩邊的類型不相容的時候，就可以報錯。
第 5 遍：做一些語義合法性的檢查。
比如 break 隻能出現在循環語句中，如果某個函數聲明了傳回值，就一定要有 return 語句，等等。
4.6 繼承和多态
- 從類型的角度，面向對象的繼承和多态是一種叫做子類型的現象，子類型能夠放寬對類型的檢查，進而支援多态。
- 在編譯期，無法準确地完成對象方法和屬性的消解，因為無法确切知道對象的子類型。
- 在運作期，我們能夠獲得對象的确切的子類型資訊，進而綁定正确的方法和屬性，實作繼承和多态。另一個需要注意的運作期的特征，是對象的逐級初始化過程。
運作時機制
程式主要跟 CPU、記憶體，以及作業系統打交道，是以需要了解的重點如下：
- CPU 上運作程式的指令，運作過程中要用到寄存器、高速緩存來提高指令和資料的存取效率。
- 記憶體可以劃分成不同的區域儲存代碼、靜态資料，并用棧和堆來存放運作時産生的動态資料。
- 作業系統會把實體的記憶體映射成程序的尋址空間，同一份代碼會被映射進多個程序的記憶體空間，作業系統的公共庫也會被映射進程序的記憶體空間，作業系統還會自動維護棧。
程式在運作時順序執行代碼，可以根據跳轉指令來跳轉；棧被劃分成棧桢，棧桢的設計有一定的自由度，但通常也要遵守一些約定；棧桢的大小和結構在編譯時就能決定；在運作時，棧桢作為活動記錄，不停地被動态建立和釋放。
生成彙編語言
對于靜态編譯型語言，比如 C 語言和 Go 語言，編譯器後端的任務就是生成彙編代碼，然後再由彙編器生成機器碼，生成的檔案叫目标檔案，最後再使用連結器就能生成可執行檔案或庫檔案了。
- 彙編語言是由指令、标簽、僞指令和注釋構成的。其中主要内容都是指令。指令包含一個該指令的助記符和操作數。操作數可以使用直接數、寄存器，以及用兩種方式通路記憶體位址。
- 彙編指令中會用到一些通用寄存器。這些寄存器除了用于計算以外，還可以根據調用約定幫助傳遞參數和傳回值。使用寄存器時，要區分由調用者還是被調用者負責保護寄存器中原來的内容。
從 AST 到彙編代碼、彙編代碼到可執行檔案的完整過程中抓幾個關鍵點：
- 首先，從 AST 生成彙編代碼，可以通過比較機械的翻譯來完成，我們舉了加法運算的例子。閱讀示例程式，你也可以看看函數調用、參數傳遞等等的實作過程。總體來說，這個過程并不難。
- 第二，這種機械地翻譯生成的代碼，一定是不夠優化的。我們已經看到了加法運算不夠優化的情況，是以一定要增加一個優化的過程。
- 第三，在生成彙編的過程中，最需要注意的就是要遵守調用約定。這就需要了解調用約定的很多細節。隻要遵守調用約定，不同語言生成的二進制目标檔案也可以連結在一起，形成最後的可執行檔案。
中間代碼
在後端部分所講的 IR，目的是友善執行各種優化算法，并有利于生成彙編。這種 IR，可以看做是一種高層次的彙編語言，主要展現在：
- 它可以使用寄存器，但寄存器的數量沒有限制；
- 控制結構也跟彙編語言比較像，比如有跳轉語句，分成多個程式塊，用标簽來辨別程式塊等；
- 使用相當于彙編指令的操作碼。這些操作碼可以一對一地翻譯成彙編代碼，但有時一個操作碼會對應多個彙編指令。
7.1 三位址代碼（TAC）
三位址代碼（Three Address Code，TAC）一種常見的 IR 的格式，它的優點是很簡潔，是以适合用來讨論算法：
x := y op z // 二進制操作
x := op y // 一進制操作 每條三位址代碼最多有三個位址，其中兩個是源位址（比如第一行代碼的 y 和 z），一個是目的位址（也就是 x），每條代碼最多有一個操作（op）。
另外幾種 IR 的格式：
- 首先是四元式。它是與三位址代碼等價的另一種表達方式，格式是：（OP，arg1，arg2，result）是以，“a := b + c” 就等價于（+，b，c，a）。
- 另一種常用的格式是逆波蘭表達式。它把操作符放到後面，是以也叫做字尾表達式。“b + c”對應的逆波蘭表達式是“b c +”；而“a = b + c”對應的逆波蘭表達式是“a b c + =”。
三位址代碼主要是學習算法的工具，或者用于實作比較簡單的後端，要實作工業級的後端，充分發揮硬體的性能，還要學習 LLVM 的 IR。
7.2 LLVM彙編碼
LLVM 有很好的子產品化設計，支援即時編譯（JIT）和提前編譯（AOT），支援全過程的優化，并且具備友好的授權，值得我們好好掌握。
LLVM 彙編碼（LLVM Assembly），是 LLVM 的 IR。有的時候，我們就簡單地稱呼它為 LLVM 語言，是以我們可以把用 LLVM 彙編碼書寫的一個程式檔案叫做 LLVM 程式。
首先，LLVM 彙編碼是采用靜态單指派代碼形式的。
在三位址代碼上再加一些限制，就能得到另一種重要的代碼，即靜态單指派代碼（Static Single Assignment, SSA），在靜态單指派代碼中，一個變量隻能被指派一次。
SSA 的形式，展現了精确的“使用 - 定義”關系。
其次，LLVM IR 比起三位址代碼有更多的細節資訊。比如整型變量的字長、記憶體對齊方式等等，是以使用 LLVM IR 能夠更準确地翻譯成彙編碼。
LLVM 的 IR 有兩種格式：
- 文本格式，檔案名一般以 “.ll” 結尾
- 位元組碼（bitcode）格式，檔案名以 “.bc” 結尾
使用 LLVM 從源代碼到生成可執行檔案有兩條可能的路徑：
- 第一條路徑，是把每個源檔案分别編譯成位元組碼檔案，然後再編譯成目标檔案，最後連結成可執行檔案。
- 第二條路徑，是先把編譯好的位元組碼檔案連結在一起，形成一個更大的位元組碼檔案，然後對這個位元組碼檔案進行進一步的優化，之後再生成目标檔案和可執行檔案。
第二條路徑比第一條路徑多了一個優化的步驟，第一條路徑隻對每個子產品做了優化，沒有做整體的優化。是以，如有可能，盡量采用第二條路徑，這樣能夠生成更加優化的代碼。
總結一下 LLVM 的指令行工具包括：
- clang 前端
- llvm-as（把文本格式轉換成位元組碼格式）
- llc（把位元組碼編譯成目标平台的彙編代碼）
- opt（代碼優化）
- llvm-dis（将位元組碼再反編譯回 ll 檔案）
- llvm-link（連結）
- 還可以看它們的 help 資訊
從生成 IR 到編譯執行的完整過程的重點如下：
- LLVM 用一套對象模型在記憶體中表示 IR，包括子產品、函數、基本塊和指令，你可以通過 API 來生成這些對象。這些對象一旦生成，就可以編譯和執行。
- 對于 if 語句和循環語句，需要生成多個基本塊，并通過跳轉指令形成正确的控制流圖（CFG）。當存在多個前序節點可能改變某個變量的值的時候，使用 phi 指令來确定正确的值。
- 存儲在記憶體中的本地變量，可以多次指派。
- LLVM 能夠把外部函數和 IR 模型中的函數等價對待。
代碼優化
代碼優化的關鍵點：
- 代碼優化分為本地優化、全局優化和過程間優化三個範圍。有些優化對于這三個範圍都是适用的，但也有一些優化算法是全局優化和過程間優化專有的。
- 可用表達式分析和活躍性分析是本地優化時的兩個關鍵算法。這些算法都是由掃描方向、值、轉換函數和初始值這四個要素構成的。
- LLVM 用 pass 來做優化，可以通過指令行或程式來使用這些 Pass，也可以編寫自己的 Pass。
優化過程：
- 我們首先做一個正向掃描，進行可用表達式分析，建立可用表達式的集合，然後參照這個集合替換公共子表達式，以及做拷貝傳播。
- 接着，我們做一個反向掃描，進行活躍性分析，建立活變量的集合，識别出死變量，并依據它删除給死變量指派的代碼。
- 上述優化可能需要做不止一遍，才能得到最後的結果。
在 LLVM 中，做優化算法很友善，因為它采用的是 SSA 格式。具體來說，LLVM 中定義了 Value 和 User 兩個接口，它們展現了 LLVM IR 最強大的特性，即靜态單指派中的“定義 - 使用”鍊，這種“定義 - 使用”關系會被用到優化算法中。
- 在 User 中，可以通路所有它用到的 Value，比如一個加法指令（%c = add nsw i32 %a, %b）用到了 a 和 b 這兩個變量。
- 而在 Value 中，可以通路所有使用這個值的 User，比如給 c 指派的這條指令。
- 是以，你可以周遊一個 Value 的所有 User，把它替換成另一個 Value，這就是拷貝傳播。
全局優化中的算法，不會像在本地優化中一樣，隻針對一個基本塊。而是更複雜一些，因為要覆寫多個基本塊。這些基本塊構成了一個 CFG，代碼在運作時有多種可能的執行路徑，這會造成多路徑下，值的計算問題，比如活躍變量集合的計算。
還有些優化隻能在全局優化中做，在本地優化中做不了，比如：
- 代碼移動（code motion）能夠将代碼從一個基本塊挪到另一個基本塊，比如從循環内部挪到循環外部，來減少不必要的計算。
- 部分備援删除（Partial Redundancy Elimination），它能把一個基本塊都删掉。
總之，全局優化比本地優化能做的工作更多，分析算法也更複雜，因為 CFG 中可能存在多條執行路徑。這種基于 CFG 做優化分析的方法架構，就叫做資料流分析。
基于全局優化分析的任務的幾個要點：
- 全局分析比本地分析多處理的部分就是 CFG，因為有了多條執行分支，是以要計算分支相遇時的值，當 CFG 存在環路的時候，要用不動點法來計算出所有的 V 值。
- 資料流分析架構包含方向（D）、值（V）、轉換函數（F）、初始值（I）和交運算（Λ）5 個元素，隻要分析清楚這 5 個元素，就可以按照固定的套路來編寫分析程式。
- 對于半格理論，關鍵是要知道如何比較偏序集中元素的大小，了解了這個核心概念，那麼求最大下界、最小上界這些也就沒有問題了。
目标代碼的生成和優化
代碼生成部分需要考慮的問題主要有三點：
- 指令的選擇。同樣一個功能，可以用不同的指令或指令序列來完成，而我們需要選擇比較優化的方案。
- 寄存器配置設定。每款 CPU 的寄存器都是有限的，我們要有效地利用它。
- 指令重排序。計算執行的次序會影響所生成的代碼的效率。在不影響運作結果的情況下，我們要通過代碼重排序獲得更高的效率。
指令選擇、寄存器配置設定、指令重排序這三個領域的算法，都是“NP - 完全”的，是以尋找優化的算法，是這個領域最富有挑戰的任務。
- 相同的 IR 可以由不同的機器指令序列來實作。要了解瓦片為什麼長那個樣子，并且在大腦裡建立用瓦片覆寫一棵 AST 的直覺印象，最好具備多種覆寫方式，進而把這個問題由抽象變得具象。
- 寄存器配置設定是編譯器必須要做的一項工作，它把可以使用無限多寄存器的 IR，變成了滿足實體寄存器數量的 IR，超出的要溢出到記憶體中保管。染色算法是其中一個可行的算法。
- 要了解令重排序這個主題，首先要知道 CPU 内部是分成多個功能部件的，要知道一條指令的執行過程中，指令擷取、解碼、執行、通路資料都是如何發生的，這樣就可以了解指令級并行的原理；其次，從算法角度，要知道 List Scheduling 的步驟，掌握基于最大時延的優先級計算政策。有了這個基礎之後，就可以進一步地研究其他算法。