自己动手用java写编译器 课时9 Thompson构造，正则表达式输入预处理

缘起

RT

分析

本节课编写的程序的目的是将文本格式的正则表达式转换为链表表达的NFA. 即文本

1
2
3
D		[0-9]
{D}+	return ICON
({D}+|{D}*\.{D}+|{D}+\.{D}*})(e{D}+)

转换为

在转换前，我们需要对文本进行预处理，文本其实分成了第一行和下面2行这样的2部分，第一部分称为宏（macro）定义, 所谓的预处理就是要处理宏定义.

1
D		[0-9]

就像C语言中的宏定义，在代码编译前需要进行宏替换，我们在转换前，也需要将正则表达式中的宏进行替换，也即是要将

1
2
{D}+		return ICON
({D}+|{D}*\.{D}+|{D}+\.{D}*})(e{D}+)

转换为

1
2
{[0-9]}+		return ICON
({[0-9]}+|{[0-9]}*\.{[0-9]}+|{[0-9]}+\.{[0-9]}*})(e{[0-9]}+)

也即是把 D 换成了 [0-9]

宏定义看似只是简单地字符串替换，但是他有一个难点在于处理宏定义的嵌套. 例如

1
2
3
4
5
6
7
D		[0-9]
A		[a-z]
AD		{D}|{A}


=======上面给出了宏定义========
{AD}\.{AD}+

则宏AD替换为{D}{A}之后，还要替换宏A和D，即某些宏定义中其实还是宏定义. 所以宏替换{AD}\.{AD}+ 分为

1
2
1. 由 {AD}\.{AD}+ 替换成  {{D}|{A}}\.{{D}|{A}}+
2. 由 {{D}|{A}}\.{{D}|{A}}+ 替换为  {{[0-9]}|{[a-z]}}\.{{[0-9]}|{[a-z]}}+

所以其实宏替换要小心嵌套情况的处理. 有时候嵌套可能有多层.

在我们的程序中，宏定义的格式规定如下

1
宏名称	<一系列空格、Tab、换行符>	宏定义的内容 <一系列空格、Tab、换行符>

我们在未来几个课时要做的事情是（其实是整章要做的事情）

1
2
给定正则表达式先通过宏替换进行预处理，预处理完毕之后，再转换为NFA（Thompson算法），再将NFA转换为DFA， 
再将DFA通过最小化算法得到正则表达式对应的最小DFA结构，从而知道了怎么判定一个文本是否符合该正则表达式.

其实，我们要实现的——将正则表达式转换为自动机的过程就是编译——正则表达式和自动机都是为了判定一个表达式是否满足某种条件，将正则表达式编译成自动机

首先，宏替换进行宏展开预处理是简单的.

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
#include "stdafx.h"

#include <iostream>
#include <string>
#include <map>

using namespace std;
#define LOCAL

string macroname, macrocontent,reg; // 宏名称、宏定义的内容,(待宏展开的)正则表达式
map<string, string> macroholder; // <宏名称, 宏定义的内容>

string macroexpand(string reg) // 宏展开reg
{
	string ans;
	bool flag; // 此轮是否有宏替换发生? false 表示没有, true表示有(之所以要一轮一轮的, 是因为可能有内嵌宏替换)
	do 
	{
		flag = false;
		int cnt = 0; // " 的个数
		for (int i = 0; i< reg.length(); )
		{
			if (cnt) // 如果有 " 的话
			{
				if (reg[i]!='"') // 如果不等于 " 的话, 则原样输出即可
				{
					ans.push_back(reg[i]);
				}
				else // 如果等于 " 的话, 则和之前出现的 " 抵消掉了
				{
					cnt--;
				}
				i++;
			}
			else if (reg[i]=='"') // 如果尚无 " , 但是现在出现了 "
			{
				cnt++;
				i++;
			}
			else if (reg[i]!='{') // 如果字符不是 {,也不是 ", 而且也没有 " 出现的话(或者已经被抵消掉了),直接原样输出
			{
				ans.push_back(reg[i]);
				i++;
			}
			else // 如果不是 " ,  是 {, 就要开始宏替换了
			{
				flag = true; // 此次发生了宏替换
				++i; // 过掉 {
				string mname; // 要抽取的宏名称
				while(reg[i]!='}')
				{
					mname.push_back(reg[i]);
					i++;
				} // 抽取出宏名称, 最后 reg[i]='}'了
				string mcontent("(");
				mcontent.append(macroholder[mname]); // 从缓存中取出宏定义内容
				mcontent.append(")");
				ans.append(mcontent);
				i++; // 最后把 '}' 也过掉
			}
		}
		reg = ans; // 每一次都是从res开始, 到ans结束
		if (flag) ans.clear(); // 如果发生了宏替换， 则清空 ans（因为反正还要进行一轮, 这一轮ans会被重新赋值的）
	} while (flag);
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(cin >> macroname)
	{
		if (macroname=="end")
		{
			cin >> reg;
			cout << macroexpand(reg) << endl;
			break;
		}
		else
		{
			cin >> macrocontent;
			macroholder[macroname]= macrocontent;
		}

	}
	return 0;
}
/*
测试数据
D    [0-9]
end
{D}+
end
或者
D    [0-9]
A    [a-z]
AD   {A}|{D}
end
{AD}+
end
*/

vs2010编译运行上述程序之后的结果如下

1
2
3
([0-9])+
和
(([a-z])|([0-9]))+

这就实现了正则表达式输入的预处理——宏展开

在课时4的时候，我们了解到了编译器的架构（也就是运行过程），大体就是通过词法解析器，将要编译的内容读入，词法解析将读入的内容分解成有特定意义的子部分，也就是打标签。语法解析器通过词法解析器解读输入内容。当遇到特定标签的时候，采取特定的解读操作。由于我们目前正在开发的也是一个（正则表达式的）编译器，因此，同样需要走类似的流程。所以我们同样需要正则表达式的词法解析器.

我们可以回顾一下正则表达式的特点

我们在前面的章节中，曾对正则表达式做过解析，在这里，我们复习一下。正则表达式其实是由一组由普通字符和特殊字符组合而成的一种表达形式。特殊的字符有特殊的含义，在正则表达式中，特殊字符有：

1
+ ? { } [ ] ( )  .  ^  $  "  \

在解读正则表达式时，遇到普通字符，我们知道，普通字符匹配它对应的ascii字符，例如字符 a 匹配 它对应的ascii字符 ‘a’. 但普通字符和特殊字符结合在一起时，我们需要进行不同的解读，例如 [a-z] 匹配所有小写字母。普通字母跟转义符结合时，也需要进行不同的解读，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
\b  表示backspace， 相当于键盘的delete

\n  表示换行

\r  表示回车

\s  表示空格

\e  表示键盘的 esc 键

\ddd  d表示数字，\ddd 表示三位八进制数

\xddd 表示三位十六进制数

\^C 一个反斜杠，一个上尖括号，C代码任意一个字母，他表示键盘键Ctrl 加对应字母的组合

\c  一个转义符加任何一个字符，表示匹配这个字符本身。例如 . 就匹配字符 .

如果没有斜杠，. 在正则表达式中是一个通配符。 * 表示匹配字符 ‘*‘, 如果没有斜杠， ‘*’ 在正则表达式中表示闭包操作。也就是特殊字符前面是转义符的话，它就不再具有特殊含义。

有一些特殊符号，例如^ 表示开头匹配， ^[a-z] 表示匹配任何以小写字符开头的字符串，[a-z]$ 匹配任何以小写字母结尾的字符串。{ 表示宏定义的开始， }表示宏定义的结束。

在双引号” “ 中的任何特殊字符都不再具备特殊含义，例如 正则表达式 “+?” 就只匹配三个字符 + ?