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

C語(yǔ)言與CPP編程

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

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

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

2、原理介紹
這就是我要介紹 Bootstrappable Builds 項(xiàng)目的目的。在我看來(lái)，這就是開(kāi)源社區(qū)中最有趣的項(xiàng)目之一，也基本上屬于代碼煉金術(shù)。
其 Linux 引導(dǎo)過(guò)程從一個(gè) 512 字節(jié)的二進(jìn)制種子開(kāi)始。這個(gè)種子包含了一個(gè)最簡(jiǎn)單的編譯器：能接收十六進(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)容都是注釋，所有的空白字符也都被去掉了。坦白說(shuō)，我甚至不確定這能否被稱為編程語(yǔ)言。但嚴(yán)格來(lái)說(shuō)，這確實(shí)是可分析、可剖析的源代碼。
接下來(lái)，這個(gè)編譯器就會(huì)編譯一個(gè)非常簡(jiǎn)單的操作系統(tǒng)，一個(gè)簡(jiǎn)陋的 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說(shuō)到這兒，你會(huì)覺(jué)得我把匯編代碼當(dāng)作比其他東西更高層次的語(yǔ)言，好像有點(diǎn)奇怪，對(duì)吧？
但這就足以得到一個(gè)非�；�礎(chǔ)的 C 語(yǔ)言子集，然后，利用這個(gè)子集編譯一個(gè)稍微高級(jí)一點(diǎn)的 C 編譯器。幾步之后，就能編譯 TinyCC 了。接著可以引導(dǎo) yacc、基本 coreutils、Bash、autotools，并最終到達(dá) GCC 和 Linux。
我這樣講，可能還是沒(méi)法完全體現(xiàn)出這個(gè)過(guò)程的魅力，但這真的很引人入勝�？傊�，從“一個(gè)小到足以手動(dòng)分析的二進(jìn)制文件”開(kāi)始，一步步到 Linux、GCC，再到基本上所有其他的東西，你基本上都經(jīng)歷過(guò)了。不過(guò)，我們還是從 TinyCC 開(kāi)始再來(lái)一次吧。
目前，Rust 在這個(gè)過(guò)程中出現(xiàn)得非常晚。他們使用 mrustc，這是一種用 C++ 編寫的 Rust 替代實(shí)現(xiàn)，可以編譯 rustc 1.56 版本。在此基礎(chǔ)上，他們?cè)倬幾g現(xiàn)代 Rust 代碼。
這里的主要問(wèn)題是，到引入 C++ 時(shí)，引導(dǎo)過(guò)程基本上已經(jīng)結(jié)束了。因此，如果你想在引入 C++ 之前的任何時(shí)候使用 Rust，那是不可能的。
所以，對(duì)我來(lái)說(shuō)，如果有一個(gè) Rust 編譯器能夠從 C 開(kāi)始引導(dǎo)，那就太好了。具體來(lái)說(shuō)，就是一個(gè)可以從 TinyCC 開(kāi)始引導(dǎo)的 Rust 編譯器，同時(shí)假設(shè)系統(tǒng)中還沒(méi)有可能有用的工具——這個(gè)編譯器就是 Dozer。

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

fn rust_main() -> i32 {    (2 - 1) * 6 + 3}那么，接下來(lái)怎么辦呢？這是我的計(jì)劃：
（1）慢慢推進(jìn) Dozer，直到它能夠編譯一些使用 libc 的基本示例代碼，然后再編譯 libcore，最后到 rustc。（順便提一下，我計(jì)劃編譯 rustc 的 Cranelift 后端，這部分完全是用 Rust 編寫的。由于我們假定還沒(méi)有 C++，所以無(wú)法編譯 LLVM。）
（2）創(chuàng)建一個(gè)等同于 cargo 的工具，可以用 Dozer 來(lái)編譯 Rust 包。
（3）找出 rustc 中那些自動(dòng)生成的代碼源文件，并將它們剔除。根據(jù) Bootstrappable 項(xiàng)目的規(guī)則，不允許使用自動(dòng)生成的代碼。
（4）創(chuàng)建一個(gè)可以用來(lái)編譯 rustc 和 cargo 的過(guò)程，然后使用我們編譯的 rustc/cargo 版本重新編譯標(biāo)準(zhǔn)版本的 rustc/cargo。
毫無(wú)疑問(wèn)，這是我迄今為止創(chuàng)建的最困難的項(xiàng)目，我也很懷疑自己到底能否完成它。但你知道嗎？嘗試過(guò)卻失敗了，總比從未嘗試過(guò)要好。
本文轉(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è)微信，打開(kāi)另一扇窗
經(jīng)常遇到有讀者后臺(tái)私信想要一些編程學(xué)習(xí)資源，這里分享 1T 的編程電子書(shū)、C/C++開(kāi)發(fā)手冊(cè)、Github上182K+的架構(gòu)路線圖、LeetCode算法刷題筆記等精品學(xué)習(xí)資料，點(diǎn)擊下方公眾號(hào)會(huì)回復(fù)"編程"即可免費(fèi)領(lǐng)取~
感謝你的分享，點(diǎn)贊，在看三連