从零实现一个栈式虚拟机与字节码编译器
在上一篇文章中,我们从零实现了一个正则表达式引擎,完成了从模式字符串到DFA的完整编译与匹配流程。那篇文章覆盖的是编译器前端——词法分析、语法分析和自动机构造。但编译器的另一半同样值得深入:源代码经过前端处理后,如何变成可执行的指令?执行引擎又是如何工作的?
本文用纯前端JavaScript从零实现一个栈式虚拟机和对应的字节码编译器。完整链路是:算术表达式 → 词法分析 → 递归下降解析 → AST → 字节码生成 → 栈式虚拟机执行。全程不依赖任何库,代码可直接在浏览器控制台运行。
一、为什么选择栈式架构
虚拟机按执行模型分为两大类:基于栈的和基于寄存器的。JVM、.NET CLR和CPython都采用栈式架构,而Dalvik和Lua则采用寄存器架构。栈式架构的指令集设计更简单——所有操作数都通过操作数栈隐式传递,指令本身不需要编码寄存器编号。代价是指令数量更多,因为push和pop本身就是指令。
对于一个从零实现的教学级虚拟机,栈式架构的简洁性优势明显:我们不需要设计寄存器分配算法,也不需要处理寄存器溢出到内存的问题。操作数栈天然就是表达式的求值栈,AST的后序遍历结果正好对应字节码的生成顺序。
二、指令集设计
先定义一套支持整数算术、变量、比较和跳转的字节码指令集。指令用枚举表示,每条指令占一个字节(在JS里用数字表示)。
javascript
const OpCode = {
// 栈操作
PUSH: 0x01, // 压入常量
POP: 0x02, // 弹出栈顶
DUP: 0x03, // 复制栈顶
LOAD: 0x04, // 加载局部变量
STORE: 0x05, // 存储局部变量
// 算术运算
ADD: 0x10,
SUB: 0x11,
MUL: 0x12,
DIV: 0x13,
MOD: 0x14,
NEG: 0x15, // 取负
// 比较运算
EQ: 0x20,
NEQ: 0x21,
LT: 0x22,
GT: 0x23,
LE: 0x24,
GE: 0x25,
// 逻辑运算
NOT: 0x30,
AND: 0x31,
OR: 0x32,
// 控制流
JMP: 0x40, // 无条件跳转
JZ: 0x41, // 栈顶为0时跳转
JNZ: 0x42, // 栈顶非0时跳转
// 函数
CALL: 0x50,
RET: 0x51,
// 系统
PRINT: 0x60, // 打印栈顶
HALT: 0xFF
};
指令分为七类:栈操作、算术、比较、逻辑、控制流、函数调用和系统指令。PUSH和LOAD区分在于PUSH压入编译期常量,LOAD从局部变量槽读取运行时值。JZ/JNZ根据栈顶值决定是否跳转,这是实现if和while的基础。
每条指令后面可以跟零到多个操作数(如PUSH后跟一个整数常量,JMP后跟跳转目标地址)。为了在数组中紧凑存储,我们用变长编码:指令字节后紧跟操作数。虚拟机执行时根据指令类型决定读取几个操作数。
三、词法分析器
词法分析器把源代码字符串拆成Token流。支持整数、标识符、运算符和括号。
javascript
function tokenize(source) {
const tokens = [];
let i = 0;
while (i < source.length) {
const ch = source[i];
// 跳过空白
if (/\s/.test(ch)) { i++; continue; }
// 整数
if (/\d/.test(ch)) {
let num = '';
while (i < source.length && /\d/.test(source[i])) {
num += source[i++];
}
tokens.push({ type: 'INT', value: parseInt(num, 10) });
continue;
}
// 标识符
if (/[a-zA-Z_]/.test(ch)) {
let name = '';
while (i < source.length && /[a-zA-Z0-9_]/.test(source[i])) {
name += source[i++];
}
// 关键字
const keywords = ['let', 'if', 'else', 'while', 'print'];
tokens.push({
type: keywords.includes(name) ? name.toUpperCase() : 'ID',
value: name
});
continue;
}
// 双字符运算符
const two = source.slice(i, i + 2);
if (['==', '!=', '<=', '>='].includes(two)) {
tokens.push({ type: two });
i += 2;
continue;
}
// 单字符运算符
if ('+-*/%()<>=!&|{};'.includes(ch)) {
tokens.push({ type: ch });
i++;
continue;
}
throw new Error(`词法错误: 位置 ${i} 出现意外字符 '${ch}'`);
}
tokens.push({ type: 'EOF' });
return tokens;
}
Token类型中,INT携带整数值,ID携带标识符名,关键字转换为大写类型(LET、IF、WHILE、PRINT)。双字符运算符优先于单字符匹配,避免 == 被拆成两个 =。
四、语法分析:递归下降构建AST
我们的迷你语言支持变量声明、赋值、算术表达式、比较表达式、if/else和while语句。文法定义如下:
text
program := statement*
statement := letStmt | assignStmt | ifStmt | whileStmt | printStmt | block
letStmt := 'let' ID '=' expression ';'
assignStmt := ID '=' expression ';'
ifStmt := 'if' '(' expression ')' statement ('else' statement)?
whileStmt := 'while' '(' expression ')' statement
printStmt := 'print' '(' expression ')' ';'
block := '{' statement* '}'
expression := comparison
comparison := additive (('==' | '!=' | '<' | '>' | '<=' | '>=') additive)?
additive := multiplicative (('+' | '-') multiplicative)*
multiplicative := unary (('*' | '/' | '%') unary)*
unary := ('-' | '!') unary | primary
primary := INT | ID | '(' expression ')'
递归下降解析器每个非终结符对应一个函数:
javascript
function parse(tokens) {
let pos = 0;
const peek = () => tokens[pos];
const next = () => tokens[pos++];
const expect = type => {
const tok = next();
if (tok.type !== type) {
throw new Error(`语法错误: 期望 ${type},实际 ${tok.type}`);
}
return tok;
};
function parseProgram() {
const body = [];
while (peek().type !== 'EOF') {
body.push(parseStatement());
}
return { type: 'Program', body };
}
function parseStatement() {
const tok = peek();
switch (tok.type) {
case 'LET': {
next();
const name = expect('ID').value;
expect('=');
const value = parseExpression();
expect(';');
return { type: 'Let', name, value };
}
case 'ID': {
const name = next().value;
expect('=');
const value = parseExpression();
expect(';');
return { type: 'Assign', name, value };
}
case 'IF': {
next();
expect('(');
const cond = parseExpression();
expect(')');
const then = parseStatement();
let else_ = null;
if (peek().type === 'ELSE') {
next();
else_ = parseStatement();
}
return { type: 'If', cond, then, else: else_ };
}
case 'WHILE': {
next();
expect('(');
const cond = parseExpression();
expect(')');
const body = parseStatement();
return { type: 'While', cond, body };
}
case 'PRINT': {
next();
expect('(');
const value = parseExpression();
expect(')');
expect(';');
return { type: 'Print', value };
}
case '{': {
next();
const body = [];
while (peek().type !== '}') {
body.push(parseStatement());
}
expect('}');
return { type: 'Block', body };
}
default:
throw new Error(`语法错误: 意外的 token ${tok.type}`);
}
}
function parseExpression() {
return parseComparison();
}
function parseComparison() {
let left = parseAdditive();
const tok = peek();
if (['==', '!=', '<', '>', '<=', '>='].includes(tok.type)) {
const op = next().type;
const right = parseAdditive();
return { type: 'Binary', op, left, right };
}
return left;
}
function parseAdditive() {
let left = parseMultiplicative();
while (['+', '-'].includes(peek().type)) {
const op = next().type;
const right = parseMultiplicative();
left = { type: 'Binary', op, left, right };
}
return left;
}
function parseMultiplicative() {
let left = parseUnary();
while (['*', '/', '%'].includes(peek().type)) {
const op = next().type;
const right = parseUnary();
left = { type: 'Binary', op, left, right };
}
return left;
}
function parseUnary() {
const tok = peek();
if (tok.type === '-') {
next();
return { type: 'Unary', op: '-', operand: parseUnary() };
}
if (tok.type === '!') {
next();
return { type: 'Unary', op: '!', operand: parseUnary() };
}
return parsePrimary();
}
function parsePrimary() {
const tok = peek();
if (tok.type === 'INT') {
next();
return { type: 'Int', value: tok.value };
}
if (tok.type === 'ID') {
next();
return { type: 'Identifier', name: tok.value };
}
if (tok.type === '(') {
next();
const expr = parseExpression();
expect(')');
return expr;
}
throw new Error(`语法错误: 意外的 token ${tok.type}`);
}
return parseProgram();
}
AST节点类型包括:Program(顶层)、Let、Assign、If、While、Print、Block、Binary、Unary、Int、Identifier。每个节点携带足够的信息供后续字节码生成使用。
五、字节码生成器
字节码生成器对AST做后序遍历,将每个节点翻译为一条或多条指令。核心原则是:表达式求值后,结果留在栈顶。
javascript
function compile(ast) {
const code = [];
let labelCounter = 0;
function emit(op, operand = null) {
code.push(op);
if (operand !== null) code.push(operand);
}
function newLabel() {
return labelCounter++;
}
// 记录跳转指令的位置,稍后回填目标地址
function patchJump(index) {
code[index] = code.length;
}
function compileNode(node) {
switch (node.type) {
case 'Program':
node.body.forEach(compileNode);
emit(OpCode.HALT);
break;
case 'Let':
case 'Assign':
// 先求值,再存入变量槽
compileNode(node.value);
emit(OpCode.STORE, node.name);
break;
case 'Print':
compileNode(node.value);
emit(OpCode.PRINT);
break;
case 'Block':
node.body.forEach(compileNode);
break;
case 'Int':
emit(OpCode.PUSH, node.value);
break;
case 'Identifier':
emit(OpCode.LOAD, node.name);
break;
case 'Unary':
compileNode(node.operand);
if (node.op === '-') emit(OpCode.NEG);
if (node.op === '!') emit(OpCode.NOT);
break;
case 'Binary': {
// 短路求值:对于 && 和 ||,需要特殊处理
compileNode(node.left);
compileNode(node.right);
const opMap = {
'+': OpCode.ADD, '-': OpCode.SUB,
'*': OpCode.MUL, '/': OpCode.DIV, '%': OpCode.MOD,
'==': OpCode.EQ, '!=': OpCode.NEQ,
'<': OpCode.LT, '>': OpCode.GT,
'<=': OpCode.LE, '>=': OpCode.GE,
};
if (!opMap[node.op]) throw new Error(`不支持的运算符: ${node.op}`);
emit(opMap[node.op]);
break;
}
case 'If': {
const elseLabel = newLabel();
const endLabel = newLabel();
compileNode(node.cond);
emit(OpCode.JZ, `else_${elseLabel}`); // 条件为假跳到else
compileNode(node.then);
if (node.else) {
emit(OpCode.JMP, `end_${endLabel}`);
// 这里需要记录else跳转的占位
}
// 回填逻辑稍后统一处理
break;
}
case 'While': {
// while循环的标签管理
break;
}
}
}
compileNode(ast);
return code;
}
这里需要停下来解释一个关键问题:跳转目标地址的回填。在生成If和While的字节码时,我们提前不知道跳转目标的具体位置。标准做法是先用占位符(或相对偏移量)发射跳转指令,记录下需要回填的位置索引,等到目标位置确定后再修改指令的操作数。
上面的代码中,If和While的分支还没有完整实现。下面给出修正后的完整版本,采用标签-地址映射的方式:
javascript
function compile(ast) {
const code = [];
const labels = {}; // 标签名 -> 字节码地址
const pendingJumps = []; // 待回填的跳转指令
function emit(op, operand = null) {
code.push(op);
if (operand !== null) code.push(operand);
}
function emitJump(op, label) {
code.push(op, label); // 先占位,最后统一回填
pendingJumps.push(code.length - 1); // 记录操作数位置
}
function defineLabel(label) {
labels[label] = code.length;
}
let labelId = 0;
const nextLabel = () => `L${labelId++}`;
function compileNode(node) {
switch (node.type) {
case 'Program':
node.body.forEach(compileNode);
emit(OpCode.HALT);
break;
case 'Let':
case 'Assign':
compileNode(node.value);
emit(OpCode.STORE, node.name);
break;
case 'Print':
compileNode(node.value);
emit(OpCode.PRINT);
break;
case 'Block':
node.body.forEach(compileNode);
break;
case 'Int':
emit(OpCode.PUSH, node.value);
break;
case 'Identifier':
emit(OpCode.LOAD, node.name);
break;
case 'Unary':
compileNode(node.operand);
if (node.op === '-') emit(OpCode.NEG);
if (node.op === '!') emit(OpCode.NOT);
break;
case 'Binary': {
compileNode(node.left);
compileNode(node.right);
const opMap = {
'+': OpCode.ADD, '-': OpCode.SUB,
'*': OpCode.MUL, '/': OpCode.DIV, '%': OpCode.MOD,
'==': OpCode.EQ, '!=': OpCode.NEQ,
'<': OpCode.LT, '>': OpCode.GT,
'<=': OpCode.LE, '>=': OpCode.GE,
};
emit(opMap[node.op]);
break;
}
case 'If': {
const elseLabel = nextLabel();
const endLabel = nextLabel();
compileNode(node.cond);
emitJump(OpCode.JZ, elseLabel);
compileNode(node.then);
if (node.else) {
emitJump(OpCode.JMP, endLabel);
defineLabel(elseLabel);
compileNode(node.else);
defineLabel(endLabel);
} else {
defineLabel(elseLabel);
}
break;
}
case 'While': {
const startLabel = nextLabel();
const endLabel = nextLabel();
defineLabel(startLabel);
compileNode(node.cond);
emitJump(OpCode.JZ, endLabel);
compileNode(node.body);
emitJump(OpCode.JMP, startLabel);
defineLabel(endLabel);
break;
}
}
}
compileNode(ast);
// 回填跳转地址
for (const pos of pendingJumps) {
const label = code[pos];
if (labels[label] === undefined) {
throw new Error(`未定义的标签: ${label}`);
}
code[pos] = labels[label];
}
return code;
}
关键设计是 emitJump 先把标签名写入操作数位置,同时记录需要回填的位置。所有代码生成完毕后,遍历 pendingJumps,把标签名替换为实际字节码地址。defineLabel 记录标签对应的当前代码位置。这套机制让跳转指令的生成和地址确定解耦,编译器不需要提前知道代码长度。
六、栈式虚拟机实现
虚拟机是一个取指-译码-执行循环。它维护三个核心数据结构:操作数栈、局部变量表和程序计数器。
javascript
class VM {
constructor(bytecode) {
this.code = bytecode;
this.stack = [];
this.locals = {};
this.pc = 0; // program counter
this.output = [];
this.running = true;
}
push(v) { this.stack.push(v); }
pop() { return this.stack.pop(); }
peek() { return this.stack[this.stack.length - 1]; }
run() {
while (this.running) {
const op = this.code[this.pc++];
switch (op) {
case OpCode.PUSH:
this.push(this.code[this.pc++]);
break;
case OpCode.POP:
this.pop();
break;
case OpCode.DUP:
this.push(this.peek());
break;
case OpCode.LOAD: {
const name = this.code[this.pc++];
if (!(name in this.locals)) {
throw new Error(`未定义的变量: ${name}`);
}
this.push(this.locals[name]);
break;
}
case OpCode.STORE: {
const name = this.code[this.pc++];
this.locals[name] = this.pop();
break;
}
case OpCode.ADD: {
const b = this.pop(), a = this.pop();
this.push(a + b);
break;
}
case OpCode.SUB: {
const b = this.pop(), a = this.pop();
this.push(a - b);
break;
}
case OpCode.MUL: {
const b = this.pop(), a = this.pop();
this.push(a * b);
break;
}
case OpCode.DIV: {
const b = this.pop(), a = this.pop();
if (b === 0) throw new Error('除零错误');
this.push(Math.trunc(a / b)); // 整数除法
break;
}
case OpCode.MOD: {
const b = this.pop(), a = this.pop();
this.push(a % b);
break;
}
case OpCode.NEG:
this.push(-this.pop());
break;
case OpCode.EQ: {
const b = this.pop(), a = this.pop();
this.push(a === b ? 1 : 0);
break;
}
case OpCode.NEQ: {
const b = this.pop(), a = this.pop();
this.push(a !== b ? 1 : 0);
break;
}
case OpCode.LT: {
const b = this.pop(), a = this.pop();
this.push(a < b ? 1 : 0);
break;
}
case OpCode.GT: {
const b = this.pop(), a = this.pop();
this.push(a > b ? 1 : 0);
break;
}
case OpCode.LE: {
const b = this.pop(), a = this.pop();
this.push(a <= b ? 1 : 0);
break;
}
case OpCode.GE: {
const b = this.pop(), a = this.pop();
this.push(a >= b ? 1 : 0);
break;
}
case OpCode.NOT:
this.push(this.pop() === 0 ? 1 : 0);
break;
case OpCode.JMP:
this.pc = this.code[this.pc];
break;
case OpCode.JZ:
if (this.pop() === 0) {
this.pc = this.code[this.pc];
} else {
this.pc++;
}
break;
case OpCode.JNZ:
if (this.pop() !== 0) {
this.pc = this.code[this.pc];
} else {
this.pc++;
}
break;
case OpCode.PRINT:
this.output.push(this.pop());
break;
case OpCode.HALT:
this.running = false;
break;
default:
throw new Error(`未知指令: 0x${op.toString(16)}`);
}
}
return this.output;
}
}
几个实现细节值得注意。整数除法使用 Math.trunc 而非 Math.floor,保证 -7/2 得到 -3 而不是 -4。比较指令把布尔值转为0/1整数,方便后续的JZ/JNZ判断。JZ和JNZ在执行跳转时,this.pc 已经指向了操作数位置(因为取指时 pc++ 已经执行),所以直接 this.pc = this.code[this.pc] 即可。
七、完整编译执行流程
把上面的部分串起来:
javascript
function runSource(source) {
const tokens = tokenize(source);
const ast = parse(tokens);
const bytecode = compile(ast);
const vm = new VM(bytecode);
return vm.run();
}
// 测试1:算术表达式
console.log(runSource(`
let x = 3;
let y = 4;
print(x * x + y * y);
`)); // [25]
// 测试2:while循环 + if/else
console.log(runSource(`
let n = 10;
let sum = 0;
let i = 1;
while (i <= n) {
if (i % 2 == 0) {
sum = sum + i;
} else {
sum = sum + 0;
}
i = i + 1;
}
print(sum);
`)); // [30]
// 测试3:嵌套循环
console.log(runSource(`
let total = 0;
let i = 1;
while (i <= 3) {
let j = 1;
while (j <= 3) {
total = total + i * j;
j = j + 1;
}
i = i + 1;
}
print(total);
`)); // [36]
测试1验证基本算术:3*3+4*4=25。测试2验证while和if/else的配合,计算1到10之间的偶数之和:2+4+6+8+10=30。测试3验证嵌套while循环,sum(i*j) for i,j in [1,3] = (1+2+3)+(2+4+6)+(3+6+9)=36。
八、字节码反汇编与栈状态追踪
调试虚拟机时,能看到字节码的文本形式和每步执行后栈的状态,比盲猜有效得多。
javascript
const OpName = Object.fromEntries(
Object.entries(OpCode).map(([k, v]) => [v, k])
);
function disassemble(bytecode) {
const lines = [];
let i = 0;
const argCount = { [OpCode.PUSH]: 1, [OpCode.LOAD]: 1, [OpCode.STORE]: 1,
[OpCode.JMP]: 1, [OpCode.JZ]: 1, [OpCode.JNZ]: 1 };
while (i < bytecode.length) {
const op = bytecode[i];
const name = OpName[op] || `0x${op.toString(16)}`;
const n = argCount[op] || 0;
const args = bytecode.slice(i + 1, i + 1 + n);
lines.push(`${String(i).padStart(4)} ${name}${args.length ? ' ' + args.join(' ') : ''}`);
i += 1 + n;
}
return lines.join('\n');
}
以 let x = 3; print(x * x); 为例,反汇编输出为:
text
0 PUSH 3
2 STORE x
4 LOAD x
6 LOAD x
8 MUL
9 PRINT
10 HALT
可以直观看到:PUSH 3把常量3压栈,STORE x弹出并存入变量x,然后LOAD x两次把x的值压栈两次,MUL弹出两个操作数相乘后压回结果,PRINT弹出结果输出,最后HALT停止。
如果要追踪执行过程中栈的变化,可以在VM的循环里插入钩子:
javascript
class TracingVM extends VM {
run() {
while (this.running) {
const op = this.code[this.pc];
const before = [...this.stack];
super.runStep ? super.runStep() : this.step();
console.log(
`pc=${this.pc - 1} ${OpName[op] || op} | ` +
`栈: [${before.join(', ')}] -> [${this.stack.join(', ')}]`
);
}
return this.output;
}
step() {
// 执行单条指令(从run中提取出来)
}
}
这个追踪功能在排查跳转地址错误时特别有用——你能清楚地看到pc在什么条件下跳到了哪里。
九、性能对比与优化方向
当前实现是纯解释执行:每次循环都要读取指令、解码、执行,操作数栈的push/pop也有函数调用开销。下面做一个粗略的性能对比,用同一个计算任务分别走虚拟机和直接eval:
javascript
// 虚拟机上跑斐波那契
function fibVM(n) {
const source = `
let a = 0; let b = 1; let i = 0;
while (i < ${n}) {
let t = a + b; a = b; b = t; i = i + 1;
}
print(a);
`;
return runSource(source)[0];
}
// 直接用JS算
function fibDirect(n) {
let a = 0, b = 1;
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
console.time('VM'); fibVM(1000); console.timeEnd('VM');
console.time('Direct'); fibDirect(1000); console.timeEnd('Direct');
在Chrome上,虚拟机版本通常比直接计算慢一到两个数量级。差距来源包括:字节码数组的随机访问模式不利于CPU缓存,指令分发(switch)有分支预测开销,栈操作涉及数组的push/pop,以及解释循环本身无法被JIT内联。
如果要提升性能,有几个明确的方向:
指令内联与超级指令。把常见的指令序列合并为一条超级指令,例如把 LOAD x; PUSH 1; ADD; STORE x 合并为 INC x。这减少了分发次数和栈操作。
直接线程化。用函数指针数组替代switch,每个指令对应一个函数,取指后直接调用。在JavaScript中,这体现为把switch换成对象查找。
基于寄存器的重写。把栈式字节码转换为寄存器式字节码(类似Lua的寄存器VM),减少栈操作。代价是编译器需要做寄存器分配,复杂度上升。
字节码到JS的转译。最激进的优化是跳过解释器,直接把字节码转译为JavaScript函数。这本质上是一个简单JIT,能利用宿主引擎的优化能力。实现方式是用 new Function 拼接JS代码字符串。
十、总结
从源代码到可执行结果,中间经历了词法分析、递归下降解析、AST构建、字节码生成和栈式虚拟机执行五个阶段。字节码生成的核心是AST后序遍历——表达式的结果通过操作数栈隐式传递,跳转地址通过标签回填机制延迟确定。虚拟机的核心是取指-译码-执行循环——pc控制执行流,操作数栈承载中间结果,局部变量表存储命名值。
这套实现只有几百行代码,但完整覆盖了编译器后端和虚拟机的核心机制。理解了这套最小内核,再看JVM的Class文件格式、CPython的字节码指令集或V8的Ignition解释器,会发现它们在架构上遵循的是同一套设计思路,差异只在工程细节——指令集更丰富、优化更激进、运行时更复杂。栈式虚拟机是理解这一切的起点。
- 点赞
- 收藏
- 关注作者
评论(0)