Hello, world!

0%

动手写词法分析器

发表于 分类于 阅读次数： Valine：
本文字数： 6.7k 阅读时长 ≈ 17 分钟

前言

这个学期学了编译原理，所以，本学期的课程设计就是写一个词法分析器和一个语法分析器。一个很庞大的内容啊，12周就要交，于是趁着五一假期，在宿舍里写一发。

任务要求

Create a lexical analysis program, which supports analyzing regular grammar.
You must use DFA (Deterministic Finite Automata) or NFA (Nondeterministic Finite Automata) to implement this program. The inputs of the program are a text document including a set of productions of 3º grammar (the regular grammar) and a source code text document contains a set of strings to be recoganized. The output of the program is a token table which consists of 5 types token: key words, identifier, const, limiter and operator.

准备资料

先做一下理论知识的储备。

正规式

设$G=(V_N, V_T, P, S)$，若P中的每一个产生式都是$A \rightarrow aB$和$A \rightarrow a$，其中A和B都是非终结符，$a \in V_T^*$，则G是3型文法或正规文法

有穷自动机

是一种识别装置，能够准确的识别正规集，即识别正规文法所定义的语言和正规式所表达的集合。

正规式到NFA

算法描述

  1. 读入 A->aB 或 A->a
  2. 若A不在map中，把A加入到map中；若A在map中，则进入第三步
  3. 若B不存在，则把(a, B)加入到A的multimap中，然后把B加入到map中；若B存在，则把(a, y)加入到A的multimap中
  4. 重复第1~3步，直到把文法全部读入

我主要使用map和multimap来存储NFA。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//第一行表示NFA的开始状态
//我通过tuple来存储了一个三元组，表示A->aB
for(int i = 1; i<len; i++)
	{
		A = std::get<0>(grammar[i]);
		a = std::get<1>(grammar[i]);
		B = std::get<2>(grammar[i]);
		//统计终结符Vn和非终结符Vt
		vn.insert(a);
		vt.insert(A);
		if (B != "###")		//###表示终止状态
			vt.insert(B);

		map<string, multimap<string, string> >::iterator res;
		res = nfa.find(A);
		if (res == nfa.end())
		{
			nfa.insert(pair<string, multimap<string, string> >(A, multimap<string, string>()));
			res = nfa.find(A);
		}
		res->second.insert(pair<string, string>(a, B));
	}

NFA转DFA

转换函数

$D([S_1, S_2, …, S_j], a) = [R_1, R_2, …, R_i]$
其中$\varepsilon-closure(move([S_1, S_2, …, S_j], a)) = [R_1, R_2, …, R_i]$

最小集算法

因为在本程序中，没有$\varepsilon$，所以，$\varepsilon-closure$函数与$move$函数等价

1
2
3
4
5
6
7
开始，另closure(K_0)为C中的唯一成员，并且他是未被标记的
while C中存在未被标记的子集T
    标记T
    for a in 终结符集Vn
        U = closure(move(T, a))
        if U不在C中
            将U作为未标记的子集加入到C中

核心代码

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
while (!c.empty())
{
	pair<int, set<string> > t = c.front();
	c.pop();								
	buffer.insert(t.second);				
	auto pos = visit.find(t.first);
	if (pos != visit.end())					//如果已经标记过，则跳过这个状态
		continue;
	visit.insert(t.first);					//标记T
	
	map<string, int> temp;
	set<string>::iterator i;
	for (i = vn.begin(); i != vn.end(); i++)
	{
		set<string> u = move(t.second, *i);
		auto pos = buffer.find(u);
		if (!(findInQueue(c, u) || pos != buffer.end()) && !u.empty())  //判断状态U是否在C中
		{
			//U不在C中，插入到C中
			hash.insert(pair<set<string>, int>(u, id));			
			rhash.insert(pair<int, set<string> >(id, u));
			c.push(pair<int, set<string> >(id++, u));
		}
		if (!u.empty())
		{
			map<set<string>, int>::iterator res = hash.find(u);
			temp.insert(pair<string, int>(*i, res->second));
		}
	}

	dfa.insert(pair<int, map<string, int> >(t.first, temp));
}

用DFA进行词法分析

算法说明

  1. 预处理: 消除空白字符，主要使用std::isspace(char ch)来进行判断。
  2. 读入下一个字符，并判断文件是否结束。
  3. 对终结符进行转换。
  4. 检查下一个字符是否符合DFA的规则。
  5. 若符合，则加入到buffer中。判断是否是终结状态，如果是，则修改nearestAccept，并跳到第2步；否则直接跳到第2步。
  6. 对于不符合规则的，退回到nearestAccept，然后提交buffer，并返回Token。

注意: 在进行匹配的过程中，我们遵循最长匹配优先的原则。
例如，当出现 abc 字符串的时候，我们的程序应该把 abc 作为一个Token，而不是把 a 或者 ab 作为一个Token。
因此，我们需要在程序中加入最近可接受nearestAccept变量，来记录目前最长的可接受字符串，当发生匹配错误时，应退回到nearestAccept的位置，并提交。

核心代码

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
string Scanner::getToken()
{
	preprocess();		//预处理并初始化状态
	bLine = line;
	bColumn = column;
	bool stop = false;
	nearestAccept = 0;
	state = 0;
	buffer.clear();

	while (!stop)
	{
		char c = peekChar();	//预读一个字符
		if (c == EOF)			//判断文件是否结束
		{
			state = -2;
			return "EOF";
		}
		c = transform(c);
		pair<int, map<string, int> > res = dfa.find(state);
		char s[2];
		s[0] = c;
		s[1] = '\0';
		map<string, int>::iterator i = res.second.find(s);
		if (i == res.second.end())
		{						//DFA中找不到可行通路
			stop = true;
			string temp = buffer.substr(nearestAccept);
			buffer.erase(nearestAccept);
			nextRead.insert(0, temp);
			if (nearestAccept == 0)			//没有可接受字符串，报错
			{
				cout << "错误:" << line << ":" << column << endl;
				state = -1;
				getNextChar();
			}
		}
		else
		{					//字符可行，加入到buffer中，并进行状态转移
			state = i->second;
			getNextChar();
			buffer.push_back(currentChar);
			pair<int, map<string, int> > res = dfa.find(state);		
			i = res.second.find("&");
			if (i != res.second.end())			//判断是否是终结状态
			{
				nearestAccept = buffer.size();
			}
		}
	}
	return buffer;		//返回Token
}

编写目标语言的正规文法

我理想中的目标语言是Pascal，所以下面我所写的，是Pascal的词法规则。
为了简化程序的编写，我以begin作为NFA的起始状态，&符号作为结束的标志，!作为空白字符。
文法的表示方式如下：
$A \rightarrow aB$
表示为: A a B
$A \rightarrow a$
表示为: A a

标识符

关键字在文法中属于标识符，当确认某个Token为标识符时，还需要到关键字表中验证是否是关键字。
在Pascal中，标识符的要求是：

  1. 以字母或下划线开始
  2. 只包含字母、下划线和数字
  3. 长度小于255
  4. 不区分大小写
1
2
3
begin letter-underline identifier
identifier letter-digit-underline identifier
identifier &

数字

Pascal中的数字表达还是比较丰富的，包括整数(100)、浮点数(1.2)、科学记数法(10.2e+5)以及十六进制的整数($ae3)。

整数

1
2
3
4
5
begin +|- integer-1
begin digit integer
integer-1 digit integer
integer digit integer
integer &

浮点数

1
2
3
4
integer . real-1
real-1 digit real	//保证小数点后一定要有数字
real digit real
real &

科学计数法

1
2
3
4
5
6
7
8
9
integer e science-1
integer E science-1
real e science-1
real E science-1
science-1 +|- science-2		//保证e和正负号后面要有数字
science-1 digit science
science-2 digit science
science digit science
science &

十六进制整数

1
2
3
4
begin $ Xinteger-1
Xinteger-1 xdigit Xinteger	//保证$后面要有数字
Xinteger xdigit Xinteger
Xinteger &

字符和字符串

在Pascal中，字符和字符串都是用单引号括起来的，例如: ‘a’和’abc’。
暂时不支持转义符，但是可以通过修改文法，使其支持此功能。

字符

1
2
3
4
begin ' char-1
char-1 char char-2
char-2 ' char
char &

字符串

1
2
3
4
begin ' string-1
string-1 char string-1
string-1 ' string
string &

注释

在正常的词法分析其中，注释部分应该是在预处理过程中将其消除的，但是作为一个通用的词法分析器，注释部分必须出现在文法部分中，而不能再预处理过程中处理掉。
Pascal中的注释分为行注释和块注释。
行注释是(*开头的，以*)结尾的字符，块注释是以{开始的，以}结束的字符。
注意: 注释不遵循最长优先匹配，而是最短优先匹配，因此，只要碰到*)或者}，就会停止匹配，并返回。VC++也是这样操作的。

行注释

1
2
3
4
5
6
7
begin ( row-comment-1
row-comment-1 * row-comment-2
row-comment-2 char-no-star row-comment-2
row-comment-2 * row-comment-3
row-comment-3 char-no-right row-comment-2
row-comment-3 ) row-comment
row-comment &

块注释

1
2
3
4
begin { block-comment-1
block-comment-1 char-no-Right block-comment-1
block-comment-1 } block-comment
block-comment &

界符和运算符

界符和运算符都比较好处理，唯一比较困难的是..这个界符，因为这个符号经常出现在数字后面，如果与前面的数字不加空格等分隔，程序会把第一个.识别成小数点，把后面的.识别成句号。这个问题暂时没有解决，或许可以从语法编写上解决。有知道如何解决的可以告诉我啊~
PS:这个问题已经解决，通过最长匹配原则，可以避免这个问题。

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
begin : colon
colon &

colon = assignment
assignment &

begin . period
period &

period . duble-period
duble-period &

begin , comma
comma &

begin ; semicolon
semicolon &

begin ^ tip
tip &

begin / div
div &

begin + add
add &

begin - sub
sub &

begin * mul
mul &

begin % mod
mod &

begin = equ
equ &

begin < less
less &

less = less-equ
less-equ &

less > not-equ
not-equ &

begin > great
great &

great = great-equ
great-equ &

begin ( left
left &

begin ) right
right &

begin [ left-m
left-m &

begin ] right-m
right-m &

后记

词法分析器到这里基本上是写完了，但只实现了基本的功能，具体的报错等附加功能还是比较差，因为在编写过程中，并没有考虑性能问题，所以代码执行效率比较低，特别是NFA转DFA的过程。

整个项目我已经上传了gitee，有兴趣的可以去下载下来研究一下。
本人水平有限，如果你有更好的想法或者实现方法，我们可以一起讨论。

项目地址：点击查看

接下来一周要考试，语法部分等我复习完编译原理再写吧。

相关文章