三个月自制编程语言Shoolang(下)

四个本科生,从零开始学习,三个月完成了Shoolang的开发。(围观地址:GitHub @ TCXX)

甜欣屋的上一篇文章简单地介绍了上下文无关语言,还有Shoolang的设计理念。这一篇来说说Shoo编译器的架构和OCaml实现。编译器是一种神奇的程序,输入的是源代码,输出的是要看源代码编译出了什么鬼。

*

Shoo编译器像一条流水线,把一段源代码一步步加工成最后的二进制码。它由以下几个模块串在一起——

1)词法分析(scanner.mll)

将读入的ASCII码形式的源代码转化成一个个token,比如关键词、数字、字符串、运算符、括号等等。代码的注释会在这一步被舍弃。

指定了空格作为分隔符:

rule token = parse
 [‘ ‘ ‘\t’ ‘\r’ ‘\n’] { token lexbuf } (* Whitespace *)

之后是指定各种合法字符,每一行都是一种token,支持多个字符的组合,并被赋予别名:

| ‘+’ { PLUS }
| ‘-‘ { MINUS }
| ‘*’ { TIMES }
| ‘%’ { MOD }
| ‘/’ { DIVIDE }

编译器在这一阶段如果报错,说明源代码含有非法字符。

2)语法分析(parser.mly)

把上一步产生的token,根据定义好的Shoo语法(详见系列的上一篇文章),转换成一个抽象语义树(abstract syntax tree,简称AST)。树画起来太麻烦,不画了。总之树的每个末位的节点(leaf)是一个token。

语法糖(syntactic sugar)也在这一步转化。语法糖就是,有些语句可以有等价形式,比如把“i=i+1;”写成“i++;”写起来就很方便。那么编译器在这一步,看到带“++”运算符的语句,就自己转换过去了。这步转化了省时省力,还有助于统一两种语句的表现。

编译器在这一步报错,说明有语法错误。比如“2 = 1 + 1;”会报错,因为它不符合任何一条语法规则。

3)语义分析(sement.ml)

遍历AST树,将其转换为SAST树。这个树的每个节点都是一个包含了多种元数据的对象(object),在后一步骤有用。

这一步用来找出语义错误。共两种,变量类型(typing)错误和变量作用域(scoping)错误。

举例,以下代码用来检查某对象在特定语境是否是Shoolang定义的布尔变量:

check_bool_expr (ctxt : styp StringMap.t list) e =
 let (t, st) = check_expr ctxt e in
 if (t <> SBool) then
   raise (Failure(“Error: ” ^ fmt_styp t ^ ” is not a boolean type”))
 else (t, st)

为什么要语义检查?理论上不检查源代码是否符合要求也是可以的,我们可以写一个很暴躁的编译器,啥也不检查,二话不说转成二进制码,跑崩了谁写的码谁背锅。为了世界的和平,编译器最好还是好好检查错误,并告诉程序员哪里不对。

4)中间代码的转换(lift.ml)

Shoolang支持头等函数(first class functions),所以有对应的模块负责做转换。其它可能的模块有类型推断(type inference),那么再串一个模块做类型的转换。

支持头等函数,就是说函数可以被当作变量传递。比如以下这段Shoolang的冒泡排序,“compare”是形式参数,用来指定元素比较的方式:

function bubbleSort(array<Object> arr, int n, func(Object, Object; bool) compare) array<Object> {}

Shoo编译器用SAST节点的元数据记录语境信息,将所有被嵌套的函数上升到全局范围的同时不改变程序表现。每个语境包含独有的变量,用关联地图(map)存储。

5)代码生成(codegen.ml)

直接对接LLVM模块,把SAST节点转成更低级的语言。以下代码简单示范如何一一绑定部分运算符:

match op with
 Add     -> L.build_fadd
| Sub     -> L.build_fsub
| Mult    -> L.build_fmul
| Div     -> L.build_fdiv

这种方法的前提是,Shoo语言的源代码和LLVM代码存在token层级的一一对应关系。举个反例,“or”这个运算符在有的语言中有短路效果,比如“A or B”如果编译器判定A的值为真,那么会跳过对B的值的判定。于是我们舍弃了短路这个特性。

然后链接C库(builtins.c),用来辅助完成输入输出的一些功能,还有字符串相关的操作。最后输出二进制码。

*

我们有很详细的语言手册:《Shoo语言:从入门到放弃》。

作为史上最破,Shoolang编译器有以下特性:

垃圾回收全靠重启。遇到问题,重启试试。
不支持互相递归(mutually recursive),所以写不了Lisp解释器。
不能链多个文件,所有源码要写在一个文件里。

Shoolang还是可以写很多东西的,GitHub上有很多测试例子。有几个是我直接拿Leetcode改的,弄个数独程序解决器什么的毫无压力。

扯一扯为什么用OCaml语言。

首先,用OCaml定义上下文无关文法(context free grammar)方便得跟开挂一样,从Shoo编译器的代码就能看出。还可以各种调Lex和LLVM模块。用Java写的话,代码分分钟上千行。

OCaml的优点还有一大堆。尾递归(tail recursion)优化很好,处理得快;没有指针,相对而言较安全;类型系统不容易出错;还带自动的垃圾回收。

用Ocaml写也是有缺点的。很难学。超级烦。但是很有用。你会花很多很多的时间,写很少很少的码,来做很多很多事情。

最后,造编译器推荐看龙书(Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, Jeffrey D.Ullman)。里面啥都有,除了龙。

评论区

  1. 拱猪技巧 2019年3月23日 回复

    从入门 到放弃

  2. 增大网 2019年3月6日 回复

    没玩过博客,认真学习学习!

  3. 飞之梦 2019年2月21日 回复

    写这些,我没看明白怎么用。(ಥ﹏ಥ)

  4. 增大网 2019年2月11日 回复

    年后第一次来,恭喜恭喜!

发表评论

电子邮件地址不会被公开。 必填项已用*标注