※ [本文转录自 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/cn.aspx?n=bbs/Programming/M.1410966435.A.2AE.html

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: suhorng (111.248.47.80), 09/17/2014 23:46:54