4. 编译
- 创建compiler目录, 也就是我们C语言项目的compiler模块, 该模块与使用该脚本语言的用户是最亲近的了, 因为编译就是一个桥梁, 将用户输入的文本转换为内部调用, 在VM内部, 我们通过Value统一操作对象, ObjHeader实现多态等功能, 对于Value和ObjHeader, 如果知道是什么类型的就使用具体以Obj开头的对象, 如果不知道则使用Value, 但是这些都不是用户直接操作的, 用户需要通过compiler这个模块将一些自己的输入, 如var f = 10中的f转为一个Value, 转换就需要在compiler模块中定义一些struct辅助实现
- compileUnit处理的是一个代码集合, 如一个模块, 模块中又会有一个class, 构成了嵌套结构, 注意一点, 在compiler模块中的数据结构体中需要考虑到嵌套, 所以引入了scopeDepth和enclosing开头的指向外层的指针
- 在compiler目录下创建compiler.h, 因为不在object模块中, 所有都不是对象, 没有ObjHeader
- 因为Value是与后端交互(通过指令)的, 而compiler模块与用户交互的, 所有该模块基本上就没有Value的使用
compiler结构体"们"
- compiler的核心业务就是生成指令然后交给VM执行, 在生成指令的时候, 同时我们也要存储数据, 最常见的数据就是符号表了, 有常量表, 局部变量表, 显然易见, 单纯有指令没有数据是不行的
- 下面是.h文件中结构的定义
/* 定义一堆与编译有关的数据结构, 这些基本是与用户很接近 */
// 这些自己规定
#define MAX_ID_LEN ...
#define MAX_METHOD_NAME_LEN ...
#define MAX_SIGN_LEN ...
#define MAX_ARGS ...
#define MAX_LOCAL_VARS ...
#define MAX_UPVALUES ...
#define MAX_FILED_NUM ...
// 注意: 要与object模块中的obj_fn.h文件中定义的ObjUpvalue区别开来
typedef struct upvalue {
// 是否应用了外层函数的局部变量
bool is_enclosing_local_var;
// 如果应用了, 则应用的是外层栈中的哪一个
uint32_t index;
} Upvalue;
// 在模块中用不到:-)
typedef struct LocalVar {
const char *name;
uint32_t length;
int scope_depth; // 作用域的深度(这应该很好理解)
bool is_upvalue; // 是否是对于内层函数的闭包
} LocalVar;
typedef enum {
SignatureConstruct,
SignatureMethod,
SignatureSetter,
SignatureGetter,
SignatureSubScriptGetter,
SignatureSubScriptSetter
} SignatureType;
typedef struct Signature {
SignatureType type;
const char *name;
uint32_t length;
uint32_t arg_num;
} Signature;
typedef struct Loop{
int cond_start_index;
int body_start_index;
int exit_index_index;
int scope_depth_index;
struct Loop *enclosing_loop; // 外层循环
} Loop;
typedef struct {
ObjString *name;
SymbolTable fields;
bool is_static; // 当前编译的是否是静态方法
IntBuffer instantmethods; // 实例方法索引
IntBuffer staticmethod; // 静态方法索引
Signature *signature; // 当前编译类中, 编译的是哪个方法签名
} ClassBookKeep;
typedef struct compileUnit CompileUnit;
// compiler提供的接口, 用于定义模块变量, 包括class的定义, 模块全局变量的定义
int defineModuleVar(VM *vm, ObjModule *objModule, const char *name, uint32_t length, Value value);
- 在compiler中定义编译模块的核心数据结构, compileUnit
struct compileUnit{
ObjFunc *obj_func;
// 这里的localVars存储的不仅仅指当前与的, 还有子域的, 所以128个是有一点小哈, 但是无所谓了
LocalVar localVars[MAX_VARS];
uint32_t localVarNum; // 指向最新的可用的LocalVar, 和ObjThread中的Frame使用是一样的
Upvalue upvalues[MAX_UPVALUES]; // 保存upvalue
ClassBookKeep *classBK; // 可以编译的是类
uint32_t max_slot_size
Loop *loop; // 可能会有循环
int scope_depth; // 考虑到了嵌套
struct compileUnit *enclosingCompileUnit; // 考虑到了嵌套, 指向外层编译单元
Parser *cur_parser; // 为什么, 加入import一个模块则需要创建一个新的parser, 所以需要cur_parser指定到底是哪一个parser
}
// 在调用init函数初始化compileUnit结构体的时候, 默认应该是一个对于模块的compileUnit, 所以在init函数初始化的逻辑应该是这样的, ObjFn需要在init中new一个
// !!!!!!!!!!!!!注意, CompileUnit针对的是module, function和method等有业务逻辑的, class的定义不是, 因为它只能声明有哪些属性和那些方法, 所有我们需要考虑isMethod
void initCompileUnit(CompileUnit *cu, CompileUnit *enclosing, Parser *parser, bool isMethod) {
cu->obj_func = newObjFunc();
cu->classBK = NULL;
cu->loop = NULL;
// vm切换parser
parser->cur_cu = cu;
cu->cur_parser = parser;
// 表示当前初始化的CU就是一个模块编译单元, 它没有外层的CU了
if (enclosing == NULL) {
cu->scope_depth = -1;
cu->enclosingCompileUnit = NULL;
} else {
// 如果是方法, 则要考虑到this对象
if (cu->isMethod) {
cu->localVars[0].name = "this";
cu->localVars[0].length = 4;
} else {
// 为了和isMethod==true的情况一致
cu->localVars[0].name = NULL;
cu->localVars[0].length = 0;
}
cu->localVarNum = 1;
cu->scope_depth = 0;
cu->localVars[0].is_upvalue = false;
}
}
// 定义一个更加底层的函数, compileProgram函数专门用于编译CompileUnit, 所有需要一个CompileUnit指针参数
static void compileProgram(CompileUnit *cu);
// compiler模块还需要定义写入指令的函数
// 我们规定操作码占用一个字节, 操作数可以是1个字节也可能是2个字节, 这要看具体的操作码, 操作码的定义可以参考Python和Intel CPU
// 写入一个字节则返回index, 写入两个字节则不用返回
static uint32_t writeOneByte(VM *vm, CompileUnit *cu, code);
static void writeTwoBytes(VM *vm, CompileUnit, code);
...
- 实现defineModuleVar函数, 这里只提一下思路
我们知道在ObjModule中有moduleVarName和moduleVarValue, 它维护这name->value的映射, 我们在定义模块变量(注意是模块变量)的时候, 需要先判断是否模块已经存在在moduleVarName中, 如果没有存在则将其添加到moduleVarName中, 对应的Value也添加到moduleVarValue中, 在编译阶段我们传入的Value因为为NULL类型的; 如果已经存在了, 我们还需要判断moduleVarValue中的那个name对应的value的类型是不是NUM类型, 如果是则表示之前没有声明就应用了, 这在C/C++中是错误, 但是在Java和Python中是可以弥补的, 他们支持先应用, 接着在后面的位置查找声明, 我们也和Java和Python一样, 在第一种情况中, 我们没有考虑到一个变量引用与声明的关系, 所以就算是前向引用了我们也直接加入到了moduleVarName和moduleVarValue中, 在后者我们也是为了解决第一种情况的偷懒, 在调用defineModuleVar的时候, 如果是前向应用则传入的Value是NUM类型的, num是行号, 在第二种情况下, 如果判断是Value的type是NUM则表示之前前向引用了, 在这里我们继续为其赋新的Value值。当所有的变量都添加到moduelVarName和moduleVarValue中之后, 我们好在在编译一遍, 判断是否还有Value的类型为NUM的, 如果有则表示前向应用了, 但是没有声明, 接着报错就可以了
compiler的核心功能实现
- 怕忘了在这里写一下, 在生成指令的时候, 一定要将要指令要操作的东西存起来, 接着通过index或者其他方式在VM执行的通过index之类的可以访问到
- 在编译中我们要解决语法分析与语义分析, 采用TDOP套路
- 下面是compiler.c文件中的函数实现, 通过下面的函数了解编译原理
// 根据TDOP, 为所有的运算符定义权重Binding Power, 与优先级差不多
// 优先级从低到高
typedef enum {
BP_NONE,
BP_LOWEST,
BP_ASSIGN,
BP_CONDITION,
BP_LOGIC_OR,
BP_LOGIC_AND,
BP_EQUAL,
BP_IS,
BP_CMP,
BP_BIT_OR,
BP_BIT_AND,
BP_BIT_SHIFT,
BP_RANGE,
BP_TERM,
BP_FACTOR,
BP_UNARY,
BP_CALL,
BP_HIGHTEST
} BindingPower;
// 根据TDOP, 需要定义一个结构体, 该结构体为符号结构体, 需要有如下属性
typedef struct {
const char *id; // 符号名, 如+, -, /
BindingPower lbp; // 对左操作数的吸引力
// 下面的函数
// 除非这个符号既可以是前置又可以是中置, 否则nud和led其中一个为NULL
// 在SymbolBindRule对象中调用nud或者led方法在该方法的最后一定要调用函数生成指令
DenotationFn nud; // 如果该符号不关心左操作数则调用nud, 如常量, 字面量, 前置符号
DenotationFn led; // 如果该符号关心左操作数则调用led, 如*, /, %等
MethodSignatureFn methodSign;// 如果符号在一个类中, 则该符号被视为一个方法, 根据Signature生成方法签名
} SymbolBindRule;
// TDOP核心函数expression, 讨论来啦, Mark了, 此时curToken一定是一个操作符
/*
大致思路:
1. 获取当前curToken
2. 获取下一个nextToken
3. 调用curToken.nud方法, left接受返回值
4. 在while条件中比较nextToken.lbp与参数rbp
5. t = nextToken
6. 调用getNextToken获取nextNextToken
7. left = t.led(left)
8. 在函数的最后返回left
*/
static void expression(CompileUnit *cu, BindPower rbp) {
DenotationFn nud = Rules[cu->cur_parser->curToken.type].nud;
getNextToken(cu->parser);
nud(cu);
while (rbp < Rules[cu->cur_parser->curToken.type].lbp) {
DenotationFn led = Rules[cu->cur_parser->curToken.type].led;
getNextToken(cu->Parser);
led(cu);
}
}
// 现在定义SymbolBindRule中的led与nud的逻辑
// 中置运算符nud为NULL, led需要定义, 因为中置运算符关心左操作数, 我们命名为infixOperator, 这里的中置运算符灵感来源于C++的运算符重载, 我们在该脚本语言中将所有的中置运算符都当做函数调用, 如1+1 -> 1.+(1)
static void infixOperator(CompileUnit *cu) {
// 获取preToken对应的SymbolBindRule
// 将其lbp作为rbp, 因为中置运算符中lbp==rbp
// 紧接着调用expression(cu, rbp)构成递归
// 本来到这里就已经完了的, 但是我们这是面向对象的语言, 类中的方法也是中置运算符, 所以需要在调用了expression之后生成方法标签, 在生成方法标签函数中***将方法签名生成对应的指令***
SymbolBindRule *rule = Rules[cu->cur_parser->preToken.type];
BindPower rbp = rule->lbp;
expression(cu, rbp);
// ***参数为1, 因为1+2 -> 1.+(2), +方法参数就是2一个***
Signature *sign = {MethodType, , 参数为1};
emitCallSignature(...);
}
// 现在为前置运算符定义nud函数, 它的表现形式与led一样, 和C++的运算符重载一样, 如!3->3.!, 只不过没有参数罢了
/*
获取preToken对应的SymbolBindRule
调用expression
生成方法签名指令, 但是又因为其没有参数, 所以方法签名就是方法名
*/
static void unaryOperator(CompileUnit *cu) {
SymbolBindRule *rule = Rules[cu->cur_parser->preToken.type];
// BP_UNARY是前置运算符的BP
expression(cu, BP_UNARY);
// 生成调用方法的指令, 在emitCall函数中生成指令, 其实按理说也可以使用上面个提到的emitCallSignature函数的, 只是现在这个unaryOperator有一点特别, 它的方法名就是方法签名
emitCall(...);
}
// 字面量和常量的nud为literal, 直接将生成常量的指令
static void literal(CompileUnit *cu, Value constant) {
emitLoadConstant(cu, constant);
}
// ====================================================
// 刚才提到了emitCall和emitCallSignature函数, 现在使用伪代码实现以下
static void emitCallSinagure() {
method_sign_string = sign2string
if method_sign_string not in vm->allMethodNames:
add
// need argNum to choose callX(call0?, call1? and so on)
writeOpCodeOperand(method_sign_string, argNum);
// 注意点, 现在还没有完呢, 考虑到继承, 这里还有写入一个空的slot, 将来绑定到基类上
writeOperand();
}
static void emitCall() {
// 思路和emitCallSignature一样就是不用sign2string了
}
// 关于sign2string参考
// 将Signature转换为字符串, 也就是方法签名, 参数使用_占位
static uint32_t sign2String(Signature *sign, char *buf) {
uint32_t pos = 0;
// 复制方法名xxx
memcpy(buf + pos, sign->name, sign->length);
pos += sign->length;
switch(sign->type) {
// xxx, 无参数, 上面的memcpy已经完成
case SIGN_GETTER:
break;
// xxx=(_), 和C++中的操作符重载非常的类似
case SIGN_SETTER:
buf[pos++] = '=';
buf[pos++] = '(';
buf[pos++] = '_';
buf[pos++] = ')';
break;
// xxx(_, ...)
case SIGN_CONSTRUCT:
case SIGN_METHOD: {
buf[pos++] = '(';
uint32_t idx = 0;
while (idx < sign->argNum) {
buf[pos++] = '_';
buf[pos++] = ',';
++idx;
}
if (idx == 0) {
buf[pos++] = ')';
} else {
buf[pos - 1] = ')';
}
}
break;
// xxx[_,...]
case SIGN_SUBSCRIPT:{
buf[pos++] = '[';
uint32_t idx = 0;
while (idx < sign->argNum) {
buf[pos++] = '_';
buf[pos++] = ',';
++idx;
}
if (idx == 0) {
buf[pos++] = ']';
} else {
buf[pos - 1] = ']';
}
}
break;
case SIGN_SUBSCRIPT_SETTER: {
buf[pos++] == '[';
uint32_t idx = 0;
while (idx < sign->argNum - 1) {
buf[pos++] = '_';
buf[pos++] = ',';
++idx;
}
if (idx == 0) {
buf[pos++] = ']';
} else {
buf[pos - 1] = ']';
}
buf[pos++] = '=';
buf[pos++] = '(';
buf[pos++] = '_';
buf[pos++] = ')';
}
break;
}
buf[pos] = ' ';
return pos;
}
// 定义emitLoadConstant函数用来加载常量的指令
static void emitLoadConstant() {
// 既然要加载常量, 那就应该先把源码中解析到的常量保存起来, 返回一个index, 这样再生成指令, 该指令表示加载常量, 参数就是常量在常量表中的index
index = addConstant()
write(constant, index);
}
1. 字面量: nud函数literal将id添加到表中, 生成loadConstant指令
2. 前置运算符: nud函数为单元函数(unaryOperator), 在该函数中会生成调用方法的指令
3. 中置运算符: led函数为infixOperator, 该函数中生成调用方法签名的指令
ObjFn *compileModule(VM *vm, ObjModule *objModule, const char *sourceCode) {
// 注意, 一个模块一个parser, 所以这里需要创建一个的新的parser
Parser parser;
parser.parent = vm->cur_parser;
vm->cur_parser = parser;
// 初始化parser
// 要编译就要有CompileUnit, 让cu来编译程序
CompileUnit cu;
initCompileUnit(&cu);
if (!matchNextToken(parser, TOKEN_EOF)) {
compileProgram(cu); // 在compile
}
}