三个月自制编程语言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. txh 2019年6月25日 回复

    唔。。好厉害的姑娘

  2. idelem 2019年5月11日 回复

    话说为啥不支持 mutual recursion 呢?还没看编译到 assembly 的部分,但彼此 call 应该也可以的吧,是和什么特性的 trade off 么

    • 甜菜欣欣 2019年5月15日 回复

      编译到第一个函数的时候,第二个函数还没有被添加到变量列表里,相当于是未定义的状态。不是tradeoff,单纯没有加这个feature哈哈哈

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

    从入门 到放弃

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

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

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

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

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

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

发表回复

您的电子邮箱地址不会被公开。