自己动手用java写编译器 课时7 有限状态机驱动的整形，浮点型数值识别器

缘起

如题

分析

本节根据上一节课讲解的原理实现一个FSM用于识别用户输入的到底是整型还是浮点型.

识别整型还是浮点型需要使用的FSM的图如下

接收状态仅有 1、 2、 4 三种. 即以 . 或者 e结尾都是不被接收的状态.

下面是具体实现，当然，使用的是c++. 依旧觉得讲师写的代码好丑~

要弄懂下面的程序, 必须要明白: 0~5这6个状态都是合法状态，但只有1,2,4属于可接受的状态.

项目目录如下

其中，main.cpp 仅仅是一个测试代码

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

#include <stdio.h>
#include "fsm.h"
#define LOCAL

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	FSM fsm; // 部署一台自动机
	int c;
	while(1) // 不断的从标准输入读取字符
	{
		c = getchar();
		fsm.process(c);
		if (!~c) break;
	}
	return 0;
}
/*
测试数据
12 34.5		 5     2b 3.4e
.7
3.1
1x2
1a
3e4
*/

fsm.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
/************************************************************************/
/* FSM                                                                     */
/************************************************************************/
#include <string.h>

class FSM
{
public:
	FSM()
	{
		lineno = 1;
		clean();
		init();
	}
	~FSM(){}
	void process(int c) // 自动机处理字符c
	{
		int nextState = ~c?next[currentState][c]:FAILURE_STATE; // 根据当前字符确定下一个状态
		if (!~nextState) // 如果下一个状态是非法状态, 则需要根据上一次的状态是否是合法状态来判断是否
		{
			if (~currentState&&currentState) // 如果当前状态是合法状态（非初始化状态）的话, 例如 "3.4ex", 则3.4e都是合法的, 这里的c = 'x', expression中是 3.4e ,则就要打印了, 但是打印的是可接受的表达式,即3.4而不是3.4e
			{
				expression[acceptTop] = 0;
				printf("行 %d, 解析到了一个%s, 它是 %s\n", lineno, (currentAcceptState&1)?"整型":"浮点型", expression);
			}
			clean(); // 初始化状态机
			if (c==10) // 如果读取到了换行符, 则行号+1
			{
				lineno++;
			}
			printf("略去非法字符%d\n", c);
		}
		else // 如果下一个状态是合法状态
		{
			printf("状态机读入字符%c之后, 状态从%d转换为%d\n", c, currentState, nextState);
			currentState = nextState; // 更新状态
			expression[top++] = c; // 塞入字符
			if (accepted[nextState]) // 如果下一个状态是可接受状态. 则需要考虑currentAcceptState跟上currentState的脚步， 例如3e4(这块代码的理解主要就是借助这个3e4), 一开始读到e的时候, e对应状态5， 是不可接受的, 则acceptTop不会跟上来, 但是一旦读到4(即c是'4'),则acceptTop就要跟上来了
			{
				currentAcceptState = nextState; // 更新可接受状态
				acceptTop = top;
			}
		}
	}
	
private:
	static const int STATE_SIZE = 6; // 状态机状态的数量
	static const int SYMBOL_SIZE = 128; // 符号表的符号数量
	static const int FAILURE_STATE = -1; //失败的状态
	static const int EXPRESSION_MAX_SIZE = 128; // 表达式的最大长度
	bool accepted[STATE_SIZE]; // accepted[i]表示状态i是否可接收
	int next[STATE_SIZE][SYMBOL_SIZE]; // 状态机的转移函数, next[s][t] = p, 表示状态机当前状态是s, 输入符号t,则状态机的状态变成p
	int currentState; // 当前自动机状态
	int currentAcceptState; // 当前自动机可接收的状态
	char expression[EXPRESSION_MAX_SIZE]; // 用于装载表达式
	int top; // expression中的表达式的长度
	int acceptTop; // expression中可接收的表达式的长度, top和acceptTop的区别可以参见一个例子 3.4e, 则expression = "3.4e", top是 3.4e的长度, 但是acceptTop是3.4的长度,因为5不是可接收的状态
	int lineno; // 当前行号
	
	void clean() // 状态机回到初始状态
	{
		currentState = 0;
		currentAcceptState = 0;
		top = acceptTop = 0;
	}

	void init() // 初始化自动机转移函数
	{
		accepted[0] = false;
		accepted[1] = true;
		accepted[2] = true;
		accepted[3] = false;
		accepted[4] = true;
		accepted[5] = false;
		memset(next, FAILURE_STATE, sizeof(next)); // -1 是非法状态
		for (int i = 0; i<10; i++) // 初始化状态机的转移函数
		{
			next[0][i+'0'] = 1; // 0状态（FSM的初始化状态）输入0~9的话, 则状态机变为1状态
			next[1][i+'0'] = 1; // 1状态输入 0~9 变动到1状态
			next[2][i+'0'] = 2; // 2状态输入 0~9 变动到2状态
			next[3][i+'0'] = 2; // 3状态输入 0~9 变动到2状态
			next[4][i+'0'] = 4; // 4状态输入0~9变动到4状态
			next[5][i+'0'] = 4; // 5状态输入0~9变动到4状态
		}
		next[0]['.'] = 3; // 0状态输入'.'的话, 状态机变为3状态
		next[1]['.'] = 2;  // 1状态输入 . 变动到2状态
		next[2]['e'] = next[1]['e'] = 5; // 1和 2状态输入'e', 进入5状态
	}
};

使用测试数据的输出结果是

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
状态机读入字符1之后, 状态从0转换为1
状态机读入字符2之后, 状态从1转换为1
行 1, 解析到了一个整型, 它是 12
略去非法字符32
状态机读入字符3之后, 状态从0转换为1
状态机读入字符4之后, 状态从1转换为1
状态机读入字符.之后, 状态从1转换为2
状态机读入字符5之后, 状态从2转换为2
行 1, 解析到了一个浮点型, 它是 34.5
略去非法字符9
略去非法字符9
略去非法字符32
状态机读入字符5之后, 状态从0转换为1
行 1, 解析到了一个整型, 它是 5
略去非法字符32
略去非法字符32
略去非法字符32
略去非法字符32
略去非法字符32
状态机读入字符2之后, 状态从0转换为1
行 1, 解析到了一个整型, 它是 2
略去非法字符98
略去非法字符32
状态机读入字符3之后, 状态从0转换为1
状态机读入字符.之后, 状态从1转换为2
状态机读入字符4之后, 状态从2转换为2
状态机读入字符e之后, 状态从2转换为5
行 1, 解析到了一个浮点型, 它是 3.4
略去非法字符10
状态机读入字符.之后, 状态从0转换为3
状态机读入字符7之后, 状态从3转换为2
行 2, 解析到了一个浮点型, 它是 .7
略去非法字符10
状态机读入字符3之后, 状态从0转换为1
状态机读入字符.之后, 状态从1转换为2
状态机读入字符1之后, 状态从2转换为2
行 3, 解析到了一个浮点型, 它是 3.1
略去非法字符10
状态机读入字符1之后, 状态从0转换为1
行 4, 解析到了一个整型, 它是 1
略去非法字符120
状态机读入字符2之后, 状态从0转换为1
行 4, 解析到了一个整型, 它是 2
略去非法字符10
状态机读入字符1之后, 状态从0转换为1
行 5, 解析到了一个整型, 它是 1
略去非法字符97
略去非法字符10
状态机读入字符3之后, 状态从0转换为1
状态机读入字符e之后, 状态从1转换为5
状态机读入字符4之后, 状态从5转换为4
行 6, 解析到了一个浮点型, 它是 3e4
略去非法字符-1

可见, 该状态机很棒！！！ 我自己实现了.