欢迎点击「算法与编程之美」↑关注我们！
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列博客。
DOM(Document Object Model)即文档对象模型，是一种非常重要的数据结构，用途非常广泛。
对于浏览器的渲染引擎来说，需要将html 字符串转换成 DOM 树，再转换成渲染树，最后才进行渲染。
对于数据采集来说，经常需要做的是解析已经下载的 html 文档，而这种解析工作的前提是要生成 html 文档的 DOM 树，然后才能解析。
本系列博客将为大家介绍一种基于状态机的 DOM树生成技术，从最初的 html 文档如何一步步生成最终的 DOM 树。
本讲我们将为大家介绍状态机的基本知识。
1 状态机介绍
图1- 1 状态机示例图
我们从上述一个简单的示例来介绍什么是状态机，图中四个圆圈分别表示四个状态即状态0，状态1，状态2，状态3。其中状态0表示起始状态，状态2、状态3表示终止状态。起始状态表示任务开始的地方，终止状态将不再接受任何输入。
状态0：当用户输入字符'a'的时候，将进入状态1，其他字符将进入状态3。
状态1：用户可以不停的输入字符'b'，但是会一直处于状态1，当用户输入字符'a'的时候，将进入状态2，其他字符进入状态3。
状态2：终止状态，不再接受任何输入。
状态3：终止状态，不再接受任何输入。
上面给大家介绍的就是状态机，在状态机中有多个状态，一般情况下，有一个起始状态，多个中间状态和终止状态。对于每一个状态可以接受不同的输入，或维持在当前状态，或进入下一个状态。
上面给大家介绍的这个状态机，其实功能很简单，这个状态机可以接受任何abbbb*a模式的字符串如:aba,abba, abbba等。
状态机的用途非常的广泛，不仅在正则表达式，编译器等众多领域发挥重要作用。
2 状态机实现
有了上述的状态机基本知识后，本节将为大家介绍如何用 Java 语言实现状态机。
要想实现上述状态机，我们有以下三个任务需要完成：
（1）对字符串输入的控制。
我们需要定义一个类能够实现非常方便的控制整个输入的字符串，每次移动一个字符。
这个类非常的简单，如下所示：
public class CharacterReader {private String content;private int pos;public CharacterReader(String content) {this.content = content;pos = 0;public char consume() {return content.charAt(pos++);
对于给定的任意一个字符串如"abbba"，我们保存在 content 属性中，再定义一个 pos 属性，标记当前正在处理的是哪一个字符位置，处理完一个字符后，位置后移一位，初始位置为0。
CharacterReaderreader = newCharacterReader("abbba");
(2)各种状态的定义。
在本例中，我们有四个状态，所以需要定义四个状态类StateZero, StateOne, StateTwo,StateThree。
每一个状态类的处理逻辑都是类似的，基本的业务处理逻辑为：
接受一个字符，然后判断是否进行状态转移。
所以我们可以抽象一个状态基类 State，在基类中可以定义一个共同的抽象方法，如下：
public enum State {abstract void read(StateControllercontroller, CharacterReader reader);
这里面我们使用是枚举类型来定义基类 State，并且定义了一个抽象方法 read，该方法有两个参数：
第一个是状态控制逻辑controller，通过 controller我们可以快速的转移状态；
第二个是输入字符串的一个封装，通过consume方法可以快速的得到当前字符。
接下来我们介绍 StateZero 的实现：
StateZero {@Overridevoid read(StateController controller,CharacterReader reader) {char ch = reader.consume();switch (ch) {case 'a':StateOne);break;default:StateThree);break;
上述代码非常容易理解，根据第一节的状态转换图，我们知道，在状态0的时候，当输入字符'a'就转移到状态1，其他字符则转移到状态3。所以大家看到上述代码非常的简单易懂。
StateOne和 StateZero 类似，不再赘述。接下来介绍终止状态的实现。
StateTwo {@Overridevoid read(StateController controller, CharacterReaderreader) {true);out.println("Match!");StateThree{@Overridevoid read(StateController controller,CharacterReader reader) {true);out.println("UnMatch!");
状态2和3都是终止状态，不再接受任何的输入，因此直接将 controller 的 terminated 设置为true 即可。
(3)状态控制逻辑。
这个任务是我们状态机实现的核心部分，也是最精彩的部分。我们通过定义一个状态控制逻辑类StateController 来控制所有的流程。
public class StateController {private CharacterReader reader;private State state = State.StateZero;
private boolean isTerminated = false; public StateController(CharacterReader reader) {this.reader = reader;
// 将当前状态转移到新的状态public void transition(State state){this.state = state;public void run() {while (!isTerminated) {state.read(this, reader);public void setTerminated(boolean terminated) {isTerminated = terminated;
state属性持有当前状态机的状态，初始状态为 StateZero，isTerminated 属性表示当前状态机是否已经进入终止状态。
核心代码是：
while (!isTerminated) {state.read(this, reader);
}
不停的检测状态机当前的状态是否处于终止状态，如果不是则不停的从 reader 接受输入字符，进入状态机。
最后是测试代码了：
public class StateTest {public static void main(String[] args) {new CharacterReader("abbba");new StateController(reader);
综上，已经完成了一个状态机的设计，简单总结就是三个：输入控制，各种状态类定义，状态控制逻辑。
3 总结
本文通过一个简单的案例向大家介绍了状态机的基本知识，并给出了设计状态机的基本思路和相关代码，为后续讲解基于状态机的DOM 树的生成打好基础。
本文所有代码可在以下 git 库中 day01模块中找到，git 地址为：
https://gitee.com/gschen/sctu-treebuilder.git
欢迎持续关注“算法与编程之美”微信公众号，了解更多。
