有限状态机在词法分析中的应用
概念
有限状态自动机（FSM “finite state machine” 或者FSA “finite state automaton” ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。
有限状态机在计算机领域的应用非常多，本篇文章主要介绍下在词法解析方面的应用。
应用
将字符串
100+200-300
转化成如下tokens
1
2
3
4
5
6
7
| [
{ type: 'Numeric', value: '100' },
{ type: 'Punctuator', value: '+' },
{ type: 'Numeric', value: '200' },
{ type: 'Punctuator', value: '-' },
{ type: 'Numeric', value: '300' }
]
|
案例一：
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
| // 四则运算字符串
const inputStr = '100+200-300';
// 匹配数字的正则
const NumReg = /[0-9]/
// 匹配标点符号的正则规则
const PunctuatorReg = /[\+\-\*\/]/
// 最终输出的所有tokens合集
const tokens = []
// 当前状态机中正在处理的token
let currentToken = {}
/**
* 词法分析函数
* @param {*} inputStr
* @returns tokens
*/
function stateMachine(inputStr) {
// 定义状态机的初始状态判断函数
let state = start
// 依次迭代输入的字符串
// while(inputStr) {
// state = state(inputStr[0]);
// inputStr = inputStr.slice(1);
// }
inputStr.split("").forEach(char => {
// 此处的char是每一个字符
// 调用state函数 并且传入char
state = state(char)
})
// 遍历结束后仍然需要发送一次最后
tokens.push(currentToken)
return tokens;
}
/**
* 状态机初始函数
* @param {*} char 输入的字符
* @return {*}
*/
function start (char) {
if(NumReg.test(char)) {
// 首个输入的char是数字 初始化token为numeric
currentToken = { type: 'Numeric', value: char }
// 返回的是一个nunmer的处理函数
return numeric
}else if (PunctuatorReg.test(char)) {
// 首个输入的char是标点符号 初始化current为punctuator
currentToken = { type: 'Punctuator', value: char }
// 返回的是一个punctuator的处理函数
return punctuator
}
}
// 数字处理函数
function numeric(char) {
if(NumReg.test(char)) {
// 如果当前输入是数字 不分词 连续累加value值
currentToken.value += char
// 返回numeric函数赋给state
return numeric
}else if (PunctuatorReg.test(char)) {
// 如果是标点符号 分词
// 如果当前输入的标点符号 进行分词
// 首先将旧的token输入到tokens中
emitToken(currentToken)
// 修改当前token
currentToken = { type: 'Punctuator', value: char }
// 返回punctuator处理函数
return punctuator
}
}
// 标点符号状态处理函数
function punctuator(char) {
// 无论如何都要发射 因为标点符号在分词阶段不会被拼接起来
emitToken(currentToken)
if (NumReg.test(char)) {
currentToken = { type: 'Numeric', value: char }
return numeric
} else if (PunctuatorReg.test(char)) {
currentToken = { type: 'Punctuator', value: char }
return punctuator
}
return punctuator
}
// 将token放入tokens中
function emitToken(token) {
// 重制 currentToken
currentToken = { type: '', value: '' }
// 将上一次传入的token参数保存到最终输入的tokens中
tokens.push(token)
}
console.log(stateMachine(inputStr));
|
案例二：
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
| // 四则运算字符串
const inputStr = '100+200-300';
// 匹配数字的正则
const NumReg = /[0-9]/
// 匹配标点符号的正则规则
const PunctuatorReg = /[\+\-\*\/]/
// 最终输出的所有tokens合集
const tokens = []
// 当前状态机中正在处理的token
let currentToken = '';
let type = 'start';
function start(char, i, str) {
if( type==='start'&&NumReg.test(char)) {
type = 'Numberic';
currentToken += char;
}else if(type==='Numberic'&&NumReg.test(char)) {
currentToken += char;
}else if(type==='Numberic'&&PunctuatorReg.test(char)) {
tokens.push({
type: 'Numberic',
value: currentToken
});
type = 'Punctuator';
currentToken = char;
}else if(type==='Punctuator'&&NumReg.test(char)) {
type = 'Numberic';
tokens.push({
type: 'Punctuator',
value: currentToken
});
currentToken = char;
}
if(type==='Numberic'&&i===(str.length-1)) {
tokens.push({
type: 'Numberic',
value: currentToken
});
currentToken = '';
}
}
function stateMachine(str) {
for(let i=0; i<str.length; i++) {
start(str[i], i, str);
}
return tokens;
}
console.log(stateMachine(inputStr));
|
上面两个案例结果一样，但是过程不同。案例一的状态变化是以返回函数的形式，对代码进行了抽象解耦。案例二有点面向过程的写法，代码冗余，逻辑复杂的话，肯定是第一种方法好。
总结
本篇文章只是简单的介绍下，有限状态机在编译的词法分析阶段的应用。