※ [本文轉錄自 Programming 看板 #1K6QEZAk ] 作者: wayfarer (maniac) 看板: Programming 標題: [心得] 寫一個自己的程式語言 -- ACLang 時間: Wed Sep 17 23:07:04 2014 寫一個自己的程式語言 -- ACLang (æ- klæng) ACLang 是個 C-Like 的動態型別語言，目前大部份語法已完成， 目標是成為 Embedded-Scripting Language，開發 Plugin 用。 這篇只是在寫 ACLang 過程中隨手的心得而已，有興趣就看一下吧。 ACLang 完整程式碼在： https://github.com/madedit/aclang 編譯好的Win32執行檔可在此下載： http://sourceforge.net/projects/aclang/files/?source=navbar 可輸入多行程式碼，最後要按 Ctrl+D & Enter 才是真正開始執行輸入的程式。 可用： printAST(1); 開啟印出 AST 的功能 printIR(1); 開啟印出 LLVM IR 的功能 printGC(1); 開啟印出 GC delete 的功能。 對開發自己語言有興趣的可先參考此篇文章： http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/ Writing Your Own Toy Compiler Using Flex, Bison and LLVM 以下心得文開始： * 手寫 Lexer & Language Syntax： ACLang 是 C-Like 的語法，純粹只是個人喜好。 我並沒有使用 Lex/Flex 之類的工具來做， 第一是 Lexer 的功能算是簡單的， 就只是處理輸入的一整段程式碼，切成一個一個的 Token； 第二就是有些語法用 Lex 來做不夠彈性，錯誤處理也比較麻煩。 一開始是參考 D 的語法來寫的，所以會有一些 D 才有的語法小功能，像是： * var i = 987_654_321; //可在數字中隨意插 _ * print( 0x8000_0000_0000_0000 ); * var b = 0b0110_0011; //二進位數字 0b 開頭 * var a = /+ /+ +/ +/ 100; //階層式的範圍註解 /+ +/ ACLang 也參考了很多 Squirrel (http://squirrel-lang.org/)， 像 array, table 型別是從 Squrriel 來的，而 Squirrel 也參考很多 Lua。 ACLang 裡對要使用的變數都要先明確的用 var 或 local 宣告， 避免像 Lua 變數打錯字還是當做有效變數(只是值是nil)的問題。 用 var 宣告表示此變數會存到一個指定的 table 中，如： var ::a = 10; //在 root-table 新增變數 a var this.t = {}; //在 this-table 新增變數 t var t.x = "abc"; //在 t table 新增變數 x 因為 t 沒有指定 scope，所以會以 this-table 為第一順位。 變數的 scope 就是以指定的為主，有 :: (root-table) 與 this. (this-table) 若沒指定就先找 local變數，再找 this-table，最後找 root-table。 local 則表示此變數只會存在現在的執行的 function 中， 當離開此 function 即無法存取此 local 變數，除非用 return 的方式傳出。 以效率來說盡量使用 local 變數會比較好。 每個 function 都會有個隱性的 this-table， 若是在 global 的話， this-table 就是 root-table 。 * Parser & AST，使用 GNU Bison： 網路上可找到 ANSI C 的 yacc 語法檔，我是用這個再修改成 ACLang 的語法。 Parser 透過 Lexer 取得每個 Token，再由建立好的表格找到這 一系列 Token 對應到的程式區塊，然後執行這個程式區塊， 這個程式區塊裡面就是產生 AST (Abstract Syntax Tree) 的程式碼。 寫語法定義一定會遇到很多 conflicts，只有想辦法消除了。 像 if(ooo) xxx; 跟 if(ooo) xxx; else yyy; 就一定會衝到， 就只能用 %nonassoc %prec 來解了。 就跟 Lexer 一樣，用 Bison 來做 parser 會遇到的問題就是不夠彈性， 還有錯誤處理有些麻煩的問題，Bison 印出來的錯誤訊息太過制式化了， 除非以後 Parser 也要改成自己手寫的，不然就只能先這樣了。 * Code Generation： 在經過 Parser 產生 AST 後，每個 AST 可對應到一個 LLVM::Value*， 這樣可很簡單的針對每一個 AST 寫個 codegen 的 function 出來， 回傳值都是 LLVM::Value* 。 大部份 IR 指令都可用 LLVM::IRBuilder 裡包裝好的 function 來產生。 ACLang 使用 LLVM 的 JIT 功能做中介層，但底層還是 C++ 寫的Code， 例如 var a = "123" + 456; 這個加法的運算實際會去呼叫 ACLang 向 LLVM JIT 註冊的一個全域函式 opAddVar()，這個函式裡面才會 去判斷兩個變數的型別再來決定要做整數相加還是字串連結。 LLVM 有提供 CppBackend 的功能，就是可以把 LLVM IR 轉換成 C++ 的 code， 有時候不知道怎麼create某些 IR，就可以用這個作為參考。 以後 ACLang 的 C++ 底層也可用 LLVM 的 CppBackend 轉成 LLVM 的 IR， 再利用LLVM的IR最佳化提升效能。不過這也是個大工程，以後有空再說吧。 * Data Type & Variable ACLang 是動態型別語言，目前有以下類型： * integer: int32 & int64 * float: float & double * string * array * table * function * userfunc: C/C++寫的 function 再 bind 到VM中，stdlib中的都是(如 print) 變數Variable在使用前必須用 var 或 local 明確宣告，例如： var a, b, c=[1,2,3]; for(a,b : c) print(a, b); for(local c, d : [1,2,3]) print(c, d); local t = { a=10 }; var t.b = 20; //在 table t 新增 b 變數 function也是變數的一種，可當參數傳遞： function f1(f) { f(100); } var f2 = function(i) { print(i); }; f1(f2); * Virtual Machine： VM 在 ACLang 只是個包裝所有功能的架子。 VM.runCode(code) 會 compile 傳進來的 code， 用 LLVM JIT 編譯成一段 function 再去執行它。 VM 裡有個最主要的 RootTable，所有的資料都是存在裡面。 * Garbage Collection： GC 已是現代程式語言必備的功能，讓你只需要 new ，不需要管 delete， 由語言幫你檢查並 delete 不再使用的資料。 ACLang 有個中央控管的資料結構 root-table，所以實作 GC 並不是非常困難。 ACLang 使用的是 Tri-Color Incremental Mark & Sweep GC ， 所有的 Variable, Function...等等一切資料都會在 root-table 裡面， 然後當要產生物件時都是透過 gc.createObject()， GC再將產生物件都存在一個 List 裡面，存實際 new 出來的所有變數， 然後只要去 mark root-table 裡面的變數， 若沒被 mark 到就表示此變數是無主孤魂不再被使用，可以被回收刪除了。 這個演算法的好處是可以使用 gc.incrementalGC(time) 告訴此次gc會花多少時間， 讓使用者決定本次要花多久來做 GC，例如在遊戲中每個frame花個一個clock來做GC。 當然也可使用 gc.completeGC() 做一次完整的GC，這就可能會花很久時間了， 若是在遊戲中你就可能會發現遊戲lag一下。 * Error Handling： * Compile-Time Error 在Compile階段會有 Lexer&Parser&LLVM JIT編譯時的錯誤， 比較先進的Compiler都可以在遇到一個錯誤時設法壓住這個錯誤， 繼續Compile剩下的Code，看能不能再找到更多的錯， ACLang 沒這麼強，只能一次處理一個錯。 * Run-Time Error 目前還沒有完整實作，只有最基本的，在執行時遇到錯誤就印出錯誤訊息， 然後用 setjmp/longjmp 跳回一開始設定的插入點，結束程式。 例如字串除數字： var a = "123" / 10; 目前只會印一行錯誤訊息而已，以後還需要印出 CallStack 跟行號， 才能讓使用者能更清楚是哪裡發生錯誤。 * StdLib： 像是 print(), typeof() 之類的都是用 C++ 寫的function， 再 bind 回 ACLang VM 中使用的 userfunc。 以後會再增加字串處理、數學函式、檔案讀寫等等的標準函式庫。 目前要bind function還是必須寫個 wrapper function才能讓 ACLang VM使用， 以後或許可以再改進用 C++ template 的方式做。 * 效能： 雖然是用 LLVM 的 JIT 產生 native code，但是 ACLang 是動態型別的語言， 所以還是必須在執行時期動態判斷變數的型別，才能正確的進行運算， 例如: var a = "abc" + 123; //a會等於"abc123"，123先轉成字串，再連接起來 因此效能就比不上靜態型別的語言。 還有在每次call function時都會產生一些暫時的變數用來傳遞參數， 這也是很花時間，需要再做改進。 * TODO： * 類似 OOP 裡 class 的繼承功能 與 Operator Overloading 目前已有初步的想法了，會用類似 Lua 的 metatable 的作法， 這個是之後會優先實作的功能。 * namespace 其實就是用 table 包著 table 來實作就可以了。 * delegate 可改變傳給 function 的 this-table。 * 移除 LLVM JIT 產生的 function ACLang 每個 function 裡實際上是包著 JIT 產生的 function pointer， 目前當 function 被 gc delete 掉後，JIT的function還是存在著， 之後要再看看怎樣移除。 對寫個自己的 Programing Language 有興趣的話可以一起討論, Thanks~~ --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.11.150 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/Programming/M.1410966435.A.2AE.html

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: suhorng (111.248.47.80), 09/17/2014 23:46:54