前言
编译技术这行当，入门就得先过分词这一关，而分词又离不开有限状态机。说白了，状态机搞不明白，编译的大门就进不去。上一篇文章我们聊了状态机的实现原理，还顺带介绍了状态模式这种实现方式。不过话说回来，光看原理是远远不够的，编程这东西，得动手练。所以今天咱们直接进入实战，用状态机解决一个通信领域里的经典问题——在通讯序列中查找“帧头”。
帧头是什么？就是数据帧开始的那个特殊标记，比如二进制串中的“1011”。接收端只有快速、准确地找到这个帧头，才能知道数据从哪儿开始，然后才能正确解析后续内容。如果帧头被误读或者漏掉，整个数据帧就全乱套了。那么问题来了：有限状态机怎么帮忙干这个活儿？用 Ja vaScript 又如何实现？
有限状态机的经典问题
咱们先看一个具体的例子。在光纤通讯系统中，经常需要在一个很长的二进制串里找到连续的“1011”模式。比如输入：
11110111101111010001010010110100001011011111101011001001010010010111
期望的输出是：
00000010000100000000000000010000000001001000000001000000000000000010
这个输出是什么意思？当输入信号与帧头“1011”匹配时，状态机要输出一个“1”，其他时候输出“0”。而且有一个细节：如果前一个“1011”和后一个“1011”有重叠的比特，比如输入“1011011”，那么输出应该是“0001001”，因为前一个“1011”的最后一个“1”同时也是后一个“1011”的第一个“1”，所以需要输出两个“1”。
要实现这个功能，状态机就是最自然的工具。按照之前学的思路，第一步是定义状态，第二步是设定转换规则。就像上一篇文章里红绿灯的例子，状态是红、绿、黄，转换规则是红转绿、绿转黄、黄转红。对于帧头“1011”，我们可以定义四个状态：
- S1：初始状态，还没匹配到任何部分
- S2：已经匹配到了第一个“1”
- S3：已经匹配到了“10”
- S4：已经匹配到了“101”
然后设定状态转换规则（理想情况，只考虑匹配路径）：
- S1 输入 1 → 输出 0，切换到 S2
- S2 输入 0 → 输出 0，切换到 S3
- S3 输入 1 → 输出 0，切换到 S4
- S4 输入 1 → 输出 1，切换到 S2（注意这里匹配完成，但下一个字符可能又是新的开始，所以回到 S2）
根据这个规则，我们可以写出第一版代码：
// 定义状态
const State = {
'S1': 1,
'S2': 2,
'S3': 3,
'S4': 4
}
// 用于追踪当前的状态，初始状态被设置为 S1
let state = State.S1
// 用于存储状态机在处理输入序列时产生的输出
const output = []
// parse 函数接收一个字符 c 作为输入，并根据当前状态和输入字符来决定下一步的状态和输出
function parse(c) {
switch(state) {
case State.S1: {
if (c === '1') {
// 在 S1 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S2
output.push('0')
state = State.S2
}
break
}
case State.S2: {
if (c === '0') {
// 在 S2 状态下，如果输入是 '0'，则输出 '0'，并将状态切换到 S3
output.push('0')
state = State.S3
}
break
}
case State.S3: {
if (c === '1') {
// 在 S3 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S4
output.push('0')
state = State.S4
}
break
}
case State.S4: {
if (c === '1') {
// 在 S4 状态下，如果输入是 '1'，则输出 '1'，并将状态切换到 S2
output.push('1')
state = State.S2
}
break
}
}
}
// 输入序列
const input = '1011'
for (let i = 0; i < input.length; i ++) {
// 输入序列 '1011' 被逐个字符地传递给 parse 函数进行处理
parse(input[i])
}
// 输出结果
console.log('输出：', output.join(''))
一个状态机最核心的三要素：拥有多种状态（即变量 State）、当前处于其中一种状态（即变量 state）、状态切换（即 parse 函数）。上面的代码实现了这三个要素，输入“1011”就会输出“0001”，符合预期。但问题也很明显——它只处理了匹配路径，对于不匹配的情况（比如在 S1 输入 0，在 S2 输入 1 等）完全没有处理。而且 State、state、output 都是全局变量，容易造成命名冲突。咱们得想办法改进。
通过面向对象编程（OOP）迭代状态机
其实状态机的实现跟发布订阅模式一样，没有固定的代码结构。上面那种过程式写法虽然简单，但全局变量满天飞，维护起来很头疼。面向对象编程（OOP）可以把数据（属性）和操作数据的方法封装在一起，形成一个整体，避免全局污染。咱们用 OOP 重新实现一下：
// 定义状态
const State = {
'S1': 1,
'S2': 2,
'S3': 3,
'S4': 4
}
class StateMachine {
// 用于追踪当前的状态，初始状态被设置为 S1
state = State.S1
// 用于存储输入字符序列的属性，在 parse 方法中，输入字符串被赋值给这个属性
buffer = ''
// 用于追踪 buffer 中当前正在处理的字符的索引
index = 0
// 用于存储状态机在处理输入序列时产生的所有输出的数组
output = []
constructor() {}
// parse 函数接收一个字符 c 作为输入，并根据当前状态和输入字符来决定下一步的状态和输出
parse(input) {
this.buffer = input
while (this.index < this.buffer.length) {
const c = this.buffer[this.index]
switch(this.state) {
case State.S1: {
if (c === '1') {
// 在 S1 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S2
this.output.push('0')
this.state = State.S2
}
break
}
case State.S2: {
if (c === '0') {
// 在 S2 状态下，如果输入是 '0'，则输出 '0'，并将状态切换到 S3
this.output.push('0')
this.state = State.S3
}
break
}
case State.S3: {
if (c === '1') {
// 在 S3 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S4
this.output.push('0')
this.state = State.S4
}
break
}
case State.S4: {
if (c === '1') {
// 在 S4 状态下，如果输入是 '1'，则输出 '1'，并将状态切换到 S2
this.output.push('1')
state = State.S2
}
break
}
}
this.index++
}
}
}
// 实例化状态机
const stateMachine = new StateMachine()
// 输入特定序列
stateMachine.parse('1011')
// 输出
console.log(stateMachine.output.join(''))
通过这个迭代，我们更好地理解了 OOP 在 Ja vaScript 中的作用——核心就是封装性。一段段功能可以用函数封装，而一组相关的函数又可以用类封装，让代码更模块化、更容易理解和维护。一旦封装成类，还能在多个项目里复用，不用每次都重写一遍。
状态转换表的引入
不过上面这段代码还是不完整——它只处理了匹配路径，对于不匹配的情况压根没管。比如在 S1 状态下输入 0，应该怎么办？在 S2 状态下输入 1，又该怎么办？要想把所有情况都覆盖，得先把所有状态之间的转换关系梳理清楚。最直观的方式就是用一张表：
| 当前状态 | 已经匹配 | 输入 | 下一个状态 | 输出 |
|---|---|---|---|---|
| S1 | 0 | S1 | 0 | |
| S1 | 1 | S2 | 0 | |
| S2 | 1 | 0 | S3 | 0 |
| S2 | 1 | 1 | S2 | 0 |
| S3 | 10 | 0 | S1 | 0 |
| S3 | 10 | 1 | S4 | 0 |
| S4 | 101 | 0 | S3 | 0 |
| S4 | 101 | 1 | S2 | 1 |
这张表把每一种当前状态和每一种输入都考虑到了，一目了然。总结一下就是：
- S1（什么也没匹配到）：输入0 → 输出0，保持S1；输入1 → 输出0，切换到S2。
- S2（已匹配到1）：输入0 → 输出0，切换到S3；输入1 → 输出0，保持S2。
- S3（已匹配到10）：输入0 → 输出0，切换到S1；输入1 → 输出0，切换到S4。
- S4（已匹配到101）：输入0 → 输出0，切换到S3；输入1 → 输出1，切换到S2。
除了用表格，还可以用画图的方式来表示。
状态机经典图示
下面这张图就是“1011”帧头状态机的经典图示：
每个圆圈代表一个状态（S1、S2、S3、S4），启动状态（S1）用两个圆圈表示。箭头从当前状态指向下一个状态，表示转换方向。箭头上的标注 输入/输出 表示：左边是输入，右边是输出。比如从 S1 到 S2 的箭头标注 1/0，意思是输入 1 输出 0。
完善状态机代码
根据上面的状态转换表（以及图示），我们就能写出完整的状态机代码了：
// 定义状态
const State = {
'S1': 1,
'S2': 2,
'S3': 3,
'S4': 4
}
class StateMachine {
// 用于追踪当前的状态，初始状态被设置为 S1
state = State.S1
// 缓冲区内容
buffer = ''
// 正在查看的缓冲区内的索引
index = 0
// 用于存储状态机在处理输入序列时产生的输出
output = []
constructor() {}
// parse 函数接收一个字符 c 作为输入，并根据当前状态和输入字符来决定下一步的状态和输出
parse(input) {
this.buffer = input
while (this.index < this.buffer.length) {
const c = this.buffer[this.index]
switch(this.state) {
case State.S1: {
if (c === '1') {
// 在 S1 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S2
this.output.push('0')
this.state = State.S2
} else if (c === '0') {
// 在 S1 状态下，如果输入是 '0'，则输出 '0'，并将状态切换到 S1
this.output.push('0')
this.state = State.S1
}
break
}
case State.S2: {
if (c === '0') {
// 在 S2 状态下，如果输入是 '0'，则输出 '0'，并将状态切换到 S3
this.output.push('0')
this.state = State.S3
} else if (c === '1') {
// 在 S2 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S2
this.output.push('0')
this.state = State.S2
}
break
}
case State.S3: {
if (c === '1') {
// 在 S3 状态下，如果输入是 '1'，则输出 '0'，并将状态切换到 S4
this.output.push('0')
this.state = State.S4
} else if (c === '0') {
// 在 S3 状态下，如果输入是 '0'，则输出 '0'，并将状态切换到 S1
this.output.push('0')
this.state = State.S1
}
break
}
case State.S4: {
if (c === '1') {
// 在 S4 状态下，如果输入是 '1'，则输出 '1'，并将状态切换到 S2
this.output.push('1')
this.state = State.S2
} else if (c === '0') {
// 在 S4 状态下，如果输入是 '0'，则输出 '0'，并将状态切换到 S3
this.output.push('0')
this.state = State.S3
}
break
}
}
this.index++
}
}
}
// 实例化状态机
const stateMachine = new StateMachine()
// 输入特定序列
stateMachine.parse('11110111101111010001010010110100001011011111101011001001010010010111')
// 输出 00000010000100000000000000010000000001001000000001000000000000000010
console.log(stateMachine.output.join(''))
运行结果和预期完全一致。现在不管输入什么，状态机都能正确处理了。
有限状态机与编译技术的联系
聊完了实战，咱们再回头看看状态机和编译技术的关系。在编译过程的词法分析阶段，编译器需要把源代码字符串分解成一个个标记（token）。这个过程本质上就是一个有限状态机在逐字符处理输入流，根据当前状态和输入字符转移到下一个状态，同时输出对应的标记。跟我们找帧头“1011”的例子完全一样——源代码就是那个长串，标记就是输出的“0001”。只不过编译器的输出是 token 或者 AST（抽象语法树），而不是简单的二进制串。
到了语法分析阶段，虽然状态机不像词法分析那么直观，但编译器内部往往也采用了类似的状态机逻辑，通过维护一个状态栈或状态表来跟踪当前语法结构，判断下一步该往哪走。
两者还有一个共同点：都擅长分解复杂性。编译器把源代码拆成词法、语法等多个阶段，每个阶段只处理一个小问题。状态机也是把系统行为分解成有限个状态，状态之间用明确的转换规则连接，从而让复杂系统的建模和控制变得简单。
最后，编译技术和有限状态机都强调基于状态的逻辑处理。编译器在处理源代码时，会根据当前所处的分析阶段（词法、语法等）来决定下一步操作。状态机则通过维护当前状态，并根据输入事件触发转移和动作。这种思想上的契合，让状态机在编译领域占据了不可替代的位置。
总结
这篇文章围绕“在通讯序列中查找帧头‘1011’”这个经典问题，逐步深入讲解了状态机的实现、优化和应用。主要涵盖了以下几点：
- 回顾了状态机的基本原理，包括状态定义、转换规则，以及它在编译技术和通信领域的重要性。
- 通过“1011”帧头查找的例子，展示了如何用状态机解决问题，并给出了第一版 Ja vaScript 实现。
- 用面向对象编程（OOP）迭代了状态机代码，解决了全局变量污染的问题，让代码更模块化。
- 引入了状态转换表，清晰列出了所有状态、输入、下一个状态和输出的对应关系。
- 介绍了状态机经典图示，用圆圈和箭头直观表达状态转换。
- 根据状态转换表完善了代码，处理了所有输入情况，确保输出正确。
- 讨论了有限状态机与编译技术的紧密联系，尤其是词法分析和语法分析阶段的应用，以及两者在分解复杂性和基于状态逻辑处理上的共性。
理论结合实战，希望能帮助大家真正掌握状态机在编程中的应用。搞懂了这些，再去看编译原理，路子就顺多了。
