Slisp:编译到JVM平台上的lisp方言_玖富娱乐主管发


玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。

一、媒介

之前常常调换进修偏向,没有收到很好的进修效果,浪费了很多时刻。近来痛定思痛,把偏向定为JVM和编译道理,此次真的不改了。本文是进修该偏向的阶段性总结。

之前写过几个诠释器,但还没写过编译器。恰好看到知乎Belleve给出的一幅进修路线图,因而决议完成一个lisp方言的编译器。

之以是挑选JVM而不是X86作为目的平台,一是JVM平经常运用的多一些,能够相互印证、相互增补;二是文档和社区资源丰富友爱,开辟体验较好。

项目地点:https://github.com/tdkihrr/Slisp

停止最新的commit77f126d4,完成的功用有:

  • 界说变量

  • 支撑字符串、整数和布尔范例

  • 打印以上三种预置范例的值

  • 四则运算

  • 前提推断

二、编译和运转要领

来一段详细的Slisp顺序:

(define a (  1 2 3 4))

(println a)

(define b (  a a))

(println b)

(define a (  b b))

(println a)

(println (  (  1 1)
            (- 6 4)
            (* 2 2)
            (/ 4 2)))

(println "Hello Slisp!")

(define c "Hello world!")

(println c)

(println true)

(println false)

(define d true)

(println d)

(if true (println true) (println false))

(if (== 1 1) (println "1 == 1") (println "1 != 1"))

以上顺序出自本项目/Slisp/Hello.slisp。

想要运转必须先打包编译器:

./gradlew clean build

获得了build/libs/slisp-0.1.0.jar,以后在命令行编译源代码:

java -jar build/libs/slisp-0.1.0.jar Slisp/Hello.slisp

便可天生Hello.class文件,java Hello运转该文件,输出为:

10
20
40
10
Hello Slisp!
Hello world!
true
false
true
true
1 == 1



三、编译器构成局部

这个编译器由三局部构成,一是前端局部,二是构建笼统语法树,三是递归下落天生字节码。

前端局部运用了Antlr来构建。Antlr是一个盛行的parser generator,能够依据给定的文法,天生响应的parser。因为Slisp自身采用了lisp系的语法,其实不庞杂,以是很轻易写出文法供Antlr运用。

构建笼统语法树运用了visitor形式。因为Antlr自身返回的效果已经是一棵树,以是这局部的事情是,依据每一个节点分歧的形状建立响应的类和实例。

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。-

这里有一些完成上的细节能够优化,好比针对四则运算,能够将这些运算悉数用一个类来透露表现,只变动个中的一个字段以示区分。另有一点是,若是盘算只运用一个visitor,那末每一个节点类都须要继承同一个接口或父类。

另有,完成了一点简朴的范例推导。传统的lisp方言大多是动态言语,不外Slisp是静态的,并且能够在界说变量时推导出变量的范例,不须要开辟者手动声明变量的范例。(define a 123)(define b "Hello")(define c true)能够由字面值推导出范例,而(define d ( 1 (- 2 3))也能够推导出表达式( 1 (- 2 3))的范例并以此肯定d的范例。

天生字节码局部采用了递归下落来天生。好比对( ( 1 1) (- 6 4) (* 2 2) (/ 4 2)),天生了:

      44: bipush        1
      46: bipush        1
      48: iadd
      49: bipush        6
      51: bipush        4
      53: isub
      54: iadd
      55: bipush        2
      57: bipush        2
      59: imul
      60: iadd
      61: bipush        4
      63: bipush        2
      65: idiv
      66: iadd

这段代码是Hello.class文件中的一局部,运用OpenJDK中的javap反汇编器天生。

( 1 1)对应44、46和48,先将两个1压入栈中,然后相加,将之前的两个人从栈中弹出,然后将效果压入栈顶,继承实行(- 6 4)

这里须要注重的是,并非说实行完这四个运算( 1 1) (- 6 4) (* 2 2) (/ 4 2),然后再盘算它们的和。而是在盘算完( 1 1)(- 6 4)以后(效果为2和2),马上盘算了( 2 2)(获得4),然后盘算(* 2 2)(获得4),再盘算( 4 4),以此类推。历程以下所示:

(  (  1 1) (- 6 4) (* 2 2) (/ 4 2))
(  2 (- 6 4) (* 2 2) (/ 4 2))
(  2 2 (* 2 2) (/ 4 2))
(  4 (* 2 2) (/ 4 2))
(  4 4 (/ 4 2))
(  8 (/ 4 2))
(  8 2)
(10)

为了相符如许的字节码运算体式格局,后端在建立笼统语法树的时刻须要注重“左连系与右连系”的题目。这里采用了右连系的体式格局,大抵构造以下所示:

(  (/ 4 2)
   (  (* 2 2)
      (  (- 6 4)
         (  1 1))))

如许从底层最先天生字节码,每天生一层,就向上通报,继承天生上层节点的字节码。

现实开辟中运用了ASM库来辅佐天生字节码,只须要手动拼接好类似于bipush 1如许的文本传给ASM中适宜的类和要领,末了挪用generateBytecode如许的要领便可。

虽然ASM库很轻易,但想要天生相符语义的字节码,开辟者仍须要浏览JVM范例。JVM范例中界说了各字节码的称号与语义,对照着收集上的浩瀚示例照样很轻易明白的。

四、字节码简介

bipush是指将一个范例为byte扩大为int,然后压到栈上。

iadd是将栈最上面的两个int弹出,然后盘算它们的和,将效果压入栈顶。imulisubidiv都类似于iadd,分歧之处在于将运算符变为了*-/

istoreint生存在局部变量中。

iload从局部变量中掏出生存在个中的值。

astore是将对一个Ojbect的援用生存在局部变量中。

alocal是将生存在局部变量中的援用压入栈顶。

ifeq是将栈顶的值与0举行对照,若是相称,进入true branch,不然举行false branch。该指令还会指定一个数字作为false branch进口的地点。

if_icmpne是对照栈上的两个范例为int的值,若是不相称,进入true branch,不然进入false branch。

值得注重的是,诸如if如许的指令并非单个存在,它们更多的像是一个家庭,好比对照两个int会有很多类似的指令,从JVM范例中缮写一段:

• if_icmpeq succeeds if and only if value1 = value2
• if_icmpne succeeds if and only if value1 ≠ value2
• if_icmplt succeeds if and only if value1 < value2
• if_icmple succeeds if and only if value1 ≤ value2
• if_icmpgt succeeds if and only if value1 > value2
• if_icmpge succeeds if and only if value1 ≥ value2

能够看到if_icmpne只是用来对照两个数相称时的状况,另有别的指令用于对照不等、大于、小于、相称时的状况。像如许类似而略有区分的指令,JVM范例大多将它们的文档兼并在一起,并起名为if_icmp<cond>,这里的cond代表每一个指令奇特的局部。

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。