从字符处理到简单虚拟机的实现

预取与回滚

字符是语言的最基本单位，如果我们需要编写特定的程序对某个字符串进行某种特殊处理。我们从微观的角度上，一般通过处理每一个字符来达到目的。通常来说，计算机一般情况下是使用线性结构来存储字符串的。从结构上看就是一个字符接着一个字符，以此类推，然后通过一种结束标记来表示来表示这串字符的末尾，即字符串「到此为止」。
编写语言处理程序的时候，可以将字符串看做是「流」。有时候，我们的读取器需要在一串字符之间跳跃 —— 进行预取判断或者回滚（回退）。这个预取判断与回滚距离可能不止一个字符。
C 语言标准 I/O 与 C++ 语言的 I/O 流都提供了字符获取以及相对应的字符回滚函数，比如 C 语言标准 I/O 的 fgetc 和 ungetc 函数，比如 C++ 语言 I/O 流的 std::ifstream::get 和 std::ifstream::unget 函数。为了对付应用开发时的特殊需求，它们总是成对出现。
也许你并不是很清楚这样的字符处理机制在实际编码时的作用，其实我想用更系统的方式来说明，比如请看下面这个例子。

从简单的虚拟机开始

假设我们需要从上帝视角出发，设计一个虚拟机，机器名字叫做「染色体 VM」（或者别的什么名字），这个虚拟机的中央处理器内置两个整数寄存器 —— X 和 Y。并且你给它预设了 4 条机器指令。每一条指令由两个部分组成，分别是操作码 (opcode) 与操作数 (opnum) 。这 4 条指令的机器功能分别如下：

• AXY reg：将寄存器 X 与寄存器 Y 相加，结果放置在形式参数 reg 指定的寄存器中
• SX num：将寄存器 X 中的数值设置为形式参数 num 指定的数值
• SY num：将寄存器 Y 中的数值设置为形式参数 num 指定的数值
• S reg：将形式参数 reg 指定的寄存器中的数值输出到屏幕上

比如，有一段「染色体 VM」机器的程序：

SX 100
SY 50
S X
AXY Y
S X
S Y

100
100
150

你现在可以暂停阅读，用代码去实现一下这个虚拟机的功能，但是不允许用正则表达式或者字符串比较。因为，这将使得你有很多偷懒的方法可以实现这个虚拟机。请用原始方式来判断字符，并且在代码分支结构中做出相应的「动作」，这样你也许会对字符预判和回溯的必要性有更深刻的认识。
比如说，当你的虚拟机程序读取到「S」的时候，下一步需要再预取一个字符，来判断是否是「X」或者是「Y」，如果是，那这个指令就是「SX」或者「SY」并且往后读取 （操作数 num） 。如果不是，就将读出的这个字符放回字符流中（想想为什么？如果不放回会怎么样？），然后暂且将这个指令作为「S」，然后往后继续读取（操作数 reg），当然这样一来会先读到刚放回去的字符。有人可能会问「为什么需要先放回这个字符，然后要之后再读取这个字符，这不是多此一举吗？」，其实是因为后来读这个字符的时候跟之前比起来，程序运行的时候肯定不在同一个代码分支里面了（你想想，一个是要接着读 num 参数，一个是接着读 reg 参数，能一样吗），对应分支所执行的动作是不同的。这样写的代码逻辑更加清晰，逻辑也更容易实现，此处代码结构的拿捏是很微妙的，你可以细品。
一般来说，这就是一个手工编写「有限状态机」代码的过程。
与递归代码类似，编写这种状态机代码也是有一定的规律的。编写递归代码的时候需要掌握两个条件 —— 基线条件和递归条件（有其他译法），当触发基线条件的时候，递归终止并且不会继续往更深处执行。同样地，状态机代码也可以找到一定的规律，我个人对状态机代码编写有一般的总结，可以结合下文的示例代码来看：

• 状态变量与状态值域：你得定义一个状态变量（比如下文代码是 status），以便指示状态机内部的当前状态，它应该在状态值域（比如下文代码是枚举类型 Status）中取值，以便于比较与判断。
• 大循环：你得编写一个大循环来维持状态机的运转，每一次循环完毕，状态变量至少改变 0 到 1 次
• 状态判定：判定状态变量是否处于特定状态，以执行以下两种操作。
• 状态迁移（状态转换）：状态必须按照某种规则进行转换，也当条件满足的时候，给状态变量重新赋值（使状态被改变）
• 主要功能代码：这是状态机的要完成的主要功能部分（比如像下述代码一样，满足特定状态的时候，执行某条指令）

我们可以根据这个状态转换图写出实现程序。下面是我用 C++ 语言编写的「染色体 VM」虚拟机实现程序，我把主要的代码贴上来了。为了方便理解，我把状态枚举破例地定义为中文，对不了解状态机的读者更友好。

/**
 * 文件名：ChromosomeVM.cpp
 * 作者：Alone Cafe
 * 描述：ChromosomeVM 虚拟机实现代码
 * 时间：2020/07/27
 */
#include <iostream>
#include <fstream>
#include <cstdio>
#include <stdexcept>

using namespace std;

// 虚拟机异常
class VMException : public exception {
	const char* m_msg;
public:
	explicit VMException(const char* msg) : m_msg(msg) {}
	virtual const char* what() const noexcept {
		return m_msg;
	}
};

// 虚拟机
class ChromosomeVM {
	ifstream& m_ifs;
	int m_regX, m_regY;  // 两个内置寄存器 X、Y

	enum Status { // 状态集
		初始状态,
		得到串S了,
		确定指令S,
		确定指令SX,
		确定指令SY,
		得到串A了,
		得到串AX了,
		确定指令AXY
	};

	static void halt(const char* last_msg) noexcept {
		cerr << last_msg << endl;
		cerr << "虚拟机已停机！" << endl;
	}

	inline int absorbNum() {
		char buff[BUFSIZ], * pbuff = buff;
		int num = 0;
		while (1) {
			char ch = m_ifs.get();
			if (ch == '\n' || ch == EOF)
				break;
			if (ch < '0' || ch > '9')
				throw VMException("非法整数值！");
			*pbuff++ = ch;
		}
		*pbuff = '\0';
		num = atoi(buff);
		return num;
	}

	inline char absorbReg() {
		char ch = m_ifs.get();
		if (ch != 'X' && ch != 'Y')
			throw VMException("非法寄存器！");
		return ch;
	}

public:
	explicit ChromosomeVM(ifstream& ifs) : m_ifs(ifs), m_regX(0), m_regY(0) {}
	ChromosomeVM() = delete;
	ChromosomeVM(const ChromosomeVM&) = delete;

	inline int runVM() noexcept {
		Status status = 初始状态;
		while (true) {
			int num;
			char reg;

			char ch = m_ifs.get();
			if (ch == EOF)
				return 0;

			switch (status) {
			case 初始状态:
				if (ch == 'S')
					status = 得到串S了;
				else if (ch == 'A')
					status = 得到串A了;
				else if (isblank(ch) || ch == '\n')
					; // 空白字符，忽略
				else {
					halt("非法指令");
					return 1;
				}
				break;

			case 得到串S了:
				if (ch == 'X')
					status = 确定指令SX;
				else if (ch == 'Y')
					status = 确定指令SY;
				else {
					// 回滚字符
					m_ifs.unget();
					status = 确定指令S;
				}
				break;

			case 得到串A了:
				if (ch == 'X')
					status = 得到串AX了;
				else {
					halt("非法指令");
					return 1;
				}
				break;

			case 得到串AX了:
				if (ch == 'Y')
					status = 确定指令AXY;
				else {
					halt("非法指令");
					return 1;
				}
				break;

			case 确定指令SX:
				try { // 接着，吸收一个 num 参数就行
					num = absorbNum();
				}
				catch (VMException& ex) {
					halt(ex.what());
					return 1;
				}
				m_regX = num; // 设置寄存器 X

				status = 初始状态; // 还原状态，以便运行下一条指令
				break;

			case 确定指令SY:
				try { // 接着，吸收一个 num 参数就行
					num = absorbNum();
				}
				catch (VMException& ex) {
					halt(ex.what());
					return 1;
				}
				m_regY = num; // 设置寄存器 Y

				status = 初始状态; // 还原状态，以便运行下一条指令
				break;

			case 确定指令S:
				try { // 接着，吸收一个 reg 参数就行
					reg = absorbReg();
				}
				catch (VMException& ex) {
					halt(ex.what());
					return 1;
				}
				// 输出对应寄存器的数值
				cout << (reg == 'X' ? m_regX : m_regY) << endl;

				status = 初始状态; // 还原状态，以便运行下一条指令
				break;

			case 确定指令AXY:
				try { // 接着，吸收一个 reg 参数就行
					reg = absorbReg();
				}
				catch (VMException& ex) {
					halt(ex.what());
					return 1;
				}
				// 两寄存器相加，并将相加结果设置到指定寄存器
				(reg == 'X' ? m_regX : m_regY) = m_regX + m_regY;

				status = 初始状态; // 还原状态，以便运行下一条指令
				break;
			}

		}
		return 0;
	}
};

int main(int argc, char** argv) {
	if (argc < 2)
		return 1;

	ifstream ifs;
	ifs.open(argv[1], std::ios::in);
	if (!ifs.is_open())
		return 1;

	// 运行染色体 VM
	return ChromosomeVM(ifs).runVM();
}

编译这个程序之后，通过命令行将源代码路径参数传递给程序就能执行「染色体 VM」机器指令了。没错，实际上这就是一个简单的解释器的实现。
说起来，其实这个程序存在一些问题，从状态转换图就能看出来。比如要是用户编写诸如「SXFUCKYOU」这样的指令，它会把它的前部武断地当成「SX」指令来看待（即便后续操作肯定在读取数字的时候会报错）。这些不严谨的代码有时会造成复杂的问题，所以编写状态机代码一定要考虑周全。这里可以通过加中间状态来改良程序，但是为了举例，我还是别写复杂了。
通过这个简单的例子，想必你已经清楚了字符的预取判断与回滚（回退）的关键作用，这同时也就是词法分析器的工作原理，如果你需要手工编写词法分析器的话，编写状态机代码一般是必要的。

练习

尽你所能，改写（可以直接改掉原有的部分）上面的示例代码，挑战一下如下练习任务，使「染色体 VM」虚拟机更加强大：

• 指令至上：为虚拟机的指令集增加一条新指令「AX num」，与其他指令格式类似，接受一个 num 形式参数，将 num 累加到寄存器 X 之上。比如，「AX 67」将 AX 增加 67，相当于表达式 “ AX += 67 ” 的效果
• 就差输入啦：请你为虚拟机的指令集增加一条新指令「SS」，终端阻塞并从键盘上获得整数输入，存入寄存器 X 中，这将覆盖原有值。
  可以编写一些测试用例，来确保使你的程序足够健壮。加油！

后续

下一篇文章将从一个实例开始切入，逐步围绕某种范式，用 C++ 语言去实现一个词法分析器，词法分析器将是最基础的部分，我们设计的语言处理程序所有的分析工作都得建立在它之上。