學習編譯系統的心得

金字塔門檻

fig 1

fig 2

fig 3

fig 4

fig 5

fig 6

fig 7

fig 8

fig 9

fig 10

20170128 是 2017 的農曆新年 (大年初一), 就來點溫馨的學習文章好了。

在看了知乎《如何学习编译原理？》這個問題後, 我寫下這篇 (由於實名認證, 現在我已經無法在知乎 po 文), 這是個好問題, 光是發現怎麼學習編譯原理就花了不少時間, 也買了不少書, 但每本書的實作都不同, 讓學習更難了。希望這篇文章能幫助和我一樣想學習編譯器的朋友, 也紀錄著我自己的學習之路。

os 和 compiler 大概是資工本科功夫裡頭基本中的基本, 但基本可不代表他們很簡單, 一定有很多人想要掌握這兩塊, 也一定很多人失敗了, 我也曾經失敗幾次後再度挑戰, os 我已經略有小成, 編譯技術則剛開始。這篇紀錄我如何找到學習編譯原理的方法, 希望對有興趣的人有所幫助。

有人說編譯器很簡單, 有人說很難, 我是認為很難的那一派別, 也許每個人程度都不同, 所以認定方式也不同, 我之前完成了一個小型 os kernel, 但對我學習編譯器不太有幫助, 在開始的時候, 我還是覺得很難, 而就算是我完成了一個玩具型的 c 編譯器的現在, 我也還是覺得很難。

Re: [問卦] 有沒資工系畢業門坎 沒"自己的編譯器"這要求?

這篇回文也和編譯器相關, 很豐富。

真的有決心要學習編譯原理的話, 請從金字塔門檻圖一步步從底層爬上來, 所有的東西都手工打造, 絕對不要使用 flex/bison 之類的工具, 但如果是工作上的專案, 我是贊成使用這些工具的, 畢竟能減輕工作份量, 沒理由不使用的。

我似乎忽略了 debugger, debugger 嚴格來說不應歸類在編譯系統, 但實際上沒有 debugger 是很難除錯的, 要「全端」 (full stack) 地學習編譯系統, 應該要補上 debugger 的, 而 debugger 的難度, 我覺得應該是最難的。

在我最後更新本篇文章時 (20170609), 我來到了 assembler 階段, 真是令人開心, 只剩下 linker 了呢, 如果再完成 linker, 就可以完整體驗編譯原理了。當然, 在學習過程我簡化不少東西, 以下便是我的學習心得。

若以不那麼嚴謹的方式來說, 其實我已經會寫 compiler, assembler, linker, loader, 剩下 debugger。

買書一向是我的主要學習方式, fig 1 是一開始我擁有的書, 翻閱之後卻發現有一種無所適從的感覺, 每本書好像都寫的不錯 (我會過濾爛書, 但其實在繁體中文的世界沒什麼可以挑), 但又好像有什麼不足之處, 總之我沒學成。

fig 2 ~ fig 10 是我在進入簡體中文世界後所購得的書籍, 有了新武器後, 201604 我再次挑戰編譯器這個題目, 一樣感到困難, 沒有因為這些新武器而得到救贖。和學習寫 os kernel 完全不同, 我幾乎只靠 2 本書, 就可以寫出 os kernel 了, 但買了這麼多編譯器的書, 卻還是覺得困難, 找不到適合自己的書。

再繼續堅持下去後, 從中摸索如何學習編譯器就花了不少時間, 打定學習方式後, 慢慢有了進步。

學習重點一樣是簡化再簡化, 但要怎麼簡化就是學問了。

買的書中有些是實作 pascal (fig 1 右下那兩本), 有些是用 java 來實作編譯器, 但我想要用 c++ 來實作 c 語言編譯器, 其實是想寫 c++ 編譯器, 但 c++ 太複雜, 惦惦自己的斤兩, 退一步實作 c 編譯器好了。而選擇 java 實作的書是無奈之舉 (不是我沒注意到, 就是需要其內容), 我需要該書裡頭的知識, 所以只能認了, 事實上, 書單中只有一本是用 c++ 實作編譯器。

而買的書一定要有完整的範例程式, 絕對不要買理論型的書籍 (對, 就是在說那本), 對於初學者來說, 絕對不可能靠理解理論來完成編譯器, 編譯器是很難的程式, 在真實世界上, 也僅有少數人有能力寫出來。沒有一個範例在那邊讓我們參考,不是一個有效率的學習方式。

而事實上, 我發現書中對於講解程式碼的部份都很薄弱, 幾乎都要自己去追蹤這些程式碼, 才能看懂在寫什麼, 不怪作者們, 因為要怎麼講清楚這些程式碼還真的蠻難的。這應該是這類型的程式一般人很少寫過, 所以很陌生, 幸運的是, 努力追蹤這些程式碼一段時間後, 就會習慣了。

再來是要實作那個語言? 當然是實作你有在用或是喜歡的語言, 如果你喜歡 python, 那實作 python 絕對比實作你不會的 pascal 還能引起你的興趣, 我根本沒在用 pascal, 怎麼可能有興趣去實作 pascal。動力是很重要的, 因為跌跤的時間會佔了很大一部份, 沒有繼續前進的動力, 很容易就放棄了, 而興趣就是你源源不絕的動力來源。

再來是 c 很複雜, 有辦法全部實作她嗎? 可能可以, 但在 lexer 就得花上不少時間, parser 可能要更久, 像以下的宣告:

void (*f[10]) (int, int);
char (*(*x())[]) ();
char (*(*x[3])())[5];

要付出不少時間來實作, 而一開始的我, 也沒有能力可以處理這種複雜的 ebnf。

我的重點在實作整個編譯流程:

1. lexer
2. parser
3. AST
4. C preprocessor
5. interpreter
6. 輸出組合語言
7. 實作 assembler
8. 實作 linker
9. 實作 virtual machine
10. 實作 jit
11. 實作 GC

這些我都想跑過一遍, 簡化這些是很重要的, 要怎麼縮短時間, 又能完整的走過一遍。編譯系統並不是只有編譯器一項, 還有很多很多的東西一起組合起來的, 大部份的書都只著重在編譯器上, 其實是遠遠不夠的, 這樣對於編譯系統的技術就會少了一些拼圖, 神功未成, 有了死角, 豈不可惜。

我喜歡研究微小的整體, 而不是某個部份的深入, 「麻雀雖小, 五臟俱全」, 可以用來形容我的學習風格。

所以我把 c 簡化成只實作:

• if/else, while, function call
• type 只支援 char, int

當然還有指標, c 語言沒實作指標還能算是 c 嗎? 簡化時有些可以省略, 有些不行, 指標就是不能省略的部份, 別小看這些簡化後的目標, 乍看之下很簡單, 一寫下去知道, 難度還是很高的。

所以最後實作的 simple c interpreter 是有支援指標的。疑, 不是要寫編譯器嗎? 怎麼變成直譯器了, 哎呀! 功力不夠, 只好先改變目標。Joel 的邊走邊開槍你沒讀過嗎? 不過就算是 interpreter 也是存在某種難度的。

再來是 lex, parser 都一定要自己實作, 絕對不用 flex, bison, 要練習怎麼可以偷懶呢? 這些都要自己做。但如果是工作上的專案, 我建議使用 lex, bison, 這會大幅減低程式的負擔, 也會提高整體的正確性, 更擁有方便的彈性。

再來我選擇要產生 AST, 不產生 AST 的作法也有, 但我要實作 AST, 這部份我在《两周自制脚本语言》獲得此技能, 雖然這本書是使用 java, 而我是用 c++, 但這本書的 java code 依然給了我很好的參考, 讓我得以突破 lexer, parser, AST 這三道關卡。

實作出 fig 21, fig 22 的 AST 時, 那種興奮感一定很多人都可以體會。我建議最好可以把 AST 具象化, 若不能很清楚的看到自己建立的 AST, 一定會覺得很模糊, 有一種我真的把 AST 建對了的疑惑。這邊可能會是第一個卡關的地方。tree 可是一個很難搞的資料結構, 要怎麼確定建立的 AST 是對的呢? 還有比把它印出來更可靠的方法了嗎?

再來的 interpreter 我就沒靠相關的 compiler 書籍了, 因為我在 SICP 4.1 中獲得了這個技能。

在 SICP 我實作了 4.1 的 scheme (一樣用 c++ 實作), 所以接下來的 eval 我靠自己的能力就可以完成。這可不是件容易的事情, 在這裡是可能會卡住的第二關。

實作 AST 可以怎麼開始呢? 因為總共有:

list 1

1. 四則運算
2. 使用變數
3. if/else
4. while
5. function declare/definition
6. function call

要處理。

為什麼要搞定這些, 因為有了這些結構, 實作出來的簡化 c 語言就不再是玩具, 而是真的可以用來寫程式, 你總不希望辛苦搞定的語言, 什麼都不能做吧, 為此目的我還實作出 printf, 讓這個 interpreter 更有實際功用, 當可以用 recursive 算出 5! 時, 超興奮 der。

parser 要怎麼進行才能減低學習負擔呢? 先從《四則運算》開始, 能把 1+2*(9-2) 的 AST 產生出來, 就已經邁進了一大步, 很有成就感。而且在這樣的拆解後, 難度下降, 也可以用下班後的少數時間來實作, 不需要一個很大塊很完整的時間來學習。而當完成《四則運算》後, 你就會尊敬每個平台上都有的計算機程式, 這可不是容易寫的程式哦! 我不知道寫了多少張的 A4 紙, 就只是為了描述這個《四則運算》的 AST, 到寫文章的這個時候, 我已經對 AST 有所感覺了。

再來就照 list 1 的順序慢慢實作, 我就是這樣把所有功能完成的。

我買的書籍中, 有些有很嚇人的理論和資料結構, 理論很難懂, 資料結構很難實作, 很有可能實作這些資料結構就得花不少時間, 但我沒有用到這些還是把玩具等級的 interpreter 做出來了。

記得你是來學習寫編譯程式, 不是來練習資料結構的。雖然我用的是 c++, 但也沒用到特別的東西, 只用到 if/else, while, function call, 一點 class, vector, stirng, map, 也沒用到多型, 但這樣的武器就已經足夠完成一個玩具版的練習了。在提醒一次, 記得你是來學習寫編譯程式, 不是來把玩 c++ 的。

你還要把時間花在精巧的 c++ 語言特性嗎? 不, 我喜歡把時間用在實作某個東西上, c++ 語言特性有他的好處, 但不一定是必須的, 你能寫出很酷的或是讓人迷惑的 c++ 程式碼, 但我可以寫編譯器, 而裡頭只用到 if/else, function call, while loop, 沒有什麼特別的 c++ 語法, 那個厲害呢? 吾 ... 都很厲害, 看怎麼選擇而己, 當然如果可以兩個都掌握那是最棒的。

雖然寫程式很有趣, 但世界上還有很多有趣的事情, 我希望能把時間也分點給這些有趣的東西, 要能同時掌握這兩項可能要很久之後了。

fig 21

fig 22

我目前走到了《產生 asm》這塊 (在我更新本文時, 我已經在寫組譯器, 可以讓 gnu ld link 出 elf 執行檔, 不過, 我在這裡停止開發了), 還有很多部份需要努力, 而且愈來愈難。我用一樣的方式來學習《產生 asm》, 一開始還是處理《四則運算》, 不過其難度比我想像中的要難很多, code generator 比 interpreter 難了 5 倍以上, 我刻意不看書上的實作, 完全自己想, 還真的有點吃不消, 方法可能不是最好, 但這可都是我自己想出來的哦! 這樣的成就感, 實在是令人滿足, 作夢都會笑。實在想不出方法, 再來查閱書籍。

在學生時代把這些完成是比較好的, 但我在想, 如果是學生時代的我, 有能力完成定下的這些目標嗎? 大概不行, 那時候可能沒這麼多的學習資訊, 我的程式功力也很差 (這當然不是說我現在就比較好), 直接挑戰編譯器可能太難了, 對於組合語言也不熟悉, 那怎麼可能寫得出 code generator 呢? 可能連 lexer, parser 的狀態機都能難倒我, 程式真的就像砍柴一樣, 一直砍, 一直砍, 就能找到訣竅。但如果在學生時代努力過, 就算沒成功, 也不是壞事。

把這些都簡化實作過一次, 就相當於走過一輪了, 有興趣的部份再去深入。

有些書是用 LLVM 來打造自己的編譯器, 我一樣建議真正要學習的朋友不要使用 LLVM, 這樣會漏掉一些拼圖, 但如果是工作上的專案, 我是很贊成使用的, 正確性高, 有最佳化的功能, 開發速度快。

不過學習最忌諱速度快, 真正專業的東西是沒有捷徑的, 只能像螞蟻一樣, 一次爬一小步, 慢慢的累積這些專業, 一旦掌握了好幾個部份, 再把他們組合起來, 擁有這些深厚的基礎, 就是自己的優勢所在。

現在有些速食課程, 號稱在短短時間就可以怎麼樣, 也許你真的在短時間完成了什麼, 但如果要繼續下去, 該花的時間還是要補回來的, 我不相信有什麼快速學習方法。『真正有用的知識, 都不是那麼容易獲得的。』

ref:
寫自己的程式語言 (For Rubyist) 一文, 作者是文組學生, 卻開發出自己的程式語言, 資工本科系還不見得可以作到這件事情, 真是不簡單。參考其《自學歷程 (1)》