Skip to content

Compiler and Interpreter

LLVM框架(1): 开篇

引言

LLVM(Low Level Virtual machine)项目是由一系列现代编译工具组成的编译器框架,主要子项目包括:

  • LLVM Core: 提供LLVM IR
  • Clang:一个现代C、C++等语言编译器前端
  • LLDB: 调试器
  • libc++:支持C++11、C++14的C++标准库
  • compiler-rt: 运行时库
  • polly: 公共库
  • OpenMP:让Clang支持OpenMP
  • libclc: 实现OpenCL
  • LLD: 链接器
  • ......

按照理解,通过LLVM可以快速建立一个新的编程语言,只要建立了AST后,遍历AST生成LLVM IR形式,这样就可以利用起LLVM自带的大量优化和后端代码生成,从而支持更多的后端硬件平台。

Ledge语言:字节码编译文件的存储与加载

Ledge语言: https://ledge-lang.github.io/zh/

引言

虚拟机编译器生成字节码后,如果不是保存在内存中,而是要保存为字节码文件,比如Java保存的.class文件,Python保存的.pyc文件,这些文件里面主要是序列化的常量池和字节码本身。

这里先简单看看.pyc文件里面存了什么,然后为Ledge语言实现初步的字节码文件存储与加载。

C++实现编译器(12): 结语

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

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

引言

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

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

C++实现编译器(11): 闭包

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

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

引言

本篇对应的源码位于目录: src/10/

闭包是迄今为止字节码编译器和虚拟机领域中最重要的功能之一。

比如:

let newAdder = fn(a){
    let adder = fn(b) { a + b; }
    return adder;
}

let addTwo = newAdder(2);

addTwo(3); // => 5

newAdder函数返回的adder就是闭包,因为它不仅有自己的参数b,还可以继续访问自己被定义时候的newAdder的参数a。

C++实现编译器(9): 函数与栈帧

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

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

引言

本篇对应的源码位于目录: src/08/

函数部分是最重要也是最难的部分,随着函数的编译需要切换编译作用域,而函数的递归和互相调用则需要切换调用栈环境,引入了栈帧

C++实现编译器(8): 符号表、字符串、数组与字典

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

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

引言

本篇对应的源码位于目录: src/07/

src
 |07
 | |token
 | | |token.hpp
 | |evaluator
 | | |evaluator.hpp
 | | |builtins.hpp
 | |CMakeLists.txt
 | |test
 | | |lexer_test.hpp
 | | |parser_test.hpp
 | | |evaluator_test.hpp
 | | |symbol_table_test.hpp
 | | |vm_test.hpp
 | | |objects_test.hpp
 | | |ast_test.hpp
 | | |code_test.hpp
 | | |compiler_test.hpp
 | | |main.cpp
 | |lexer
 | | |lexer.hpp
 | |repl
 | | |repl.hpp
 | |code
 | | |code.hpp
 | |objects
 | | |objects.hpp
 | | |environment.hpp
 | |parser
 | | |parser.hpp
 | | |parser_tracing.hpp
 | |vm
 | | |vm.hpp
 | |ast
 | | |ast.hpp
 | |main
 | | |monkey.cpp
 | |compiler
 | | |symbol_table.hpp
 | | |compiler.hpp

这里为虚拟机添加一个符号表,用于绑定变量。

因为字节码每个操作码的操作数只能是整数,因此在符号表里面将变量和一个整数建立映射关系,然后通过这个整数来代表变量写到字节码。等到虚拟机解码执行的时候,这个数字就是这个变量解码后存储的索引,可以直接访问。

目前这个符号表是全局的,后续再处理非全局的。

增加对字符串、数组和哈希表的编译支持。

C++实现编译器(7): 跳转指令

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

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

引言

本篇对应的源码位于目录: src/06/

src
 |06
 | |token
 | | |token.hpp
 | |evaluator
 | | |evaluator.hpp
 | | |builtins.hpp
 | |CMakeLists.txt
 | |test
 | | |lexer_test.hpp
 | | |parser_test.hpp
 | | |evaluator_test.hpp
 | | |vm_test.hpp
 | | |objects_test.hpp
 | | |ast_test.hpp
 | | |code_test.hpp
 | | |compiler_test.hpp
 | | |main.cpp
 | |lexer
 | | |lexer.hpp
 | |repl
 | | |repl.hpp
 | |code
 | | |code.hpp
 | |objects
 | | |objects.hpp
 | | |environment.hpp
 | |parser
 | | |parser.hpp
 | | |parser_tracing.hpp
 | |vm
 | | |vm.hpp
 | |ast
 | | |ast.hpp
 | |main
 | | |monkey.cpp
 | |compiler
 | | |compiler.hpp

之前字节码和编译器已经支持整数加法运算,现在添加对表达式和条件语句的支持,会涉及到编译顺序的调整,执行条件语句的跳转指令等。

C++实现编译器(6): 字节码与虚拟机

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

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

引言

本篇对应的源码位于目录: src/05/

src
 |05
 | |token
 | | |token.hpp
 | |evaluator
 | | |evaluator.hpp
 | | |builtins.hpp
 | |CMakeLists.txt
 | |test
 | | |lexer_test.hpp
 | | |parser_test.hpp
 | | |evaluator_test.hpp
 | | |vm_test.hpp
 | | |objects_test.hpp
 | | |ast_test.hpp
 | | |code_test.hpp
 | | |compiler_test.hpp
 | | |main.cpp
 | |lexer
 | | |lexer.hpp
 | |repl
 | | |repl.hpp
 | |code
 | | |code.hpp
 | |objects
 | | |objects.hpp
 | | |environment.hpp
 | |parser
 | | |parser.hpp
 | | |parser_tracing.hpp
 | |vm
 | | |vm.hpp
 | |ast
 | | |ast.hpp
 | |main
 | | |monkey.cpp
 | |compiler
 | | |compiler.hpp

为了提高性能和移植性,在前面树遍历解释器基础上,引入虚拟机和字节码。

为了在代码结构和接口形式上都尽量保持和原有Go语言代码相近,多花了一些时间,因为Go原生带有切片、字节序大小端读写等封装好的功能,而在C++就需要自己去组装这些工具。

目前进度为止,虚拟机只支持通过字节码进行整数的加法操作。

C++实现解释器(5): 功能扩展

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

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

引言

本篇对应的源码位于目录: src/04/

04
 |token
 | |token.hpp
 |evaluator
 | |evaluator.hpp
 | |builtins.hpp
 |CMakeLists.txt
 |test
 | |lexer_test.hpp
 | |parser_test.hpp
 | |evaluator_test.hpp
 | |objects_test.hpp
 | |ast_test.hpp
 | |main.cpp
 |lexer
 | |lexer.hpp
 |repl
 | |repl.hpp
 |objects
 | |objects.hpp
 | |environment.hpp
 |parser
 | |parser.hpp
 | |parser_tracing.hpp
 |ast
 | |ast.hpp
 |main
 | |monkey.cpp

这篇主要在现有框架上扩展一些功能:

  • 字符串
  • 内置函数: len,first,rest,push,puts
  • 数组
  • 字典或哈希表
  • 索引表达式