3上的修課回顧——編譯器

2018 年 2 月 18 日

學弟妹請注意：這不是評論老師的文章，不要把這篇文章當成選課的建議

我修游逸平（yyp）的編譯器設計的課，只是因為我同學說 yyp 的物件導向程式設計很可怕。我管他有多可怕，就直接把他填進選課系統

我覺得我上課很不認真，因為老師講過 L-Attribute 和 S-Attribute ，我卻還是不了解這兩個字的意思，還要等到下課之後，去查維基百科。哈哈～

不過我還是有學到如何使用 lex 和 yacc 來產生語法解析器。這兩個工具超好玩的。當我在這堂課聽到 lex 以後，我第一個嘗試寫的程式叫做音樂代碼分析器（我的個人計畫之一），但是發現很難寫，因為我定的語法並沒有界定明確的 token

在這堂課聽到 yacc 以後，我第一個嘗試寫的程式是 OOPS 程式語言直譯器。OOPS 程式語言是我發明的，故意設計成難以使用的程式語言，好用來說明物件導向是如何的難用。老實說我已經嘗試寫這個編譯器 2 年這麽久，從大一的寒假就在做，可是我卻卡在技術問題而做不出來。剛好學了編譯器的課之後，就可以拿來用了，好開心！

老師總共出了 5 個作業：

  1. 用 lex 解析 P 語言的 token
  2. 用 yacc 描述 P 語言的語法
  3. 建立符號表，檢查 P 程式是否有重複定義的變數。用到 yacc 的 S-Attribute
  4. 檢查 P 語言程式的語意 （型別檢查、變數名稱檢查、……等）
  5. 把 P 程式轉成 Java bytecode assembly，可以用 Jasmin 組譯成 Java 程式。就是 code generation

另外，最後一個作業有 Demo，要去實驗室給助教看程式

以上的 5 個作業是連貫的，5 個作業都做完的話，你就做出了一個 P 語言編譯器。P 語言到底是啥呢？就是 yyp 參考 Pascal 語言後發明的迷你程式語言，語法簡單，方便我們實作

老師說，以前他教這堂課的時候，他只出 4 個作業，但是發現作業 3 太難了，所以這一屆決定把以前的作業 3 分成現在的作業 3 和作業 4

做各個作業的經過

作業 1

我把老師的模板下載下來，然後就在裡面加入幾種 token 的正規運算式。這感覺上是 5 份作業裡最簡單的

看到作業的說明檔要求寫報告，我感到很焦慮。我不知道怎麽寫報告才好。問老師，老師說，就照著說明檔要求的寫就好了，所以我的報告就 隨便寫 寫我的程式的功能

為了確保每一種 token 都有檢查到，我加入幾個測試檔，並把它們加進作業裡。這樣我就是最強的了，哇哈哈～～

我還發現老師的模板裡面，用來顯示每一行原始碼的程式時間複雜度是 O(n2)，因為用了 strcat 指令。我有改掉這個部份，時間複雜度變成 O(n)

在寫作業的時候，看論壇發現好多人都在問問題，我也發現老師給的作業說明不完整，那就是，不知道浮點數是否可以寫成「12.」或「.02」

之後的每份作業都有如此的瑕疵，從此進入由論壇定義規格的時代～～

作業評分完以後，我看了得分，90 分。奇怪，我還有哪裡做錯？

作業 2

再次把老師的模板下載下來，因為我害怕程式的輸出有任何一個字不一樣，就沒有分數

做這份作業的時候，我很怕我描述的語言有誤，因為用 yacc 產生的程式不會輸出語法樹，只會輸出兩種結果：語法正確和語法錯誤

想要加上測試檔，卻發現 e3 上面寫說，交出的作業只能包含 lex 檔、yacc 檔、C 程式、Makefile 和報告。可惡，難道是我上一份作業包含的測試檔，造成改作業的困難嗎？

教授有在上課時講到 Shift/Reduce Conflict 和 Reduce/Reduce Conflict，好險我都沒碰到，要是遇上了，作業可就要花更久來完成啦

作業 3

從這份作業開始，我就被作業追著跑。終於體驗到「交作業」大學的威力了

這個作業要求使用到 符號表（symbol table），而我當時無法決定要用哪種方法實做符號表，於是就上網詢問

編譯器都要有symbol table，到底要用哪種資料結構？演算法？
hash table、二分樹、trie、還是直接開個 char *names[9487]
我的作業要來不及了

有個學長跟我說：「hash table + 1」，於是我就用 雜湊表（hash table）來處理符號表

做這個作業才發現，我在家裡什麼程式都寫不出來。回到家裡，腦袋就好像凍結了一樣，沒辦法思考，大概一整個下午，只能寫出 2 行程式

這次的報告寫得很「詳細」，不，我覺得太冗贅了，因為我把符號表的所有子程序都寫進報告裡。感覺助教要花好一段時間來閱讀了

在這個作業的成績出來後，我終於決定去問助教，為何我第一次作業的成績是 90。助教測試後告訴我，我的程式在遇到 else 關鍵字的輸出是 <KWelas>。哈哈！我打錯字了，應該是 <KWelse>

第 2 次作業的成績是 98，不過我知道哪裡出錯，就是定義函數的語法，我以為是 foo(a:integer,b,c:string)，其實是 foo(a:integer;b,c:string)，不同型別的參數要用分號區隔

作業 4

這個作業有點無聊，因為還是不能執行 P 程式，只能輸出錯誤訊息

而且在做作業的期間，我在論壇上問了很多問題，導致胡安鳳叫我不要再問了，免得又多出一堆要做的功能。我忘了我問過什麼，只記得我為了得知錯誤訊息怎麼輸出，寫了好多個 P 程式，丟到編譯器模擬器

老師為了這個作業寫了一個編譯器模擬器，可以用來測試 P 程式是否符合語意

為了讓我寫的程式更人性化，我參考 gcc 和 Java 編譯器的輸出訊息，使得程式輸出更好理解。老師有說，程式的輸出不需要和模擬器完全一樣，只要訊息合理就好

因為上次報告寫的太冗，這次的報告簡化了不少

作業得到 100 分

作業 5

最好玩的作業，因為我終於可以執行 P 語言程式了！

在作業的開始，我先試用 Jasmin，還有嘗試人力反組譯 Java bytecode，以便得知 Java 程式怎麼運作

不過寫作業的時間正好卡到期末考，還有計算機圖學的作業，還有家庭聚餐，害的我必須延後寫作業

老師說，為了減輕同學的負擔，作業不需要支援字串相連和陣列，不過我還是硬要做

這個作業我交了兩個版本，版本一在 1 月 14 日星期日上傳，做好老師要求的基本功能，沒有陣列功能，也沒有報告（其實是把作業 4 的報告交出來）

在做版本一的時候，我就在想著陣列怎麼處理，因為之前的作業說明有講到，P 語言的陣列是 pass by value 傳值呼叫，所以要做複製陣列的功能

在交出版本一的那天，發現作業期限延期到 1 月 15 日，看來我有機會做出進階功能：陣列。我決定隔天去學校繼續做（隔天也是計算機圖學的 Demo）

在系計中，我看到有同學在 GitHub 上找學長的程式，想要拿去改一改就交作業。我覺得這不是什麼好主意，但我拿他們沒辦法

結果寫進階功能寫好久，大家都陸續交出作業了，而我在晚上 11 點半才寫好程式，還有報告要寫呢

由於當時時間實在不夠，我只好簡潔的寫一下功能就趕快交作業

然後，在越明日（過了 PM 11:59）之後，我發現我的程式有 bug！只要 P 程式的函數有引數，我的程式就會把它編譯成錯誤的 Java bytecode

雖然只要改一行，可是沒辦法改作業了 ;-(

還有 Demo

老師要求最後一個作業要到實驗室 Demo，Demo 日期就是作業期限的下一天，1 月 16 日。我怕怕的，因為我交的程式有 bug

我去 DEMO 得到 110 分，滿分是 150 分。果然被我的程式的 bug 害到了

一開始想說可不可以修程式，結果實驗室裡的助教說，我的分數已經夠高了，不能再改程式。可是我就是不喜歡那種感覺，明明只要改一行而已啊～

其實我的程式還有一個問題，就是編譯產生的 .j 檔案沒有放在工作目錄裡，卻放在原始碼的目錄裡。不過我和助教講說，作業的說明沒有提到這件事，助教就原諒我，並且讓我改檔案輸出的程式

後來，陸續有好多個人，寫出來的編譯器根本連動都不能動，助教才開放每個人在 Demo 的時候改程式，但是扣遲交分數 15 分

我也就跟助教要求改程式，並且把那一行改掉，終於得到 140 分，扣掉遲交分數後是 125 分。等等，怎麼還有一個測資出錯？助教研究了一下發現，我的程式沒有輸出 tab，tab 字元可以寫成 \t，但是我的程式卻沒有印出 tab，而是輸出「反斜線 t」。這也是作業說明沒有提到的事，所以助教算我那個測資正確，我最終得分是 135 分

繼續留在實驗室

自此，已經沒有我的事了，然而我對別人寫得怎麽樣很好奇，所以繼續待在那裡看，也有了幾個發現

  1. 好多人的程式都長的好像，都有 codegen.c，還有那個難以理解的 for 迴圈的單行 bytecode

  2. 助教不知道作業的規格已經改了，關閉原始顯示功能的指令從 //&D- 改成 //&S-，結果測試的時候，都會印出測試程式

    我有和助教反應，然而那裡有 4 個助教，不是每個助教都接受這件事

  3. 還是有人不懂 Java bytecode 裡的 sipush、bipush、iconst 和 ldc。大概是被作業的說明搞混了吧

    作業說明說，sipush 用來把字串放進堆疊，很不幸的這是錯的。根據 Java 虛擬機規格，sipush 是把介於 -32768 ~ 32767 的整數放進堆疊，我想是 short integer push 的簡稱。bipush 和 iconst 都可以把整數放進堆疊，不過有範圍限制。bipush 只支援 -128 ~ 127，iconst 則是 -1 到 5

    ldc 可以把任何的 P 語言整數放到堆疊上，也可以放字串和浮點數

    只能說，多看一下網路上的說明，總會有幫助的

  4. 有人的作業會 Segmentation fault，還有的會產生奇怪的 bytecode 使得 Java 無法執行
  5. 連我認為是大神的人都沒有得到高分，因為他們有別的功課要忙
  6. 在那裡看了一整天，沒有看到其他人有實做陣列的。我該不會是唯一有實做進階功能的人？

因為很多人的程式長的超像的，所以助教覺得是抄襲，被他們發現都是抄襲某一個學長的程式

我也擔心我會被說是抄襲，因為我的程式檔裡也有 codegen.c（誤）我根本就沒有看學長的程式，而且助教說，我的程式太高級了，不會是抄襲的

終於

我的作業放在 GitHub 上面 https://github.com/stdio2016/compile，拜託不要把我的程式拿去交作業啊～～老師絕對不會接受抄襲的

我的程式支援 and 和 or 的短路邏輯、陣列操作還有字串相連，還沒有聽過有誰做出這些功能的。如果有人有做出來，請告訴我！

編譯器設計課程的作業很花時間，難怪好多人都想放棄，或是重修。以下是我花費在作業上的時間表：

功課 行數 時數（估計）
1 173 9
2 469 13
3 1200 18
4 2034 25
5 3150 40

剛好可以練習寫一個實用的程式，不過 3000 行實在很多耶～

考試

考試共有兩次，我覺得第一次普通難，第二次很簡單。想問我考什麼？門都沒有！

文章完成日期為 2018 年 3 月 4 日

來寫個評論吧