開發(fā)者“瘋狂”整活：用純 C 語言，從頭編寫一個(gè) Rust 編譯器！

C語言與CPP編程

本文經(jīng)授權(quán)轉(zhuǎn)自公眾號(hào)CSDN（ID：CSDNnews）
作者 | John Nunley，翻譯 | 鄭麗媛
近日，一個(gè)項(xiàng)目在 HN 上引起了許多開發(fā)者的注意——一名富有創(chuàng)新精神的開發(fā)者正在嘗試使用 C 語言來編寫 Rust 編譯器。這位開發(fā)者表示：為了引導(dǎo) Rust 發(fā)展，無論付出什么代價(jià)都值得。
原文鏈接：https://notgull.net/announcing-dozer/
細(xì)心的 Rust 愛好者可能已經(jīng)注意到，我最近不太活躍。導(dǎo)致這種情況的原因有很多：最近我經(jīng)歷了一系列非常糟糕的事情，包括一位親人的離世讓我感到極其意外，同時(shí)我在工作中承擔(dān)了更多責(zé)任，不再有很多時(shí)間和精力去貢獻(xiàn)開源項(xiàng)目了。亦或許，我也失去了當(dāng)初在大學(xué)時(shí)代、那種足以讓我全身心投入開源世界的熱情。
除此之外，還有另一個(gè)原因：我正忙于一個(gè)占據(jù)了我大部分業(yè)余時(shí)間的項(xiàng)目。這個(gè)項(xiàng)目是我在開源領(lǐng)域中創(chuàng)建的最大型的一個(gè)，如果我最后能完成它，那它一定會(huì)成為我的巔峰之作。
我正在用純 C 語言編寫一個(gè) Rust 編譯器：不用 C++，不用 flex 或 yacc，甚至不用 Makefile——僅僅用純 C 語言。這個(gè)項(xiàng)目叫做 Dozer。
1、為什么要這么做？
想要理解我為何走上這條“瘋狂”之路，你首先需要了解 Bootstrapping（引導(dǎo)法）以及它的重要性（所謂引導(dǎo)法，這是一種在編程中常見的技術(shù)，意為通過已有的基本代碼或資源來構(gòu)建更復(fù)雜的系統(tǒng)或工具）。
假設(shè)你用 Rust 寫了一些代碼，為了運(yùn)行這些代碼，你需要先編譯它們。編譯器是一種程序，它會(huì)解析你的代碼，驗(yàn)證其正確性，然后將其轉(zhuǎn)換為 CPU 可以理解的機(jī)器代碼。
對(duì)于 Rust 來說，主要的編譯器是 rustc——也就是你運(yùn)行 cargo build 時(shí)所調(diào)用的底層程序。不得不說，rustc 是一個(gè)很棒的軟件，甚至可以說是開源社區(qū)的瑰寶，其代碼質(zhì)量可以媲美 Linux 內(nèi)核和 Quake III 源代碼。
然而，rustc 本身也是一個(gè)程序，所以它也需要一個(gè)編譯器將其從源代碼編譯為機(jī)器代碼。那么問題來了：rustc 是用什么語言編寫的呢？

這樣來看，rustc 是一個(gè)用 Rust 編寫的程序，其目的是為了編譯 Rust 代碼。但請仔細(xì)想想，如果 rustc 是用 Rust 編寫的，而我們又需要用 rustc 來編譯 Rust 代碼，這意味著我們需要用 rustc 來編譯 rustc……？
對(duì)于一般用戶來說，這其實(shí)沒什么問題，因?yàn)槲覀兛梢灾苯訌木W(wǎng)上下載 rustc 并使用它。但有個(gè)問題：第一個(gè) rustc 是誰編譯的，總得先有“雞”才有“蛋”吧？這到底是從哪里開始的？
其實(shí)，這個(gè)問題并不復(fù)雜：每個(gè)新 rustc 版本都是由前一個(gè)版本的 rustc 編譯出來的。也就是說，rustc 1.80.0 版本是用 rustc 1.79.0 版本編譯的，rustc 1.79.0 版本又是由 rustc 1.78.0 版本編譯的……以此類推，一直可以追溯到 rustc 0.7 版本。而那時(shí)，編譯器是用 OCaml 寫的，因此只需要一個(gè) OCaml 編譯器就能得到一個(gè)完整的 rustc 程序。
好了，問題解決了，我們已經(jīng)搞清楚如何從頭開始創(chuàng)建 rustc。但是，要讓這一切都正常工作，我們?nèi)孕枰�一個(gè) OCaml 編譯器的版本。所以說，OCaml 編譯器又是用什么語言編寫的呢？

額……沒事兒！有一個(gè)項(xiàng)目能成功用 Guile 編譯 OCaml 編譯器，而 Guile 是 Scheme 的眾多變體之一，Scheme 又是 Lisp 的眾多變體之一。另外，Guile 的解釋器是用 C 編寫的。
于是，這一切最終都指向了 C 語言。我們只需用 GCC 來編譯它，一切就能順利進(jìn)行。那么我們只需要編譯 GCC，而 GCC 是用……C++編寫的？！
這個(gè)說法有點(diǎn)不準(zhǔn)確。GCC 直到第 5 版之前都是用 C 語言編寫的，這世上也并不缺少用 C 編寫的 C 編譯器……但這仍然沒有回答我們的問題。第一個(gè) C 編譯器是用什么寫的？匯編語言？那么第一個(gè)匯編器又是用什么寫的呢？

2、原理介紹
這就是我要介紹 Bootstrappable Builds 項(xiàng)目的目的。在我看來，這就是開源社區(qū)中最有趣的項(xiàng)目之一，也基本上屬于代碼煉金術(shù)。
其 Linux 引導(dǎo)過程從一個(gè) 512 字節(jié)的二進(jìn)制種子開始。這個(gè)種子包含了一個(gè)最簡單的編譯器：能接收十六進(jìn)制數(shù)字并輸出相應(yīng)的原始字節(jié)。例如，以下為該編譯器編譯的部分“源代碼”：

31 C0           # xor ax, ax8E D8           # mov ds, ax8E C0           # mov es, ax8E D0           # mov ss, axBC 00 77        # mov sp, 0x7700FC              # cld ; clear direction flag88 16 15 7C     # mov [boot_drive], dl注意，井號(hào)后的所有內(nèi)容都是注釋，所有的空白字符也都被去掉了。坦白說，我甚至不確定這能否被稱為編程語言。但嚴(yán)格來說，這確實(shí)是可分析、可剖析的源代碼。
接下來，這個(gè)編譯器就會(huì)編譯一個(gè)非常簡單的操作系統(tǒng)，一個(gè)簡陋的 shell，以及一個(gè)稍微高級(jí)一點(diǎn)的編譯器。那個(gè)編譯器又編譯了一個(gè)更高級(jí)一點(diǎn)的編譯器。這樣幾步之后，你就有了類似匯編代碼的東西。

DEFINE cmp_ebx,edx 39D3DEFINE je 0F84DEFINE sub_ebx, 81EB
:loop_options    cmp_ebx,edx                         # Check if we are done    je %loop_options_done               # We are done    sub_ebx, %2                         # --options說到這兒，你會(huì)覺得我把匯編代碼當(dāng)作比其他東西更高層次的語言，好像有點(diǎn)奇怪，對(duì)吧？
但這就足以得到一個(gè)非常基礎(chǔ)的 C 語言子集，然后，利用這個(gè)子集編譯一個(gè)稍微高級(jí)一點(diǎn)的 C 編譯器。幾步之后，就能編譯 TinyCC 了。接著可以引導(dǎo) yacc、基本 coreutils、Bash、autotools，并最終到達(dá) GCC 和 Linux。
我這樣講，可能還是沒法完全體現(xiàn)出這個(gè)過程的魅力，但這真的很引人入勝�？傊�，從“一個(gè)小到足以手動(dòng)分析的二進(jìn)制文件”開始，一步步到 Linux、GCC，再到基本上所有其他的東西，你基本上都經(jīng)歷過了。不過，我們還是從 TinyCC 開始再來一次吧。
目前，Rust 在這個(gè)過程中出現(xiàn)得非常晚。他們使用 mrustc，這是一種用 C++ 編寫的 Rust 替代實(shí)現(xiàn)，可以編譯 rustc 1.56 版本。在此基礎(chǔ)上，他們再編譯現(xiàn)代 Rust 代碼。
這里的主要問題是，到引入 C++ 時(shí)，引導(dǎo)過程基本上已經(jīng)結(jié)束了。因此，如果你想在引入 C++ 之前的任何時(shí)候使用 Rust，那是不可能的。
所以，對(duì)我來說，如果有一個(gè) Rust 編譯器能夠從 C 開始引導(dǎo)，那就太好了。具體來說，就是一個(gè)可以從 TinyCC 開始引導(dǎo)的 Rust 編譯器，同時(shí)假設(shè)系統(tǒng)中還沒有可能有用的工具——這個(gè)編譯器就是 Dozer。

3、未來計(jì)劃
過去兩個(gè)月中，我一直在忙于 Dozer 項(xiàng)目：把我那本就少得可憐的空閑時(shí)間，用來編寫一種我有點(diǎn)討厭的語言。
這個(gè)項(xiàng)目沒有使用任何擴(kuò)展功能，目前 TinyCC 和 cproc 都能順利編譯。我使用 QBE 作為后端。除此之外，我假設(shè)系統(tǒng)上沒有其他工具，只有一個(gè) C 編譯器和一些非�；�礎(chǔ)的 shell 實(shí)現(xiàn)，再無其他。
在本文中，我不會(huì)深入探討編寫一個(gè)編譯器的原始體驗(yàn)。但到目前為止，我已經(jīng)完成了詞法分析器，還完成了相當(dāng)大一部分的語法解析器。宏/模塊擴(kuò)展我會(huì)盡量推遲，類型檢查目前只支持 i32，而代碼生成還稍顯粗糙——但這已經(jīng)是一個(gè)不錯(cuò)的開始了。
目前，我已可以成功編譯以下代碼：

fn rust_main() -> i32 {    (2 - 1) * 6 + 3}那么，接下來怎么辦呢？這是我的計(jì)劃：
（1）慢慢推進(jìn) Dozer，直到它能夠編譯一些使用 libc 的基本示例代碼，然后再編譯 libcore，最后到 rustc。（順便提一下，我計(jì)劃編譯 rustc 的 Cranelift 后端，這部分完全是用 Rust 編寫的。由于我們假定還沒有 C++，所以無法編譯 LLVM。）
（2）創(chuàng)建一個(gè)等同于 cargo 的工具，可以用 Dozer 來編譯 Rust 包。
（3）找出 rustc 中那些自動(dòng)生成的代碼源文件，并將它們剔除。根據(jù) Bootstrappable 項(xiàng)目的規(guī)則，不允許使用自動(dòng)生成的代碼。
（4）創(chuàng)建一個(gè)可以用來編譯 rustc 和 cargo 的過程，然后使用我們編譯的 rustc/cargo 版本重新編譯標(biāo)準(zhǔn)版本的 rustc/cargo。
毫無疑問，這是我迄今為止創(chuàng)建的最困難的項(xiàng)目，我也很懷疑自己到底能否完成它。但你知道嗎？嘗試過卻失敗了，總比從未嘗試過要好。
本文轉(zhuǎn)自公眾號(hào)“CSDN”，ID：CSDNnews——EOF——你好，我是飛宇。日常分享C/C++、計(jì)算機(jī)學(xué)習(xí)經(jīng)驗(yàn)、工作體會(huì)，歡迎點(diǎn)擊此處查看我以前的學(xué)習(xí)筆記&經(jīng)驗(yàn)&分享的資源。
我組建了一些社群一起交流，群里有大牛也有小白，如果你有意可以一起進(jìn)群交流。

歡迎你添加我的微信，我拉你進(jìn)技術(shù)交流群。此外，我也會(huì)經(jīng)常在微信上分享一些計(jì)算機(jī)學(xué)習(xí)經(jīng)驗(yàn)以及工作體驗(yàn)，還有一些內(nèi)推機(jī)會(huì)。


加個(gè)微信，打開另一扇窗
經(jīng)常遇到有讀者后臺(tái)私信想要一些編程學(xué)習(xí)資源，這里分享 1T 的編程電子書、C/C++開發(fā)手冊、Github上182K+的架構(gòu)路線圖、LeetCode算法刷題筆記等精品學(xué)習(xí)資料，點(diǎn)擊下方公眾號(hào)會(huì)回復(fù)"編程"即可免費(fèi)領(lǐng)取~
感謝你的分享，點(diǎn)贊，在看三連