四个本科生，从零开始学习，三个月完成了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）。里面啥都有，除了龙。