“世上现有的编程语言都太破了。
我要自己设计个语言，年底前做出编译器。
来证明还可以有更破的。​​​”

四个本科生，从零开始学习，三个月完成了Shoolang的开发。（围观地址：GitHub @ TCXX）

我说过写完Shoolang就来写文章的。一动笔才发现内容还挺多，因此分作上下两篇，分别讲语言的设计和编译器的实现。编程语言和编译器的区别是，语言是对一种编程规范的抽象概括，而编译器是某种语言的具体实现。这篇文章先从理论角度介绍如何构建语法，然后讲Shoo语言的缘起、设计思路和理念。

*

编程语言是由语法和语义构成的。语法规定了一个语言长什么样子。

语法的定义方式是上下文无关文法（context free grammar），也就是摆出一个语法规则，来代表所有符合语法的程序的集合。一个上下文无关文法可被写作G = (V, Z, R, S)，其中V是非终结符的集合，Z是终结符的集合，R可以理解为变量的替换规则，S是起始变量。

举个例子，四则运算的算式。我们从起始变量”E”开始，每次可以把式子里的“E”替换成“E + E”或者“E − E”或者“E * E”或者“E / E”或者“(E)”或者某个数字。替换规则R就可以被写为：

E -> E + E | E − E | E ∗ E | E / E | (E) | 数字

终结符是存在于最后语言里的字符集，在这个例子里是加减乘除括号和数字。非终结符，也就是中间步骤里出现的变量，在这里只有“E”。为了简化例子，暂不考虑负数情况，或者说负号也包含在“数字”这一部分里了。

这个语法，可以产生“4 + 5 * 3”这个算式。过程是：

E -> E + E -> E + E * E -> 4 + E * E -> 4 + 5 * E -> 4 + 5 * 3

Shoo语言的定义比四则运算复杂得多，但原理是类似的。比如表达式（expression）的定义，这段OCaml代码（sam-jay/shoo-lang/src/ast.ml）的意思是，每个“expr”可以被替换为整型数字、浮点型字符、字符串型字符、数组型字符、变量名、二元运算的式子、一元运算的式子、赋值语句、函数调用、函数表达式等等：

expr =
IntLit of int
| FloatLit of string
| StrLit of string
| BoolLit of bool
| ArrayLit of expr list
| Id of string
| Binop of expr * op * expr
| Unop of uop * expr
| Pop of expr * pop
| Assign of expr * expr
| FCall of expr * expr list
| FExpr of fexpr

可以想象，这些组成单元又可以继续细分下去，直到所有的变量都被替换为终结符。

表达式有优先级（precedence）的问题。回到刚才说的四则运算的那个算式，按照替换规则，也可以是另一种产生途径：

E -> E * E -> E + E * E -> 4 + E * E -> 4 + 5 * E -> 4 + 5 * 3

两种产生途径（derivatation），相当于是先计算“5 * 3”还是“4 + 5”的区别。这说明，刚才的语法会让算式有歧义（ambiguity）。解决的办法有几种，一种是引入更多的非终结符，用替换规则来确保顺序：

E ->
| (E)
| E + E
| E − E
| L

L ->
| L ∗ L
| L / L
| 数字

还有一种办法，适用于更加复杂的应用场景，也是Shoolang采用的，就是直接规定每种运算符的优先级高低。以下是Shoo编译器的代码（sam-jay/shoo-lang/src/parser.mly），从赋值符号（ASSIGN）到点运算符（DOT），越往下符号的优先级越高：

%right ASSIGN
%left OR
%left AND
%left EQ NEQ
%left LT GT LEQ GEQ
%left PLUS MINUS NEG
%left TIMES DIVIDE MOD
%right NOT
%right INCREMENT DECREMENT
%left DOT

这种方法比前一种更进一步的地方是，它还规定了每种符号是向左还是向右结合。举个例子，“1 + 2 + 3”这个算式按照原先的四则运算语法，可以先计算“1 + 2”也可以先计算“2 + 3”，而规定结合律（associativity）后，同一种符号并列出现时从哪一边开始计算就是确定的了。

需要指出的是，这个方法并不在本文最初给出的上下文无关文法的严格定义范围内，算是一种辅助定义语法的方式。

放眼全局，对于整个源文件，首先定义一个程序要以文件尾（end of line，EOF）结束，由一个个的语句（statement）组成。每个语句可以是一个表达式后面加上分号，或者返回语句（return statement），或者“function”关键词开头的函数声明，等等（sam-jay/shoo-lang/src/parser.mly）：

stmt:
expr SEMI { Expr $1 }
| LBRACKET destruct RBRACKET ASSIGN expr SEMI { Destruct(List.rev $2, $5, “”) }
| typ ID opt_init SEMI { VDecl($1, $2, $3) }
| RETURN expr_opt SEMI { Return($2) }
| FUNCTION ID LPAREN params_opt RPAREN ret_typ LBRACKET stmt_list RBRACKET {
VDecl(Func({ param_typs = List.map (fun (ty, _) -> ty) $4; return_typ = $6 }),
$2, Some(FExpr({ name = $2; typ = $6; params = $4; body = List.rev $8 })))
}

从程序到语句到表达式直到终结符，一个完整的无歧义的语法就定义好了。

再说说语义，它规定了一个语言表达什么意思。举个Shoo语言的例子。“int i = pointer + 1; ”这个语句，意思是定义一个名叫“i”的整型变量，赋值为名叫“pointer”这个变量所对应的再加一的值。关于语义检查等细节，会在下一篇文章详细说明。

*

然后我来瞎扯一下程序语言的设计，真的是瞎扯，因为我才刚学三个月。

Shoolang是面向过程的、静态作用域的（statically scoped）、强类型的（strongly typed）通用编程语言。通俗讲，就是有点像C/C++，但是少了很多的功能，以及多了很少的功能。

我对我们的编程语言的设想是，要非常方便使用。所以Shoo会有while循坏，会有递增和递减运算符（“++”和“–”）。同时要能完成最基本的一些算法，所以Shoo支持多维数组，并且通过struct可以实现基本的多态甚至模拟出简单的对象。

最初这个语言是要致敬Golang的，这也是Shoolang得名的原因之一。我是Java选手，但我觉得用Golang实现多线程非常方便，于是想要个长得像Java实际是Go的语言。当时定下来的特性是要有channel和锁，然而最后没有做出来。

没有做成的原因是，单个的任一特性都不难，真正难的是它们组合在一起的各种情况。比如一数组的锁，或者往channel里狂扔struct。这是个几何指数的难度，我总算体会到设计语言的难点了。Shoo语言开始于我对程序语言设计的不满足，结束于“啊造个轮子可真不容易”的对语言们的珍惜（appreciation）。

写Shoo语言参考手册（language reference manual），参考《C++ Primer Plus》的结构编排，洋洋洒洒居然有十几页。我的设计水平挺烂的，比如我二维数组的定义长这样子：

<array[2]>[5] myArray = make(array[2]>[5]);

微博@loopback_0 评论：“这真的是励志更破（此处有狗头）​​​​”