再看編譯原理

編譯器

編譯器也是個程式，可以閱讀某一種語言（源語言）編寫的程式，並把該程式翻譯為一個等價的，用另一種語言（目標語言）編寫的程式。

即，輸入源程式，輸出目標程式的程式，能夠把源程式映射為語義等價的目標程式：

       編譯器
源程式 -------> 目標程式

源程式一般是可讀性較好的字串，目標程式則有多種形式：

機器碼，例如 C 語言編譯得到可執行的二進位程式
中間位元組碼，例如 Java 編譯得到面向 JVM 的 .class 檔案
字串，例如經 Babel 轉過的 JavaScript 程式碼

其實就是翻譯，比如從字串編譯到機器碼，就是把人能理解的程式碼語言翻譯成機器能「理解」（識別執行）的機器語言，然後使用者借助目標程式就可以與機器互動了：

         目標程式
使用者輸入 ---------> 輸出

P.S. 與編譯器很像的是解釋器，區別在於沒有生成目標程式的環節：

                 解釋器
源程式 & 使用者輸入 -------> 輸出

執行時解釋執行，所以解釋型語言的執行效率一般要低於編譯型語言

編譯過程

分為兩部分：

分析：把源程式拆分成多個部分，再加上語法結構，生成中間表示形式與符號表（symbol table）
合成：根據中間表示形式及符號表來構造目標程式

典型編譯器的處理步驟如下：

（輸入）字元流
|
|- 詞法分析器（lexer）
|  （生成）符號流
|  （生成）符號表
|- 語法分析
|  （生成）語法樹
|- 語義分析
|  （生成）語法樹
|- 中間程式碼生成器
|  （生成）中間表示形式
|- 機器無關程式碼最佳化器
|  （生成）中間表示形式
|- 程式碼生成器
|  （生成）目標機器語言
|- 機器相關程式碼最佳化器
v
（輸出）目標機器語言

其中，主要步驟是詞法分析，語法分析，語義分析，以及程式碼生成，而中間程式碼生成和兩步最佳化是可選的

詞法分析（lexical analysis）

編譯工作的第一步，目標是把字元流轉換成詞法單元（token）序列

Takes raw input, which is a stream of characters, and converts it into a stream of tokens, which are logical units, each representing one or more characters that "belong together."

例如：

// 輸入
position = initial + rate * 60

// 輸出
[
  (id, 1),
  (=),
  (id, 2),
  (+),
  (id, 3),
  (*),
  (number, 4)
]

具體過程是逐字元掃描，去掉註解和空白字元，把字元流拆分成詞素（lexeme）：

position,=,initial,+,rate,*,60

再把詞素轉換成 token 形式：

(token-name, attribute-value)

token 是建立在字元之上的第一層抽象，之所以是這種鍵值對兒的形式，是因為之後的多數環節都只需要關注類型（token-name），最後生成程式碼時才需要詳細的值資訊（attribute-value）。其中 token-name 是語法分析步驟需要的抽象符號（比如 id 表示識別字），attribute-value 是符號表中該詞素的索引：

[
  (1, position),
  (2, initial),
  (3, rate),
  (4, 60)
]

符號表

符號表是一種供編譯器用於保存有關源程式構造的各種資訊的資料結構。

在分析階段生成，在合成階段使用：

從效果看，符號表的作用是把資訊從宣告的地方傳遞到實際使用的地方。

由於詞法分析器擁有的資訊有限（詞素字面量），生成的符號表只含有基本資訊（詞素字面量與識別字的映射關係），之後語法分析器會根據語義資訊來決定是採用現有符號表條目還是建立新條目

另外，符號表並不是全域只有一張，而是每個作用域都有一張獨立的符號表，目的是支援同一識別字在程式的不同宣告塊中可以重複出現，即讓不同作用域下變數名不衝突。同時，為了支援語句塊的最近嵌套（most-closely）規則，需要把這些符號表按嵌套層級連結起來形成樹結構，以支援繼承、閉包等語法特性

P.S. 關鍵字也像識別字一樣存放在符號表裡，查表時透過返回碼來區分

語法分析（syntax analysis）

語法分析階段，取 token-name 建立樹形的中間表示，用來描述語法結構，同時校驗語法錯誤

Check input is well-formed and build a parse tree or similar representation of input.

比如抽象語法樹（abstract syntax tree）就是一種常見的中間表示形式，能夠描述源程式的層次化語法結構，樹中每個節點表示一個運算，子節點表示該運算的運算分量：

=
  (id, 1)
  +
    (id, 2)
    *
      (id, 3)
      (number, 4)

語法樹是字元之上的第二層抽象，到這裡就有優先級與結合性的概念了，運算需要按照這些規則匹配其運算分量，從而生成唯一的樹結構（要求語法沒有二義性）。這個階段能夠確認輸入的源程式形式是否正確，比如括號是否匹配之類的

上下文無關文法

語言的語法結構通常用上下文無關文法（context-free grammar）來定義，例如：

if (expression) statement else statement

對應的產生式（production）為：

stmt -> if (expr) stmt else stmt

其中 expr，stmt 這樣的變數是非終結符（nonterminal），表示終結符（terminal，如 if，() 這樣的詞法元素）序列

上下文無關文法由 4 個要素組成：

終結符集合：語言的基本符號集合
非終結符集合：也稱為語法變數，能夠替換為終結符序列
產生式集合：用來表示某個構造的某種書寫形式
開始符號：指定一個非終結符作為開始符號

從開始符號出發，不斷將非終結符替換為右側的產生式體的過程叫做推導。可以從開始符號推導得到的所有終結符序列的集合就是該文法所定義的語言，反過來看，語言就是符合產生式規則的一系列終結符字串

例如，CSS 中屬性宣告對應的文法：

// 終結符
ident	[-]?{nmstart}{nmchar}*
// 非終結符
IDENT	{ident}
// 產生式
property    : IDENT;

P.S. 開始符號是 stylesheet，對應的產生式為 stylesheet : [ CDO | CDC | S | statement ]*;，具體見 CSS 核心語法

優先級與結合性

運算的優先級與結合性也由產生式規則來定義，例如：

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | (expr)

含義如下：

factor：不能被任何運算符分開的運算式，是運算分量的最小單元，要麼是數值，要麼是由括號保護起來的運算式
term：能被高優先級的運算符（* 和 /）分開，但不能被低優先級運算符（+ 和 -）分開的運算式
expr：一般運算式，能被上面任何一個運算符分開

所以，控制優先級的思路是，每個優先級都有一個專用的非終結符，表示能被該優先級的或更高優先級的運算符分開的運算式

語義分析

在這個階段會做一些靜態檢查，看輸入的語法結構是否滿足語法要求：

型別檢查（type checking）：比如看每個運算符是否具有匹配的運算分量，陣列索引資料型別是否正確
型別轉換（coercion）：比如對運算元進行隱式型別轉換

例如：

=
  (id, 1)
  +
    (id, 2)
    *
      (id, 3)
      inttofloat
        (number, 4)

P.S. 其中 inttofloat 表示整型轉浮點型的一元運算，是型別轉換中插入的操作

中間程式碼生成

語法分析和語義分析完成之後，接下來可能要生成一種類機器語言的中間表示，這種表示形式有兩個特點：

易於生成（只是中間表示，生成成本不能太高）
容易翻譯到機器語言（一步步向目標語言逼近）

比如三位址碼（three-address code）是一種常見的中間表示形式，類似於組合語言指令：

t1 = inttofloat(number4)
t2 = id3 * t1
t2 = id2 + t2
id1 = t3

程式碼最佳化

分為兩類：

機器無關最佳化：針對中間表示的最佳化，以生成更好的目標程式，比如 Closure Compiler 對 JS 程式碼做的一些最佳化，比如最佳化迴圈、不可達程式碼消除、冗餘程式碼簡化等等
機器相關最佳化：針對目標程式的最佳化，涉及 CPU 暫存器、記憶體引用等，目標是最大限度的利用並行性、記憶體階層結構等電腦體系結構特性

前者發生在中間程式碼生成環節之後，而後者發生在目標程式生成之後，是出廠前的最後一道工序

P.S. 比如上一步中的 inttofloat 型別轉換可以在編譯時完成（把 60 轉成 60.0），算是機器無關最佳化

程式碼生成

輸入中間表示形式，輸出目標語言。比如要生成機器語言的話，需要給每個變數指定暫存器或記憶體位置，再把中間表示翻譯成等價的機器指令序列

最佳化過的三位址碼對應的機器語言（不知道什麼語言，看著像組合語言）是：

LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1

用了 2 個暫存器 R1 和 R2，讀入 id3 放到 R2 裡，再與 60.0 相乘，把乘積放到 R2 裡……最後把 R1 的值被放到 id1 對應的記憶體位址，完成賦值

不考慮機器相關最佳化的話，編譯過程到這裡就結束了。邏輯上要經歷詞法分析，語法分析，語義分析，程式碼生成這 4 個必要環節。實際實作中，這些環節並不一定都有清晰的邊界，而是儘量一趟完成多道工序，以提高效能

參考資料

《編譯原理》（龍書第二版）
http://infolab.stanford.edu/~ullman/dragon/slides1.pdf
Compiler Design - Code Optimization
Compiled language

編譯器