用 Swift 搭建一個微型編譯器

iunj9154 8年前發布 | 5K 次閱讀編譯器 Swift Apple Swift開發

對絕大多數開發者來說，盡管我們每天都要與編譯器打交道，然而實際上編譯器對我們來說仍然像一個神秘的黑盒。在本次 try! Swift 的講演中，Samuel Giddins 從頭搭建了一個全新的微型編譯器，用來編譯他自制的一門編程語言，從而借此去學習編譯器的基本工作機制。他還講述了 Swift 是如何為復雜問題（例如語義解析、詞法分析和代碼生成）提供優雅的解決方案的。最后，我們將實現一門全新的編程語言，并完成對它的編譯工作！

我構建了一門名為「Sipquick」的編程語言，然后我用 Swift 為其搭建了編譯器和測試用例。

那么這個微型編譯器長什么樣呢？僅僅只有 310 行代碼！我并沒有去計算 Swift 編譯器的代碼行數，不過我猜想它起碼會超過 100,000 行。所以，相比之下，我的這個編譯器的的確確配得上「微型」這一稱號。

為啥要編寫一個編譯器呢？

編譯器是每個開發人員都要每天打交道的玩意兒。因此，我很好奇編譯器是如何工作的。當我運行 Swift 、C 程序或者運行 Clang 的時候會發生什么呢？
這是一個很出名的問題領域。現在編譯器的種類有成百上千種。您可以去谷歌「我該如何在編譯器當中執行……」，您會得到一些比在 Stack Overflow 上更好的答案。您可能會搜索到推ter 上的推文、博客上的文章以及相關的書籍。
這些建議在任何語言當中都是可行的。它本質上是一個將某種文本文件轉換為另一種文本文件的程序。
我此前從未編寫過編譯器。不過現在我可以在簡歷上大書一筆「編譯器工程師」。

編譯器其實非常簡單，就是一函數：

let compiler: (String) -> Data /* 可執行文件 */

這個函數接收一個字符串為參數，這個字符串我們稱之為 「源文件」 ，然后輸出一個可執行文件。它將我們可以閱讀、理解、編寫和分析的語言所編寫的程序，轉換為另一種機器可以閱讀、理解、分析以及執行的語言。

那么，我們該如何編寫一個編譯器呢？下面是一系列眾所周知的步驟：

解析源代碼
詞法分析
做所謂的「語義分析」。比如說「現在這里有一些 Token，它們是啥意思？在 Swift 當中， Class 這個單詞意味著什么呢？」
優化
生成機器代碼

編譯器的本質決定了編譯器一定是 高度函數化 (functional) 的。我構建了一門名為「Sipquick」的編程語言。這是一本書中虛構的一種叫聲非常響亮、聒噪的鳥類（譯者注：源自 “The Wise Man’s Fear” ，這可能是一種與蜂鳥相關的鳥類）。

這是一門非常簡陋的語言，是我專門為本次講演而發明的。如果我試圖為現有的語言編寫一個編譯器，那么我將不得不實現很多東西，這將會導致我的工作變得困難、復雜。
這是一個基于 s-表達式 (s-expressions) 的語言（類似于 Lisp）。所有的內容都包含在括號當中，因此您的編譯器必須要能夠實現括號自動匹配，這樣我們才能夠很方便的保證所有的內容都能成功編譯。

s-表達式：全稱是 Symbolic Expression，可以是一個原子量 (atom)，也可以是成對括號組成的列表，例如：(x, y)、x、y 都是一個 s-表達式 。
這是一門動態語言，因此編譯時是沒有類型之分的。
編譯器并不知曉類型，這是一門函數式語言。由于它的本質所致，這使得每個函數都需要接受參數并返回一些東西，這可能會導致語言當中存在某種副作用。

(def hello name (+ "Hello, " name))
(print (hello "world!"))

這就是我們在 Sipquick 當中編寫「Hello, world!」的方式。 def 是定義函數的關鍵字，這個函數的名字為 hello 。它接受一個名為 name 的參數，然后它與一個字符串建立了連接。第二行，我們調用了這個函數并對其進行了輸出。

首先我們需要搭建一個解析器 (Parser)。它是一個解析器組合器 (Combinator) —— 這里面有一些很有意思的玩意兒，類似于 Monad。不過我很不喜歡那些花里胡哨的運算符——我將其改成了可以即寫即讀的玩意兒。

這是最主要的解析過程：

let schemeParser: Parser<String, [Sexp]> = {
  return ignoreSecond(
  sexp().
    then(unichar("\n").maybe()).
    maybeMany().
    fmap { $0.map { $0.0 } }
  .then(dropEndingMetadata().or(empty().andThatsAll())))
}

這里我忽略了配置解析器的所有內容，以及一些 s-表達式 的定義。但是我們的基本思路就是需要在一組 s-表達式 當中完成解析操作，然后一旦遇到了文件尾或者遇到了換行標志，那么我們就完成了這一行代碼的解析。最后我們會得到一個包含 s-表達式 的數組。

這里出現了各種各樣的泛型。編譯器其實很討厭泛型的，但是我們可以將我們所獲取到的字符串、Token 轉換為 s-表達式 。

_.fmap { Sexp.single($0) }
_.fmap { Sexp.many($0) }
_.fmap { _ in Sexp.none }

解析過程中，我們會將所解析的東西轉換為 AST (抽象語法樹 Abstract Syntax Tree)。我可以分析出「這些是空括號、這些是空的 s-表達式 」，從而讓分析過程變得簡單。我不必去關注這些字符串在不同的位置意味著什么。這些操作是在 parser.swift 文件當中進行的。

let sema: ([Sexp]) -> [Expression]

我們已經完成了解析，現在需要對 Token 進行處理了。但是很多語言當中 Token 都具有不同的特殊意義。您該如何定義一個函數呢？如何定義一個變量呢？此外還有關鍵字，這些是運算符嗎？不同行之間該如何協同工作呢？

這就是所謂的語義分析 (Semantic Analysis)：通過分析這個抽象語法樹，然后將其折疊 (collapse) 成 Expression ，從而讓編程語言能夠進行分析：

struct Expression {
    init(sexp: Sexp) {
        switch exp {
        ...
        }
    }
}

這個初始化語句當中包含了一個臃腫的 switch 語句。我上周都一直在編寫這玩意兒。這里我將不會具體描述這段代碼，因為我覺得在 Swift 本身的語義分析當中并不會出現這種方式。我們對所要找的東西進行選擇，然后將這些類似 Lisp 的 s-表達式 轉換為編譯器所能夠理解的 Expression ，從而理解這個表達式是定義了一個變量，還是定義了一個函數，或者是進行了函數的調用。

在絕大多數編譯器當中，我們可能會進行檢查「這段程序是否正確？它的構造是否正確？」。在類似 Swift 的語言當中，這還意味著我們需要檢查 「這個類型是否正確？調用的這個函數的參數數量是否正確？這個函數是否存在？」 。而我們現在編寫的這個語言并不需要執行這些操作。此外，我們這個編譯器也不會去執行優化操作。

諷刺的是， 優化 (Optimization) 是編譯器當中 最簡單的事情之一 ：

let optimizations: Array<[Expression] -> [Expression]>

優化是指「這里有一些相應的表達式，然后我們需要把它們轉換為另一種表達式」。在絕大多數久經風霜的編譯器當中，您可能會看到很多的優化流程。在這個流程當中，您將要執行下述操作：

是否有無法訪問的代碼？如果有就刪掉。
是否有重復使用的純函數 (pure function)？如果有，我們可以對值進行計算，然后將結果直接放到重復使用的地方。

這里我一項優化操作都沒有做，但是這個操作是編譯器執行過程當中最為重要的部分之一，因此人們會在這個步驟花費大量的時間。如果我花了 10 個小時來進行優化，從而可以使代碼運行速度加快 1%，那么這就是值得的。因為使用編譯器的用戶很多，1% 的優化可能意味著可以節省用戶成千上萬個小時來進行編譯。此外，編譯器的優化也是學術研究的熱點所在，我們需要研究何種轉換是既安全又迅速的。

代碼生成 (Code Generation) 是最后的步驟了，這個時候我已經理解了整個程序的意圖。編譯器已經知道了整個程序需要執行的操作，但是現在還需要輸出電腦能夠運行的東西才行：

let codeGen: ([Expression]) -> Data

我們用 Expression 數組作為參數，然后將它們轉換為可執行文件。

什么是可執行文件呢？生成機器代碼的工作是交給 Clang 和 LLVM 代勞的。如果您曾經使用過 Babel for JavaScript 的話，那么它本質上是將某種形式的 JavaScript 編譯成另一種形式的 JavaScript；它本質上仍然是一種編譯過程。

我覺得代碼生成這個步驟是非常困難的。人們所想出的最簡單方法是：導入 LLVM，然后將相關的數據交給 LLVM 來完成，LLVM 當中會有很多的優化操作，并且會生成很棒的機器代碼。如果您使用的是類似 C 語言類似的東西的話，那么 LLVM 將會非常好用。因為 LLVM 是專門為 C、C++ 和 Objective-C 的編譯器而編寫的。

這里我所構建的語言是一門非常動態的語言，沒有任何類型，我們根本不知道這個變量是一個字符串還是一個整數，也不知道這個函數是否切實存在。我試圖將它適配到 LLVM 當中，但是這并未奏效。

在第 27 頁幻燈片上，這就是理想化的「現代編譯器的工作方式」。所有的 LLVM 操作都發生在編譯的最后階段，但是我現在無法這么做。我不得不自行實現最艱難的部分。

我將我的這門類似 Lisp 的語言編譯為 Ruby。Ruby 是一門動態語言，它有一門很穩定的標準庫，這樣我就不用去編寫諸如「我該如何將這個參數傳遞給程序？我該如何向屏幕輸入內容」此類的內容。

extension Expression {
    func asRuby() -> String {
        switch self.type {
            ...
        }
    }
}

我將代碼生成這一步驟基本上作為 Expression 的擴展來實現。我們的做法是「這里有一個表達式，然后我們可以將其轉變為 Ruby 來表示」。

這個操作是遞歸進行的。因為我們會有嵌套的表達式存在，比如說函數調用這種形式，我們進行了一次頂層的函數調用，然后可能其參數本身就包含了其他函數調用或者其他的表達式。這個 asRuby() 方法將會對表達式進行轉換，然后輸出 Ruby 代碼，只要您的機器上可以運行 Ruby，那么我們就可以運行我們的程序了。

這段代碼的要點是：我們要將表達式通過 $0.asRuby() 進行映射，然后將所得到的內容通過換行標志聯結在一起，然后在頂部添加一個 Shebang ( #! ) 符號，接著執行 chmod 命令，這樣就生成了可執行文件，從而就可以運行了。

那么這個步驟是什么樣子的呢？

; fibonacci.spq
(def fib x (condition (<= x 1) x (+ (fib (- x 1)) (fib (- x 2)))))
(print (fib 10))

將會轉換為：

#!/usr/bin/env ruby
def fib(x)
    if (x.<=(1))
        x
    else
        (fib((x.-(1))).+(fib((x.-(2)))))
    end
end
print(fib(10))

這里我們添加了一個定義，定義了第 n 個斐波那契數是什么。Lisp 并不是最具表現力的語言，因為它當中有很多的括號，但是我們可以將其編譯為某種看起來很像 Ruby 的玩意兒，這就相對比較友好。如果您實際運行這段代碼，會發現它是能夠正常工作的。

在第 32 頁幻燈片上，我列出了整個代碼生成的步驟。我知道大家根本看不清，當然我這是故意的。這段代碼放在了一個文件當中，非常地緊湊，但是實現起來也比較簡單，我還針對 Ruby 做了比較好的轉換和優化。

它基本上就是對 Expression 執行選擇操作，然后挑選出「這是一個函數定義，而這些是參數名稱」，然后轉換為對應的 Ruby 表達式。

extension Expression {
    func parenthesize(_ s: String) -> String

    var isOperatorCall: Bool { get }

    func asRuby(depth: Int = 0) -> String {
        switch kind {
        case .bare: { }
        case .call:
            if isOperatorCall {  }
            else {  }
        case .functionDefinition: {  }
        case .empty: {  }
        case .variableDeclaration: {  }
        case .conditional:
            guard children.count == 3 else {  }
            let conditional = children[0]
            let positive = children[1]
            let negative = children[2]
            {  }
        }
    }
}

不過除此之外，之前的語義分析、優化操作都是非常簡單的，我們只要實現「將其輸出成某個讀起來與我們所操作的語言一樣的對象」即可。

如果我試圖將這個語言編譯成 Swift 或者 C，那么這將是一個非常困難的操作，因為我該如何判斷某個數字是一個整數還是一個浮點數呢？如何判斷這是一個字符串還是一個字符呢？我該如何進行棧的分配，如何進行堆的分配？因此，當您試圖以傳統的編譯器的做法來思考這門語言的時候，會發現有很多不匹配的地方。所以，這個步驟完全取決于您所要編譯運行的語言特性。

$ cat fibonacci.spq
(def fib x (condition (<= x 1) x (+ (fib (- x 1)) (fib (- x 2)))))
(puts (fib ([] ARGV 0)))
$ sipquick fibonacci.spq fibonacci
$ ./fibonacci 10
55

我很喜歡這個 .spq 擴展名。您可以編寫一個文件，然后將以 spq 結尾。您可以選擇它輸出的文件是什么，然后您便可以像其他任何一個正常的可執行文件一樣，傳遞參數并運行程序。

我只寫了集成測試 (integration test)。這些測試主要是編譯一個文件，然后進行運行，并驗證輸出是否符合我的期望。只有通過測試我才知道編譯器能夠正常工作，因此這需要一個格式良好的程序進行編譯和運行，而不是用其他糟糕的例子來驗證其穩定性。此外我沒有編寫任何的單元測試。

這是其中的一個測試用例：

(def print_even x (condition (== (% x 2) 0) (print "even") (print "odd")))
(print_even 17)
(print_even 12)
(print_even -1)
(print_even 1)
(print_even (* 0 1))
/////
it allows branching
0oddevenoddoddeven

基本上我會在頂部添加一個 Sipquick 標志，然后添加五個斜杠，隨后寫上測試用例的名稱、期望的退出代碼 (exit code) 以及期望的輸出，此外還有測試者的名稱。

這就是一個標準測試的格式。它擁有一個名稱、您所運行的腳本、期望的輸出和期望的退出代碼。然后您只需要運行這段代碼即可，并確保所有的內容都是相等的。然后，找到編譯器的路徑，或者找到具有所有 spec 文件的路徑，找到之后，實例化這些測試用例，運行它們，看看它們是否通過即可。

這是我今天早上寫的最后一個測試用例：

(def fizzbuzz x
    (condition (<= x 0) (return "")
        (condition (== 0 (% x 15)) (+ (fizzbuzz (- x 1)) "fizzbuzz")
            (condition (== 0 (% x 3)) (+ (fizzbuzz (- x 1)) "fizz")
                (condition (== 0 (% x 5)) (+ (fizzbuzz (- x 1)) "buzz")
                (+ (fizzbuzz (- x 1)) (String x)))))))
(def fetch_arg position default
    (condition (!= nil ([] ARGV position))
    ([] ARGV position)
    (return default)))
(print (fizzbuzz (fetch_arg 0 100)))
/////
it computes fizzbuzz
012fizz4buzzfizz78fizzbuzz11fizz1314fizzbuzz1617fizz19buzzfizz2223fizzbuzz26fizz2 829fizzbuzz3132fizz34buzzfizz3738fizzbuzz41fizz4344fizzbuzz4647fizz49buzzfizz525 3fizzbuzz56fizz5859fizzbuzz6162fizz64buzzfizz6768fizzbuzz71fizz7374fizzbuzz7677f izz79buzzfizz8283fizzbuzz86fizz8889fizzbuzz9192fizz94buzzfizz9798fizzbuzz

我試圖實現一下 FizzBuzz 程序，而這個測試使得我不得不修復一些編譯器當中的錯誤，從而讓這個用例能夠正常工作。我不得不花了一段時間弄明白為什么這個用例無法工作，我發現結果是括號并未匹配，因為我的編譯器只能夠處理一段語句全部位于一行當中的情況，最終我讓這個用例成功地通過了。我成功用屬于自己的編程語言實現了 FizzBuzz！

我編寫的 Swift 代碼比較糟糕，此外需要把一些用 struct 的地方改寫為 enum ；
沒有實現優化。Ruby 代碼并不是世界上運行最快的代碼，我很肯定將我的代碼編譯為 Ruby 運行會導致運行速度極大地減慢；
需要能夠在函數域當中定義新變量。函數之類的東西目前并不太理想；
沒有錯誤消息。如果沒有生成正確的 s-表達式 ，程序僅僅只是報告一個致命錯誤。這使得找出何種原因導致編譯失敗變得異常困難；
沒有語義分析錯誤。您可以使用錯誤的參數數量來定義函數，還可以使用錯誤的參數數量來調用函數，此外還可以將某個實際上是函數的東西定義為一個變量，這些操作都仍然可以編譯為 Ruby，但是實際上這個做法應該是被禁止的；
我將去探索如何直接將代碼編譯為機器代碼，我覺得這將是一件非常有趣的事情。

此外：

沒有合適的標準庫。我現在正在借用 Ruby 的標準庫；
注釋不起作用（我知道肯定會有朋友希望我構建一個禁止編寫注釋的編程語言）；
沒有 Lambda 表達式的概念，如果 Lisp 當中沒有 Lambda，那么這會很奇怪的；
表達式當中只能包含一個簡單的表達式，因此函數體目前必須是純函數。目前沒有辦法說打印一個值，然后再調用另一個函數。

首先是： 不要為了一次會議的演講而真的去動手開寫一個編譯器！ 這里面的工作量真的太大了。除非你想在自己的職稱當中加上一個：編譯器工程師。

對編譯器進行測試是非常必要的，因為我沒必要寫一個一次性的玩意兒，只在第一次用的時候才工作正常，隨后就報廢了。

Swift 當中進行字符串解析真的是件折磨人的事情。Unicode 大法好，但是這也使得解析源文件之類的事情變得無比的困難。

錯誤消息也是一個很難的事。這看起來很簡單，但是要報告為什么在解析的時候這個地方出現了錯誤、發生了何種錯誤真的非常難，此外我該如何表達？「您在這里遺漏了一個右括號？」

我所希望使用的 LLVM API 是專門為類型語言設計的，從中我們可以推斷出這個變量的類型是 Int32 ，或者這個函數存在函數簽名。

實現屬于自己的編程語言是很有趣的，同時也很有意義。在我的 Github 上，我實現了一個屬于自己的編程語言。不過實際上，那些能夠實際使用的編程語言遠遠比我上周所做的那些玩意兒要厲害得多，因為它們是人們花費了大量時間、經歷和技術所完成的。因此，后面如果我想抱怨 Swift 不能做什么的時候，我想我可能會更好地理解 Swift 開發人員的心情。因為這玩意兒實在是太難了。

來自：https://realm.io/cn/news/tryswift-samuel-giddins-building-tiny-compiler-swift-ios/

本文由用戶 iunj9154 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1480323684773.html

編譯器 Swift Apple Swift開發

用 Swift 搭建一個微型編譯器

為啥要編寫一個編譯器呢？

相關經驗

相關資訊

相關文檔

目錄