編譯原理學習筆記-1

• 2020 年 3 月 17 日
• 筆記

1. 翻譯程式

機器不能理解我們用高級語言編寫的程式碼，所以要在程式執行前將高級語言「翻譯」為機器語言。這是一個將源語言程式轉化為目標語言程式的過程，它依靠翻譯程式來完成。

翻譯程式包括：

• 編譯器：將編譯型語言（C++，Go）翻譯為機器語言。
• 解釋器：將解釋型語言（JavaScript、Python）翻譯為機器語言。

編譯與解釋的不同：

編譯和解釋都可以將高級語言翻譯為機器語言，不同之處在於：

• 編譯是將源程式碼經過分析後生成語法樹，再優化生成中間程式碼，最後生成機器碼。編譯的結果是生成一個可執行的二進位文件；
• 而解釋也是將源程式碼經過分析後生成語法樹，只不過此後它是基於語法樹生成位元組碼，再根據位元組碼去執行程式。它並不會生成目標文件，更多的是一個結果。

PS：JavaScript 本身是解釋型語言，但是在「翻譯」過程中同時有解釋器和編譯器（JIT）的參與。在其它文章會學習這個知識，此處不做進一步討論。Anyway，這個系列的筆記中會將重點聚焦在編譯型語言上。

2. 編譯器的演進

二階段編譯器（單盒模型）

早期的二階段編譯器，任務主要有兩個，一是理解輸入的源程式，二是將其功能映射到目標機上，據此將編譯器內部劃分為前端和後端兩個模組 —— 前端負責理解，後端負責映射。前端對源程式碼的理解反映在 IR （intermediate representation，中間表示）這一結構中，IR 再傳遞給後端進行處理。

三階段編譯器

後面出現了三階段編譯器，也就是在前後端之間增加了一個用以改進 IR 的優化器。注意：這個優化器本身是一個源到源的編譯器。自此，三者的分工變為：

• 前端：理解源程式，並將理解的結果映射到 IR 中
• 優化器：改進 IR 的形式
• 後端：將改進後的 IR 映射到目標機的有限資源上

3. 編譯步驟一覽

3.1 前端

• 詞法分析：詞法分析器（掃描器）以字元流為輸入，對其進行掃描和分解，產生多個 token（單詞、符號），這個過程叫做 tokenize（分詞化）。接著，這些 token 被歸入對應的詞類，最後再輸出由已歸類單詞構成的流（形如(typeA,"str1"),(typeB,"str2"),(typeA,"str3"),(typeC,"str4")......）
• 語法分析：語法分析器（分析器）在詞法分析的基礎上，根據事先約定的語法規則，對已歸類單詞構成的流進行匹配，以語法單位的形式進行重組，構造並輸出一棵語法樹（syntax tree | | parsing tree | | derivation tree）。
• 語義分析與中間程式碼生成：語義分析與中間程式碼生成器基於語義規則，對語法樹進行語義分析（變數是否定義，類型是否正確）和中間程式碼生成（三元式、四元式等）。

3.2 優化器

• 中間程式碼優化：包括分析和轉換（數據流分析、相關性分析）兩個過程

3.3 後端

• 指令選擇：將每個 IR 操作映射為一個或多個實際的目標機操作
• 暫存器分配：將指令選擇階段使用的虛擬暫存器映射到實際的目標機暫存器，最小化暫存器的使用
• 指令調度：重排程式碼中的各個操作，最小化等待操作數所浪費的周期數