Vincent Chan 的巴士站 🚉

编译原理学习笔记 3:实现一个虚拟机

至于 Lexer 和 Parser 部分,教程和用法实在太多,实现起来也比较简单,所以也没什么好说的,这里说说如何实现一个虚拟机(Virtual Machine)

虚拟机的实现有很多种,常见的分为 Stack Machine 和 Register Machine 前者基于栈,后者基于寄存器。 目前来说,基于栈的虚拟机比较多,像(CPython, JVM, .NET…)都是基于栈的虚拟机,二基于寄存器的虚拟机中比较出名的就是 Lua 的官方实现了,官方称这是最早的基于寄存器的虚拟机,具体如何我们就无法考究了。但是本文主要介绍的是基于栈的虚拟机,因为比较好实现。

我们来看看下面这一行代码

1 + 2 * 3

如果用 StackMachine 来表示是这样的

LOAD 1
LOAD 2
LOAD 3
MULTIPLE // result: 6
ADD  // result: 7

这样应该很好理解,执行这段代码后,栈顶的值是 7,也就是我们表达式的值。那么接下来做两件事情就好好了,一是把语法树生成一连串的指令,二是执行这些指令

语法树如何生成指令呢?

+
| \
1  *
         |\
         2 3

粗略地画,语法树是这个样子地,那么很明显,生成指令地过程就是后序遍历语法树地过程。理解这句话之后,就好做了。但是也有几点要注意地地方,我们通常用一个常量表,把用到地常量给储存起来,如整形,字符串等等。所以我们设计指令的时候,比如说 LOAD_C 指令就可以从常量表里面加载一个值到栈顶。

下面看一下我正在实现的哈语言里面的指令集

#pragma once

namespace halang
{
	enum class VM_CODE
	{
		LOAD_C,					// 0x00 A - load constant
		LOAD_V,					// 0x01 A - load variable
		LOAD_G,					// 0x02 A - load global variable
		LOAD_UPVAL,				// 0x03 A - load upvalue
		STORE_V,				// 0x04 A - store the top of stack to A
		STORE_G,				// 0x05 A - store to the global value
		STORE_UPVAL,			// 0x06 A - store to the upvalue table
		PUSH_INT,				// 0x07 A - load A
		PUSH_BOOL,				// 0x08 A - load A
		POP,					// 0x09 A - Pop A
		CLOSURE,				// 0x0a A - linked Function's upvalue to current env
		CALL,					// 0x0b (A, B, C...) call function(A, B, C...)
		RETURN,					// 0x0c A - if A != 0 return exp else return nothing
		IFNO,					// 0x0d if not true, jump to the location.
		JMP,					// 0x0e
		NOT,					// 0x0f
		ADD,					// 0x10 add the top two val
		SUB,					// 0x11
		MUL,					// 0x12
		DIV,					// 0x13
		MOD,					// 0x14
		POW,					// 0x15
		GT, LT,					// 0x16 0x17
		GTEQ, LTEQ,				// 0x18 0x19
		EQ,						// 0x1a
		OUT,					// 0x1b
		STOP					// 0x1c
	};

};

至于运行,如何储存变量呢,最简单的做法就是用 Environment 方法。用一个表来储存变量,这个表当然可以用哈希表(变量名-变量值)来做,但是这样还不够快。其实我们知道,在一个环境里面,我们可以为每一个变量名编一个号,这样子这个变量表就可以用数组(变量编号-变量值)来做,这样子,访问变量和储存变量的时候就快很多了。

项目 Github 地址:https://github.com/vincentdchan/halang