Fw: [心得] 寫一個自己的程式語言 -- ACLang

看板PLT (程式語言與理論)作者suhorng ( )時間10年前 (2014/09/17 23:46)推噓2(2推 0噓 0→)

留言2則, 1人參與討論串1/1

※ [本文轉錄自 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://www.ptt.cc/bbs/Programming/M.1410966435.A.2AE.html