(二)单词处理:设计脚本语言的词法

战前回顾

上一篇在《(一)字符处理:简单虚拟机的实现》文章中,我们实现了一个简单的虚拟机,又或者可以说它是一个简单的解释器。因为它功能有限,实际上,除了计算加法和输出,它不具备其他更高级的功能,比如类似 if 语句这种分支结构、类似 while 语句的循环结构,甚至更高级的,函数定义与调用都是没有实现的。这些功能对于第一个例子未免过于复杂。我们必须重新审视我们的工作,去完成一个更高级的解释器,它应该被设计成就像某些脚本语言(如 JavaScript、Basic 或者 Python)一样。

MyScript

我们为了后续工作能够有条理地进行下去,最好需要我们现在就直接定义(构思)一个编程语言。在本文中,我们定义的编程语言名字叫做 MyScript。顾名思义,这个编程语言至少在语法上将会设计得和 JavaScript 语言类似(当然有很多都不一样)。比如下面是一段 MyScript 编程语言的示例程序,用户将输入圆的半径,程序计算出圆的面积并显示出来。

func area(r) {
    return r * r * 3.14159;
}
var a;
input a;
if (a < 0) {
    print "半径不能小于0";
} else {
    print area(a);
}

词法规则

既然设计编程语言,首先得需要制定一套完备的、能够避免语法发生冲突的规则。

大多数语言都有一些「保留字」(或者也可以说是关键字,但是我建议还是用保留字这个说法比较好),它们用于控制编程语言的最基本功能,比如定义变量、函数、或者定义分支、循环结构。必然地,我们将给 MyScript 也制定一套保留字规则:

func
var
return
if
else
while
break
continue
input
print

如你所见,相较于 C 语言而言,MyScript 的关键字少之又少,比如没有 do、for,但是麻雀虽小五脏俱全,利用这几个保留字就能构造出三种基本结构(顺序、分支、循环),这样至少已经足够用于构造一个图灵完备的、结构化的编程语言了,即便这样做会减少很多基本功能,对编程开发很不方便。

除了保留字之外,我们的编程语言还有一个重要的组成部分,那就是「标点符号」(我不知道怎么把运算符和花括号、圆括号之类的放在一起说,这里我就擅自统一称作「标点符号」)。比如表达式里面出现的各类运算符,以及分号、成对出现的各类花括号、方括号、圆括号等……。这里我们也把它们列举出来:

;
+
+=
-
-=
*
*=
/
/=
%
%=
&&
||
!
[
]
(
)
{
}
=
==
!=
<
<=
>
>=
.

除了保留字和标点符号之外,代码里面可能还会出现什么呢?

对,「字面量」和「标识符」。标识符的规则比较简单,只要遵循「由字母数字和下划线组成,且不能以数字开头」的原则就可以了。但是对字面量而言就复杂很多,我们需要制定一个规则出来,否则编写处理程序的工作就无法进行下去。于是,我们可以暂且定义以下规则:

  • 实数字面量:以十进制数字字符(0~9)组成数字串,并且可以包含并且仅可以包含一个小数点,小数点可以在数字串开头出现,与 0.XXXXX 等价,也可在结尾出现,与 XXXXX.0 等价。数字串必须以 f 或者 F 结尾
  • 整数字面量:以十进制数字字符(0~9)组成的数字串。
  • 字符字面量:以单引号开头、以单引号结尾的一个字符,可以是转义字符。
  • 字符串字面量:以双引号开头、以双引号结尾的一串字符,可包含转义字符。

关于转义字符,其组成规则将严格按照下表:

此外还需注意几点,MyScript 语言的数值类型将只有实数型和整数型,实数型运算操作都定义在计算机浮点运算之上,整数型将按常规运算进行。字符字面量在运算过程中若碰到整数或者实数将被转换成对应的 ASCII 码值参与运算,若碰到字符串则视为串的合并操作,整数或者浮点碰到字符串则直接「字符串化」。当然,这些操作本章内容不会涉及到,这是语法(语义)分析过程中需要考虑的问题。

关于缺失的特性

这个世界上没有完美的编程语言,而且编程语言本身也是需要不断完善、更新的。纵观主流的编程语言,其诸多特性并不是一开始就存在于语言中的,一般都是后来随着时间推移进一步补充并且完善的。本教程全篇为了可读性,设计过程将会牺牲很多主流编程语言当中的特性,以换取你沿着「如何编写语言处理程序」这一目标笔直向前进的动力,这样读者就无须在意编程语言设计过程中细枝末节的问题。若有一天你有心继续深挖下去,实现属于你自己的编程语言,便可随意添加自己想实现的特性,岂不美哉!

准备好动手

现在我们拥有一个保留字列表,一个标点符号列表。还有一套识别标识符字面量的规则,多么好的食材。下一章节我们将重心放在整理设计思路并且编程实现我们的单词处理程序 —— 词法分析器。作为厨师的你,应当将这些现有食材做成美味菜肴。

(一)字符处理:简单虚拟机的实现

预取与回滚

字符是语言的最基本单位,如果我们需要编写特定的程序对某个字符串进行某种特殊处理。我们从微观的角度上,一般通过处理每一个字符来达到目的。通常来说,计算机一般情况下是使用线性结构来存储字符串的。从结构上看就是一个字符接着一个字符,以此类推,然后通过一种结束标记来表示来表示这串字符的末尾,即字符串「到此为止」。

编写语言处理程序的时候,可以将字符串看做是「流」。有时候,我们的读取器需要在一串字符之间跳跃 —— 进行预取判断或者回滚回退)。这个预取判断与回滚距离可能不止一个字符。

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++ 语言去实现一个词法分析器,词法分析器将是最基础的部分,我们设计的语言处理程序所有的分析工作都得建立在它之上。