当组织处于从0到1的发展阶段时主要任务是，设计一门课程的步骤
作者： 唐
如果计算机工程的顶峰有珍珠，那么操作系统、数据库和编译器一定是其中最闪亮的。能创造、打磨出这样的珍珠的人，就能做到别人做不到的事情，成为人们口中的“神”。笔者在学习了“大神”写的编译器入门书籍后，愿与感兴趣的读者分享一些经验，激发大家的学习兴趣。
1. 为什么我们需要编译计算机科学家David Wheeler 有句名言：“计算机科学中的每个问题都可以通过另一层间接来解决，除了太多间接层的问题。”确实如此。一般的想法是，计算机科学中的所有问题都可以通过多一层间接来解决，除了那些本身具有太多间接层的问题。编译是计算机科学中诞生的一种“间接方法”，旨在解决“人类如何让机器更好地工作？”的问题。
以上是二进制数据，虽然机器可以有效地识别和应用由0和1组成的数字信号，但人脑却不能。人脑不擅长处理这种无聊又长的信号。因此，古代计算机科学家方便地为某些二进制数据赋予含义，并发明了早期的机器代码。
图1 早期机器代码：W65C816S 机器语言监视器，https://en.wikipedia.org/wiki/Machine_code 从上图中可以看到，自然语言的几个语义元素已添加到机器代码中。虽然它比原始二进制数据更容易被人脑理解，但它仍然是非常劳动密集型的。计算机科学家后来在此基础上细化了汇编语言，并做了进一步的改进，但在构建大型软件项目时仍然非常繁琐。从1957年开始，一代代计算机工作者绞尽脑汁，发明了数百种对人脑更加友好的高级编程语言，为了自己的福祉，也为了子孙后代的福祉。作者列出了你可能听说过的高级语言：语言012TypeScript2014Swift2015Rust.表1 常见编程语言及其起源，这些高级语言要么关注执行性能，要么关注开发效率，要么关注业务安全。总体而言，与低级语言相比，它可以帮助计算机工作者更好地使用机器并以更少的精神压力解决问题。然而，这些高级语言并不能直接控制机器，而为了控制机器，就需要将这些高级语言转换成低级语言的机器代码，这个过程称为编译。
2、编译原理简述一个完整的编译过程包括扫描、解析、分析、转换、优化、生成几个步骤。有些步骤是可选的，如下图所示。
图2 编译过程以如下Go代码为例。
a :=(,base + 10.2)/2 扫描后，我们得到token列表token：a,=, (,base,+,10.2,),/,2。然后解析token列表得到语法树如下：
图3 语法树一旦有了语法树，您就可以选择将其直接翻译为另一种高级语言，或者将语义分析转换为中间结果。这里的语法树可以选择直接转换为JavaScript。
var a=(base + 10.2)/2; 或者，您可以将其转换为中间结果。中间结果是初始输入和最终输出之间的中间状态，可以是控制流图（CFG，控制流图）或静态单赋值（SSA，静态单赋值）的形式。 CFG 的一般形状如下图所示。
图4 CFG 示例https://en.wikipedia.org/wiki/Control-flow_graph 中间结果通常是抽象的，不绑定到特定的机器架构（x86、ARM 等）。因此，中间结果可以选择生成自定义字节码或使用编译器框架（例如LLVM）生成多个平台的本地机器代码，从而利用编程语言的跨平台能力来实现。不追求极致性能的编程语言通常会选择生成自定义字节码以方便维护。自定义字节码无法直接命令机器硬件执行，但可以借助虚拟机进行控制。虚拟机拥有语言开发者心目中理想的CPU架构，可以直接执行开发者设计的理想字节码指令，而忽略实际硬件平台的差异。以下面介绍的字节码为例，上面的简单代码可以翻译为如下字节码指令：
//a :=(base + 10.2)/20000 1 OP_GET_GLOBAL1 'base'0002 | OP_CONSTANT 2 '10.2'0004 | OP_ADD0005 | OP_CONSTANT 3 '2'0007 | OP_DIVIDE0008 | OP_DEFINE_GLOBAL 0 'a'0010 2 OP_ NIL0011 | OP_RETURN 基于这些从节代码指令的名称中，读者可以推断出诸如检索变量、构造常量或执行算术运算之类的事情。执行编译过程的工具当然是编译器。从广义上讲，编译器是任何将高级语言源代码编译为低级指令的工具。不过，从狭义上讲，编译工具可以分为编译器和解释器。其中，编译器特指仅将源代码转换为另一种格式，但不执行它的工具。解释器特指在转换过程中直接执行源代码的工具，即所谓“解释并执行”。根据上面狭义的定义，GCC、Clang、Rust等被称为编译器，早期版本的Ruby和PHP被称为解释器，而CPython是两者之间的中间状态。在简单介绍了编译的基本原理后，作者站在Dart 语言贡献者Robert Nystrom 和Lua 语言创建者Roberto Ierusalimschy 等巨人的肩膀上，与读者分享从零到一创建脚本语言的兴奋。你要明白。
本文的主要知识来自Robert Nystrom的Crafting Interpreters和Roberto Ierusalimschy的The Implement of Lua 5.0和The Design of Lua。
3、由于Eben解释器是在鹅厂学习并编写的脚本语言，所以我们暂时将其命名为Penguin Script，并简称为Eben。它的英文名字是eben。 Eben解释器名为Eben Interpreter，对应的文件后缀为.eb。 Eben Learning利用Python、NodeJS等语言的可执行文件，可以以REPL模式运行（直接运行eben可执行文件），也可以以文件模式运行（eben FILE_PATH，指定可执行文件后面的脚本文件的路径）。被处决。文件）。
图5 执行eben REPL（Read-Eval-Print-Loop）模式
3.1 基本概念3.1.1 BNF范式eben的语法规则借鉴了Python、Rust、C/C++等语言。以下面的打印语句为例。
print 'hello' + ' world';print 5 9;print 4 * 9 + -8/2;将其抽象为BNF 范式。
printStmt - 'print' 表达式';'; 该范例表明print 语句由'print' 关键字、一个表达式（expression）和';' 组成。在其中，表示可以进一步具体化为其他子范式。例如， print 5 9;表征范式可以具体化为比较-比较表征子范式。
Expression - .| Comparison | .Comparison - Term ('' | '=' | '' | '=') Term ;Term 是比较表达式中的一项，对应上面的5 和9。代码声明。以print 4 * 9 + -8/2; 为例，该术语可以进一步细分为以下范式：
term - 因子( ( '-' | '+') 因子)* ;因子- 一元( ( '/' | '*' ) 一元)* ;因子是算术运算中的因子。星号* 与正则表达式中的星号含义相同，表示左边括号内的部分可以出现任意多次。在四种算术运算中，乘法和除法的优先级高于加法和减法，因此范式中的加法和减法元素可以细分为乘法和除法表达式。解析过程是自上而下递归的，因此内部范式越深，最终执行优先级越高。这里的设计确保算术表达式的乘法和除法部分在加法和减法部分之前完成。范式中的一元对应于一元操作数。例如，-8/2 中的-8 是一元操作数，其中的减号- - 是一元运算符。它比四个算术运算具有更高的优先级。其他范式的逐渐具体化的过程与printStmt 的过程大体相似。以类声明语句为例，eben 代码如下所示：
class Bird { Fly() { print 'Hi, sky!'; }}class Canary : Bird { Eat() {}}相关范例是：
classDecl - 'class' IDENTIFIER (':' IDENTIFIER) '{' function* '}' ;function - IDENTIFIER '('parameters ')' 块；参数- IDENTIFIER (',' IDENTIFIER )* ;IDENTIFIER - ALPHA ( ALPHA | DIGIT )* ;类声明以class 关键字开头，后跟标识符IDENTIFIER，最后是可选的继承符号和父类标识符。接下来是用大括号括起来的主体，其中可以包含任意数量的函数定义。函数声明由标识符后跟一对括号组成，括号是可选参数列表中的参数，括号后面是函数体。参数列表由多个以逗号分隔的标识符组成。标识符以字母开头，后跟任意数量的字母ALPHA 或数字DIGIT。 eben中其他语句的范式与这里的例子类似，不再赘述。
3.1.2 字节码eben借鉴了Python、Lua等语言的设计，同样采用了虚拟机执行模式来执行自定义的字节码。常用的字节码有： BYTECODE MENENCE OP_ADD 加法、拼接操作OP_SUBTRATION 操作OP_MULTIPLY 乘法操作OP_DIVIDE DIVISION OPEANT OP_NOT NEGATION OPEATION OP_JUMP JUMP OPEATION OP_CALL CALL CALL OP_CALL OP_PRINT PRINT OPEATION OP_RETURN REATURE OPERTION OPER OPERATION OP_POP OPREATION OP_ POP O PERATION OP_POP OPREATION OP_POP OPREATION OP_POP OPREATION OPECOPR OP_GET_LOCAL 局部变量获取操作OP_DEFINE_GLOBAL 全局变量操作的定义. 表2 eben常用字节码（摘录） 所有eben代码都会转换为上述字节码并在虚拟机上执行。以var b='hello' + 'world';\nprint b; 为例，可以转换为如下字节码。
0000 1 OP_CONSTANT 1 'hello' //创建一个文字常量'hello'0002 | OP_CONSTANT 2 'world' //创建一个文字常量'world'0004 | OP_ADD //字符串连接0005 | OP_DEFINE_GLOBAL 0 'b ' //定义一个全局变量b0007 2 OP_GET_GLOBAL3 'b' //获取全局变量b0009 | OP_PRINT //打印3.1.3 虚拟机虚拟机是eben 的核心。它负责管理内存、维护函数调用栈、管理全局变量、连接系统函数、执行字节码等。 eben是用C语言开发的，C代码中虚拟机的一般结构为：
typedef struct { CallFrame Frames[FRAMES_MAX]; //函数调用栈Value stack[STACK_MAX]; //值栈Value *stackPop; //栈顶指针Table globals; //存储变量和函数的全局表ObjUpvalue *openUpvalues;//闭包值的链表，用于存储函数闭包所需的参数。 obj *objects; //用于对象链表、垃圾回收等.} VM; 执行字节码的主要逻辑是一个非常大的switch 语句。形式如下。
Result run() { for(;) { switch(instruction=READ_BYTE()) { //获取下一个字节码case OP_CONSTANT:break; case OP_POP: Pop();break; case OP_GET_GLOBAL: Break; } case OP_ADD:break; case OP_CLOSURE:break; case OP_CLASS: Push(OBJ_VAL(newClass(READ_STRING())));break; //创建类对象. } }} BNF 了解范式一次你了解了字节码和虚拟机的基本概念，你可以探索编译和运行eben的主要过程。
3.2 词法扫描词法扫描是源代码处理的第一步，将eben 代码转换为标记字符串。如果发现词法错误，则直接返回错误。大型行业编程语言通常使用Yacc、Lex等专门的辅助工具来完成词法分析扫描。然而，这些工具会带来大量的额外开销，并增加开发人员的脑力负担。为了更清楚地解释词汇扫描的原理，本文选择使用手写扫描的方法。 eben 的基本代币BNF 范式是：
NUMBER - DIGIT+ ( '.' DIGIT+ ); //数字标识符- ALPHA ( ALPHA | DIGIT )* ; //标识符ALPHA - 'a' . 'z' | 'A' . 'Z' | '_ ' ; //字符（包括下划线） DIGIT - '0' . '9' ; //数字STRING - ''' (^')* ''' ; //字符串（^' 是不带引号的） 词法扫描读取一个源代码文件，逐个字符检测结果，并将结果添加到标记词列表中。
//字符或下划线bool isAlpha(char c) { return (c='a' c='z') || (c='A' c='Z') || c=='_ '; }//是否是数字bool isDigit(char c) { return c='0' c='9'; }//扫描数字Token number() { while(isDigit(peek(0)) Advance ();//前进光标//小数部分if(peek(0)=='.' isDigit(peek(1))) { Advance(); while(isDigit(peek(0))) Advance(); } return makeToken( TOKEN_NUMBER ) ;}//扫描字符串Token string() { while(peek(0) !=''' !isAtEnd()) {advanced(); } if(isAtEnd()) return error('Unend string ' ); advance (); return makeToken(TOKEN_STRING);} 整体扫描逻辑也可以使用大型开关来实现，如下所述。
Token scan() { char c=advanced();if(isAlpha(c)) //检测到字符或下划线return identifer(); //扫描标识符if(isDigit(c)) //检测到数字return number (); } //扫描值switch(c) { case '+': return makeToken(TOKEN_PLUS); //扫描加号//根据下一个字符，小于、等于或小于号case '' : return makeToken(match('=') TOKEN_LESS_EQUAL : TOKEN_LESS); case '': return string(); //扫描字符串直到找到结束双引号}//如果发现无法识别的字符则报错return error('unrecognizedcharacter');} 如果没有出现词法错误，则编译器不断调用scan() 函数对源代码进行词法扫描即可完成。 scan()第4行的identifier()函数有点特殊。扫描标识符后，不能直接将其用作变量或函数名称的常规标识符。 eben自己的保留关键字也需要过滤。开始。下表显示了保留关键字。关键字含义及逻辑和类声明else 条件控制： false else 布尔值： false for循环fn 函数声明if 条件控制： nil if 空值或逻辑或print 打印return 返回超级父类引用this 实例自引用true 布尔值： True var变量声明while 循环表3 eben 中的保留关键字过滤保留关键字的简单方法是每次获取标识符时扫描上表中的值，一一确定字符串strncmp 等操作。你得到了结果，但它们的效率不够高。更好的方法是使用字典树Trie进行过滤。 eben的trie结构，由几个关键字组成，大致如下。
image-20231009142132144 图6 eben部分保留关键字Trie构建的字典树有了Trie，就不需要每次都遍历整个表了。您只需对特定字符进行操作即可。一般逻辑是：
swtich(c1) { case 'a': return checkReserved('nd', TOKEN_AND); //checkReserved 判断其余字符串是否相同，返回TOKEN_AND case 'f': { . switch (c2) { case ' a': return checkReserved('lse', TOKEN_FALSE); //如果f + a + lse 的三个部分都匹配，则返回TOKEN_FALSE case 'o': return checkReserved('r ', TOKEN_FOR); case 'n': return checkReserved('', TOKEN_FUNC); } } case 'v': return checkReserved('ar', TOKEN_VAR);}return TOKEN_IDENTIFIER; //关键字符号，值，表示标识符后面的字符串不匹配，等等。如果处理成功，源代码将成为令牌。可以通过以下方式执行解析：
3.3 语法分析根据eben的语法规则，整个程序可以使用如下范式来表达。
//程序代码由任意语句和文件结束符程序组成- decl* EOF ;//语句可以是类声明、函数声明、变量声明等，也可以是语句decl - classDecl | funcDecl | varDecl | stmt ;//语句可以是表达式语句、for循环、if条件、print、return、while循环、块等block; 像上面的decl 和stmt 这样的东西仍然会降低物化。根据这些范式，语法分析的主要逻辑是：
void apply(const char *source) { . scan(); //完整词法扫描while(!match(TOKEN_EOF)) {declaration(); //循环解析声明语句直到文件末尾}。}static void declaration() { if(match(TOKEN_CLASS)) { classDeclaration(); //解析类声明} else if(match(TOKEN_FUNC)) { funcDeclaration(); //解析函数声明} else if (match (TOKEN_VAR)) { varDeclaration(); //解析变量声明} else {statement(); //解析其他语句}}static void statements() { if(match(TOKEN_PRINT )) { printStatement(); } //解析打印语句} else if (match(TOKEN_FOR)) { forStatement(); //解析for循环语句} . //解析其他语句else {expressionStatement(); //解析表达式语句}}.每种声明范式都有相应的分析函数。以funcDeclaration函数声明为例，其主要解析逻辑如下：
static void funcDeclaration() { uint8_t funcNameIndex=parseVariable('此处需要函数名'); //解析函数名标识符，失败则报错ConsumerToken(TOKEN_LEFT_PAREN, '需要左括号'); //完成解析左括号，否，如果存在则报错if(!check(TOKEN_RIGHT_PAREN)) { //如果下一个token 不是右括号，则函数参数列表do { uint8_t paramNameIndex=parseVariable('需要形参名称');defineVariable(paramNameIndex); } while (match(TOKEN_COMMA)); //如果找到逗号，说明参数仍然存在，循环解析} ConsumerToken(TOKEN_RIGHT_PAREN, '需要右括号');//完成右括号的解析。如果右大括号不存在，会报错ConsumerToken(TOKEN_LEFT_BRACE, 'Left大括号是必需的') Curly括号'); //完成左大括号的解析；如果没有，会报错block(); //解析函数体，函数体是一个block块.defineVariable(funcNameIndex); //将Put函数名转换为全局表中其他声明的解析可以使用上面的方法和解析a类似函数声明。主要目的是根据BNF范式解析上游token，生成下游操作所需的字节码指令和数据。如果过程中遇到不符合BNF范式的token，所有检测到的错误都会被打包反馈给用户，方便调整和修复。
3.4 底层数据结构解析过程不仅生成字节码指令，还生成运行时需要的底层数据。数据主要有四种类型，这四种底层数据类型可以代表eben脚本中的所有用户数据类型。
typedef enum { VAL_BOOL, //布尔类型VAL_NIL, //空类型VAL_NUMBER, //数值类型VAL_OBJ
// 对象类型} ValueType;其中 VAL_BOOL ，VAL_NIL ，VAL_NUMBER 表示常见的基础类型，VAL_OBJ 表示 eben 底层实现中的复杂类型。这些类型统一用 Value 结构体来呈现，枚举字段 type 表示 Value 类型，联合字段 as 承载 Value 实际存储或指向的值。 typedef struct { ValueType type; // 数据类型 // 使用联合实现空间复用，节约内存 union { bool boolean; // C 中 bool 类型来表示 eben 布尔类型 double number; // C 中 double 类型来表示 eben 数值类型 Obj *obj; // C 中 Obj* 指针来指向动态分配的复杂结构 } as;} Value;Obj 结构体指针所指向的复杂结构还可以再度细分。 typedef enum { OBJ_CLASS, // 类 OBJ_CLOSURE, // 闭包 OBJ_FUNCTION, // 函数 OBJ_INSTANCE, // 实例 OBJ_NATIVE, // 本地函数 OBJ_STRING, // 字符串 OBJ_UPVALUE, // 闭包参数} ObjType;struct Obj { ObjType type; // Object 类型 bool isMarked; // 用于 GC 标记，下文将介绍 struct Obj *next; // 链表指针}Obj 结构体中包含具体复杂结构的枚举类型，GC 标记位，链表指针等元信息。它可以嵌入到各个细分类型结构体的头部，从而方便虚拟机统一分配管理对象。以 ObjString 和 ObjClass 具体结构为例，其主要字段如下。 typedef struct { Obj obj; // 元信息 int length; char *chars;} ObjString;typedef struct { Obj obj; // 元信息 ObjString *name; Table methods;} ObjClass;C 语言的特性使得定义在结构体头部的字段在内存中也会被分配到该结构体头部位置。所以，ObjClass 和 ObjString 等指针指向 struct ObjClass 和 struct ObjString 的内存开始处的同时也在指向对应的 struct Obj 的内存开始处，故 C 代码中可以安全地将二者转化为 Obj 指针，反向亦然。这个特性使得一些面向对象语言中才常见的操作在 C 中成为可能。下面代码就利用了该特性将 Obj 转化成具体类型指针来进行各种内存释放操作。 void freeObject(Obj *object) { switch(object->type) { case OBJ_CLASS: { ObjClass *klass = (ObjClass *)object; freeTable(&klass->methods); FREE(ObjClass, object); break; } case OBJ_STRING: { ObjString *string = (ObjString *)object; FREE_ARRAY(char, string->chars, string->length+1); FREE(ObjString, object); break; } ... // 其他类型对象的释放 }}eben 使用 ObjXXX 这些底层数据结构相互配合，完美地实现了脚本代码中类、实例、函数、闭包、字符串等等数据类型的操作。 3.5 变量3.5.1 全局变量在 eben 中声明变量很简单，其语法范式如下所示。 varDecl -> "var" IDENTIFIER ( "=" expression ) ";" ;变量声明时，初始值是可选项。没有初始值的变量默认赋值为 nil。 var abc = "hello"; // 赋值 "hello"var bcd; // 没有赋初始值，默认为 nil如果变量被声明在顶级作用域，就称之为全局变量。解析过程中，TOKEN_VAR 会触发以下变量解析逻辑。 static void varDeclaration() { uint8_t global = parseVariable("需要变量名"); // 解析变量名，获取序号 if(match(TOKEN_EQUAL)) { expression(); // 继续解析等于号右侧的表达式，此处就是 "hello" 字符串 } else { emitByte(OP_NIL); // 直接生成压入空值字节码 } consumeToken(TOKEN_SEMICOLON, "声明结尾需要分号"); emitBytes(OP_DEFINE_GLOBAL, global); // 带入序号，生成定义变量字节码}parseVariable 函数解析出代码中的abc, bcd，它们就是范式中的 IDENTIFIER 。如果检测到有等号 TOKEN_EQUAL ，则尝试解析出等号右边的表达式，此处字符串 "hello"会生成 OP_CONSTANT 字节码，用来填入字面常量值；否则，直接生成 OP_NIL字节码，用来填入空值。最后一步生成的 OP_DEFINE_GLOBAL 字节码会读取上一步压入的值，要么是某常量，要么是空值，将其写入到虚拟机全局表 vm.globals 中。如下所示。 case OP_DEFINE_GLOBAL: { ObjString *name = READ_STRING_FROM_CONSTANTS(); // 从常量列表中取出之前暂存的变量名 tableSet(&vm.globals, name, peek(0)); // peek(0) 取出值栈的栈顶元素 pop(); // 使用完成，弹出栈顶元素 break;}OP_DEFINE_GLOBAL 字节码负责写入变量，OP_GET_GLOBAL 字节码则负责读取变量。以 print abc;为例，第一步是读取变量 abc 的值。 case OP_GET_GLOBAL: { ObjString *name = READ_STRING_FROM_CONSTANTS(); // 获得变量名 "abc" Value value; if(!tableGet(&vm.globals, name, &value)) { // 用 "abc" 去全局表中查找，找到则将值回填到 value 中 runtimeError("未定义变量 %s", name->chars); // 如果没找到，报“未定义的变量”错误 return RUNTIME_ERROR; } push(value); // 如果存在，压入值栈待后续使用 break;}OP_GET_GLOBAL 将变量值压入栈后，第二步则是print 生成的 OP_PRINT 字节码将其取出并打印。 case OP_PRINT: printValue(pop()); break;3.5.2 局部变量局部变量 声明的语法与全局变量无异，不过它必须声明在非顶级作用域，比如嵌套区块内，函数体内等等。下面的例子中，除了值为 global a 的变量 a，其余都是局部变量。 var a = "global a";{ var a = "outer a"; var b = "outer b"; { var a = "inner a"; print a; // 打印"inner a" print b; // 打印"outer b" } print a; // 打印"outer a"}print a; // 打印"global a"如上文所述，值为global a的全局变量 a 存放在虚拟机的全局表 vm.globals 中，所以它会一直存活到脚本结束。值为outer a, outer b 的 a, b 和值为inner a 的 a 都是局部变量，它们的名字只会被存放在其所属作用域 current->locals 中（current代表当前 scope 作用域）。这就意味着局部变量会随着作用域的结束而消亡。所以，此处代码例子中最后两句 print a; 打印的都是当前所处作用域中的值。嵌套最里层的 print a; 打印结果是 inner a。这是因为，eben 尝试使用变量时，会优先查找当前作用域的局部变量，存在则使用，不存在则往外层继续找。如果一直到了顶层连全局变量都找不到，直接报“未定义变量”错误。 int arg = resolveLocal(current, &name); // 尝试查找局部变量，递归向外执行if(arg != -1) { op = OP_GET_LOCAL;} else { op = OP_GET_GLOBAL;}emitBytes(op, arg); // 传入变量序号，生成获取变量字节码局部变量的生命周期比全局变量短，都会随着作用域的开始而存在，其结束而消亡。所以，局部变量不需要存在全局表中，只需要存在栈上即可。需要时压入，用完则弹出。虚拟机需要取局部变量时，也只要找到其序号，再次压入栈顶即可。 case OP_GET_LOCAL: { uint8_t index = READ_BYTE(); // 在字节码数据中读出上文代码中传入的 arg，即变量序号 push(vm.stack[index]); // 将序号对应的值压入栈顶，以备后续使用 break;}3.6 条件控制eben 中条件控制语句主要有 if 语句，while 循环，for 循环，逻辑与 and 和逻辑或 or 。其中 and, or 与 C 系列语言中的 &&, || 逻辑运算符类似，有短路运算（shortcut）效果。 3.6.1 if 语句条件控制语句允许用户根据条件的真假，选择不同的逻辑分支进行执行。但是 eben 在解析时会把所有逻辑分支都解析成一长串字节码，然后按照代码中出现的顺序线性地加入到最终的字节码串中。所以，“选择不同的逻辑分支进行执行”需要虚拟机能够Jump 跳过某一段字节码，直接执行其后的内容。以下面的 if 语句为例。 if(true) { print "hi";}print "hello";编译之后的字节码内容如下。 0000 1 OP_TRUE // 将布尔值 true 压入值栈0001 | OP_JUMP_IF_FALSE 1 -> 11 // 如果为假，跳到 0011 处0004 | OP_POP // 弹出栈顶值0005 2 OP_CONSTANT 0 'hi'0007 | OP_PRINT0008 3 OP_JUMP 8 -> 12 // 无条件跳到 0012 处0011 | OP_POP // 弹出栈顶值0012 4 OP_CONSTANT 1 'hello'0014 | OP_PRINT0001处的 OP_JUMP_IF_FALSE 由 if 语句生成。如果条件值为假，跳过整个 if 分支；如果为真，则正常执行 if 分支内容，并在0008处无条件跳过 else 分支内容（用户没有写 else 分支情况下，eben 会自动加入空的 else 分支）。本例中并未写 else 分支，否则会在 0011 到 0012 间生成其对应的字节码。解析 if 语句的逻辑如下所示。 static void ifStatement() { consumeToken(TOKEN_LEFT_PAREN, "需要左括号"); // 完成左括号解析，不存在则报错 expression(); // 解析括号中的条件表达式 consumeToken(TOKEN_RIGHT_PAREN, "需要右括号"); int thenJump = emitJump(OP_JUMP_IF_FALSE); // 生成条件跳跃字节码 emitByte(OP_POP); // 弹出条件表达式的值，用完即丢 statement(); // 解析 if 分支中语句 int elseJump = emitJump(OP_JUMP); // 生成无条件跳跃字节码 patchJump(thenJump); // 计算并回填跳跃距离 emitByte(OP_POP); if(match(TOKEN_ELSE)) // 如果 else 存在，解析其分支语句 statement(); patchJump(elseJump); // 计算并回填跳跃距离}代码中的 patchJump 是为了将 OP_JUMP, OP_JUMP_IF_FALSE 字节码所需的跳跃距离回填到字节码参数中。因为在解析 if 语句的条件时，编译器并不知道 if 分支中内容有多少，也不知道会产生多少条字节码，所以只能等解析完分支之后再去回填参数。最后一句的 pathcJump(elseJump); 为 else 分支回填跳跃距离也是同样原理。 3.6.2 while 循环while 循环的条件控制在 OP_JUMP, OP_JUMP_IF_FALSE 字节码之外增加了一个 OP_LOOP字节码。前二者负责向前跳，后者负责向后跳。 OP_JUMP 配合负数参数也可以实现向后跳跃。不过字节码指令及其参数在虚拟机内部都使用 uint8_t 类型存储，故此处不使用负数以防诸多麻烦。 while 样例脚本代码如下。 var a = 5;while(a > 0) { a = a - 1;}转化成字节码如下。 0000 1 OP_CONSTANT 1 '5'0002 | OP_DEFINE_GLOBAL 0 'a'0004 2 OP_GET_GLOBAL2 'a'0006 | OP_CONSTANT 3 '0'0008 | OP_GREATER // 判断 a 是否大于 00009 | OP_JUMP_IF_FALSE 9 -> 24 // 如果判定为假，跳过整个循环体0012 | OP_POP0013 3 OP_GET_GLOBAL5 'a'0015 | OP_CONSTANT 6 '1'0017 | OP_SUBTRACT0018 | OP_SET_GLOBAL4 'a'0020 | OP_POP0021 4 OP_LOOP 21 -> 4 // 跳回到 0004 处，再次进行条件判定0024 | OP_POP这里的核心是 0009 处的 OP_JUMP_IF_FALSE 和 0021 处的 OP_LOOP，分别负责“条件不成立时跳过循环体”和“跳到条件判定处继续执行”。编译器对 while 循环的解析逻辑如下所示。 static void whileStatement() { consumeToken(TOKEN_LEFT_PAREN, "需要左括号"); // 完成左括号解析，不存在则报错 expression(); // 解析括号中的条件表达式 consumeToken(TOKEN_RIGHT_PAREN, "需要右括号"); int exitJump = emitJump(OP_JUMP_IF_FALSE); // 生成跳出循环体的条件跳跃字节码 emitByte(OP_POP); statement(); // 解析循环体中语句 emitLoop(loopStart); // 生成跳回字节码 OP_LOOP patchJump(exitJump); // 回填跳跃的距离参数 emitByte(OP_POP);}3.6.3 for 循环for 循环用到的跳跃字节码指令与 while 循环相同，但是因为其特殊语句结构，跳跃的逻辑会相对复杂。以下面的 for 循环代码为例。 for(var i=0; i<5; i=i+1) { print i;}var i=0; 初始化部分只会执行 1 次；i<5; 条件判定部分每次循环都需要验证计算；i=i+1更新部分则在每次循环体执行完之后执行。该段代码生成的字节码如下所示。 0000 1 OP_CONSTANT 0 '0' // 生成字面量 00002 | OP_GET_LOCAL 1 // 获取序号 1 处局部变量值，即 i 的值0004 | OP_CONSTANT 1 '5' // 生成字面量 50006 | OP_LESS // 判断是否小于 50007 | OP_JUMP_IF_FALSE 7 -> 31 // 如果为假，跳过循环体0010 | OP_POP0011 | OP_JUMP 11 -> 25 // 无条件跳到 0025 处，跳过更新部分，循环体执行之后才执行这里0014 | OP_GET_LOCAL 10016 | OP_CONSTANT 2 '1'0018 | OP_ADD // 将序号 1 处局部变量，即 i 的值加10019 | OP_SET_LOCAL 10021 | OP_POP0022 | OP_LOOP 22 -> 2 // 跳回到 0002 处进行条件判定0025 2 OP_GET_LOCAL 1 // 执行循环体内逻辑0027 | OP_PRINT // 打印变量值0028 3 OP_LOOP 28 -> 14 // 执行完循环体后，跳回到 0014 处，执行 i=i+1 更新部分逻辑0031 | OP_POP0032 | OP_POP编译器对 for 循环的转化逻辑如下所示。 static void forStatement() { consumeToken(TOKEN_LEFT_PAREN, "需要左括号"); // 完成左括号解析，不存在则报错 // 初始化部分 if(match(TOKEN_SEMICOLON)) { // for(;...) 形式，空初始化，无需操作 } else if(match(TOKEN_VAR)) { // for(var i=0;...) 形式，声明新的循环变量 i varDeclaration(); } else { // for(i=0;...) 形式，直接使用外界的变量 i；或者是只需要其副作用的任意表达式 expressionStatement(); } // 条件部分 ... int exitJump = -1; if(!match(TOKEN_SEMICOLON)) { // 不是分号，条件部分不为空 ... exitJump = emitJump(OP_JUMP_IF_FALSE); // 如果假，跳出循环体 ... } // 更新部分 if(!match(TOKEN_RIGHT_PAREN)) { // 不是右括号，更新部分不为空 int bodyJump = emitJump(OP_JUMP); // 无条件跳到循环体部分 ... emitLoop(loopStart); // 执行完更新之后跳回到条件判定处 loopStart = ...; patchJump(bodyJump); } statement(); // 解析循环体中语句 emitLoop(loopStart); // 跳回到更新部分去执行 if(exitJump != -1) { patchJump(exitJump); // 回填跳跃的距离参数 emitByte(OP_POP); }}3.6.4 逻辑与和或and 和 or 逻辑运算符因为有 短路运算 效果，所以也可以用来做条件控制。以下面的“ and 逻辑与”为例。 if(true and true) { // 为了样例简便，矫揉造作了这里的写法 print "AND is ok";}对应的字节码如下。 0000 1 OP_TRUE0001 | OP_JUMP_IF_FALSE 1 -> 6 // 如果假，跳到 0006。此处真，不跳。0004 | OP_POP0005 | OP_TRUE0006 | OP_JUMP_IF_FALSE 6 -> 16 // 如果假，跳到 0016。此处真，不跳。0009 | OP_POP0010 2 OP_CONSTANT 0 'AND is ok'0012 | OP_PRINT // 正常执行打印0013 3 OP_JUMP 13 -> 170016 | OP_POP如果用户代码改成： if(false and true) { print "shortcut";}对应的字节码如下。 0000 1 OP_FALSE0001 | OP_JUMP_IF_FALSE 1 -> 6 // 如果假，跳到 0006。此处假，跳。0004 | OP_POP0005 | OP_TRUE0006 | OP_JUMP_IF_FALSE 6 -> 16 // 0004 和 0005 处的操作被跳过，目前栈顶值还是假，跳到 00160009 | OP_POP0010 2 OP_CONSTANT 0 'shortcut'0012 | OP_PRINT0013 3 OP_JUMP 13 -> 170016 | OP_POP // 打印操作被跳过如上注释所示，and 左边的值为假后，后面的操作全部被跳过。这证实了 eben 中逻辑运算符有短路运算 效果。and 运算符的解析逻辑如下。 static void andOperator(){ int endJump = emitJump(OP_JUMP_IF_FALSE); // 生成跳跃字节码 emitByte(OP_POP); // 左边值出栈 ... // 继续解析右边的表达式，可能有 a and b and c and d 的情况 patchJump(endJump); // 回填跳跃的距离参数}or 逻辑运算符也有同样效果。 if(true or false) { print "shortcut";}这段脚本的字节码如下。 0000 1 OP_TRUE0001 | OP_JUMP_IF_FALSE 1 -> 7 // 如果假，跳到 0007。此处真，不跳。0004 | OP_JUMP 4 -> 9 // 直接跳到 00090007 | OP_POP0008 | OP_FALSE0009 | OP_JUMP_IF_FALSE 9 -> 19 // 0007 和 0008 处的操作被跳过，目前栈顶值还是真，不跳0012 | OP_POP0013 2 OP_CONSTANT 0 'shortcut'0015 | OP_PRINT // 正常执行打印0016 3 OP_JUMP 16 -> 200019 | OP_POPor 左边的结果为真后，条件判定中后面的表达式全部被跳过，符合预期。or 运算符的解析逻辑如下。 static void orOperator(){ int elseJump = emitJump(OP_JUMP_IF_FALSE); // 如果假，跳到 or 右边第一个值处继续判定 int endJump = emitJump(OP_JUMP); // 如果真，跳过整个判定条件表达式 patchJump(elseJump); // 回填 or 左边值判定假后跳跃的距离参数 emitByte(OP_POP); // 左边值出栈 ... // 继续解析右边的表达式 patchJump(endJump); // 回填跳跃整个条件表达式的距离参数}3.7 函数eben 中 函数 的使用如下所示。fn 关键字借鉴自 Rust ，它既不像 f 那么单薄，也不像function 那般冗长。 fn sayHi(first, last) { print "Hi, " + first + " " + last + "!";}sayHi("Code", "读者");这段脚本编译成字节码后，脚本主体 sayHi 函数也生成了一段自己的字节码。这样的设计是为了方便后文介绍的 CallFrame 调用栈帧实现隔离。 == sayHi == // sayHi 函数体0000 2 OP_CONSTANT 0 'Hi, ' // 构建字面常量0002 | OP_GET_LOCAL 1 // 获取序号 1 处局部变量，即第一个参数 first0004 | OP_ADD // 字符串拼接0005 | OP_CONSTANT 1 ' ' // 构建字面常量0007 | OP_ADD // 字符串拼接0008 | OP_GET_LOCAL 2 // 获取序号 2 处局部变量，即第二个参数 last0010 | OP_ADD // 字符串拼接0011 | OP_CONSTANT 2 '!' // 构建字面常量0013 | OP_ADD // 字符串拼接0014 | OP_PRINT // 打印0015 3 OP_NIL0016 | OP_RETURN // 该函数没有明确返回值，故默认返回值为 nil== 函数相关的两个关键字节码是 OP_CLOSURE 和 OP_CALL。二者分别用来生成函数和调用函数。如果不考虑闭包的话，前者本该叫做 OP_FUNCTION。eben 为了代码实现的方便、统一，将闭包函数和非闭包函数的构建都归一到 OP_CLOSURE 字节码指令中。虚拟机遇到 OP_CLOSURE指令时，先构建 ObjFunction，再包装成 ObjClosure，压入栈中供后续使用。 case OP_CLOSURE: { ObjFunctioin *function = AS_FUNCTION(READ_CONSTANT()); // 根据序号读出函数对象 ObjClosure *closure = newClosure(function); // 构建闭包对象 push(OBJ_VAL(closure)); // 将 sayHi 函数压入值栈，供后面的 OP_DEFINE_GLOBAL 指令使用 ... break;}编译器对 sayHi 函数定义的解析流程如下。 static void function(FunctionType type){ ... consumeToken(TOKEN_LEFT_PAREN, "需要左括号"); if (!check(TOKEN_RIGHT_PAREN)) // 如果没有遇到右括号，解析参数 { do { ... // 解析函数形式参数 } while (match(TOKEN_COMMA));// 如果遇到逗号，继续解析下一个参数 } consumeToken(TOKEN_RIGHT_PAREN, "需要右括号"); consumeToken(TOKEN_LEFT_BRACE, "需要左花括号"); block(); // 解析函数体 ObjFunction *function = ...; // 构建函数对象 emitBytes(OP_CLOSURE, makeConstant(OBJ_VAL(function))); // 生成 OP_CLOUSRE 字节码指令 ...}OP_CALL 是函数最核心的字节码指令，其在虚拟机中执行逻辑如下。 case OP_CALL: { int argCount = READ_BYTE(); // 获取函数参数个数 if(!call_(peek(argCount), argCount)) { // 调用 call_ 完成调用逻辑，peek(argCount) 是指栈顶往下 argCount 个位置的函数对象 return RUNTIME_ERROR; // 失败则报运行时错误 } frame = &vm.frames[vm.frameCount - 1]; // 成功完成，重新指向栈顶下方的函数调用栈帧 break;}peek(1) 读取栈顶往下一个位置的元素，peek(argCount)则读取栈顶往下argCount个位置的元素。这个位置存放的正是事先安排好的函数对象，这个位置之上的argCount个位置则存放函数调用所需要的参数。eben 函数调用的具体工作由 call_ C 函数实现。 static bool call_(ObjClosure *closure, int argCount) //如前文所述，ObjClosure 就是封装后的 ObjFunction{ if (argCount != closure->function->arity) { // 检查参数个数，不匹配则打回 runtimeError("需要 %d 个参数，提供了 %d 个", closure->function->arity, argCount); return false; } // 调用层数超出限制，给出经典的 Stack Overflow 错误 if (vm.frameCount == FRAMES_MAX) { runtimeError("栈溢出"); return false; } // 构建调用栈帧，压入调用栈 CallFrame *frame = &vm.frames[vm.frameCount++]; frame->closure = closure; // ip 即 instruction pointer 指令指针，指向函数体内字节码，比如上文中 sayHi 函数的字节码 frame->ip = closure->function->chunk.code; // 函数调用所需参数列表指向虚拟机值栈对应位置 frame->slots = vm.stackTop - argCount - 1; return true;}调用栈帧 CallFrame 的结构如下。 typedef struct { ObjClosure *closure; // 闭包对象 uint8_t *ip; // 指向当前指令的指令指针 Instruction Pointer，有些语言里会称作 Program Counter (PC) Value *slots; // 参数列表指针} CallFrame;代码中，frame->ip = closure->function->chunk.code; 语句是将指令指针指向被调函数（比如 sayHi 函数）字节码指令开始处。逐条执行该处的指令就代表该函数正在被调用。frame->slots = vm.stackTop - argCount - 1; 将参数列表指针指向虚拟机值栈中函数对象所在位置，这样通过frame->slots就可以直接访问函数对象及其参数，如下图所示。 图 7 CallFrame slotsframe->slots设置完成后，栈上的值正好与函数调用所需的形式参数 Parameter first 和 last按序匹配，例子中的 Code 和 读者也就成了本次函数调用的实际参数 Argument。有了 CallFrame 之后，递归 Recursion 也可以轻松实现。在栈没有溢出的前提下，不停地压入新的 CallFrame 即可。以下面这个矫揉做作的求和程序为例。 fn adder(operand) { if(operand <= 0) { return 0; } return operand + adder(operand - 1);}print adder(5);编译产出的字节码如下。 == adder ==0000 2 OP_GET_LOCAL 10002 | OP_CONSTANT 0 '0'0004 | OP_GREATER0005 | OP_NOT // operand <= 0 等价于 !(operand > 0)0006 | OP_JUMP_IF_FALSE 6 -> 16 // 未达到基准条件，跳到 00160009 | OP_POP0010 3 OP_CONSTANT 1 '0'0012 | OP_RETURN0013 4 OP_JUMP 13 -> 170016 | OP_POP0017 5 OP_GET_LOCAL 10019 | OP_GET_GLOBAL2 'adder'0021 | OP_GET_LOCAL 10023 | OP_CONSTANT 3 '1'0025 | OP_SUBTRACT // 当前参数减 1 后的值放入栈顶0026 | OP_CALL 1 // 再次发起调用，即再压入一个 CallFrame0028 | OP_ADD // 将当前参数与调用产生的值相加0029 | OP_RETURN== 脚本主体的逻辑清晰简单，定义一个 adder函数，然后传参给它并调用，最后打印出结果。adder 函数内部通过OP_JUMP指令构成递归的基准条件 Base Case ，再用OP_CALL引发递归调用。递归调用会不断压入新栈帧，直到遇到基准条件，然后再逐层弹出，返回到调用点位置。 3.8 闭包闭包 Closure 可以使函数变得更加方便，是提升语言开发效率的一大利器。以下面闭包代码为例。 fn makeFunc() { var a = "hello"; fn myFunc() { print a; } return myFunc;}var f = makeFunc();f(); // 成功打印 "hello"myFunc 内部函数意图打印其父函数的局部变量 a。如果没有闭包机制的话，局部变量 a 会随着 makeFunc 函数作用域的结束而消失。最后一句 f(); 也就无法打印一个不存在的变量。好在 eben 有闭包机制，所以该语句可以成功打印出 hello 。这段脚本对应的字节码如下。 == myFunc ==0000 4 OP_GET_UPVALUE 0 // 获取被闭包的参数0002 | OP_PRINT // 打印0003 5 OP_NIL0004 | OP_RETURN== makeFunc ==0000 2 OP_CONSTANT 0 'hello'0002 5 OP_CLOSURE 1 // 生成闭包函数，并携带闭包参数0004 |local 1 // myFunc 携带的闭包参数是从父函数的局部变量捕获所得，即脚本中的 a0006 6 OP_GET_LOCAL 2 // myFunc 是内部函数，所以也是 local0008 | OP_RETURN== 获取闭包参数的指令叫作 OP_GET_UPVALUE，这里是借鉴了 Lua 作者的叫法。Lua 内部将实现闭包的数据结构称为 Upvalue 。 makeFunc 中 OP_CLOSURE 字节码指令除了会创建闭包对象外，还会捕获局部变量，将其当作潜在的闭包参数。 case OP_CLOSURE: { ... ObjClosure *closure = newClosure(function); push(OBJ_VAL(closure)); for(...) { ... if(isLocal) { closure->upvalues[i] = captureUpvalue(...); // 捕获潜在闭包参数 } else { ... } } ...}static ObjUpvalue *captureUpvalue(Value *local) { ... ObjUpvalue *upvalue = vm.openUpvalues; ... ObjUpvalue *newUpvalue = newUpvalue(local); newUpvalue->next = upvalue; ... vm.openUpvalues = newUpvalue; ...}OP_CLOSURE 中触发的 captureUpvalue 函数将潜在的闭包参数加入到 vm.openUpvalues 链表中。而字节码OP_RETURN 中触发的 closeUpvalues函数会把用到的局部变量从栈上搬到堆上，延长其生命周期。 case OP_RETURN: { ... closeUpvalues(frame->slots); ...}static void closeUpvalues(Value *last){ // 在 frame->slots 之后的变量全部搬到堆上 while (vm.openUpvalues != NULL && vm.openUpvalues->location >= last) { ObjUpvalue *upvalue = vm.openUpvalues; upvalue->closed = *upvalue->location; // 原本栈上的值拷贝到 closed 字段中，也就到了堆上 upvalue->location = &upvalue->closed; // 指针位置指向 closed 字段 vm.openUpvalues = upvalue->next; }}上面用到的闭包参数对象 ObjUpvalue 的内部结构如下。 typedef struct ObjUpvalue{ Obj obj; // 元信息头部 Value *location; // 记录该变量原本在栈上的位置 Value closed; // 如果该变量被闭包，将 location 指向的值拷贝到此处。即从栈上搬到堆上，保证其长期存活 struct ObjUpvalue *next; // 链表指针} ObjUpvalue;后面在 myFunc 函数执行到 print a;时，虚拟机会按照本地变量，闭包值，全局变量的顺序去查找对应的值。 if arg = resolveLocal(current, &name);if(arg != -1) { // 找到了局部变量，生成 OP_GET_LOCAL 字节码 ...} else if(arg = resolveUpvalue(current, &name)) != -1) { // 找到了闭包参数，生成 OP_GET_UPVALUE 字节码 emitBytes(OP_GET_UPVALUE, arg);} else { // 当作全局变量处理，生成 OP_GET_GLOBAL，如果还是没有就报“未定义”错误 ...}上面用到的resolveUpvalue 函数内部会递归调用，这样可以保证在多层嵌套的情况下也能获取到外层参数。 static int resolveUpvalue(Token *name) { ... int local = resolveLocal(parent, name); // 先尝试从父作用域的局部变量中找 if(local != -1) { return addUpvalue(...); // 记录下闭包参数，下同 } int upvalue = resolveUpvalue(parent, name); // 如果没找到，再从父作用域的闭包参数中找，递归调用到顶为止 if(upvalue != -1) { return addUpvalue(...); } return -1; // 找不到则返回}如上代码所示，addUpvalue 函数既可用于将父作用域的局部变量加入到当前作用域闭包参数中，也可用于将父作用域“继承”而来的闭包参数加入到当前作用域闭包参数中。本例中，myFunc 没找到局部变量 a，但找到了闭包参数 a。所以，它生成了 OP_GET_UPVALUE 字节码指令。虚拟机执行 OP_GET_UPVALUE 指令时会从闭包函数对象的upvalues 列表中获取对应的闭包参数。 case OP_GET_UPVALUE: { uint8_t slot = READ_BYTE(); push(*frame->closure->upvalues[slot]->location); break;}如前文 closeUpvalues 函数所述，upvalues[slot]->location 此刻已经指向其结构体自身的 closed 字段。因为该闭包参数整个结构体都存活在堆上，所以myFunc 函数可以在 makeFunc作用域结束后依然正确地拿到 a 的值并打印。 3.9 面向对象class Cake { eat() { // 定义成员函数 eat var adjective = "好吃"; print "这个" + this.flavor + "蛋糕真" + adjective + "!"; }}var cake = Cake();cake.flavor = "巧克力"; // 动态地设置实例字段cake.eat(); // 输出“这个巧克力蛋糕真好吃!”class Cake 中的 Cake 就是类，var cake = Cake() 中的cake就是类调用后生成的实例，而cake.eat() 中的 eat 就是该类的成员方法。 3.9.1 类与实例上面脚本中，定义类以及构建实例部分的字节码如下所示。 0000 1 OP_CLASS 0 'Cake' // 定义 Cake 类0002 | OP_DEFINE_GLOBAL 0 'Cake' // 加到全局表0004 | OP_GET_GLOBAL1 'Cake'...0010 6 OP_POP0011 8 OP_GET_GLOBAL5 'Cake'0013 | OP_CALL 0 // 调用 Cake()，因为 Cake 未指定构造函数，故使用默认的无参构造函数0015 | OP_DEFINE_GLOBAL 4 'cake' // 加到全局表0017 9 OP_GET_GLOBAL6 'cake'...解析类定义的逻辑如下所示。 static void classDeclaration() { consumeToken(TOKEN_IDENTIFER, "需要类名"); ... emitBytes(OP_CLASS, ...); // 生成 OP_CLASS 字节码 ... if(match(TOKEN_COLON)) { // 如果有冒号符号，尝试解析父类 ... } namedVariable(className, ...); // 生成 OP_DEFINE_GLOBAL，加入到全局表，这样可以允许成员方法引用该类 consumeToken(TOKEN_LEFT_BRACE, "需要左花括号"); while (!check(TOKEN_RIGHT_BRACE) && !check(TOKEN_EOF)) { method(); // 在遇到右花括号之前，循环解析成员方法 } consumeToken(TOKEN_RIGHT_BRACE, "需要右花括号"); ...}OP_CLASS 字节码负责构建 ObjClass 类对象并将其压入栈。 case OP_CLASS: { ObjString *name = READ_STRING(); ObjClass *klass = ALLOCATE_OBJ(ObjClass, OBJ_CLASS); // 初始化结构体 klass->name = name; initTable(&klass->methods); // 初始化类成员方法表 push(OBJ_VAL(klass)); // 压入值栈，方便后续调用 break;}ObjClass 的结构如下。 typedef struct{ Obj obj; // 元信息 ObjString *name; // 类名 Table methods; // 成员方法表} ObjClass;类定义中只需要定义成员方法，不需要定义字段。字段都可以被动态设置，以代码中 cake.flavor = "巧克力"; 语句为例，其对应字节码如下所示。 ...0017 9 OP_GET_GLOBAL6 'cake' // 获得 cake 实例0019 | OP_CONSTANT 8 '巧克力'0021 | OP_SET_PROPERTY 7 'flavor' // 设置 cake 实例的属性...如 OP_SET_PROPERTY 名称所示，该指令用于设置实例字段值，其执行逻辑如下。 case OP_SET_PROPERTY: { if(!IS_INSTANCE(peek(1)) { // 只有类的实例才可以动态设置字段 runtimeError("只有实例才允许字段赋值"); return RUNTIME_ERROR; } ObjInstance *instance = AS_INSTANCE(peek(1)); // 获得实例对象 tableSet(&instance->fields, READ_STRING(), ...); // 设置其字段表的值 ... break;}其中 ObjInstance 的结构如下所示。 typedef struct{ Obj obj; // 元信息 ObjClass *klass; // 所属的类 Table fields; // 字段表} ObjInstance;脚本代码中 cake.eat(); 语句是对该实例的成员方法的调用，其字节码如下。 0024 10 OP_GET_GLOBAL9 'cake' // 从全局表中获得 cake 实例0026 | OP_INVOKE (0 args) 10 'eat' // 调用成员方法 eat，携带 0 个参数OP_INVOKE指令尝试找到成员方法并发起调用，如果找不到则报运行时错误。 case OP_INVOKE: { ObjString *method = READ_STRING(); // 获得方法名 int argCount = READ_BYTE(); // 获取参数个数 if(!invoke(method, argCount)) { // 发起调用 return RUNTIME_ERROR; } frame = &vm.frames[vm.frameCount - 1]; // 成功完成，重新指向栈顶下方的函数调用栈帧 break;}static bool invoke(ObjString *name, int argCount) { Value receiver = peek(argCount); // 获得实例对象 ... ObjInstance *instance = AS_INSTANCE(receiver); // 转成具体类型 ... ObjClass *klass = instance->class; Value method; if(!tableGet(&klass->method, name, &method)) { // 从实例关联的类中查找成员方法 runtimeError("未定义属性 '%s'", name->chars); return false; } return call_(AS_CLOSURE(method), argCount); // 包装成闭包对象，像普通函数一样调用}3.9.2 成员方法样例脚本中 Cake 类定义了一个成员方法 eat() {...}，其产生的字节码如下所示。 0004 | OP_GET_GLOBAL1 'Cake'0006 5 OP_CLOSURE 3 0008 | OP_METHOD 2 'eat'OP_CLOSURE 在前文介绍过，负责生成一个闭包对象。OP_METHOD 字节码是构建成员方法的关键，其在虚拟机中的执行逻辑如下。 case OP_METHOD: { ObjString *name = READ_STRING(); Value method = peek(0); // 获得栈顶已经包装好成员方法的闭包对象 ObjClass *klass = AS_CLASS(peek(1)); // 获取栈顶下方的 Cake 类 tableSet(&klass->methods, name, method); // 把闭包对象加入到类的 `methods` 表中，如果 name 已经存在，覆盖旧值 pop(); // 弹出栈顶元素 break;}前文在解析类的时候，method() 函数被用来循环解析类的成员方法，其具体逻辑如下。 static void method() { consumeToken(TOKEN_IDENTIFIER, "需要方法名"); ... if(token.length == 4 && memcmp(token.name, "init", 4) == 0) { // 如果成员方法名为 "init"，表示是构造函数，走特殊逻辑 ... } // 同前文普通函数解析方法 ... emitBytes(OP_ClOSURE, ...); // 生成 OP_CLOSURE 字节码 emitBytes(OP_METHOD, ...); // 生成 OP_METHOD 字节码}3.9.3 构造函数构造函数是一种特殊的成员方法，它用来构建类的实例。eben 中规定方法名叫 init 的成员方法为构造函数。和其他语言一样，构造函数不能随意指定返回值，因为它的返回值只能是该类的实例。上文的 Cake 类如果加上构造函数，其效果如下。 class Cake { init(color) { this.color = color; // 设置 color 字段 } eat() { print "这个" + this.color + "蛋糕真不错!"; }}var cake = Cake("粉色");cake.eat();对应的字节码如下。 == init ==0000 3 OP_GET_LOCAL 0 // 获得序号 0 的局部变量，即 this，此位置专门预留给 this0002 | OP_GET_LOCAL 1 // 获得序号 1 的局部变量，即 color 参数0004 | OP_SET_PROPERTY 0 'color' // 将参数赋值到 this 的属性 color 中0006 | OP_POP0007 4 OP_GET_LOCAL 0 // 获得序号 0 的局部变量，即this0009 | OP_RETURN // 返回 this，即实例自身== eat ==0000 7 OP_CONSTANT 0 '这个'0002 | OP_GET_LOCAL 0 // 获得序号 0 的局部变量，即this0004 | OP_GET_PROPERTY 1 'color' // 获得 this 上的属性字段 color0006 | OP_ADD // 字符串拼接0007 | OP_CONSTANT 2 '蛋糕真不错!'...== eben 中构造函数不需要也不允许指定返回值，一律在底层自动返回该类的实例。所以，在 eben 的类构造函数中使用 return 关键字会导致语法报错。 static void retrunStatement() { ... if(current->type == TYPE_INITIALIZER) { error("不可以在构造函数内使用 return。"); } ...}如前所述，eben 中普通函数在没有指定返回值的情况下，会默认返回空值nil。所以，编译器解析 eben 函数过程中调用 emitReturn 时需要对两种情况分别处理。 static void emitReturn() { if(current->type == TYPE_INITIALIZER) { // 是构造函数 emitBytes(OP_GET_LOCAL, 0); // this 处在局部变量预留位置 0 } else { // 是普通函数 emitByte(OP_NIL); } emitByte(OP_RETURN); // 生成返回操作字节码}名为 init 的成员方法归类为 TYPE_INITIALIZER 类型，其余方法都归类为 TYPE_METHOD 类型。 4.9.4 继承eben 中子类既可以 继承 Inherit 父类方法，也可以 覆盖 Override 父类方法，甚至还可以在子类方法中通过 super 关键字调用父类方法。 class Cake { eat() { print "这个蛋糕真好吃!"; } make() { print "做蛋糕很辛苦."; }}class BananaCake : Cake { // BananaCake 继承 Cake eat() { // 覆盖父类同名方法 super.eat(); // 调用父类的方法 print "加了香蕉更好吃!"; }}var bc = BananaCake(); // 构建实例bc.make(); // 调用继承而来的方法 make，输出“做蛋糕很辛苦.”bc.eat(); // 调用覆盖方法 eat，输出“这个蛋糕真好吃!\n加了香蕉更好吃!”其生成的字节码如下所示。 == eat == // Cake 中 eat 方法...== make == // Cake 中 make 方法...== eat ==0000 13 OP_GET_LOCAL 0 // 获得 this0002 | OP_GET_UPVALUE 0 // 获得 super0004 | OP_SUPER_INVOKE (0 args) 0 'eat' // 调用父类方法 eat0007 | OP_POP0008 14 OP_CONSTANT 1 '加了香蕉更好吃!'0010 | OP_PRINT0011 15 OP_NIL0012 | OP_RETURN== 字节码中出现的新指令是 OP_SUPER_INVOKE 和 OP_INHERIT ，分别负责调用父类方法和构建继承关系。OP_SUPER_INVOKE 与前文的 OP_INVOKE 主体逻辑相似，区别是调用主体从当前类方法变成父类方法。 ...ObjClass *superclass = AS_CLASS(pop()); // pop() 出来的参数是事先放置的父类if(!invokeFromClass(superclass, method, argcount)) { return RUNTIME_ERROR;}...编译器在解析super关键字时，如果解析完super.IDENTIFIER（比如 super.eat） 后再遇到左括号，就会触发父类方法调用逻辑。 uint8_t argCount = argumentList(); // 解析函数参数，返回参数个数namedVariable("super", ...); // 通过 resolveLocal, resolveUpvalue 查找逻辑找到闭包参数 superemitBytes(OP_SUPER_INVOKE, name); // 生成 OP_SUPER_INVOKE 指令，本例中 name 就是 "eat" 函数对象的序号emitByte(argCount); // 生成参数个数super能被子类方法引用，是因为在解析子类时该值早已被提前放入。 static void classDeclaration() { ... if(match(TOKEN_COLON)) { // 遇到冒号，有继承父类关系，当前类是一个子类 consumeToken(TOKEN_IDENTIFIER, "需要父类名称."); variable(false); // 获取父类，压入值栈 ... addLocal("super"); // super 加到局部变量列表，让其被闭包捕获，方便子类方法引用 defineVariable(0); ... } ...}eben 中子类只能继承父类的方法，不能继承字段，所以 OP_INHERIT 的逻辑比较简单。 case OP_INHERIT: { Value superclass = peek(1); ... ObjClass *subclass = AS_CLASS(peek(0)); // 将父类方法表拷贝到子类方法表 tableAddAll(&AS_CLASS(superclass)->methods, &subclass->methods); pop(); // 弹出子类 break;}OP_INHERIT 执行完之后才会循环执行子类中的 OP_METHOD 指令，逐个添加成员方法。因此，调用tableAddAll 函数不会导致子类方法被父类同名方法覆盖。OP_INHERIT 字节码也是由编译器解析“类声明”函数 classDeclaration 生成。 static void classDeclaration() { ... if(match(TOKEN_COLON)) { // 遇到冒号，有继承父类关系 ... namedVariable(className, ...); // 生成 OP_GET_GLOBAL 指令，加载 BananaCake 类进栈 emitByte(OP_INHERIT); // 生成继承指令 } ...}3.10 垃圾回收开发过程中，总要有人操心内存管理。要么是语言使用者（比如 C/C++ 使用者和 ARC 出现之前的 Obj-C 使用者），要么是语言作者（比如 Java、Python、C#、Go 的作者）。eben 带有Garbage Collection垃圾自动回收特性（简称 GC） ，所以 eben 使用者比较幸运，不需要操心内存管理。如前文所介绍，eben 脚本语言中的函数、闭包参数、闭包、类、实例、绑定方法等等都有其对应的底层类型，大致结构如下所示。 typedef struct{ Obj obj; // 元信息 ... ObjY *someObject; // 可能包含任意个对其他复杂类型的引用 Table someTable; // 可能包含自定义的哈希表结构体 char *chars; // 可能包含字符串指针} ObjX;虚拟机中通过 freeObject函数来释放这些底层类型的内存。 void freeObject(Obj *object) { swtich(object->type) { case OBJ_CLASS: { // 类对象 ObjClass *klass = (ObjClass *)object; freeTable(&klass->methods); // 释放其方法表 FREE(ObjClass, object); // 释放结构自身 break; } ... case OBJ_STRING: { // 字符串对象 ObjString *string = (ObjString*)object; FREE_ARRAY(char, string->chars, string->length+1); // 尾部的'\0'也一起释放 FREE(ObjString, object); // 释放结构自身 break; } ... }}其他底层类型的释放逻辑与上面二者大同小异。理论上，只要虚拟机能够将所有需要释放的对象归置到一起，再全部释放，就可以避免内存泄漏，也就可以管理好内存。为了判断对象是否需要释放，eben 在每一个底层类型头部都嵌套了 Obj obj 字段。该字段中内含的 isMarked布尔字段被用来判断对象是否该释放。 struct Obj { ObjType type; // OBJ_CLASS, OBJ_FUNCTION, OBJ_STRING 等等枚举值 bool isMarked; // 是否被标记 struct Obj *next; // 链接串接指针}看到isMarked字段，读者大概已经猜到 eben 中会使用 Mark-Sweep 方法来清理内存。业界有很多高级垃圾回收算法来高效地完成回收，本文为了简便使用了最朴素但是也蛮高效的 Mark-Sweep 标记清除方法。其主要流程如下表所示。 表 4 标记清除垃圾对象的过程如表中所示，垃圾回收主要有标记和清除两大步骤。其中标记步骤可以再细分成markRoots和markByReferences ，如下所示。 void gc() { markRoots(); // 虚拟机主结构直接引用的对象称为 root，将其全部标记 markByReferences(); // 从 root 出发，根据引用关系在所有对象中访问扩散并标记 sweep(); // 清除所有没被标记过的对象 ...}markRoots 负责标记虚拟机直接引用的对象。 static void markRoots() { for(Value *slot = vm.stack; slot < vm.stackTop; slot++) { markValue(*slot); } ... // 其他直接引用的对象 markTable(&vm.globals); markObject((Obj *)vm.initString); ...}其中 markObject 是最细粒度的基础操作，其他 mark 函数都是其封装。 void markObject(Obj *object) { ... if(object->isMarked) return; // 已经标记过，返回 object->isMarked = true; // 标记 ... vm.grayStack[vm.grayCount++] = object; // 加入到已访问节点栈中}在虚拟机主结构直接引用的 root 对象都标记完之后，通过 root 对象的引用关系访问扩散并标记。 static void markByReferences() { while(vm.grayStack > 0) { // 取出节点访问栈中全部对象为止 Obj *object = vm.grayStack[--vm.grayCount]; switch(object->type) { ... case OBJ_CLASS: { // 按类型标记类对象 ObjClass *klass = (ObjClass *)objects; markObject((Obj *)klass->name); // 标记 Class 中引用的名称字段 name markTable(&klass->methods); // 标记 Class 中引用的方法表字段 methods break; } case OBJ_FUNCTION: { // 按类型标记函数对象 ObjFunction *func = (ObjFunction *)object; markObject((Obj *)func->name); // 标记 Function 中引用的名称字段 name markArray(&func->chunk.constants); // 标记 Function 中引用的常量表字段 constants break; } ... // 其他需要标记其字段的对象 } }}当能被访问到的对象全部被标记后，GC 流程开始清除没被标记的对象，即没人使用的对象。 static void sweep() { Obj *prev = NULL; Obj *object = vm.objects; // vm.objects 链表中维护系统分配出来的所有对象，它不参与 markRoots while(object != NULL) { if(!object->isMarked) { Obj *garbage = object; // 锁定垃圾对象 // 链表删除节点处理 object = object->next; if(prev != NULL) { previous->next = object; } else { vm.objects = object; } freeObject(garbage); // 清除垃圾对象 } ... // 其他维护工作 }}vm.objects 链表维护虚拟机中所有对象，因此 markRoots 操作会避开此处，否则所有对象都至少有这里的引用关系存在。eben 虚拟机在创建对象时，都会将其加入到 vm.objects 链表中。 static Obj *allocateObject(size_t size, ObjType type) { Obj *object = (Obj *)custom_allocate(NULL, 0, size); // 使用自定义的内存分配函数 ... object->next = vm.objects; // 加入到链表头位置 vm.objects = object; ...}上面代码中的 custom_allocate 内存分配函数在分配内存前会有一个已使用内存空间阈值检查，一旦达到阈值，会启动垃圾回收机制。 void *custom_allocate(void *pointer, size_t oldSize, size_t newSize) { // 所有新对象的生成对会用到此函数 vm.bytesAllocated += newSize - oldSize; if(vm.bytesAllocated > vm.nextGC) { // 大于阈值，发起 gc gc(); } ...}为了防止内存分配到达临界点附近时频繁超过阈值，虚拟机会在每次 gc 时调整阈值到一个更宽裕的值。 void gc() { ... vm.nextGC = vm.bytesAllocated * GC_GROW_FACTOR;}至此，一个完整的垃圾回收机制就完成了。 4. 总结图 8 Hi, eben了解完 eben 的内在之后，想必读者再看到这个 REPL 会更感亲切，也更感透彻。笔者在学习完Robert Nystrom 的 "Crafting Interpreters" 全书和Roberto Ierusalimschy的 Lua 设计论文后，就对编译原理有了远比之前更透彻的理解。既钦佩于作者才华之美，又感叹他们计算机教育水平之高。基于前文的编程语言诞生时间表，笔者又理了一份编程语言作者表，方便读者直观地感受他们的编译原理发展水平之高。 如果此文能激起读者的学习兴趣，能激起读者对编译原理乃至计算机其他领域深刻知识的探索欲望，笔者深感荣幸。 "Crafting Interpreters" 书中的样例代码和 Lua 源代码都使用 MIT License，自由度非常高。eben 在二者基础上，修改了一些基础语法，调整了 REPL 模式的解析功能，项目完整代码在 https://git.woa.com/donghli/eben ，感兴趣的读者可以继续探究。 5. 参考文献Histroy of programming lanauage, https://en.wikipedia.org/wiki/History_of_programming_languagesRobert Nystrom. Crafting Interpreters. https://craftinginterpreters.com/Roberto Ierusalimschy. The Implementation of Lua 5.0. https://www.lua.org/doc/jucs05.pdfPerry Cheng, Guy E. Blelloch. A Parallel, Real-Time Garbage Collector. http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdfRobin Garner, Stephen M Blackburn, Daniel Frampton. Effective Prefetch for Mark-Sweep Garbage Collection https://users.cecs.anu.edu.au/~steveb/pubs/papers/pf-ismm-2007.pdf
