自己写仅包含加号、乘号、小括号、正整数数字的表达式的编译器

缘起

最近在看Coding 迪士尼老师的《自己动手用java写编译器》视频教程（一直想入手编译原理这门课，但是大部分书籍太理论化了, 深深的感觉无力，看到这门课，眼前一亮~ 有门了~）. 看了前三集，觉得思想不错，就是代码实现风格不是很赞同. 遂停下观看，针对前三集，自己写一个仅包含加号、乘号、小括号、正整数数字的表达式的编译器. 不然前三集仅仅弄懂思想，却没有自己手写实现的代码，我依旧感觉很无力. 我贯彻的思想是——没有代码的算法思想是耍流氓. 本文作为该视频教程前三集的总结.

分析

其实要做的事情，在老师的视频中讲的很清楚了，我们需要三个东西

  1. compiler

    本质上就是一个main方法. 调用其他组件（下面的lexer和parser）用的

  2. lexer

    预设一组词法规则——规定什么文本叫做有意义的，以及对应有意义的文本称之为什么（即打上标签），然后从左至右顺序读取文本，顺次将有意义的文本打上标签解析出来.

  3. parser

    语法解析器. 它其实就是通过预设的一组语法规则. 利用lexer组件读取标签化的文本的时候，利用语法规则将文本不断的拆分. 最后形成此文本的一棵语法解析树. 形成语法解析树的过程中，我们不仅最终可以得到该文本是否符合语法规则这个结论（即编译是否通过），还可以在生成语法解析树的中途干点事情——完成代码生成. 即生成伪汇编代码.

词法规则如下

1
2
3
4
5
6
7
8
;				的标签是	SEMI=1
+				的标签是	PLUS=2
*				的标签是	TIMES=3
(				的标签是	LP=4
)				的标签是	RP=5
数字或标识符		的标签是	NUM_OR_ID=6
非法字符		 的标签是	 UNKNOWN_SYMBOL=7
读到文件尾		的标签是	EOI=0

语法规则如下（为什么是这样一个语法规则，日后的视频教程老师会讲的，我们本节就是使用该语法规则将程序编写出来即可）

1
2
3
4
5
6
7
8
9
10
11
1. statements -> '空' | expression; statements

2. expression-> term expression'

3. expression'-> + term expression' | '空'   ## 如果不以+开头的话, 就解释为空

4. term -> factor term'

5. term' -> * factor  term' | '空'   ## 如果不以 * 开头的话, 就解释为 '空'

6. factor -> number | (expression)   ## number是数字

上面的 | 的含义是 “或”, 即二择一.

注意一下语法规则，有 expression和expression’, term和term’, 带撇的，都是前面有符号要处理的——expression’ 要处理+， term’ 要处理 *

用图表示为

下面的代码中, 要开始解析一个东西的时候，都要确保 lexer的current已经站在了那个东西的第一个字符处.

注意哈, 为什么所在的深度比+深? 因为\的优先级比+高. 这个以后会细说. 寄存器赋值总是在叶子处. 2个寄存器之间运算在term’解析出*号以及 expression’解析出 + 的时候.

本编译器使用c++实现. 注意，这里的寄存器的存取显然是通过栈结构实现的. 如下图所示

上图表示当前寄存器栈（reg数组来模拟）只有7个寄存器, t0已经被取走了. top指向reg[1]这个数组元素，也就是top = 1

编写如下 compiler.cpp和 lexer.h以及parser.h 三份文件 ，他们的作用已经讲过了. 代码如下

compiler.cpp

1
2
3
4
5
6
7
8
9
10
11
#include "parser.h"

int main()
{
	string statements;
	cin >> statements;
	Lexer lexer(statements);
	Parser parser(lexer);
	parser.statements();
	return 0;
}

lexer.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/************************************************************************/
/* 词法解析器                                                                     */
/************************************************************************/
#include <string>
#include <cctype>

using namespace std;

class Lexer
{
public:
	Lexer(string statements)
	{
		this->statements = statements;
		this->current = -1;
	}
	~Lexer(){}
	/************************************************************************/
	/* 判断当前token和传入的token是否一致                                                                     */
	/************************************************************************/
	bool match(int token)
	{
		if (!~current) current = advance(); // 如果尚未开始处理字符的话,那就开始处理第一个字符
		return current == token;
	}

	/************************************************************************/
	/* 读取下一个字符                                                                     */
	/************************************************************************/
	int advance()
	{
		if (!statements.length()) return current = EOI; // 如果待解析的已经空了, 则直接返回 EOI
		for (int i = 0; i< statements.length();) // 如果还有字符的话, 则遍历直至能读取到合法字符
		{
			char c = statements.at(0); // 取第一个字符
			switch(c)
			{
			case ';':
				statements = statements.substr(1); // 截掉第一个字符
				return current = SEMI;
			case '+':
				statements = statements.substr(1); // 截掉第一个字符
				return current = PLUS;
			case '*':
				statements = statements.substr(1); // 截掉第一个字符
				return current = TIMES;
			case '(':
				statements = statements.substr(1); // 截掉第一个字符
				return current = LP;
			case ')':
				statements = statements.substr(1); // 截掉第一个字符
				return current = RP;
			case '\n':
			case '\t':
			case ' ': // 只有是空格、Tab、换行符的时候, 循环才要继续, 其余情况都是直接返回的
				statements = statements.substr(1); // 截掉第一个字符
				i++;
				continue;
			default:
				if (!isdigitsorid(c)) return UNKNOWN_SYMBOL; // 如果既不是数字又不是标识符的话, 返回非法字符
				symbol = ""; // string在 c++中是一等公民, 是可以直接赋值的
				while(i<statements.length() && isdigitsorid(c)) // 走到这里,c肯定是数字或者标识符, 所以肯定会进入循环
				{
					symbol += c;
					if (++i<statements.length()) // 防御性编程
					{
						c=statements.at(i); // 读取下一个字符, 最后要么超了(即i=statements.length(),此时调用substr得到的是空字符串""), 要么statements[i]不是字母或者数字
					}
				}
				statements = statements.substr(i); // 把数字或标识符给截掉
				return current = NUM_OR_ID; // 记录当前是数字或者标识符
			}
		}
		return current = EOI; // 走到这里，只可能是 换行符、空格、Tab将for循环耗尽, 然后这里返回EOI.
	}

	/************************************************************************/
	/* 词法解析器规定的token们                                                                     */
	/************************************************************************/
	static int const EOI = 0; // 输入尾
	static int const SEMI = 1; // 分号
	static int const PLUS = 2; // +
	static int const TIMES = 3; // *
	static int const LP = 4; // (
	static int const RP = 5; // )
	static int const NUM_OR_ID = 6; // 数字或者标识符
	static int const UNKNOWN_SYMBOL = 7; // 未知字符
	string symbol; // 当前符号（即当前解析出来的有意义的字符串,如数字"49",如标识符"wocao"）

private:
	/************************************************************************/
	/* 判断一个字符是否是数字或者标识符                                                                     */
	/************************************************************************/
	bool isdigitsorid(char c)
	{
		return isdigit(c) || isalpha(c);
	}

	int current; // 当前token
	string statements; // 当前还需要分析的文本
};

其实lexer.h 暴露对外的接口仅仅有一个 match（当前字符是否匹配） 一个是 advance（读取下一个字符）.

最后是parser.h, 它暴露对外的接口仅仅是一个 statements （即解析表达式（statements）的.）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include "lexer.h"
/************************************************************************/
/*  语法解析器                                                                     */
/************************************************************************/

#include <iostream>
using namespace std;

class Parser
{
public:
	Parser(Lexer lexer):lexer(lexer),islegal(true)  // 默认表达式是合法的
	{
		reg[0] = "t0";
		reg[1] = "t1";
		reg[2] = "t2";
		reg[3] = "t3";
		reg[4] = "t4";
		reg[5] = "t5";
		reg[6] = "t6";
		reg[7] = "t7";
		top = 0; // 栈顶指针
	}

	/************************************************************************/
	/* 解析statements                                                                     */
	/************************************************************************/
	void statements()
	{
		while(!lexer.match(Lexer::EOI)) // 这里使用while消除递归， 注意，不能用 Lexer.EOI 而要使用 ::
		{
			string regName = fetchReg(); // 获取一个寄存器
			expression(regName); // 先解析表达式的第一个expression(将此寄存器传入)
			if (lexer.match(Lexer::SEMI))
			{
				lexer.advance(); // 读取下一个字符(使得lexer的current可能是EOI（已经到文件尾了）也可能是下一个expression的开始字符)
			}
			else
			{
				islegal = false;
				cout<<"【syntax error】 缺少分号" << endl;
			}
		}
		if (islegal)
		{
			cout << "表达式解析正确." << endl;
		}
	}

private:
	Lexer lexer;
	void expression(string regName)
	{
		term(regName);
		while(lexer.match(Lexer::PLUS)) // 这个循环其实是在解析expression' 只要匹配加号, 就继续（后面都是这样，一旦匹配上，就继续读取下一个字符），这里使用while消除递归
		{
			lexer.advance(); // 继续读取下一个字符
			string _regName = fetchReg();
			term(_regName);
			cout << regName << "+=" << _regName << endl;
			freeReg(_regName); // 归还寄存器
		}
	}

	void term(string regName)
	{
		factor(regName);
		while(lexer.match(Lexer::TIMES)) // 这个循环其实是在解析图中的 term'
		{
			lexer.advance(); // 走到下一个字符, 也就是factor的起点字符
			string _regName = fetchReg();
			factor(_regName);
			cout << regName << "*=" << _regName <<endl;
			freeReg(_regName);
		}
	}

	void factor(string regName)
	{
		if (lexer.match(Lexer::NUM_OR_ID))
		{
			cout << regName << "=" << lexer.symbol << endl; // 注意, 打印c++中的string不能使用c中的printf
			lexer.advance();
		}
		else if (lexer.match(Lexer::LP))
		{
			lexer.advance();
			expression(regName); // 保证做完一单业务, lexer一定滚动到下一个
			if (lexer.match(Lexer::RP))
			{
				lexer.advance();
			}
			else
			{
				islegal = false;
				cout << "【syntax error】 需要右括号." << endl;
			}
		}
		else // 既不是数字也不是标识符也不是左括号
		{
			islegal = false;
			cout << "【syntax error】 需要数字或者标识符." << endl;
		}
	}

	/************************************************************************/
	/* 获取一个寄存器                                                                     */
	/************************************************************************/
	string fetchReg()
	{
		if (top>=8) // 8是寄存器数组的长度
		{
			puts("【运行时错误】 寄存器栈underflow");
			exit(EXIT_FAILURE);
		}
		return reg[top++];
	}

	/************************************************************************/
	/* 归还一个寄存器, 此寄存器的名称为s                                                                   */
	/************************************************************************/
	void freeReg(string s)
	{
		if (!top) // 如果
		{
			puts("【运行时错误】 寄存器栈overflow.");
			exit(EXIT_FAILURE);
		}
		reg[--top] = s;
	}

	/************************************************************************/
	/*  此表达式是否合法
	 *  本解析器只能解析三种错误
	 *  1. 表达式没有分号.
	 *  2. 缺少右括号.
	 *  3. 需要数字或者标识符.
	/************************************************************************/
	bool islegal;

	/************************************************************************/
	/* 8个寄存器（用于汇编伪代码生成）                                                                     */
	/************************************************************************/
	string reg[8];

	int top;
};

最后将这三份文件放在一个目录下面，确保机器正确安装了mingw64（并且已经写入了Path）. 然后在这个目录下cmd执行如下命令

1
g++ -o simplecompiler compiler.cpp lexer.h parser.h

得到的simplecompiler.exe 见DEMO【1】. 大家可以下载下来运行玩玩.

参考

【1】https://github.com/yfsyfs/algorithm/blob/master/simplecompiler.exe