自舉 (編譯器)

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

計算機科學中,自舉是一種自生成編譯器的技術——也就是,某個編程語言編譯器(或匯編器)是由該語言編寫的。最初的核心編譯器(自舉編譯器)是由其他編程語言生成的(可以是使用匯編語言),而之後版本的編譯器則是使用該語言的最小子集編寫而成。自生成編譯器的編譯問題被稱為編譯器設計先有雞還是先有蛋問題,而自舉則是這個問題的解決方法。[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).