Dai Chao

fordring866@gmail.com | Put your faith in the Light!

Crowbar源码剖析:总体框架

Introduction

Crowbar是《自制编程语言》一书中作者自己构思的无类型语言。本书一边向读者讲述编程语言的基本要素,一边讲解具体的实现方法,可作为编译技术的入门材料。此外,书中还有一门叫做Diksam的静态类型语言,等我学完了再来写。不🐦,真的。

Crowbar

不管什么语言,本质上就是一个文本解析程序,只不过在解析的同时配上了动作的执行,此所谓词法+语法+语义。如果没有特别要求,制作一套自己的编程语言其实并非难事——要分析词法,我们有Lex;要分析语法,我们有Yacc。唯一需要独立编写的就是语义,而这也是最关键的地方。

既然是C程序,那就从main函数看起吧。读取代码文件,然后初始化一个“解释器”,用它编译、执行代码,最后回收掉解释器。真简单!

int main(int argc, char **argv) {
    CRB_Interpreter *interpreter;
    FILE *fp;

    if (argc != 2) {
        fprintf(stderr, "usage:%s filename", argv[0]);
        exit(1);
    }

    fp = fopen(argv[1], "r");
    if (fp == NULL) {
        fprintf(stderr, "%s not found.\n", argv[1]);
        exit(1);
    }

    interpreter = CRB_create_interpreter();
    CRB_compile(interpreter, fp);
    CRB_interpret(interpreter);
    CRB_dispose_interpreter(interpreter);
    MEM_dump_blocks(stdout);
    return 0;
}

Crowbar-main

简介

本层让大家看看main函数的每一步大概做了些什么事情。

Crowbar-main-CRB_create_interpreter

所谓解释器,其实就是一个数据结构,存储着程序的解析结果,并管理着自己的存储空间。它形成了一个封闭的运行环境

struct CRB_Interpreter_tag {
    MEM_Storage         interpreter_storage;
    MEM_Storage         execute_storage;
    Variable            *variable;
    FunctionDefinition  *function_list;
    StatementList       *statement_list;
    int                 current_line_number;
    Stack               stack;
    Heap                heap;
    CRB_LocalEnvironment    *top_environment;
};

还没读懂top_environment

CRB_Interpreter *CRB_create_interpreter(void) {
    MEM_Storage storage;
    CRB_Interpreter *interpreter; // 等同于CRB_Interpreter_tag*
    // 1
    storage = MEM_open_storage(0);
    interpreter = MEM_storage_malloc(storage, sizeof(struct CRB_Interpreter_tag));
    // 2
    interpreter->interpreter_storage = storage; // 注意
    interpreter->execute_storage = NULL;
    interpreter->variable = NULL;
    interpreter->function_list = NULL;
    interpreter->statement_list = NULL;
    interpreter->current_line_number = 1;
    interpreter->stack.stack_alloc_size = 0;
    interpreter->stack.stack_pointer = 0;
    interpreter->stack.stack = MEM_malloc(sizeof(CRB_Value) * STACK_ALLOC_SIZE); // 注意
    interpreter->heap.current_heap_size = 0;
    interpreter->heap.current_threshold = HEAP_THRESHOLD_SIZE; // 注意
    interpreter->heap.header = NULL;
    interpreter->top_environment = NULL;
    // 3
    crb_set_current_interpreter(interpreter);
    // 4
    add_native_functions(interpreter);
    return interpreter;
}

本函数的执行过程如下:

  1. 开一片存储空间,为解释器留出位置
  2. 初始化各种成员变量,大部分都是平凡的初始值
  3. 设置另一个包的static变量,没什么特殊的
  4. “注册”原生函数(后面说)

Crowbar-main-CRB_compile

初步的数据结构有了,开始解析代码:

void CRB_compile(CRB_Interpreter *interpreter, FILE *fp) {
    extern int yyparse(void);
    extern FILE *yyin;
    crb_set_current_interpreter(interpreter);
    yyin = fp;
    if (yyparse()) {
        fprintf(stderr, "Error ! Error ! Error !\n");
        exit(1);
    }
    crb_reset_string_literal_buffer();
}

yyparse()是整个函数的主干,由Lex和Yacc共同生成。简单来说,这个函数逐个字符读取源码,和Lex文件里的词法规则进行匹配。每匹配一次就触发一些“动作”,并可能返回一种“token”,此所谓词法分析。返回的token经过累积后(移进),又会满足Yacc文件里的语法规则(归约),于是又会据此做一些“动作”,此所谓语法分析。整个文件读完(术语叫做“one pass”,一趟),代码就解析得差不多了,解释器里的数据结构也会被填满,留待执行。

Lex和Yacc文件的具体内容,留到后面说。

Crowbar-main-CRB_interpret

现在就要真正地执行代码了。

void CRB_interpret(CRB_Interpreter *interpreter)
{
    interpreter->execute_storage = MEM_open_storage(0);
    crb_add_std_fp(interpreter);
    crb_execute_statement_list(interpreter, NULL, interpreter->statement_list);
    crb_garbage_collect(interpreter);
}

第一行,开辟一个“存储器”,后面说。

第二行,暂时说不清楚

第三行,执行解释器里的语句链表(由上一步编译生成)。该函数只是遍历链表,对每条语句调用execute_statement,而后者又根据语句的具体类型,再调用不同的处理函数execute_X_statement,其中X可以是expression, global, if, while, for, return, break, continue等种类名称。Layer-2将介绍具体的处理过程。

第四行,垃圾回收,后面说。

Crowbar-main-CRB_dispose_interpreter

垃圾回收,内存释放等等,在进一步了解Crowbar的内存管理机制之前不好说细。其实我也没有完全搞懂,且写且珍惜。

Crowbar-main-MEM_dump_blocks

debug用,打印各个内存块的状态,省略了。

后续

刚才我对Crowbar的代码树进行了BFS,介绍了最简要的框架。接下来我将适当采取DFS,分几篇文章把每个模块的实现讲透彻,也让自己铭记于心。

国庆即将结束,进度依然捉急。工作日到来后,学习时间将大幅缩水,但这系列我绝对不🐦。真的。

GTMD实习!