您现在的位置是：首页 > 文章详情

状态机详解（未完待续）

日期：2020-11-26点击：485收藏

什么是状态机（FSM）？

状态机（Finite State Machine）是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。

字面上讲它是用来管理状态的，状态数量是有限的，并且可以自动执行，即给定一个当前状态与输入，可以明确得到输出状态，当然他不是一个机器，而是一个数学模型。

它有四个概念：

State（状态）：一个状态机至少要包含两个状态，并且状态个数是有限的；
Event（事件）：执行某个操作的触发条件或口令；
Action（动作）：事件发生以后要执行的动作，在我们编程中一般就代指一个函数；
Transition（变换）：从一个状态变到另一个状态。

其他的理解：状态机可归纳为4个要素，即现态、条件、动作、次态。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：

现态：是指当前所处的状态。
条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。
次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。

状态机能用来做什么

正则表达式引擎

正则表达是引擎是一个典型的状态机的栗子，它分为非确定有限状态自动机NFA(Nondeterministic Finite Automaton)与确定有限状态自动机DFA(Deterministic Finite Automaton)两种，都通通过状态机的概念来实现的。

简单实现一个关于ab|bc的正则匹配：

function match(string) { let state = start; for (let s of string) { console.log('s==>',s); state = state(s); } return state === end; } function start(s) { if (s === 'a') { return foundB1; } if (s === 'b') { return foundB2; } } function end(s) { return end; } function foundB1(s) { if (s === 'b') { return end; } return start(s); } function foundB2(s) { if (s === 'c') { return end; } return start(s); } const string = 'ab'; console.log(match(string));

KMP算法（Knuth–Morris–Pratt algorithm）

以字符串"BBC ABCDAB ABCDABCDABDE"与搜索词"ABCDABD"进行举例

移动位数 = 已匹配的字符数 - 对应的部分匹配值

Promise

手撸一个Promise的实现：

function Promise(executor) { var _this = this this.state = 'PENDING'; //状态 this.value = undefined; //成功结果 this.reason = undefined; //失败原因 this.onFulfilled = [];//成功的回调 this.onRejected = []; //失败的回调 function resolve(value) { if(_this.state === 'PENDING'){ _this.state = 'FULFILLED' _this.value = value _this.onFulfilled.forEach(fn => fn(value)) } } function reject(reason) { if(_this.state === 'PENDING'){ _this.state = 'REJECTED' _this.reason = reason _this.onRejected.forEach(fn => fn(reason)) } } try { executor(resolve, reject); } catch (e) { reject(e); } } Promise.prototype.then = function (onFulfilled, onRejected) { if(this.state === 'FULFILLED'){ typeof onFulfilled === 'function' && onFulfilled(this.value) } if(this.state === 'REJECTED'){ typeof onRejected === 'function' && onRejected(this.reason) } if(this.state === 'PENDING'){ typeof onFulfilled === 'function' && this.onFulfilled.push(onFulfilled) typeof onRejected === 'function' && this.onRejected.push(onRejected) } };

HTTP协议

简单封装一个http请求的响应解析器：

const net = require('net'); const images = require('images'); const parser = require('./parser'); const render = require('./render'); class Request { constructor(options) { this.method = options.method || 'GET'; this.host = options.host; this.port = options.port || 80; this.path = options.path || '/'; this.body = options.body || {}; this.headers = options.headers || {}; if (!this.headers['Content-Type']) { this.headers['Content-Type'] = 'application/x-www-form-urlencoded'; } if (this.headers['Content-Type'] == 'application/json') { this.bodyText = JSON.stringify(this.body); } else if (this.headers['Content-Type'] === 'application/x-www-form-urlencoded') { this.bodyText = Object.keys(this.body).map(key => `${key}=${encodeURIComponent(this.body[key])}`).join('&'); } this.headers['Content-Length'] = this.bodyText.length; } send(connection) { return new Promise((resolve, reject) => { // do something let parser = new ResponseParser(); if (connection) { connection.write(this.toString()); } else { connection = net.createConnection({ host: this.host, port: this.port }, () => { connection.write(this.toString()); }); } connection.on('data', data => { parser.receive(data.toString()); console.log(parser.isFinished,'isFinished'); if (parser.isFinished) { resolve(parser.response); connection.end(); } }); connection.on('error', err => { reject(err); connection.end(); }); }); } toString() { return `${this.method} ${this.path} HTTP/1.1\r ${Object.keys(this.headers).map(key => `${key}: ${this.headers[key]}`).join('\r\n')}\r \r ${this.bodyText}`; } }; class ResponseParser { constructor() { this.WAITING_STATUS_LINE = 0; this.WAITING_STATUS_LINE_END = 1; this.WAITING_HEADER_NAME = 2; this.WAITING_HEADER_SPACE = 3; this.WAITING_HEADER_VALUE = 4; this.WAITING_HEADER_LINE_END = 5; this.WAITING_HEADER_BLOCK_END = 6; this.WAITING_BODY = 7; this.current = this.WAITING_STATUS_LINE; this.statusLine = ''; this.headers = {}; this.headerName = ''; this.headerValue = ''; this.bodyParser = null; } get isFinished() { return this.bodyParser && this.bodyParser.isFinished; } get response() { this.statusLine.match(/HTTP\/1.1 ([0-9]+) ([\s\S]+)/); return { statusCode: RegExp.$1, statusText: RegExp.$2, headers: this.headers, body: this.bodyParser.content.join('') } } receive(string) { for (let i = 0; i < string.length; i++) { this.receiveChar(string.charAt(i)); } } receiveChar(char) { if (this.current === this.WAITING_STATUS_LINE) { if (char === '\r') { this.current = this.WAITING_STATUS_LINE_END; } else { this.statusLine += char; } } else if (this.current === this.WAITING_STATUS_LINE_END) { if (char === '\n') { this.current = this.WAITING_HEADER_NAME; } } else if (this.current === this.WAITING_HEADER_NAME) { if (char === ':') { this.current = this.WAITING_HEADER_SPACE; } else if (char === '\r') { this.current = this.WAITING_HEADER_BLOCK_END; if (this.headers['Transfer-Encoding'] === 'chunked') { this.bodyParser = new TrunkedBodyParser(); } } else { this.headerName += char; } } else if (this.current === this.WAITING_HEADER_SPACE) { if (char === ' ') { this.current = this.WAITING_HEADER_VALUE; } } else if (this.current === this.WAITING_HEADER_VALUE) { if (char === '\r') { this.current = this.WAITING_HEADER_LINE_END; this.headers[this.headerName] = this.headerValue; this.headerName = ''; this.headerValue = ''; } else { this.headerValue += char; } } else if (this.current === this.WAITING_HEADER_LINE_END) { if (char === '\n') { this.current = this.WAITING_HEADER_NAME; } } else if (this.current === this.WAITING_HEADER_BLOCK_END) { if (char === '\n') { this.current = this.WAITING_BODY; } } else if (this.current === this.WAITING_BODY) { this.bodyParser.receiveChar(char); } } } class TrunkedBodyParser { constructor() { this.WAITING_LENGTH = 0; this.WAITING_LENGTH_LINE_END = 1; this.READING_TRUNK = 2; this.WAITING_NEW_LINE = 3; this.WAITING_NEW_LINE_END = 4; this.length = 0; this.content = []; this.isFinished = false; this.current = this.WAITING_LENGTH; } receiveChar(char) { if (this.current === this.WAITING_LENGTH) { if (char === '\r') { if (this.length === 0) { this.isFinished = true; } this.current = this.WAITING_LENGTH_LINE_END; } else { this.length *= 16; this.length += parseInt(char, 16); } } else if (this.current === this.WAITING_LENGTH_LINE_END) { if (char === '\n') { this.current = this.READING_TRUNK; } } else if (this.current === this.READING_TRUNK) { this.content.push(char); this.length--; if (this.length === 0) { this.current = this.WAITING_NEW_LINE; } } else if (this.current === this.WAITING_NEW_LINE) { if (char === '\r') { this.current = this.WAITING_NEW_LINE_END; } } else if (this.current === this.WAITING_NEW_LINE_END) { if (char === '\n') { this.current = this.WAITING_LENGTH; } } } } void async function() { let request = new Request({ method: 'POST', host: '127.0.0.1', port: 8088, path: '/', headers: { ['X-Foo2']: 'customed' }, body: { name: 'test' } }); let response = await request.send(); let dom = parser.parseHTML(response.body); let viewport = images(800, 600); render(viewport, dom.children[0].children[3].children[1].children[3]); viewport.save("viewport.jpg"); console.log(JSON.stringify(dom, null, ' '), 'dom'); }();

HTML解析

在html标准里边，html的词法描述就是按照状态机的概念来进行描述的，详细;

设计模式--状态模式

允许一个对象在其内部状态改变时改变它的行为，对象看起来似乎修改了它的类。其别名为状态对象(Objects for States)，状态模式是一种对象行为型模式。

设计模式中有个状态模式，还有一个策略模式，两者有点相似，又有些不同，它们的相同点是，都有一个上下文、一些策略类或者状态类，上下文把请求委托给这些类来执行。它们之间的区别是策略模式中的各个策略类之间是平等又平行的，它们之间没有任何关系，所以客户必须熟知这些策略类的作用，以便客户自己可以随时主动切换算法。但是在状态模式中，状态和状态对应的行为早已被封装好，状态之间的切换也早就被规定，“改变行为”这件事发生在状态模式的内部，对于客户来说，不需要了解这些细节。

讲的多都不如直接看代码，那么我们通过栗子来理解一下状态模式的应用：

一个比较常见的场景栗子电灯只有一个开关，但是它的表现是：第一次按下打开弱光，第二次按下打开强光，第三次才是关闭电灯。

未使用状态模式：

class Light { construct () { this.state = 'off' this.button = null } // 创建一个button负责控制电灯的开关 init () { const button = document.createElement('button') this.button = document.body.appendChild(button) this.button.innerHTML = '开关' this.button.onclick = () => { this.buttonWasPressed() } } buttonWasPressed () { if (this.state === 'off') { console.log('弱光') this.state = 'weak' } else if (this.state === 'weak') { console.log('强光') this.state = 'strong' } else if (this.state === 'strong') { console.log('关灯') this.state = 'off' } } } const light = new Light() light.init()

使用状态模式的代码：

class OffLightState { construct (light) { this.light = light } buttonWasPressed () { console.log('弱光') this.light.setState(this.light.weakLightState) } } class WeakLightState { construct (light) { this.light = light } buttonWasPressed () { console.log('强光') this.light.setState(this.light.strongLightState) } } class StrongLightState { construct (light) { this.light = light } buttonWasPressed () { console.log('关灯') this.light.setState(this.light.offLightState) } } // light类 class Light { construct () { this.offLightState = new OffLightState(this) this.weakLightState = new WeakLightState(this) this.strongLightState = new StrongLightState(this) this.currentState = this.offLightState // 初始化电灯状态 this.button = null } init () { const button = document.createElement('button') this.button = document.body.appendChild(button) this.button.innerHTML = '开关' this.button.onclick = () => { this.currentState.buttonWasPressed() } } setState (newState) { this.currentState = newState } } const light = new Light() light.init()

此外，状态机的概念还用于语言的词法分析，语法分析，网络协议，游戏设计，客服机器人等各个方面，是我们编程中一个很重要的概念

推荐工具：