计算机科学家DavidWheeler有一句名言，“Allproblemsincomputersciencecanbesolvedbyanotherlevelofindirection,exceptfortheproblemoftoomanylayersofindirection.”。大意是指，计算机科学中所有问题都可以通过多一个间接层来解决，除了间接层太多这个问题本身。
编译就是为了解决计算机科学中“人如何更好地指挥机器干活”问题而生的“indirection”。
上面是一段二进制数据，机器可以高效地识别这些0和1组成的数字信号并加以应用，但是人脑不行。人脑不擅长处理这些枯燥冗长的信号。所以，上古时期的计算机科学家们为了方便，将某些二进制数据赋予含义，发明了早期的机器码（MachineCode）。
如上图所见，机器码中加入了一些自然语言的语义元素。人脑理解起来比原始二进制数据要容易一些，但依旧很费神。之后计算机科学家们在此基础上又改良出了汇编语言，进一步有所改进，但在构建大型软件工程时仍然很费神。一代又一代的计算机工作者们为了自己及后人的幸福，自1957年起，绞尽脑汁地发明了上百门对人脑更友好的高级编程语言。笔者列举大家可能听过的高级语言如下。
年份语言1957FORTRAN1958LISP1959COBOL1964BASIC1970Pascal1972C1978SQL1980C++1986Objective-C1987Perl1990Haskell1990Python1993Lua1995Ruby1995Java1995JavaScript1995PHP2001C#2003Scala2009Go2012TypeScript2014Swift2015Rust......
这些高级语言要么着重运行性能，要么着重开发效率，要么着重业务安全。总而言之，相比低级语言，它们都可以帮助计算机工作者们用更低的心智负担去更好地利用机器解决问题。但是，这些高级语言不能直接控制机器，需要有一个过程将这些高级语言转换成低级语言机器码从而去控制机器，这个过程就是编译。
一个完整的编译流程包含扫描，解析，分析，转译，优化，生成几个步骤，其中有些步骤是可选项，如下图所示。
图2编译流程
以下面的Go代码为例。
经过扫描后得到词元列表Tokens：a,:=,(,base,+,10.2,),/,2。再将该词元列表解析，得到语法树如下。
图3语法树
得到语法树后，可以选择直接转译成其他高级语言或者语义分析转成中间结果。这里的语法树可以选择直接转译成JavaScript。
vara=(base+10.2)/2;或者，也可以选择转成中间结果。中间结果是初始输入和最终输出的中间态，可以是控制流程图(CFG,ControlFlowGraph)或者静态单一赋值(SSA,StaticSingleAssignment)等等形式。其中CFG大致形态如下图所示。
中间结果一般比较抽象，不会与具体的特定机器架构（x86,ARM等）绑定。因此，中间结果既可以选择生成自定义字节码，也可以选择借助编译器框架（比如LLVM）生成多种平台的本地机器码，从而实现编程语言的跨平台特性。
对性能没有极致追求的编程语言，一般会为了易维护性而选择生成自定义字节码。自定义字节码虽无法直接指挥机器硬件执行，但可以借助虚拟机（VirtualMachine）去控制。虚拟机拥有语言开发者心中理想的CPU架构，它能够忽略现实中各硬件平台的差异，直接执行开发者设计的理想的字节码（ByteCode）指令。
以下文即将介绍的字节码为例，上文的简单代码可以转化成如下字节码指令。
根据这些字节码指令的名称，读者可以猜测它完成了获取了一个变量，构建了一些常量，做了一些算数运算等等工作。
执行编译过程的工具自然就是编译器Compiler。广义上，编译器可以指代一切将高级语言源代码编译成底层指令的工具。但是狭义上，编译工具可以分为编译器Compiler和解释器Interpreter。其中，编译器特指将源代码转换成其他格式，但是不执行的工具。解释器特指转换过程中直接执行源代码，即所谓“解释执行”的工具。
按如上狭义定义的话，GCC、Clang、Rust之类可以称为编译器，Ruby早期版本、PHP早期版本可以称为解释器，而CPython这种则是二者的中间态。
简单介绍了编译基本原理后，让笔者站在Dart语言贡献者RobertNystrom和Lua语言作者RobertoIerusalimschy等巨人的肩膀上带读者一起领略下从0到1创建一门脚本语言的精彩。
文中主要知识来自于RobertNystrom的'CraftingInterpreters'和RobertoIerusalimschy的'TheImplementationofLua5.0'以及'TheDesignofLua'。
既然是在鹅厂学习创建的脚本语言，就暂且将其命名为企鹅脚本，简称为鹅本，英文名eben。鹅本的解释器就叫鹅本解释器，它对应的文件后缀是.eb。鹅本学习借鉴了Python，NodeJS等语言的执行程序，既可以以REPL模式运行（直接执行eben可执行文件），也可以以文件模式运行（ebenFILE_PATH，可执行文件后面带脚本文件路径）。
图5鹅本ebenREPL（Read-Eval-Print-Loop）模式执行
eben的语法规则借鉴了Python，Rust，C/C++等语言。以下面打印语句为例。
print'hello'+'world';print5>9;print4*9+-8/2;将其抽象成BNF范式则是：
该范式指明打印语句由“print”关键字加上expression（表达式），再加上一个“;”组成。其中，expression可以进一步具象化成其他子范式。以print5>9;为例，expression范式可以具象成comparison比较表达式子范式。
expression->...|comparison|...;comparison->term('>'|'>='|'<'|'<=')term;term是比较式中的项，对应到上面代码语句中就是5和9。
再以print4*9+-8/2;为例，term可以再行细分拆解成如下范式。
factor就是算术运算中的因子。星号*的含义与正则表达式中星号相同，表示其左边括号括住的部分可以出现任意次。四则运算中乘除法的运算优先级高于加减法，所以范式中加减运算里的factor可以再细分成乘除运算表达式。语法解析的过程是自上而下递归执行的，所以越在内里的范式，最终执行的优先级越高。此处设计可以保证算术表达式中乘除部分优先于加减部分完成。
范式中的unary对应一元运算项，比如-8/2中-8就是一元运算项，它所携带的负号符号-就是一元运算符。它的优先级高于四则算术运算。
eben中其他语句的范式与此处例子大同小异，不再赘述。
eben借鉴了Python、Lua等语言的设计，也采用了虚拟机运行自定义字节码的执行模式。常用字节码如下所示。
字节码含义OP_ADD加法、拼接操作OP_SUBTRACT减法操作OP_MULTIPLY乘法操作OP_DIVIDE除法操作OP_NEGATE取负操作OP_NOT取反操作OP_JUMP跳跃操作OP_CALL调用操作OP_PRINT打印操作OP_RETURN返回操作OP_CLASS定义类操作OP_EQUAL等值判断操作OP_POP出栈操作OP_CONSTANT常量创建操作OP_GET_LOCAL获取局部变量操作OP_DEFINE_GLOBAL定义全局变量操作......
表2eben常用字节码（节选）
eben中所有的代码都会转化成上述字节码，再到虚拟机中执行。
以varb='hello'+'world';\nprintb;为例，其可以转化成如下字节码。
00001OP_CONSTANT1'hello'//创建字面常量'hello'0002|OP_CONSTANT2'world'//创建字面常量'world'0004|OP_ADD//字符串拼接0005|OP_DEFINE_GLOBAL0'b'//定义全局变量b00072OP_GET_GLOBAL3'b'//获取全局变量b0009|OP_PRINT//打印3.1.3虚拟机虚拟机是eben的核心所在。它负责管理内存，维护函数调用栈，管理全局变量，衔接系统函数，执行字节码等等。eben由C语言开发，虚拟机在C代码中的大致结构如下。
执行字节码的主逻辑就是一个超大的switch语句，其形态如下。
Resultrun(){for(;;){switch(instruction=READ_BYTE()){//获取下一条字节码caseOP_CONSTANT:...;break;caseOP_POP:pop();break;caseOP_GET_GLOBAL:...;break;caseOP_ADD:...;break;caseOP_CLOSURE:...;break;caseOP_CLASS:push(OBJ_VAL(newClass(READ_STRING())));break;//创建类对象...}}}了解了BNF范式，字节码，虚拟机这些基础概念之后，下面就可以探究eben编译执行的主要流程。
词法扫描是对源代码进行处理的第一个步骤，负责将eben代码转换成一串词元Tokens。如果发现词法错误，则直接报错返回。业界大型编程语言一般采用专业的辅助工具来完成词法分析扫描，比如Yacc和Lex。不过这些工具会引入很多额外开销，增加开发者的心智负担。本文为了更清晰地讲解词法扫描的原理，选择使用手写扫描法。eben中基本词元的BNF范式如下所示。
词法扫描会读入源代码文件，逐个字符地检测判定，将判定结果加入到Tokens词元列表中。
//是否是字母或下划线boolisAlpha(charc){return(c>='a'&&c<='z')||(c>='A'&&c<='Z')||c=='_';}//是否是数字boolisDigit(charc){returnc>='0'&&c<='9';}//扫描数字Tokennumber(){while(isDigit(peek(0))advance();//游标前进//小数部分if(peek(0)=='.'&&isDigit(peek(1))){advance();while(isDigit(peek(0)))advance();}returnmakeToken(TOKEN_NUMBER);}//扫描字符串Tokenstring(){while(peek(0)!='''&&!isAtEnd()){advance();}if(isAtEnd())returnerror('未收尾的字符串');advance();returnmakeToken(TOKEN_STRING);}整体扫描逻辑也可以用一个大型switch实现，大致如下所示。
没有遇到词法错误的情况下，编译器通过不停地调用scan()函数就可以完成源代码的词法扫描。scan()第4行处identifier()函数有些特殊，它扫描出标识符后，不能直接当作普通标识符给变量名、函数名使用，还需要先过滤出eben自身保留关键字。保留关键字如下表所示。
表3eben保留关键字
过滤出保留关键字的简单方法是每得到一个标识符，就遍历上表中的值，并逐个进行字符串strncmp判等操作。虽然也可以得到结果，但是不够高效。更好的方式是使用字典树Trie进行过滤。eben中部分关键字构建出来的Trie结构大致如下所示。
image-20231009142132144
图6eben部分保留关键字构建的字典树Trie
有了Trie后，不用每次都遍历全表，只需要对特定字符做运算处理即可，大致逻辑如下所示。
swtich(c1){case'a':returncheckReserved('nd',TOKEN_AND);//checkReserved判断剩下的字符串是否相同，同则返回TOKEN_ANDcase'f':{...switch(c2){case'a':returncheckReserved('lse',TOKEN_FALSE);//f+a+lse三部分都匹配的话，返回TOKEN_FALSEcase'o':returncheckReserved('r',TOKEN_FOR);case'n':returncheckReserved('',TOKEN_FUNC);}}case'v':returncheckReserved('ar',TOKEN_VAR);...}returnTOKEN_IDENTIFIER;//没有匹配，说明不是保留关键字符号、数值、字符串、标识符等都被成功处理后，源代码就变成了Tokens。下面就可以进行语法解析。
eben的语法规则中，整个程序可以由如下范式表达。
上面的decl，stmt等都可以继续往下具象化。依据这些范式，语法解析的主体逻辑如下所示。
语法解析流程不仅会生成字节码指令，还会生成运行时所需的底层数据。数据主要有4种类型，这4种底层数据类型可以呈现出eben脚本中所有的用户数据类型。
typedefenum{VAL_BOOL,//布尔类型VAL_NIL,//空类型VAL_NUMBER,//数值类型VAL_OBJ//对象类型}ValueType;其中VAL_BOOL，VAL_NIL，VAL_NUMBER表示常见的基础类型，VAL_OBJ表示eben底层实现中的复杂类型。这些类型统一用Value结构体来呈现，枚举字段type表示Value类型，联合字段as承载Value实际存储或指向的值。
Obj结构体指针所指向的复杂结构还可以再度细分。
typedefenum{OBJ_CLASS,//类OBJ_CLOSURE,//闭包OBJ_FUNCTION,//函数OBJ_INSTANCE,//实例OBJ_NATIVE,//本地函数OBJ_STRING,//字符串OBJ_UPVALUE,//闭包参数}ObjType;structObj{ObjTypetype;//Object类型boolisMarked;//用于GC标记，下文将介绍structObj*next;//链表指针}Obj结构体中包含具体复杂结构的枚举类型，GC标记位，链表指针等元信息。它可以嵌入到各个细分类型结构体的头部，从而方便虚拟机统一分配管理对象。
以ObjString和ObjClass具体结构为例，其主要字段如下。
C语言的特性使得定义在结构体头部的字段在内存中也会被分配到该结构体头部位置。所以，ObjClass和ObjString等指针指向structObjClass和structObjString的内存开始处的同时也在指向对应的structObj的内存开始处，故C代码中可以安全地将二者转化为Obj指针，反向亦然。这个特性使得一些面向对象语言中才常见的操作在C中成为可能。下面代码就利用了该特性将Obj转化成具体类型指针来进行各种内存释放操作。
voidfreeObject(Obj*object){switch(object->type){caseOBJ_CLASS:{ObjClass*klass=(ObjClass*)object;freeTable(&klass->methods);FREE(ObjClass,object);break;}caseOBJ_STRING:{ObjString*string=(ObjString*)object;FREE_ARRAY(char,string->chars,string->length+1);FREE(ObjString,object);break;}...//其他类型对象的释放}}eben使用ObjXXX这些底层数据结构相互配合，完美地实现了脚本代码中类、实例、函数、闭包、字符串等等数据类型的操作。
parseVariable函数解析出代码中的abc,bcd，它们就是范式中的IDENTIFIER。如果检测到有等号TOKEN_EQUAL，则尝试解析出等号右边的表达式，此处字符串'hello'会生成OP_CONSTANT字节码，用来填入字面常量值；否则，直接生成OP_NIL字节码，用来填入空值。最后一步生成的OP_DEFINE_GLOBAL字节码会读取上一步压入的值，要么是某常量，要么是空值，将其写入到虚拟机全局表vm.globals中。如下所示。
caseOP_DEFINE_GLOBAL:{ObjString*name=READ_STRING_FROM_CONSTANTS();//从常量列表中取出之前暂存的变量名tableSet(&vm.globals,name,peek(0));//peek(0)取出值栈的栈顶元素pop();//使用完成，弹出栈顶元素break;}OP_DEFINE_GLOBAL字节码负责写入变量，OP_GET_GLOBAL字节码则负责读取变量。以printabc;为例，第一步是读取变量abc的值。
OP_GET_GLOBAL将变量值压入栈后，第二步则是print生成的OP_PRINT字节码将其取出并打印。
如上文所述，值为globala的全局变量a存放在虚拟机的全局表vm.globals中，所以它会一直存活到脚本结束。值为outera,outerb的a,b和值为innera的a都是局部变量，它们的名字只会被存放在其所属作用域current->locals中（current代表当前scope作用域）。这就意味着局部变量会随着作用域的结束而消亡。所以，此处代码例子中最后两句printa;打印的都是当前所处作用域中的值。
嵌套最里层的printa;打印结果是innera。这是因为，eben尝试使用变量时，会优先查找当前作用域的局部变量，存在则使用，不存在则往外层继续找。如果一直到了顶层连全局变量都找不到，直接报“未定义变量”错误。
intarg=resolveLocal(current,&name);//尝试查找局部变量，递归向外执行if(arg!=-1){op=OP_GET_LOCAL;}else{op=OP_GET_GLOBAL;}emitBytes(op,arg);//传入变量序号，生成获取变量字节码局部变量的生命周期比全局变量短，都会随着作用域的开始而存在，其结束而消亡。所以，局部变量不需要存在全局表中，只需要存在栈上即可。需要时压入，用完则弹出。虚拟机需要取局部变量时，也只要找到其序号，再次压入栈顶即可。
eben中条件控制语句主要有if语句，while循环，for循环，逻辑与and和逻辑或or。其中and,or与C系列语言中的&&,||逻辑运算符类似，有短路运算（shortcut）效果。
条件控制语句允许用户根据条件的真假，选择不同的逻辑分支进行执行。但是eben在解析时会把所有逻辑分支都解析成一长串字节码，然后按照代码中出现的顺序线性地加入到最终的字节码串中。所以，“选择不同的逻辑分支进行执行”需要虚拟机能够Jump跳过某一段字节码，直接执行其后的内容。以下面的if语句为例。
if(true){print'hi';}print'hello';编译之后的字节码内容如下。
0001处的OP_JUMP_IF_FALSE由if语句生成。如果条件值为假，跳过整个if分支；如果为真，则正常执行if分支内容，并在0008处无条件跳过else分支内容（用户没有写else分支情况下，eben会自动加入空的else分支）。本例中并未写else分支，否则会在0011到0012间生成其对应的字节码。
解析if语句的逻辑如下所示。
staticvoidifStatement(){consumeToken(TOKEN_LEFT_PAREN,'需要左括号');//完成左括号解析，不存在则报错expression();//解析括号中的条件表达式consumeToken(TOKEN_RIGHT_PAREN,'需要右括号');intthenJump=emitJump(OP_JUMP_IF_FALSE);//生成条件跳跃字节码emitByte(OP_POP);//弹出条件表达式的值，用完即丢statement();//解析if分支中语句intelseJump=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分支回填跳跃距离也是同样原理。
while循环的条件控制在OP_JUMP,OP_JUMP_IF_FALSE字节码之外增加了一个OP_LOOP字节码。前二者负责向前跳，后者负责向后跳。
OP_JUMP配合负数参数也可以实现向后跳跃。不过字节码指令及其参数在虚拟机内部都使用uint8_t类型存储，故此处不使用负数以防诸多麻烦。
while样例脚本代码如下。
转化成字节码如下。
00001OP_CONSTANT1'5'0002|OP_DEFINE_GLOBAL0'a'00042OP_GET_GLOBAL2'a'0006|OP_CONSTANT3'0'0008|OP_GREATER//判断a是否大于00009|OP_JUMP_IF_FALSE9->24//如果判定为假，跳过整个循环体0012|OP_POP00133OP_GET_GLOBAL5'a'0015|OP_CONSTANT6'1'0017|OP_SUBTRACT0018|OP_SET_GLOBAL4'a'0020|OP_POP00214OP_LOOP21->4//跳回到0004处，再次进行条件判定0024|OP_POP这里的核心是0009处的OP_JUMP_IF_FALSE和0021处的OP_LOOP，分别负责“条件不成立时跳过循环体”和“跳到条件判定处继续执行”。编译器对while循环的解析逻辑如下所示。
for循环用到的跳跃字节码指令与while循环相同，但是因为其特殊语句结构，跳跃的逻辑会相对复杂。以下面的for循环代码为例。
for(vari=0;i<5;i=i+1){printi;}vari=0;初始化部分只会执行1次；i<5;条件判定部分每次循环都需要验证计算；i=i+1更新部分则在每次循环体执行完之后执行。该段代码生成的字节码如下所示。
编译器对for循环的转化逻辑如下所示。
对应的字节码如下。
00001OP_TRUE0001|OP_JUMP_IF_FALSE1->6//如果假，跳到0006。此处真，不跳。0004|OP_POP0005|OP_TRUE0006|OP_JUMP_IF_FALSE6->16//如果假，跳到0016。此处真，不跳。0009|OP_POP00102OP_CONSTANT0'ANDisok'0012|OP_PRINT//正常执行打印00133OP_JUMP13->170016|OP_POP如果用户代码改成：
00001OP_FALSE0001|OP_JUMP_IF_FALSE1->6//如果假，跳到0006。此处假，跳。0004|OP_POP0005|OP_TRUE0006|OP_JUMP_IF_FALSE6->16//0004和0005处的操作被跳过，目前栈顶值还是假，跳到00160009|OP_POP00102OP_CONSTANT0'shortcut'0012|OP_PRINT00133OP_JUMP13->170016|OP_POP//打印操作被跳过如上注释所示，and左边的值为假后，后面的操作全部被跳过。这证实了eben中逻辑运算符有短路运算效果。
and运算符的解析逻辑如下。
or逻辑运算符也有同样效果。
if(trueorfalse){print'shortcut';}这段脚本的字节码如下。
or左边的结果为真后，条件判定中后面的表达式全部被跳过，符合预期。or运算符的解析逻辑如下。
staticvoidorOperator(){intelseJump=emitJump(OP_JUMP_IF_FALSE);//如果假，跳到or右边第一个值处继续判定intendJump=emitJump(OP_JUMP);//如果真，跳过整个判定条件表达式patchJump(elseJump);//回填or左边值判定假后跳跃的距离参数emitByte(OP_POP);//左边值出栈...//继续解析右边的表达式patchJump(endJump);//回填跳跃整个条件表达式的距离参数}3.7函数eben中函数的使用如下所示。fn关键字借鉴自Rust，它既不像f那么单薄，也不像function那般冗长。
这段脚本编译成字节码后，脚本主体