自舉 (編譯器)

编程语言使用自身编写出能编译自己语言的编译器的过程

電腦科學中,自舉是一種自生成編譯器的技術——也就是,某個程式語言編譯器(或組譯器)是由該語言編寫的。最初的核心編譯器(自舉編譯器)是由其他程式語言生成的(可以是使用組合語言),而之後版本的編譯器則是使用該語言的最小子集編寫而成。自生成編譯器的編譯問題被稱為編譯器設計先有雞還是先有蛋問題,而自舉則是這個問題的解決方法。[1][2]

自舉對於建立一個新的程式語言是很普遍的做法,有很多程式語言已經實現了自舉。

步驟

編輯

一個典型的編輯器自舉過程分三到四步:[3][4][5]

  • 步驟0:準備自舉編譯器的工作環境,選擇自舉編譯器的程式語言和輸出語言。在裸機(也就是沒有任何語言的編譯器)的情況下,原始碼和輸出代碼需被編寫為二進制機器碼,或者可以通過在目標機器之外的其他機器上交叉編譯來建立。否則,該語言的自舉編譯器必選使用目標機器上存在的一種語言編寫而成,並且將生成可以在目標機器上執行的東西,包括高階程式語言、組合語言、對象檔案、甚至機器碼。
  • 步驟1:生成自舉編譯器。這個編譯器能夠將自己的原始碼編譯成能在目標機器上執行的程式,之後的語言開發將會在這個自舉編譯器所支援的語言上拓展,進入步驟2。
  • 步驟2:使用自舉編譯器生成全功能編譯器。通常是分階段進行的,比如語言版本X的編譯器能夠支援語言版本X+1的功能,但自己不會使用這些功能。一旦這個編譯器完成測試並可自行編譯後,則現在語言版本X+1的功能可能會被編譯器的後續版本使用。
  • 步驟3:使用步驟2的編譯器生成全功能編譯器。如果需要添加新的語言功能,則從步驟2重新開始。從這時候開始,可以使用步驟3生成的編譯器代替自舉編譯器來繼續該語言的開發。

全功能編譯器被構建了兩次,用於比較兩個階段的輸出。 如果它們有不同,則自舉編譯器或者全功能編譯器存在缺陷。[3]

優點

編輯

編譯器自舉有以下優點:[6][7]

  • 通過吃自己的狗糧的方式,對正在編譯的語言進行測試,而且這很重要。
  • 編譯器開發人員和缺陷報告人員只需要知道當前編譯的語言。
  • 編譯器的開發可以在當前編譯的高階程式語言上進行。
  • 對編譯器後端的改進,不僅改進了通用程式,而且改進了編譯器本身。
  • 這是一個全面的一致性檢查,因為它應該能夠重現自己的目的碼。

請注意,其中一些要點是假設語言的執行階段也是用相同的語言編寫的。

方法

編輯

如果需要用X語言編寫一個X語言的編譯器,那就會出現「如何編譯出該語言的第一個編譯器」的問題了。通常會有以下方法:

  • 使用Y語言實現X語言的編譯器或直譯器。例如尼克勞斯·維爾特就是用Fortran編譯出第一個Pascal的編譯器。[8]
  • X語言的另一個編譯器或解析器由Y語言編寫成,例如Scheme
  • 編譯器的早期版本是使用該語言的最小子集編寫成,例如JavaHaskellFree Pascal
  • 支援非標準語言擴充或可選語言功能的編譯器可以在不使用這些擴充和功能的情況下編寫,以使其能夠與另一個支援相同的語言基礎部分,但有不同的擴充和功能的編譯器一起編譯。例如C++的編譯器Clang的主要部分是由C++的子集編寫的,可以被 G++或者Microsoft Visual C++的編譯器編譯。進階功能的支援是由一些GCC擴充編寫的。
  • X語言的編譯器是由同語言但不同平台的編譯器交叉編譯得到的,這通常是C編譯器移植到其他硬體平台用到的。Free Pascal完成編譯器自舉後也是這樣繼續開發的。
  • 在語言X中編寫編譯器,但從原始碼手動編譯出來(不包括最佳化方法)並在其上面執行以獲得最佳化的編譯器。高德納就是這樣來進行WEB文學編程

歷史

編輯

第一個自舉編譯器(不包括組譯器)是由 Hart 和 Levin 於 1962 年為 Lisp 編寫的,他們使用 Lisp 編寫了一個 Lisp 編譯器。[9]

目前的改進

編輯

由於對基於信任的信任和二進制可信性的攻擊的擔憂,有一些專案在研究如何改進代碼,使其能從原始碼自行完成自舉,並且讓每個人驗證原始碼和可執行代碼是否如實運作,這包括了可自舉代碼專案及可重生成代碼專案。[10]

參考文獻

編輯
  1. ^ Reynolds, John H. Bootstrapping a self-compiling compiler from machine X to machine Y. CCSC: Eastern Conference. Journal of Computing Sciences in Colleges. December 2003, 19 (2): 175–181 [2023-06-11]. (原始內容存檔於2023-02-25). The idea of a compiler written in the language it compiles stirs up the old 'chicken-or-the-egg' conundrum: Where does the first one come from? 
  2. ^ Glück, Robert. Clarke, Edmund; Virbitskaite, Irina; Voronkov, Andrei , 編. Perspectives of Systems Informatics: 8th International Andrei Ershov Memorial Conference、PSI 2011、Novosibirsk、Russia、June 27 – July 1、2011、Revised Selected Papers. Lecture Notes in Computer Science 7162. Bootstrapping compiler generators from partial evaluators. Springer: 125–141. 2012. doi:10.1007/978-3-642-29709-0_13. Getting started presents the chicken-and-egg problem familiar from compiler construction: one needs a compiler to bootstrap a compiler、and bootstrapping compiler generators is no exception. 
  3. ^ 3.0 3.1 Installing GCC: Building. GNU Project - Free Software Foundation (FSF). [2023-06-11]. (原始內容存檔於2023-08-22). 
  4. ^ rust-lang/rust: bootstrap. GitHub. [2023-06-11]. (原始內容存檔於2023-06-12) (英語). 
  5. ^ Advanced Build Configurations — LLVM 10 documentation. llvm.org. [2023-06-11]. (原始內容存檔於2023-08-09). 
  6. ^ Compilers and Compiler Generators: An Introduction With C++. Patrick D. Terry 1997. International Thomson Computer Press. ISBN 1-85032-298-8
  7. ^ "Compiler Construction and Bootstrapping" by P.D.Terry 2000. HTML 網際網路檔案館存檔,存檔日期2009-11-23.. PDF 網際網路檔案館存檔,存檔日期December 14, 2010,..
  8. ^ Wirth, Niklaus. 50 years of Pascal. Communications of the ACM. 2021-02-22, 64 (3). ISSN 0001-0782. doi:10.1145/3447525. 
  9. ^ Tim, Hart; Mike, Levin. AI Memo 39-The new compiler (PDF). (原始內容 (PDF)存檔於2021-07-26). 
  10. ^ Reproducible Builds — a set of software development practices that create an independently-verifiable path from source to binary code. reproducible-builds.org. [2023-06-11]. (原始內容存檔於2016-05-20).