前两个月莫名的对编译原理产生了浓厚的兴趣，刷完相关理论知识后，于是迫不及待地动手用Go写了个脚本语言gscript，麻雀虽小但五脏俱全，目前已经支持现代编程语言的大部分特性，这篇博客记录下实践过程中碰到的难点以及解决思路。

简要介绍

项目地址

我给这个脚本语言起的名字叫gscript，语言的执行方式是采用主流脚本语言的实现方案：生成字节码，然后使用虚拟机执行。

一般有两种方法去实现虚拟机：1. 基于栈的虚拟机如JVM和Python。2. 基于寄存器的虚拟机如Lua。我这里采取了前者方案，实现上相较于后者会简单一些。

目前支持的语言特性如下：

  • 函数
    • 支持多返回值
    • 支持闭包
    • 支持函数递归
    • 函数参数可设置默认值
    • 支持变长参数varargs
  • 支持面向对象
  • 常规的流程控制
  • 模块化
  • try、catch和throw异常处理机制
  • 完善的变量作用域机制

除此之外，编译器也提供了生成可读性较高的类汇编代码功能，为了方便调试还提供了debug模式。使用了Go1.16提出的内嵌静态资源特性，将gscript标准库的字节码打包进了编译器中，所以整个语言所依赖的只有一个二进制文件。

由于虚拟机是使用Go编写，所以gscript能直接借用Go的垃圾回收机制，不需要单独实现一套GC。

语法一览

这里给一个简单案例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 引入标准库
import fs
import os

# 定义函数
func writeSomeMsg(filepath) {
    # 以只写模式打开文件，如果文件不存在则创建，如果文件存在则清空文件
    let file = fs.open(filepath,"wct");

    # 往文件写入一些数据
    file.write("hello world!\n")
    file.write("gscript is a good language!")

    # 关闭文件
    file.close();
}

let filepath = "./text.txt"

try{
    writeSomeMsg(filepath)

    let stat = fs.stat(filepath)
    print("size of text.txt is " + stat.size + "B");
    
    # 读取文件所有内容
    let data = fs.readFile(filepath);
    print("message of", filepath, "is:")
    print(data.toString())

    # 删除文件
    fs.remove(filepath)
    print("success!")
}
catch(e){
    print("operation failed, error msg:",e)
    os.exit(0)
}

个人感觉语法还是挺易读的，直接一股有python影子的javascript既视感(逃)，不过多解释含义。

流程控制：

1
2
3
4
5
6
7
8

# 实现1+3+5+...+49
let sum = 0;
for(let i=0;;i++) {
    if (i%2 == 0) continue;
    if (i == 40) break;
    sum += i
}
print(sum)

控制流程基本上和javascript一致，只不过else if替换成elif(抄的python)。

脚本也提供了对面向对象的支持：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Dog {
    __self(name) {
        this.name = name;
    }
    bark() {
        print(this.name, "is barking!")
    }
}

let dog = new Dog("小白");
dog.bark();

实现了闭包：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func foo() {
    let i = 0
    # 返回一个闭包函数
    return func(){		
        return ++i;		# 捕获外部的变量i
    }
}

let f = foo();

print(f())				# output: 1
print(f())				# output: 2

这里只展示了部分内容，详细的语法可见语法。

实现

编译器是分前端和后端的，至于前端部分，LL(1)文法，采用手写递归下降的方式，文法可见BNF。后端是生成虚拟机自行设计的指令集。得到字节码后，交给虚拟机进行执行。

虚拟机运行时会维护一个求值栈，所有的计算操作都是在栈上执行，如计算1 OP 2，则需要将1和2放入栈中，然后pop出两个数，根据虚拟指令指定的操作符对两数运算，最后将结果放入栈中。由我们后续的指令决定是将结果继续运算，还是存放入变量中。

下面讲讲过程中一些比较重难点特性的个人实现方案：

常量

常量这个词可能用的不是很准确，这里并不是指平常意义上用const定义的变量，而是指字面量，如直接使用的数字、字符、false、true等：

1
2
3

let str = "hello world"		# 这个hello world就是字符串字面量
let num = 1					# 1就是数字字面量
let boolean = true			# true就是boolean字面量

对于这些字面量的组织，有两种方案：①使用常量表数组存储，运行时从常量表取数据即可。②直接将字面量通过type-length-data的方式嵌入到字节码指令中。

显然前者更优，如果用户同时使用了多次相同的字符串字面量，使用常量表方式只需要存取一份这个字符串即可，而后者会让字节码膨胀。

常量表其实就是一个数组，编译阶段会将所有不相同的字面量放入数组，然后交给虚拟机，虚拟机使用LoadConst OpNum指令中的操作数指定常量表的下标，就能将对应的常量取出放入求值栈中。因为常量表是由编译器组织的，自然这个指定数组下标的操作数也由编译器决定。

变量

变量和常量类似，一般也是通过单独的符号表进行存储，只不过符号表会在虚拟机运行时中发生改变(可读可写)。

因为编程语言都是用一个字符串名称去标注变量，所以实现符号表的最简单方式就是维护一个key类型为string的map结构即可，运行时交给它变量名，就能得到相应的值。

但这种方式有个很明显的弊端，那就是存取变量的效率太低，每次访问变量都要执行一次map操作。

然而用数组去存的话，不仅更节省内存的同时还拥有更高的效率。runtime交给它一个整数下标，它将对应的值返回。为了实现这一点，我们只需要在编译阶段为每一个变量分配一个连续的下标即可(可用map去记录变量名到下标的映射)，然后在代码里每处访问变量处，用这个下标代表这个变量，作为LoadName指令的操作数即可。

变量还有一个很重要的作用域问题，以如下代码为例：

1
2
3
4
5

{
    let a = 1
    print(a)		# 合法
}
print(a)			# 非法

变量只能在自己的作用域内有效，编译器有必要检测到这一点。除此之外还有与作用域相关的变量折叠问题：

1
2
3
4
5
6

let a = "foo"
{
    let a = "bar"
    print(a)	# a="bar"
}
print(a)		# a="foo"

在大部分现代语言里，这是合法的，一般遵循就近的原则。这种不同作用域的同名变量能无限的嵌套下去，单纯用上述中一个map去维护变量名到下标映射的方案是实现不了的。

其实像这种进一个作用域，作用域结束后，回到先前作用域的情景，很容易联想到栈这个数据结构。我们将作用域的每一层作为栈的一个节点，并且为每一节点分配一个上述的map。进入新的一层作用域，就压栈，退出一层作用域就退栈，因为每一层作用域定义的变量都定义在自己的栈节点中，一旦该节点退栈，其上声明的合法变量自然也被销毁，这也正符合我们的预期。

那么编译期去查询一个变量下标的过程，就变成了先查询栈顶节点的map，如果不存在该下标就访问倒数第二个栈顶节点即更大的作用域，依次类推，直至访问到栈底都没发现对应记录，就说明使用了未定义的变量，编译器抛出异常。知道这个后我们再看上面的代码，注释注明了编译期间符号表的变化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

let a = "foo"
# 栈底到栈顶为从左至右，此时栈为: [map1{a:0}]
{
    # 进入新作用域，将该作用域上下文压栈
    # 此时栈为： [map1{a:0},map2{}]
    let a = "bar"	# 在栈顶节点的map中定义变量a
    # 此时栈为： [map1{a:0},map2{a:1}]
    print(a)		# 优先访问栈顶，a="bar"
}
# 作用域结束，退栈，此时栈为：[map1{a:0}]
print(a)		# a="foo"

结合注释还是很容易理解的，注意下上面代码注释讨论的是编译时刻的过程，而不是虚拟机运行时刻。

这是因为变量作用域只是编译时刻的问题，运行时刻的变量表不会像编译时刻这样以多层次栈的方式存储，而就是一个数组。

函数调用

函数调用的实现也是一个很值得讨论的话题。

前面漏讲了一些关于指令如何执行的基础知识，如果学过组成原理或者汇编的话，应该知道计算机指令其实就是一些二进制，一个可执行文件的指令区域称为代码区(text)。

计算机将程序读到内存后，PC寄存器就指向了代码区的起始区域，计算机然后将PC指向的指令取出并执行，执行完后将PC向后移指向下一条指令，这样不断往复就是所谓的程序的运行。

我们虚拟机要做的就是模拟这部分操作，脚本被生成字节码后，如果程序入口到结束都没有调用任何函数的话，PC也是不断+1顺序执行的过程。但一旦调用了函数，如果不采用内联，这时因为函数的字节码远在它处，想执行函数的代码的话，就需要修改PC指向，函数调用完再将PC修改回来。这里只简略介绍不过多展开，默认读者是具备相关知识。

对于编译型语言，因为生成的是机器指令，不能有任何的抽象，每个的函数虽然被单独编译后生成一段机器指令后，最后需要把多个合并成一段连续的指令，然后在函数调用处回填函数对应的地址，这个操作叫做重定位。这合并以及重定位的方式会增加实现的复杂度。

但对于脚本语言，执行字节码的是高级语言开发的虚拟机，也就意味着我们完全可以利用抽象的方法解决问题，不需要做成编译型语言那么原始的方式。

我们可以为函数抽象出一个结构体，包含了这个函数对应的字节码，参数个数，参数默认值，是否支持可变参数等必要信息。随后将所有函数放在数组中，数组的下标就是该函数的编号。那么以后我们可以使用call + 编号而非call + text地址的方式，来进行一次函数调用，很显然这样对于开发来说友好不少。

事实上，gscript也不是使用call指令 + 编号(操作码)的方式，在call之前，需要先通过LoadFunc + 编号(操作码)将函数对应的结构体放入求值栈栈顶，然后call，但大致思想一样。

对于静态编译语言，函数调用传参个数必须等于函数定义形参个数，否则编译失败。但对于脚本语言来说，这种编译期间推导是不可能实现的，一般采取的方式是传多丢弃，传少补nil，这部分操作是在运行时完成。

所以对脚本语言来说，为了让运行时实现躲弃少补的规则，一般在调用函数时，需要告诉虚拟机传入参数个数，我们的call指令后面跟的第一个操作码就是入参个数。

顺便一提，因为传参可能需要丢弃或者补nil，所以我们参数的压栈顺序不是类似于Go和C的从右至左的压栈调用约定，而是从左至右的方式，这点读者可以细心体会下。

gscript是支持多返回值的，如下代码：

1
2
3
4
5
6
7
8
9

func foo(){
	if(some_condition) return 1,2,3
    elif(another_condition) return 1,2
    elif(other_condition) return 1
    return;
}

let a,b = foo()
let a,b,c = foo()

foo这个函数返回多少个参数依旧只能在运行时确定，我们采取的规则依旧是多则丢弃，少则补nil。call指令后跟的第二个操作码就是期望的返回值个数，运行时函数执行完毕后，将实际返回值个数和期望个数比较即可。

那么通过下例捋一捋函数调用过程：

1
2
3
4
5

func foo(a) {
    return 1
}

let a,b = foo(1,2,3)
  1. 将入参从左至右压栈(1,2,3)。
  2. 通过LoadFunc指令将函数结构foo压栈。
  3. 执行Call 3 2指令，3代表入参有3个，2代表期望返回值2个。
  4. 因为函数结构标明只接受一个参数，所有连续Pop两次，丢弃两个入参3和2
  5. 执行foo代码，最后将返回值1压栈
  6. 因为期望返回2个，所以补压一个nil到栈中。
  7. 最后将栈上两值赋值给a,b

还是挺容易理解的，除此之外，函数是支持默认参数和varargs的，如下：

1
2
3
4
5
6
7
8
9

# 默认值
func foo1(age=20) {
    print(age)
}

# varargs
func foo2(...args) {
    print(len(args), args)
}

这个的实现留给读者自行思考，不再赘述。

闭包

闭包是目前主流语言都会提供的特性，除了某个老古董语言(C语言：你报我身份证号得了)。当然这是玩笑之谈，一般闭包的实现不是零成本的抽象，C作为一个纯粹的系统级编程语言来说，摒弃这些特性才是正确的选择。

gscript是支持闭包的，当初我也是思考良久才想出实现方案，经历多少辛酸只有我知道，你永远不懂我伤悲 :)

我实现闭包的思路是：在编译期间，确定每个函数它所闭包的变量在运行时刻其在变量表的下标，然后将下标存储到函数结构体中，运行时在加载函数时，将从变量表中将对应位置的变量捕获到函数即可。读起来有点拗口，以代码举例可能更清楚点：

1
2
3
4
5
6
7
8

func foo() {
    # 假设运行时刻i会被装载在变量表的第1个位置
    let i = 0
    # 匿名函数
    return func() {
        print(i)
    }
}

这里给出匿名函数的结构体的简化版：

1
2
3
4
5
6

type AnonymousFunc struct{
    // 待闭包变量在运行时刻在变量表位置
    // 对于上例代码，在编译时刻将会确认为[]uint32{1}
    Upvalues []uint32
    // ...
}

那么运行时刻在加载匿名函数时，虚拟机会将Upvalues记录的所有位置上的变量取出，并生成Closure运行时结构：

1
2
3
4

type Closure struct {
	Info     *proto.BasicInfo
	UpValues []*GsValue	// 闭包的变量
}

UpValues会保存闭包变量的引用，之后函数内访问闭包变量，直接访问UpValues即可。

当然实现完整闭包，还不会这么简单，以下面为例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func foo() {
    let i = 0
    # 匿名函数1
    return func(){		
        # 匿名函数2
        return func(){
         	return ++i;   
        }
    }
}

let f1 = foo()

# 执行匿名函数1，在此过程匿名函数2才被加载
# 但此时上下文的变量表已经没有i了，捕获不到i
let f2 = f1()

如果让匿名函数2通过捕获运行时变量表方式，来捕获变量i的话，这是做不到的。前面说了闭包捕获变量的时刻是加载函数的时刻，能捕获的变量只能是加载时刻上下文里的变量，也就意味着，匿名函数2只能捕获匿名函数1环境中的变量，对foo中的i是无能为力的。

所以为了处理这种情况，我们要扩展闭包的机制：除了让匿名函数2捕获变量i外，还需要让匿名函数1捕获变量i。

这样在加载匿名函数1时，匿名函数1先将i捕获；随后匿名函数2执行，匿名函数2就不从变量表取闭包变量，而是从匿名函数1捕获的闭包变量中取。

这就是大致的一些思路，感兴趣的同学可以看下代码。

对象

gscript是支持对象这种复合结构的。

对于强类型语言，一般来说不允许动态增加或删除对象的成员，对象的内存模型必须和类或结构体的定义完全一致，这样带来的好处是，为了访问某一个属性成员，编译器直接能通过对象内存地址加上偏移的方式快速访问。

对脚本语言不一样，对象的属性可以随意的添加，为了实现这点，一般是用map结构去进行存储。成员名作为key，成员值作为value。这也是脚本语言天生比编译语言性能低的一个原因。

map是牺牲空间换效率的一种方式，如果为了提高查询效率，大规模的KV用map存储绝对是明显优于数组存储的。但如果是小对象的话，用数组存储，以轮询查找方式其实在效率方面和map相差无几，但却极大的节省了内存。

所以gscript对对象实现进行了一定的优化，当KV个数小于8时用数组实现对象，否则用map实现。

我们从语言层面看看对象的使用：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class people{
    __self(name) {
        this.name = name
    }
    show_name() {
        print(this.name)
    }
}

let p = new people("jack")
p.show_name()

__self是构造函数，show_name是一个方法。

肯定有朋友已经注意到了上面的this，其实this并不是gscript的关键字。在调用new people("jack")时，我们会在符号表中建立一个名为this变量，接着people类中的所有方法会对这个变量进行闭包，这样就能达到在方法中访问自身对象的能力。

异常

错误处理是编程语言不可或缺的功能，各种语言的错误处理方式也是各有千秋：

  • C语言使用极为原始的errno错误码方式
  • Rust使用枚举Result的方式
  • Go使用多返回值以及显示if err!=nil的方式
  • Java、C++以及大多脚本语言采用了try-catch方式。

在gscript设计初，因为语言本身支持多返回值，其实作者一开始就打算采用Go这种方式，还不需要在语法层面提供额外支持。但因为抱着学习态度，也为了拥抱主流，最终是实现了一套try-catch功能。

其实实现也是挺简单的，大致思路就是，每次进入一个try块之前，告诉虚拟机当前try对应的catch块代码地址，虚拟机随即将这个地址用一个栈结构保存。如果在执行代码过程中，某处用throw这个内置函数抛出了异常，则虚拟机跳转到栈上保存的catch地址处执行即可。如果栈为空，说明这个throw没有被任何try-catch捕获，虚拟机panic即可。

模块化

模块化的实现也是挺有意思的，每个文件作为一个独立的编译单元，编译会生成独立的原型proto。在编译主文件时，我们会用递归的方式去编译主文件的import，直至所有文件都被编译完成，最终生成了proto数组，接着将其交给虚拟机即可。

相应的import "fs"就会被翻译成LoadProto [index]的样式，index是操作码指明数组下标。LoadProto指令会去顺带执行被import文件的字节码，直至遇到了export。

上述其实没什么难点，稍微需要注意的是可能发生import循环的现象。比如定义三个文件a、b、c，a引了b，b引了c，c引了a，这样就出现了循环，导致无限递归，为了杜绝这种情况，需要一种机制进行检测。

透过现象看本质，这其实就是一个有向无环图的判断问题，解决方式有很多，我采用的是黑白灰三色标记以及深度优先遍历的方式，这里不过多展开。

标准库和builtin

一个语言单有语法是不足够的，还需要配备相应的标准库或者内置函数，脚本语言又该如何调用宿主语言提供的函数呢？参数该如何传递？

其实宿主语言和脚本语言之间交流的桥梁早就建好了，那就是我们的求值栈。

讲解之前看看系统调用的实现，以Linux为例，系统调用的过程：指定系统调用编号，用通用寄存器传递参数，int 0x80中断指令执行系统调用。

内置函数的实现也类似，我们为每个内置函数设置一个编号，用求值栈传递参数，用call指令执行内置函数调用。

内置函数len实现可见如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func builtinLen(argCnt int, vm *VM) (retCnt int) {
	vm.assert(argCnt == 1)
	var length int64
    // 弹出求值栈上的函数调用参数
	switch val := pop(vm).(type) {
	case *types.Array:
		length = int64(len(val.Data))
	case *types.Object:
		length = int64(val.KVCount())
	case string:
		length = int64(len(val))
	case *types.Buffer:
		length = int64(len(val.Data))
	default:
		vm.assert(false)
	}
    // 将长度压入求值栈中
	push(vm, length)
	return 1
}

前面讲过call指令会跟一个代表参数个数的操作数，就是这里的argCnt。vm就是我们的虚拟机实例，通过它可以操作求值栈。宿主语言通过对求值栈pop就能拿到脚本语言传递来的参数个数，接着执行相应的逻辑，最后将执行结果压栈即可。

通过求值栈的方式，就能实现脚本语言以及宿主语言之间的交流。