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

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

四个本科生,从零开始学习,三个月完成了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 评论:“这真的是励志更破(此处有狗头)​​​​”

评论区

  1. 奥斯本 2021年1月11日 回复

    为何如此优秀

  2. honey 2020年1月7日 回复

    表示看不懂

  3. listcomp 2019年10月16日 回复

    “世上现有的编程语言都太破了。
    我要自己设计个语言,年底前做出编译器。
    来证明还可以有更破的。”
    等我的toy language写完我cite到readme里哈哈哈哈

  4. 锦州510k 2019年3月23日 回复

    看着就头疼

  5. 冰凌 2019年1月27日 回复

    欣欣写出来之后负不负责把我们都教会呢?/xyx

  6. 飞之梦 2019年1月14日 回复

    什么时候开发出来?打算学一学。这种新东西比较容易出成果,打算作为开发小软件的工具。楼主开发完一定要试一下。

  7. her blue 2019年1月9日 回复

    天呐,都看不懂。

  8. Timeless 2019年1月8日 回复

    膜程序媛大佬

发表回复

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