【Parser系列】简易解释器

陈安

专业研究野生技术

写在前面

最近找到了一个C语言解释器 lotabout/write-a-C-interpreter ，文章手把手教你构建 C 语言编译器（0）- 前言，解释器可自举，LL1分析，Lexer/Parser/CodeGen融为一体，感觉不错，拿来修改之。

由于CPaser程序已经完善了Lexer词法分析，所以可以省略，下面就是完善语法分析和指令生成，指令的话暂时用lotabout作者的，以后可以自己设计。

运行效果如题图所示，感觉非常不错，之后我会将自己写的MemoryPool融合进去，做一个malloc的内建函数。后面会添加分段和分页，希望可以用来模拟一下操作系统。

语法分析

作者的代码是三者融为一体，其实lexer不独立开来是个大问题，一方面类型判断、数字识别会有些问题，另一方面代码会很多很复杂。

Parser的整体架构不变，参照lotabout的：

主体 void program();
表达式 void expression(operator_t level);
语句 void statement();
枚举 void enum_declaration();
函数参数 void function_parameter();
函数主体 void function_body();
函数声明 void function_declaration();
变量声明 void global_declaration();

我将他的代码中的注释做了下补充，尽量用中文说明。

代码在： https:// github.com/bajdcc/CPars er/blob/v0.2/CParser/Parser.cpp

优先级

我参照 C语言运算符的优先级和结合性一览表_C语言中文网排了一下，值越小级别越高。

int op_pred[] =
    9999, // op__start,
    1401, // op_assign,
     401, // op_plus,
     402, // op_minus,
     302, // op_times,
     301, // op_divide,
    9000, // op_escape,
    1301, // op_query,
     303, // op_mod,
     801, // op_bit_and,
    1001, // op_bit_or,
     208, // op_bit_not,
     901, // op_bit_xor,
     207, // op_logical_not,
     603, // op_less_than,
     601, // op_greater_than,
     102, // op_lparan,
     102, // op_rparan,
    9000, // op_lbrace,
    9000, // op_rbrace,
     101, // op_lsquare,
     101, // op_rsquare,
    1501, // op_comma,
     103, // op_dot,
    9000, // op_semi,
    1302, // op_colon,
     701, // op_equal,
     702, // op_not_equal,
     203, // op_plus_plus,
     204, // op_minus_minus,
    1405, // op_plus_assign,
    1406, // op_minus_assign,
    1403, // op_times_assign,
    1402, // op_div_assign,
    1409, // op_and_assign,
    1411, // op_or_assign,
    1410, // op_xor_assign,
    1404, // op_mod_assign,
     604, // op_less_than_or_equal,
     602, // op_greater_than_or_equal,
    1101, // op_logical_and,
    1201, // op_logical_or,
     104, // op_pointer,
     501, // op_left_shift,
     502, // op_right_shift,
    1407, // op_left_shift_assign,
    1408, // op_right_shift_assign,
    9000, // op_ellipsis,
    9999, // op__end
};

指令生成

原作者的指令有：

enum ins_t
    LEA, IMM, JMP, CALL, JZ, JNZ, ENT, ADJ, LEV, LI, LC, SI, SC, PUSH,
    OR, XOR, AND, EQ, NE, LT, GT, LE, GE, SHL, SHR, ADD, SUB, MUL, DIV, MOD,

第二行指令他是用来排优先级的，我没用上。第三行指令是内建函数指令。

虚拟机

指令介绍在作者文章手把手教你构建 C 语言编译器（2）- 虚拟机中。

我后面会搞个虚页，这样，程序里的指针就可以0-4G范围了，这样运行也安全。

void CGen::eval()
    // setup stack
    auto poolsize = 512;
    stack.resize(512);
    auto sp = (int *)((int)stack.data() + poolsize*LEX_SIZEOF(int));
    *--sp = -1;
    //--------------------------------------------------
    auto entry = symbols.find("main");
    if (entry == symbols.end())
        printf("main() not defined\n");
        assert(0);
    auto pc = entry->second->value._int;
    auto ax = 0;
    auto bp = (int *)0;
    auto cycle = 0;
    while (pc != -1)
        cycle++;
        auto op = text[pc++]; // get next operation code
        // print debug info
        if (false)
            printf("%03d> [%02d] %.4s", cycle, pc,
                &"LEA ,IMM ,JMP ,CALL,JZ  ,JNZ ,ENT ,ADJ ,LEV ,LI  ,LC  ,SI  ,SC  ,PUSH,"
                "OR  ,XOR ,AND ,EQ  ,NE  ,LT  ,GT  ,LE  ,GE  ,SHL ,SHR ,ADD ,SUB ,MUL ,DIV ,MOD ,"
                "OPEN,READ,CLOS,PRTF,MALC,MSET,MCMP,EXIT"[op * 5]);
            if (op <= ADJ)
                printf(" %d\n", text[pc]);
                printf("\n");
        if (op == IMM) { ax = text[pc++]; }                                     // load immediate value to ax
        else if (op == LC) { ax = *(char *)ax; }                                // load character to ax, address in ax
        else if (op == LI) { ax = *(int *)ax; }                                 // load integer to ax, address in ax
        else if (op == SC) { ax = *(char *)*sp++ = ax; }                        // save character to address, value in ax, address on stack
        else if (op == SI) { *(int *)*sp++ = ax; }                              // save integer to address, value in ax, address on stack
        else if (op == PUSH) { *--sp = ax; }                                    // push the value of ax onto the stack
        else if (op == JMP) { pc = text[pc]; }                                  // jump to the address
        else if (op == JZ) { pc = ax ? pc + 1 : text[pc]; }                     // jump if ax is zero
        else if (op == JNZ) { pc = ax ? text[pc] : pc + 1; }                    // jump if ax is zero
        else if (op == CALL) { *--sp = pc + 1; pc = text[pc]; }                 // call subroutine
                                                                                // else if (op == RET)  {pc = (int *)*sp++;}                              // return from subroutine;
        else if (op == ENT) { *--sp = (int)bp; bp = sp; sp = sp - text[pc++]; } // make new stack frame
        else if (op == ADJ) { sp = sp + text[pc++]; }                           // add esp, <size>
        else if (op == LEV) { sp = bp; bp = (int *)*sp++; pc = *sp++; }         // restore call frame and PC
        else if (op == LEA) { ax = (int)(bp + text[pc++]); }                    // load address for arguments.
        else if (op == PRF) {
            auto tmp = sp + text[pc + 1]; // 利用之后的ADJ清栈指令知道函数调用的参数个数
            ax = printf((char *)(data.data() + tmp[-1]), tmp[-2], tmp[-3], tmp[-4], tmp[-5], tmp[-6]); } // load address for arguments.
        else if (op == OR)  ax = *sp++ | ax;
        else if (op == XOR) ax = *sp++ ^ ax;
        else if (op == AND) ax = *sp++ & ax;
        else if (op == EQ)  ax = *sp++ == ax;
        else if (op == NE)  ax = *sp++ != ax;
        else if (op == LT)  ax = *sp++ < ax;
        else if (op == LE)  ax = *sp++ <= ax;
        else if (op == GT)  ax = *sp++ >  ax;
        else if (op == GE)  ax = *sp++ >= ax;
        else if (op == SHL) ax = *sp++ << ax;
        else if (op == SHR) ax = *sp++ >> ax;
        else if (op == ADD) ax = *sp++ + ax;
        else if (op == SUB) ax = *sp++ - ax;
        else if (op == MUL) ax = *sp++ * ax;
        else if (op == DIV) ax = *sp++ / ax;
        else if (op == MOD) ax = *sp++ % ax;