C++实现编译器(6): 字节码与虚拟机¶

参照《Writing An Interpreter/Compiler In Go》，改用C++实现。

项目源码: https://github.com/LeslieZhu/monkey-cpp

引言¶

本篇对应的源码位于目录: src/05/

src
 |05
 | |token
 | | |token.hpp
 | |evaluator
 | | |evaluator.hpp
 | | |builtins.hpp
 | |CMakeLists.txt
 | |test
 | | |lexer_test.hpp
 | | |parser_test.hpp
 | | |evaluator_test.hpp
 | | |vm_test.hpp
 | | |objects_test.hpp
 | | |ast_test.hpp
 | | |code_test.hpp
 | | |compiler_test.hpp
 | | |main.cpp
 | |lexer
 | | |lexer.hpp
 | |repl
 | | |repl.hpp
 | |code
 | | |code.hpp
 | |objects
 | | |objects.hpp
 | | |environment.hpp
 | |parser
 | | |parser.hpp
 | | |parser_tracing.hpp
 | |vm
 | | |vm.hpp
 | |ast
 | | |ast.hpp
 | |main
 | | |monkey.cpp
 | |compiler
 | | |compiler.hpp

为了提高性能和移植性，在前面树遍历解释器基础上，引入虚拟机和字节码。

为了在代码结构和接口形式上都尽量保持和原有Go语言代码相近，多花了一些时间，因为Go原生带有切片、字节序大小端读写等封装好的功能，而在C++就需要自己去组装这些工具。

目前进度为止，虚拟机只支持通过字节码进行整数的加法操作。

编译器与虚拟机(vm)¶

由词法分析器、语法分析器对源代码进行标记和语法分析后，将源代码转换成AST，这个过程叫做前端。

之后，会有优化器将AST翻译成一种中间表示(IR)。

最后，由代码生成器生成目标语言代码，这个过程叫后端。

简而言之，编译器获取一种语言的源代码并转换成另一种语言的源代码，又叫翻译器。

虚拟机(vm)跟物理机一样，有特定的运行循环，即通过循环执行取值-解码-执行来完成运转，这个周期称之为指令周期；有一个程序计数器，可以获取指令，然后解析并执行。

虚拟机拥有栈，可以分为栈式虚拟机和寄存器式虚拟机，前者易于构建，后者则速度更快。

这里将采用基于虚拟调用栈的虚拟机，在此虚拟机中执行自定义的字节码。

大小端字节序¶

enum class BinaryEndianType
{
    SMALLENDIAN = 1,
    BIGENDIAN,
};

BinaryEndianType BinaryEndian()
{
    int iVal = 0xFFFE; // 65534
    unsigned char *p = (unsigned char *)(&iVal);
    if (p[0] == 0xFF)
    {
        return BinaryEndianType::BIGENDIAN;
    }
    return BinaryEndianType::SMALLENDIAN;
}

这里设计的字节码规定使用大端字节序。

字节码¶

因为所有指令的操作码大小都是一个字节，因此得名字节码。

using Opcode = uint8_t;
using Instructions = std::vector<Opcode>;

enum class OpcodeType : Opcode
{
    OpConstant = 1,
    OpAdd,
};

操作码只需要1个字节，这里使用uint8_t来作为其类型，等同于Go语言里面的byte类型，本质上就是C语言里面的unsigned char类型。

对于整个字节码本身来说，使用一个vector<uint8_t>这样一块连续内存空间表示，为了获得更好的类型支持，添加了一个枚举类OpcodeType，继承了uint8_t以便后续方便的转换。

对于存储字节码的这段连续内存，使用两个辅助函数来读取和写入2个字节的数字，即uint16_t类型:

void ReadUint16(Instructions &ins, int offset, uint16_t& uint16Value)
{
    memcpy(&uint16Value, (unsigned char*)(&ins[offset]), sizeof(uint16Value));

    if(bytecode::BinaryEndian() == bytecode::BinaryEndianType::SMALLENDIAN) // from BIGENDIAN
    {
        unsigned char *p = (unsigned char *)&uint16Value;
        unsigned char tmp = *(&p[0]);
        p[0] = p[1];
        p[1] = tmp;
    }
}

void WriteUint16(Instructions &ins, int offset, uint16_t& uint16Value)
{
    if(bytecode::BinaryEndian() == bytecode::BinaryEndianType::SMALLENDIAN) // to BIGENDIAN
    {
        unsigned char *p = (unsigned char *)&uint16Value;
        unsigned char tmp = *(&p[0]);
        p[0] = p[1];
        p[1] = tmp;
    }
    memcpy(&ins[offset], (unsigned char *)(&uint16Value), sizeof(uint16Value));
}

操作码定义¶

struct Definition
{
    std::string Name;
    std::vector<int> OperandWidths;

    Definition(const std::string &name) : Name(name) {}
    Definition(const std::string &name, const int &width) : Name(name) { OperandWidths.push_back(width); }
    ~Definition() { OperandWidths.clear(); }
};

static const std::map<OpcodeType, std::shared_ptr<Definition>> definitions{
    {OpcodeType::OpConstant, std::make_shared<Definition>("OpConstant", 2)},
    {OpcodeType::OpAdd, std::make_shared<Definition>("OpAdd")},
};

std::shared_ptr<Definition> Lookup(OpcodeType op){
    auto fit = definitions.find(op);
    if(fit == definitions.end())
    {
        return nullptr;
    }
    return fit->second;
}

每个操作码包含这几个信息：操作码名字、操作参数宽度。比如定义变量操作码OpConstant它包含一个参数，这个参数是2，即用2个字节来存储变量的值；而OpAdd操作码表示相加操作，它不需要读取参数，而是后续通过虚拟调用栈进行出栈操作。

生成字节码与反汇编¶

std::vector<Opcode> Make(OpcodeType op, std::vector<int> operands)
{
    auto def = Lookup(op);
    if(def == nullptr)
    {
        return std::vector<Opcode>{};
    }

    int instructionLen = 1;
    for(auto &w: def->OperandWidths)
    {
        instructionLen += w;
    }

    std::vector<Opcode> instruction = std::vector<Opcode>(instructionLen);
    instruction[0] = static_cast<Opcode>(op);

    int offset = 1;
    for(unsigned long i=0; i < operands.size(); i++)
    {
        auto width = def->OperandWidths[i];
        switch(width)
        {
            case 2:
                uint16_t uint16Value = static_cast<uint16_t>(operands[i]);
                WriteUint16(instruction, offset, uint16Value);
                break;
        }
        offset += width;
    }

    return instruction;
}

这个辅助函数Make根据每个操作码的定义，将参数的值以规定好的字节长度变成大端字节序形式。

对应的将字节码读取进来变成虚拟机中可以识别的形式，相等于反汇编角色:

std::pair<std::vector<int>, int> ReadOperands(std::shared_ptr<Definition> def, Instructions &ins, int pos)
{
    int size = def->OperandWidths.size();
    std::vector<int> operands(size);
    int offset = 0;

    for (int i = 0; i < size; i++)
    {
        auto width = def->OperandWidths[i];
        switch(width)
        {
            case 2:
                {
                    uint16_t uint16Value;
                    ReadUint16(ins, pos, uint16Value);
                    operands[i] = static_cast<int>(uint16Value);
                }
                break;
        }

        offset += width;
    }

    return std::make_pair(operands, offset);
}

方法类似，根据操作码定义好的宽度读取一定数量的字节变成整数类型，即反汇编了字节码。

最小编译器¶

字节码对象的表示形式:

struct ByteCode {
    bytecode::Instructions Instructions;
    std::vector<std::shared_ptr<objects::Object>> Constants;

    ByteCode(bytecode::Instructions &instructions,
             std::vector<std::shared_ptr<objects::Object>> &constants) : Instructions(instructions),
                                                                         Constants(constants)
    {
    }
};

因为目前字节码只支持常量，因此它的定义就是一个连续内存地址表示字节码内容，然后各个Object组成一个向量，这样在字节码里面只需要存储对应常量的位置索引即可。

定义最小的编译器:

struct Compiler
{
    bytecode::Instructions instructions;
    std::vector<std::shared_ptr<objects::Object>> constants;

    Compiler(){}

    std::shared_ptr<objects::Error> Compile([[maybe_unused]] std::shared_ptr<ast::Node> node)
    {
        return nullptr;
    }

    std::shared_ptr<ByteCode> Bytecode()
    {
        return std::make_shared<ByteCode>(instructions, constants);
    }
};

这个编译器做的事情是从AST根节点开始编译成字节码形式，目前它不支持任何操作，只有一个基本框架。

编译AST¶

std::shared_ptr<objects::Error> Compile([[maybe_unused]] std::shared_ptr<ast::Node> node)
{
    if(node->GetNodeType() == ast::NodeType::Program)
    {
        std::shared_ptr<ast::Program> program = std::dynamic_pointer_cast<ast::Program>(node);
        for(auto &stmt: program->v_pStatements)
        {
            auto resultObj = Compile(stmt);
            if(evaluator::isError(resultObj))
            {
                return resultObj;
            }
        }
    }
    else if(node->GetNodeType() == ast::NodeType::ExpressionStatement)
    {
        std::shared_ptr<ast::ExpressionStatement> exprStmt = std::dynamic_pointer_cast<ast::ExpressionStatement>(node);

        auto resultObj = Compile(exprStmt->pExpression);
        if (evaluator::isError(resultObj))
        {
            return resultObj;
        }
    }
    else if(node->GetNodeType() == ast::NodeType::InfixExpression)
    {
        std::shared_ptr<ast::InfixExpression> infixObj = std::dynamic_pointer_cast<ast::InfixExpression>(node);

        auto resultObj = Compile(infixObj->pLeft);
        if (evaluator::isError(resultObj))
        {
            return resultObj;
        }

        resultObj = Compile(infixObj->pRight);
        if (evaluator::isError(resultObj))
        {
            return resultObj;
        }

        if (infixObj->Operator == "+")
        {
            emit(bytecode::OpcodeType::OpAdd, {});
        } 
        else {
            return evaluator::newError("unknow operator: " + infixObj->Operator);
        }
    }
    else if(node->GetNodeType() == ast::NodeType::IntegerLiteral)
    {
        std::shared_ptr<ast::IntegerLiteral> integerLiteral = std::dynamic_pointer_cast<ast::IntegerLiteral>(node);
        auto integerObj = std::make_shared<objects::Integer>(integerLiteral->Value);
        auto pos = addConstant(integerObj);
        emit(bytecode::OpcodeType::OpConstant, {pos});
    }

    return nullptr;
}

这个和之前解释执行根节点类似，只是它使用两个辅助函数来记录当前常量的位置索引，然后把这个索引信息写入到字节码中，以便反汇编时候快速获取常量值:

int addConstant(std::shared_ptr<objects::Object> obj)
{
    constants.push_back(obj);
    return (constants.size() - 1);
}

int emit(bytecode::OpcodeType op, std::vector<int> operands)
{
    auto ins = bytecode::Make(op, operands);
    auto pos = addInstruction(ins);
    return pos;
}

int addInstruction(bytecode::Instructions ins)
{
    auto posNewInstruction = instructions.size();

    instructions.insert(instructions.end(), ins.begin(), ins.end());
    return posNewInstruction;
}

虚拟调用栈¶

通过虚拟调用栈来完成指令的读取-解码-执行循环，使用了一个微型虚拟机:

struct VM{
    std::vector<std::shared_ptr<objects::Object>> constants;
    bytecode::Instructions instructions;

    std::vector<std::shared_ptr<objects::Object>> stack;
    int sp; // 始终指向调用栈的下一个空闲位置，栈顶的值是stack[sp-1]

    VM(std::vector<std::shared_ptr<objects::Object>>& objs, bytecode::Instructions& ins):
    constants(objs),
    instructions(ins)
    {
        stack.resize(StackSize);
        sp = 0;
    }
};

std::shared_ptr<VM> New(std::shared_ptr<compiler::ByteCode> bytecode)
{
    return std::make_shared<VM>(bytecode->Constants, bytecode->Instructions);
}

在调用栈上只有压栈、出栈、获取栈顶几个操作:

std::shared_ptr<objects::Object> StackTop()
{
    if(sp == 0)
    {
        return nullptr;
    }

    return stack[sp - 1];
}

std::shared_ptr<objects::Object> Push(std::shared_ptr<objects::Object> obj)
{
    if(sp > StackSize)
    {
        return evaluator::newError("stack overflow");
    }

    stack[sp] = obj;
    sp += 1;

    return nullptr;
}

std::shared_ptr<objects::Object> Pop()
{
    auto obj = stack[sp - 1];
    sp -= 1;

    return obj;
}

调用栈执行加法运算¶

让调用栈执行起来，不断进入读取-解码-执行循环:

std::shared_ptr<objects::Object> Run()
{
    int size = instructions.size();
    for(int ip=0; ip < size; ip++)
    {
        bytecode::OpcodeType op = static_cast<bytecode::OpcodeType>(instructions[ip]);

        switch(op)
        {
            case bytecode::OpcodeType::OpConstant:
                {
                    uint16_t constIndex;
                    bytecode::ReadUint16(instructions, ip+1, constIndex);
                    ip += 2;
                    auto result = Push(constants[constIndex]);
                    if(evaluator::isError(result))
                    {
                        return result;
                    }
                }
                break;
            case bytecode::OpcodeType::OpAdd:
                {
                    auto right = Pop();
                    auto left = Pop();
                    auto rightObj = std::dynamic_pointer_cast<objects::Integer>(right);
                    auto leftObj = std::dynamic_pointer_cast<objects::Integer>(left);
                    auto result = leftObj->Value + rightObj->Value;
                    Push(std::make_shared<objects::Integer>(result));
                }
                break;
        }
    }

    return nullptr;
}

为了执行速度，没有继续调用Lookup来反复查找，而是直接使用规定好的字节宽度等信息。

REPL¶

Hello lesliezhu! This is the Monkey-CPP programming language!
Feel free to type in commands
>> 1+2+3+4
10
>> 1+2;3+4;5+6
11
>>
>> /2

   .--.  .-"     "-.  .--.
  / .. \/  .-. .-.  \/ .. \
 | |  '|  /   Y   \  |'  | |
 | \   \  \ 0 | 0 /  /   / |
  \ '- ,\.-"""""""-./, -' /
   ''-' /_   ^ ^   _\ '-''
       |  \._   _./  |
       \   \ '~' /   /
        '._ '-=-' _.'
           '-----'

Woops! We ran into some monkey business here!
 parser errors:
    no prefix parse function for / found
>>

测试用例¶

全部通过测试用例:

[==========] Running 45 tests from 45 test suites.
[----------] Global test environment set-up.
[----------] 1 test from TestNextToken
[ RUN      ] TestNextToken.BasicAssertions
[       OK ] TestNextToken.BasicAssertions (0 ms)
[----------] 1 test from TestNextToken (0 ms total)

......

[----------] 1 test from testVMIntegerArithmetic
[ RUN      ] testVMIntegerArithmetic.basicTest
[       OK ] testVMIntegerArithmetic.basicTest (0 ms)
[----------] 1 test from testVMIntegerArithmetic (0 ms total)

[----------] Global test environment tear-down
[==========] 45 tests from 45 test suites ran. (23 ms total)
[  PASSED  ] 45 tests.

总结¶

理解了字节码的本质就是一段连续内存地址，然后按照约定好的操作码信息反汇编回来，通过虚拟调用栈来执行；目前只支持整数的加法运算，后续进行添加其它类型的支持。

本文作者：「吴羽舒(LeslieZhu) 」创作于Saturday, December 10, 2022，共2332字，需要12分钟阅读时间
微信搜索： 「 MinYiLife 」, 关注公众号!
本文链接： https://www.lesliezhu.com/blog/2022/12/10/writing_an_interpreter_in_cpp_6/
版权声明： 原创文章，如需转载请注明文章作者和出处。谢谢！