前言
上次利用 Antlr 重构一版 用 Antlr 重构脚本解释器 之后便着手新增其余性能,也就是当初看到的反对了作用域以及函数调用。
int b= 10;
int foo(int age){for(int i=0;i<10;i++){age++;}
return b+age;
}
int add(int a,int b) {int e = foo(10);
e = e+10;
return a+b+3+e;
}
add(2,20);
// Output:65
整个语法规定大部分参考了 Java,现阶段反对了:
- 函数申明与调用。
- 函数调用的入栈和出栈,保障了函数局部变量在函数退出时销毁。
- 作用域反对,外部作用域能够拜访内部作用域的变量。
- 根本的表达式语句,如
i++, !=,==
这次实现的重点与难点则是作用域与函数调用,实现之后也算是满足了我的好奇心,不过在讲作用域与函数调用之前先来看看一个简略的变量申明与拜访语句是如何实现的,这样后续的了解会更加容易。
变量申明
int a=10;
a;
因为还没有实现内置函数,比方控制台输入函数 print(),所以这里就间接拜访变量也能拿到数据
运行后后果如下:
首先看看变量申明语句的语法:
variableDeclarators
: typeType variableDeclarator (',' variableDeclarator)*
;
variableDeclarator
: variableDeclaratorId ('=' variableInitializer)?
;
typeList
: typeType (',' typeType)*
;
typeType
: (functionType | primitiveType) ('[' ']')*
;
primitiveType
: INT
| STRING
| FLOAT
| BOOLEAN
;
只看语法不太直观,间接看下生成的 AST 树就明确了:
编译期
右边这棵 BlockVardeclar
树对应的就是 int a=10;
,左边的 blockStm
对应的就是变量拜访 a
。
整个程序的运行过程分为编译期和运行期,对应的流程:
- 遍历 AST 树,做语义剖析,生成对应的符号表、类型表、援用消解、还有一些语法校验,比方变量名、函数名是否反复、是否能拜访公有变量等。
- 运行期:从编译期中生成的符号表、类型表中获取数据,执行具体的代码逻辑。
拜访 AST
对于方才提到的编译期和运行期其实别离对应两种拜访 AST
的形式,这也是 Antlr
所提供两种形式。
Listener 模式
第一种是 Listener
模式,就这名字也能猜到是如何运行的;咱们须要实现 Antlr 所提供的接口,这些接口别离对应 AST 树中的不同节点。
接着 Antlr 会主动遍历这棵树,当拜访和退出某个节点时变会回调咱们自定义的办法,这些接口都是没有返回值的,所以咱们须要将遍历过程中的数据自行寄存起来。
这点非常适合上文提到的编译期,遍历过程中产生的数据天然就会寄存到符号表、类型表这些容器中。
以这段代码为例,咱们实现了程序根节点、for 循环节点的进入和退出 Listener,当 Antlr 运行到这些节点时便会执行其中的逻辑。
https://github.com/crossoverJie/gscript/blob/main/resolver/type_scope_resolver.go
Visitor 模式
Visitor
模式正好和 Listener
相同,这是由咱们自行管制须要拜访哪个 AST 节点,同时须要在每次拜访之后返回数据,这点非常适合来做程序运行期。
配合在编译期中寄存的数据,便能够实现各种个性了。
以上图为例,在拜访 Prog 节点时便能够从编译期中拿到以后节点所对应的作用域 scope
,同时咱们能够自行管制拜访下一个节点 VisitBlockStms
,拜访其余节点当然也是能够的,不过通常咱们还是依照语法中定义的构造进行拜访。
作用域
即使是同一个语法生成的 AST 是雷同的,但咱们在遍历 AST 时实现不同也就会导致不同的语义,这就是各个语言语义剖析的不同之处。
比方 Java 不容许在子作用域中申明和父作用域中雷同的变量,但 JavaScript 却是能够的。
有了下面的根底上面咱们来看看作用域是如何实现的。
int a=10;
a;
还是以这段代码为例:
这里我简略画了下流程:
在编译期间会会为以后节点写入一个 scope
,以及在 scope
中写入变量 “a”
。
这里的写入 scope 和写入变量是分为两次 Listener 进行的,具体代码实现在上面查看源码。
第一次:
https://github.com/crossoverJie/gscript/blob/main/resolver/type_scope_resolver.go#L21
第二次:
https://github.com/crossoverJie/gscript/blob/main/resolver/type_resolver.go#L59
接着是运行期,从编译期中生成的数据拿到 scope
以及其中的变量,获取变量时有一个细节:
以后 scope 中如果获取不到须要尝试从父级 scope
中获取,比方如下状况:
int b= 10;
int foo(){return b;}
这里的 b 在以后函数作用域中是获取不到的,只能在父级 scope
中获取。
父级 scope 的关系是在创立 scope 的时候保护进去的,默认以后 scope 就是写入时 scope 的父级。
要害代码试下如下图:
第四步获取变量的值也是须要拜访到 AST 中的字面量节点获取值即可,外围代码如下:
函数
函数的调用最外围的就是在运行时须要把以后函数中的所有数据入栈,拜访结束后出栈,这样能力实现函数退出后主动开释函数体类的数据。
外围代码如下:
int b= 10;
int foo(){return b;}
int func(int a,int b) {int e = foo();
return a+b+3+e;
}
func(2,20);
即使是有下面这类函数类调其余函数状况也不用放心,无非就是在执行函数体的时候再往栈中写入数据而已,函数退出后会顺次退出栈帧。
有点相似于匹配括号的算法 {[()]}
,实质上就是递归调用。
总结
限于篇幅其中的许多细节没有认真探讨,感兴趣的敌人能够间接跑跑单测,debug 试试。
https://github.com/crossoverJie/gscript/blob/main/compiler_test.go
目前的版本还比拟高级,比方根本类型还只有 int,也没有一些罕用的内置函数。
后续会逐步完善,比方新增:
- 函数多返回值。
- 自定义类型
- 闭包
等个性,这个坑会始终填上来,心愿在年底能够用 gscript
写一个 web
服务端那就算是里程碑实现了。
现阶段也实现了一个繁难的 REPL
工具,大家能够装置试用:
源码地址:
https://github.com/crossoverJie/gscript