参照《Writing An Interpreter/Compiler In Go》,改用C++实现。

项目源码: https://github.com/LeslieZhu/monkey-cpp

引言

这两本书是2022年6月出版,8月买到手,11月中旬开始细读,12月中旬完成,历时1个月,记录笔记共10篇。

至此,自制解释器与编译器告一段落,在这过程中获得了一个自顶向下树遍历解释器和一个基于字节码的虚拟机及编译器。

对于整个程序执行过程,对词法分析、语法分析、AST构建、AST解释或编译、虚拟机运行字节码各个阶段做一个回顾:

  • 词法分析:lexer扫描整个程序,根据词法规则拆分形成一系列的词法Token
  • 语法分析:parser接收每一个词法Token,根据不同的语句语义,检查其是否是由正确的Token组合,构建AST语法树
  • 解释求值器:evaluator根据AST语法树自顶向下解释执行,引入了Object系统和Environment系统来存储求值结果
  • 编译器: compiler根据AST语法树自顶向下编译,引入了符号表(SymbolTable)、常量表(Constants)和作用域表(Scope),最后得到的是字节码
  • 虚拟机:vm读取字节码,根据特定的操作码控制逻辑,结合符号表、常量表与作用域表,通过调用栈得到执行结果

虚拟机字节码操作数都是整数,这些整数作为索引,用于在符号表、常量表、作用域表中查找到正确的对象,然后进入调用栈,根据操作码的逻辑完成计算。

如果要将源文件编译为字节码文件,然后虚拟机加载字节码文件执行,即编译器和虚拟机分离,则需要用一种方式将符号表、常量表、作用域表能够写入文件并正确读取,然后是字节码本身的写入文件和读取。

斐波那契数基准测试

let fibonacci = fn(x){
    if(x == 0){
        return 0;
    } else {
        if(x == 1){
            return 1;
        } else {
            return fibonacci(x - 1) + fibonacci(x - 2);
        }
    }
};

fibonacci(35);

同时fibonacci也实现了内置函数形式,分别用解释器和编译器执行对比:

$ ./fibonacci
usage: fibonacci -engine vm|eval [-builtin]

$ ./fibonacci -engine eval -builtin
engine=eval, fibonacci(35)=9227465, duration=0s

$ ./fibonacci -engine vm -builtin
engine=vm, fibonacci(35)=9227465, duration=0s

$ ./fibonacci -engine eval
engine=eval, fibonacci(35)=9227465, duration=83s

$ ./fibonacci -engine vm
engine=vm, fibonacci(35)=9227465, duration=31s

$ time python fibonacci.py
fibonacci(35)= 9227465
python fibonacci.py  3.59s user 0.04s system 99% cpu 3.639 total
  • 虚拟机执行字节码比解释器执行要快3倍左右
  • 和Python对比, Python比目前虚拟机快10倍左右
  • 使用内置函数(C++)实现,不管是解释器或虚拟机都是毫秒级

总结

不管是这个解释器还是编译器,它的速度是非常慢的,无法用于生产环境,除非使用内置函数或库等形式加速,但在这个过程还是学习到很多东西:

  • 完成了刚买到书时候的想法,用C++重新实现一遍
  • 完善自己开发并一直在用的笔记工具软件OrgNote,更好的支持Markdown
  • 为了发布到公众号,发现公众号编辑器复制过去的内容必须是inline-css,否则会丢失格式,找到了Firefox插件Markdown Here完成
  • 智能指针的使用,达到最初的目标,即代码不出现new和delete
  • 对字节码、虚拟机、调用栈等有了更深的理解
  • gtest测试框架使用
  • gflags包的使用
  • 对比Go语言,现代C++写起来也可以很爽、很灵活
  • ......

下一步可以改进的方向:

  • 支持更多数据类型,比如浮点数
  • 支持更多语句类型,比如else if
  • 支持模块导入,比如import
  • 支持类定义,比如class
  • 支持宏,比如macro
  • 支持C/C++扩展
  • 支持LLVM IR
  • 支持更友好的REPL
  • ......