如何从0到1设计实现一门自己的脚本语言

作者：dong

如果说计算机工程王冠中有明珠的话，操作系统、数据库、编译器必定是其中最闪耀的那几颗。能够制造打磨出这种明珠的人，做到了其他人做不到的事情，也便成了人们口中的“神”。笔者在学习了“神”们撰写的编译器入门书籍之后，分享一些心得给感兴趣的读者，希望能激发出大家的学习兴趣。

1. 为什么需要编译

计算机科学家 David Wheeler 有一句名言，“All problems in computer science can be solved by another level of indirection, except for the problem of too many layers of indirection.”。大意是指，计算机科学中所有问题都可以通过多一个间接层来解决，除了间接层太多这个问题本身。

编译就是为了解决计算机科学中“人如何更好地指挥机器干活”问题而生的“indirection”。

上面是一段二进制数据，机器可以高效地识别这些 0  和 1 组成的数字信号并加以应用，但是人脑不行。人脑不擅长处理这些枯燥冗长的信号。所以，上古时期的计算机科学家们为了方便，将某些二进制数据赋予含义，发明了早期的机器码（Machine Code）。

图 1 早期机器码：Machine language monitor in W65C816S, https://en.wikipedia.org/wiki/Machine_code

如上图所见，机器码中加入了一些自然语言的语义元素。人脑理解起来比原始二进制数据要容易一些，但依旧很费神。之后计算机科学家们在此基础上又改良出了汇编语言，进一步有所改进，但在构建大型软件工程时仍然很费神。一代又一代的计算机工作者们为了自己及后人的幸福，自 1957 年起，绞尽脑汁地发明了上百门对人脑更友好的高级编程语言。笔者列举大家可能听过的高级语言如下。

表 1 常见编程语言及其诞生时间

这些高级语言要么着重运行性能，要么着重开发效率，要么着重业务安全。总而言之，相比低级语言，它们都可以帮助计算机工作者们用更低的心智负担去更好地利用机器解决问题。但是，这些高级语言不能直接控制机器，需要有一个过程将这些高级语言转换成低级语言机器码从而去控制机器，这个过程就是编译。

2. 编译原理简述

一个完整的编译流程包含扫描，解析，分析，转译，优化，生成几个步骤，其中有些步骤是可选项，如下图所示。

以下面的 Go 代码为例。

a := (base + 10.2) / 2

经过扫描后得到词元列表 Tokens：a, :=, (, base, +, 10.2, ), /, 2。再将该词元列表解析，得到语法树如下。

得到语法树后，可以选择直接转译成其他高级语言或者语义分析转成中间结果。这里的语法树可以选择直接转译成 JavaScript。

var a = (base + 10.2) / 2;

或者，也可以选择转成中间结果。中间结果是初始输入和最终输出的中间态，可以是控制流程图(CFG, Control Flow Graph)或者静态单一赋值(SSA, Static Single Assignment)等等形式。其中 CFG 大致形态如下图所示。

图 4 CFG 样例 https://en.wikipedia.org/wiki/Control-flow_graph

中间结果一般比较抽象，不会与具体的特定机器架构（x86, ARM 等）绑定。因此，中间结果既可以选择生成自定义字节码，也可以选择借助编译器框架（比如 LLVM）生成多种平台的本地机器码，从而实现编程语言的跨平台特性。

对性能没有极致追求的编程语言，一般会为了易维护性而选择生成自定义字节码。自定义字节码虽无法直接指挥机器硬件执行， 但可以借助虚拟机（Virtual Machine） 去控制。虚拟机拥有语言开发者心中理想的 CPU 架构，它能够忽略现实中各硬件平台的差异，直接执行开发者设计的理想的字节码（Byte Code） 指令。

以下文即将介绍的字节码为例，上文的简单代码可以转化成如下字节码指令。

// a := (base + 10.2) / 2
0000    1 OP_GET_GLOBAL       1 'base'
0002    | OP_CONSTANT         2 '10.2'
0004    | OP_ADD
0005    | OP_CONSTANT         3 '2'
0007    | OP_DIVIDE
0008    | OP_DEFINE_GLOBAL    0 'a'
0010    2 OP_NIL
0011    | OP_RETURN

根据这些字节码指令的名称，读者可以猜测它完成了获取了一个变量，构建了一些常量，做了一些算数运算等等工作。

执行编译过程的工具自然就是编译器 Compiler。广义上，编译器可以指代一切将高级语言源代码编译成底层指令的工具。但是狭义上，编译工具可以分为编译器 Compiler 和 解释器 Interpreter。其中，编译器特指将源代码转换成其他格式，但是不执行的工具。解释器特指转换过程中直接执行源代码，即所谓“解释执行”的工具。

按如上狭义定义的话，GCC、Clang、Rust 之类可以称为编译器，Ruby 早期版本、PHP 早期版本可以称为解释器，而 CPython 这种则是二者的中间态。

简单介绍了编译基本原理后，让笔者站在 Dart 语言贡献者 Robert Nystrom 和 Lua 语言作者 Roberto Ierusalimschy 等巨人的肩膀上带读者一起领略下从 0 到 1 创建一门脚本语言的精彩。

文中主要知识来自于 Robert Nystrom 的 "Crafting Interpreters" 和 Roberto Ierusalimschy 的 "The Implementation of Lua 5.0" 以及 "The Design of Lua"。

3. 鹅本解释器

既然是在鹅厂学习创建的脚本语言，就暂且将其命名为企鹅脚本，简称为鹅本，英文名eben。鹅本的解释器就叫鹅本解释器，它对应的文件后缀是.eb。鹅本学习借鉴了 Python，NodeJS 等语言的执行程序，既可以以 REPL 模式运行（直接执行 eben 可执行文件），也可以以文件模式运行（eben FILE_PATH，可执行文件后面带脚本文件路径）。

图 5 鹅本 eben REPL（Read-Eval-Print-Loop） 模式执行

3.1.1 BNF 范式

eben 的语法规则借鉴了 Python，Rust，C/C++ 等语言。以下面打印语句为例。

print "hello" + " world";
print 5 > 9;
print 4 * 9 + -8 / 2;

将其抽象成 BNF 范式 则是：

printStmt -> "print" expression ";" ;

该范式指明打印语句由“print”关键字加上expression（表达式），再加上一个“;”组成。其中，expression 可以进一步具象化成其他子范式。以 print 5 > 9; 为例，expression 范式可以具象成 comparison 比较表达式子范式。

expression -> ...| comparison | ... ;
comparison -> term (">" | ">=" | "<" | "<=") term ;

term 是比较式中的项，对应到上面代码语句中就是 5 和 9。

再以 print 4 * 9 + -8 / 2; 为例，term 可以再行细分拆解成如下范式。

term -> factor ( ( "-" | "+") factor )* ;
factor -> unary ( ( "/" | "*" ) unary )* ;

factor 就是算术运算中的因子。星号 * 的含义与正则表达式中星号相同，表示其左边括号括住的部分可以出现任意次。四则运算中乘除法的运算优先级高于加减法，所以范式中加减运算里的 factor 可以再细分成乘除运算表达式。语法解析的过程是自上而下递归执行的，所以越在内里的范式，最终执行的优先级越高。此处设计可以保证算术表达式中乘除部分优先于加减部分完成。

范式中的 unary 对应一元运算项，比如 -8 / 2 中 -8 就是一元运算项，它所携带的负号符号 - 就是一元运算符。它的优先级高于四则算术运算。

其他范式层层递进具象化的流程与 printStmt 大致相似。若以 class 声明语句为例，eben 中代码如下所示。

class Bird {
 fly() { print "Hi, sky!"; }
}
class Canary : Bird {
 eat() {}
}

其相关范式如下。

classDecl -> "class" IDENTIFIER ( ":" IDENTIFIER)? "{" function* "}" ;
function -> IDENTIFIER "(" parameters? ")" block ;
parameters -> IDENTIFIER ( "," IDENTIFIER )* ;
IDENTIFIER -> ALPHA ( ALPHA | DIGIT )* ;

类声明由 class 关键字跟随一个标识符 IDENTIFIER 开头，其后是可选的继承符号及父类标识符。再之后是花括号囊括的主体，其中可包含任意个函数 function 定义。函数声明由标识符跟随一对小括号组成，小括号中是可选的参数列表 parameters  ，小括号后跟随一个函数主体。参数列表由逗号间隔的多个标识符组成。标识符由字母开头，其后再跟随任意个字母 ALPHA 或数字 DIGIT。

eben 中其他语句的范式与此处例子大同小异，不再赘述。

3.1.2 字节码

eben 借鉴了 Python、Lua 等语言的设计，也采用了虚拟机运行自定义字节码的执行模式。常用字节码如下所示。

表 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' // 定义全局变量 b
0007    2 OP_GET_GLOBAL       3 'b' // 获取全局变量 b
0009    | 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 编译执行的主要流程。

词法扫描是对源代码进行处理的第一个步骤，负责将 eben 代码转换成一串词元 Tokens。如果发现词法错误，则直接报错返回。业界大型编程语言一般采用专业的辅助工具来完成词法分析扫描，比如 Yacc 和 Lex。不过这些工具会引入很多额外开销，增加开发者的心智负担。本文为了更清晰地讲解词法扫描的原理，选择使用手写扫描法。eben 中基本词元的 BNF 范式如下所示。

NUMBER -> DIGIT+ ( "." DIGIT+ )? ; // 数值
IDENTIFIER -> ALPHA ( ALPHA | DIGIT )* ; // 标识符
ALPHA -> "a" ... "z" | "A" .. "Z" | "_" ; // 字母（包含下划线）
DIGIT -> "0" ... "9" ; // 数字
STRING -> '"' (^")* '"' ; // 字符串（^" 表示非引号）

词法扫描会读入源代码文件，逐个字符地检测判定，将判定结果加入到 Tokens 词元列表中。

// 是否是字母或下划线
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()) {
  advance();
 }
 if(isAtEnd())
  return error("未收尾的字符串");
 advance();
 return makeToken(TOKEN_STRING);
}

整体扫描逻辑也可以用一个大型 switch 实现，大致如下所示。

Token scan() {
 char c = advance();
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("未识别字符");
}

没有遇到词法错误的情况下，编译器通过不停地调用 scan() 函数就可以完成源代码的词法扫描。scan()第 4 行处identifier()函数有些特殊，它扫描出标识符后，不能直接当作普通标识符给变量名、函数名使用，还需要先过滤出 eben 自身保留关键字。保留关键字如下表所示。

表 3 eben 保留关键字

过滤出保留关键字的简单方法是每得到一个标识符，就遍历上表中的值，并逐个进行字符串 strncmp 判等操作。虽然也可以得到结果，但是不够高效。更好的方式是使用字典树 Trie进行过滤。eben 中部分关键字构建出来的 Trie 结构大致如下所示。

图 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; // 没有匹配，说明不是保留关键字

符号、数值、字符串、标识符等都被成功处理后，源代码就变成了 Tokens。下面就可以进行语法解析。

eben 的语法规则中，整个程序可以由如下范式表达。

// 程序代码由任意条声明加上文件结束符组成
program -> decl* EOF ;
// 声明可以是类声明、函数声明、变量声明等，还可以是语句
decl -> classDecl | funcDecl | varDecl | stmt ;
// 语句可以是表达式语句，for循环，if条件，打印，返回，while循环，区块等
stmt -> exprStmt | forStmt | ifStmt | printStmt | returnStmt | whileStmt | block ;

上面的 decl，stmt 等都可以继续往下具象化。依据这些范式，语法解析的主体逻辑如下所示。

void compile(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 statement() {
 if(match(TOKEN_PRINT)) {
  printStatement(); // 解析打印语句
 } else if(match(TOKEN_FOR)) {
  forStatement(); // 解析 for 循环语句
 }
 ... // 解析其他语句
 else {
  expressionStatement(); // 解析表达式语句
 }
}
...

每一种声明范式都有其对应的解析函数。以其中的 funcDeclaration 函数声明为例，其主要语法解析逻辑如下。

static void funcDeclaration() {
 uint8_t funcNameIndex = parseVariable("此处需要函数名"); // 解析函数名标识符，失败则报错
 consumeToken(TOKEN_LEFT_PAREN, "需要左括号"); // 完成左括号解析，不存在则报错
 if(!check(TOKEN_RIGHT_PAREN)) { // 如果下一个token不是右括号，代表有函数形参列表
  do {
   uint8_t paramNameIndex = parseVariable("需要形式参数名称");
   defineVariable(paramNameIndex);
  } while(match(TOKEN_COMMA)); // 遇到逗号代表还有参数，循环解析下去
 }
 consumeToken(TOKEN_RIGHT_PAREN, "需要右括号"); // 完成右括号解析，不存在则报错
 consumeToken(TOKEN_LEFT_BRACE, "需要左花括号"); // 完成左花括号解析，不存在则报错
 block(); // 解析函数体，函数体是一个区块 block
 ...
 defineVariable(funcNameIndex); // 将函数名放入全局表中
}

其他声明的语法解析与上述函数声明的解析大同小异。主要是将上游的 Tokens 按照 BNF 范式解析出来，生成下游运行需要的字节码指令及其数据。如果过程中遇到不符合 BNF 范式的 Token，将检测到的全部错误打包反馈给用户，方便用户调整修复。

语法解析流程不仅会生成字节码指令，还会生成运行时所需的底层数据。数据主要有 4 种类型，这 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.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;
}

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_PRINT
0008    3 OP_JUMP             8 -> 12 // 无条件跳到 0012 处
0011    | OP_POP // 弹出栈顶值
0012    4 OP_CONSTANT         1 'hello'
0014    | OP_PRINT

0001处的 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_GLOBAL       2 'a'
0006    | OP_CONSTANT         3 '0'
0008    | OP_GREATER // 判断 a 是否大于 0
0009    | OP_JUMP_IF_FALSE    9 -> 24 // 如果判定为假，跳过整个循环体
0012    | OP_POP
0013    3 OP_GET_GLOBAL       5 'a'
0015    | OP_CONSTANT         6 '1'
0017    | OP_SUBTRACT
0018    | OP_SET_GLOBAL       4 'a'
0020    | OP_POP
0021    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' // 生成字面量 0
0002    | OP_GET_LOCAL        1 // 获取序号 1 处局部变量值，即 i 的值
0004    | OP_CONSTANT         1 '5' // 生成字面量 5
0006    | OP_LESS // 判断是否小于 5
0007    | OP_JUMP_IF_FALSE    7 -> 31 // 如果为假，跳过循环体
0010    | OP_POP
0011    | OP_JUMP            11 -> 25 // 无条件跳到 0025 处，跳过更新部分，循环体执行之后才执行这里
0014    | OP_GET_LOCAL        1
0016    | OP_CONSTANT         2 '1'
0018    | OP_ADD // 将序号 1 处局部变量，即 i 的值加1
0019    | OP_SET_LOCAL        1
0021    | OP_POP
0022    | 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_POP
0032    | 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_TRUE
0001    | OP_JUMP_IF_FALSE    1 -> 6 // 如果假，跳到 0006。此处真，不跳。
0004    | OP_POP
0005    | OP_TRUE
0006    | OP_JUMP_IF_FALSE    6 -> 16 // 如果假，跳到 0016。此处真，不跳。
0009    | OP_POP
0010    2 OP_CONSTANT         0 'AND is ok'
0012    | OP_PRINT // 正常执行打印
0013    3 OP_JUMP            13 -> 17
0016    | OP_POP

如果用户代码改成：

if(false and true) {
    print "shortcut";
}

对应的字节码如下。

0000    1 OP_FALSE
0001    | OP_JUMP_IF_FALSE    1 -> 6 // 如果假，跳到 0006。此处假，跳。
0004    | OP_POP
0005    | OP_TRUE
0006    | OP_JUMP_IF_FALSE    6 -> 16 // 0004 和 0005 处的操作被跳过，目前栈顶值还是假，跳到 0016
0009    | OP_POP
0010    2 OP_CONSTANT         0 'shortcut'
0012    | OP_PRINT
0013    3 OP_JUMP            13 -> 17
0016    | 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_TRUE
0001    | OP_JUMP_IF_FALSE    1 -> 7 // 如果假，跳到 0007。此处真，不跳。
0004    | OP_JUMP             4 -> 9 // 直接跳到 0009
0007    | OP_POP
0008    | OP_FALSE
0009    | OP_JUMP_IF_FALSE    9 -> 19 // 0007 和 0008 处的操作被跳过，目前栈顶值还是真，不跳
0012    | OP_POP
0013    2 OP_CONSTANT         0 'shortcut'
0015    | OP_PRINT // 正常执行打印
0016    3 OP_JUMP            16 -> 20
0019    | OP_POP

or 左边的结果为真后，条件判定中后面的表达式全部被跳过，符合预期。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); // 回填跳跃整个条件表达式的距离参数
}

eben 中 函数 的使用如下所示。fn 关键字借鉴自 Rust ，它既不像 f 那么单薄，也不像function 那般冗长。

fn sayHi(first, last) {
    print "Hi, " + first + " " + last + "!";
}

sayHi("Code", "读者");

这段脚本编译成字节码后，脚本主体 <script> ** 生成了一段字节码，sayHi 函数也生成了一段自己的字节码。这样的设计是为了方便后文介绍的 CallFrame 调用栈帧实现隔离。

== sayHi == // sayHi 函数体
0000    2 OP_CONSTANT         0 'Hi, ' // 构建字面常量
0002    | OP_GET_LOCAL        1 // 获取序号 1 处局部变量，即第一个参数 first
0004    | OP_ADD // 字符串拼接
0005    | OP_CONSTANT         1 ' '  // 构建字面常量
0007    | OP_ADD // 字符串拼接
0008    | OP_GET_LOCAL        2 // 获取序号 2 处局部变量，即第二个参数 last
0010    | OP_ADD // 字符串拼接
0011    | OP_CONSTANT         2 '!'  // 构建字面常量
0013    | OP_ADD // 字符串拼接
0014    | OP_PRINT // 打印
0015    3 OP_NIL
0016    | OP_RETURN // 该函数没有明确返回值，故默认返回值为 nil
== <script> == // 脚本主体
0000    3 OP_CLOSURE          1 <fn sayHi> // 构建函数
0002    | OP_DEFINE_GLOBAL    0 'sayHi' // sayHi 函数加入到全局表
0004    5 OP_GET_GLOBAL       2 'sayHi' // 从全局表中获取 sayHi 函数
0006    | OP_CONSTANT         3 'Code' // 构建字面常量
0008    | OP_CONSTANT         4 '读者' // 构建字面常量
0010    | OP_CALL             2 // 调用 sayHi 函数
0012    | OP_POP // 弹出栈顶值

函数相关的两个关键字节码是 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 slots

frame->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        1
0002    | OP_CONSTANT         0 '0'
0004    | OP_GREATER
0005    | OP_NOT // operand <= 0 等价于 !(operand > 0)
0006    | OP_JUMP_IF_FALSE    6 -> 16 // 未达到基准条件，跳到 0016
0009    | OP_POP
0010    3 OP_CONSTANT         1 '0'
0012    | OP_RETURN
0013    4 OP_JUMP            13 -> 17
0016    | OP_POP
0017    5 OP_GET_LOCAL        1
0019    | OP_GET_GLOBAL       2 'adder'
0021    | OP_GET_LOCAL        1
0023    | OP_CONSTANT         3 '1'
0025    | OP_SUBTRACT // 当前参数减 1 后的值放入栈顶
0026    | OP_CALL             1 // 再次发起调用，即再压入一个 CallFrame
0028    | OP_ADD // 将当前参数与调用产生的值相加
0029    | OP_RETURN
== <script> ==
0000    6 OP_CLOSURE          1 <fn adder>
0002    | OP_DEFINE_GLOBAL    0 'adder' // 定义这个全局函数
0004    8 OP_GET_GLOBAL       2 'adder'
0006    | OP_CONSTANT         3 '5'
0008    | OP_CALL             1
0010    | OP_PRINT

脚本主体的逻辑清晰简单，定义一个 adder函数，然后传参给它并调用，最后打印出结果。adder 函数内部通过OP_JUMP指令构成递归的基准条件 Base Case ，再用OP_CALL引发递归调用。递归调用会不断压入新栈帧，直到遇到基准条件，然后再逐层弹出，返回到调用点位置。

闭包 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_NIL
0004    | OP_RETURN
== makeFunc ==
0000    2 OP_CONSTANT         0 'hello'
0002    5 OP_CLOSURE          1 <fn myFunc> // 生成闭包函数，并携带闭包参数
0004      |                     local 1 // myFunc 携带的闭包参数是从父函数的局部变量捕获所得，即脚本中的 a
0006    6 OP_GET_LOCAL        2 // myFunc 是内部函数，所以也是 local
0008    | OP_RETURN
== <script> ==
0000    7 OP_CLOSURE          1 <fn makeFunc> // 生成函数
0002    | OP_DEFINE_GLOBAL    0 'makeFunc'
0004    9 OP_GET_GLOBAL       3 'makeFunc'
0006    | OP_CALL             0
0008    | OP_DEFINE_GLOBAL    2 'f'
0010   10 OP_GET_GLOBAL       4 'f'
0012    | OP_CALL             0 // 调用 f 函数
0014    | OP_POP

获取闭包参数的指令叫作 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 的值并打印。

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_GLOBAL       1 'Cake'
...
0010    6 OP_POP
0011    8 OP_GET_GLOBAL       5 'Cake'
0013    | OP_CALL             0 // 调用 Cake()，因为 Cake 未指定构造函数，故使用默认的无参构造函数
0015    | OP_DEFINE_GLOBAL    4 'cake' // 加到全局表
0017    9 OP_GET_GLOBAL       6 '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_GLOBAL       6 '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_GLOBAL       9 '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_GLOBAL       1 'Cake'
0006    5 OP_CLOSURE          3 <fn eat>
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，此位置专门预留给 this
0002    | OP_GET_LOCAL        1 // 获得序号 1 的局部变量，即 color 参数
0004    | OP_SET_PROPERTY     0 'color' // 将参数赋值到 this 的属性 color 中
0006    | OP_POP
0007    4 OP_GET_LOCAL        0 // 获得序号 0 的局部变量，即this
0009    | OP_RETURN // 返回 this，即实例自身
== eat ==
0000    7 OP_CONSTANT         0 '这个'
0002    | OP_GET_LOCAL        0 // 获得序号 0 的局部变量，即this
0004    | OP_GET_PROPERTY     1 'color' // 获得 this 上的属性字段 color
0006    | OP_ADD // 字符串拼接
0007    | OP_CONSTANT         2 '蛋糕真不错!'
...
== <script> ==
0000    1 OP_CLASS            0 'Cake'
0002    | OP_DEFINE_GLOBAL    0 'Cake'
0004    | OP_GET_GLOBAL       1 'Cake'
0006    4 OP_CLOSURE          3 <fn init> // 生成构造函数包装而成的闭包对象
0008    | OP_METHOD           2 'init' // 构造函数加入到类的成员方法表
...

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 // 获得 this
0002    | OP_GET_UPVALUE      0 // 获得 super
0004    | OP_SUPER_INVOKE  (0 args)    0 'eat' // 调用父类方法 eat
0007    | OP_POP
0008   14 OP_CONSTANT         1 '加了香蕉更好吃!'
0010    | OP_PRINT
0011   15 OP_NIL
0012    | OP_RETURN
== <script> ==
0000    1 OP_CLASS            0 'Cake' // 生成父类 Cake
... // 生成父类 Cake 成员方法
0015   11 OP_CLASS            6 'BananaCake' // 生成子类 BananaCake
0017    | OP_DEFINE_GLOBAL    6 'BananaCake'
0019    | OP_GET_GLOBAL       7 'Cake'
0021    | OP_GET_GLOBAL       8 'BananaCake'
0023    | OP_INHERIT // 继承父类的方法（只继承方法，不继承字段，因为后者都是动态设置）
0024    | OP_GET_GLOBAL       9 'BananaCake' // 开始生成其成员方法
... // OP_METHOD 指令，此处略去
0033    | OP_CLOSE_UPVALUE
0034   18 OP_GET_GLOBAL      13 'BananaCake'
0036    | OP_CALL             0 // 调用默认构造函数
0038    | OP_DEFINE_GLOBAL   12 'bc'
0040   19 OP_GET_GLOBAL      14 'bc'
0042    | OP_INVOKE        (0 args)   15 'make' // 调用继承来的 make 方法
0045    | OP_POP
0046   20 OP_GET_GLOBAL      16 'bc'
0048    | OP_INVOKE        (0 args)   17 'eat' // 调用 eat 方法
...

字节码中出现的新指令是 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 查找逻辑找到闭包参数 super
emitBytes(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); // 生成继承指令
 }
 ...
}

开发过程中，总要有人操心内存管理。要么是语言使用者（比如 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); // 尾部的''也一起释放
   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. 参考文献

1. Histroy of programming lanauage, https://en.wikipedia.org/wiki/History_of_programming_languages
2. Robert Nystrom. Crafting Interpreters. https://craftinginterpreters.com/
3. Roberto Ierusalimschy. The Implementation of Lua 5.0. https://www.lua.org/doc/jucs05.pdf
4. Perry Cheng, Guy E. Blelloch. A Parallel, Real-Time Garbage Collector. http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdf
5. Robin 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