一种基于状态机的 DOM 树生成技术（2）

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列博客。

在上一篇一种基于状态机的 DOM 树生成技术(1)我们给大家介绍了状态机的基本概念、设计思路以及基于Java语言的实现，希望大家能够了解相关知识点。状态机是我们后续介绍DOM树生成的关键技术，后面几篇博客都将基于状态机来实现。所以请大家务必掌握，如果还有不清楚的地方可以阅读之前的文章，也非常欢迎大家关注微信公众号，及时了解最新文章。

首先我们还是来回顾一下我们的任务，给定一个HTML文件，生成该文件的DOM树。一个HTML文件即一段采用HTML规则编写的字符串，如"

hello

"。

那么如何根据这样的一段字符串生成DOM树呢？

1分词

我们称第一阶段为分词，要想最终生成一颗DOM树，我们并不是一个字符一个字符的处理，而是将HTML字符串首先进行分词，然后再一个分词一个分词的处理。

我们定义以下类型的分词，称每一个分词为Token。

StartTag：开始标签如。

EndTag：结束标签如。

Character：StartTag和EndTag之间的内容如hello。

EOF:结束标记。

针对这个字符串"

hello

"，我们可以得到以下的分词：

StartTag:

StartTag:

StartTag:

Character:hello

EndTag:

EndTag:

EndTag:

现在我们已经明确了要达到什么目标，那么接下来如何实现将HTML字符串转化为一个个的分词呢？

2利用状态机实现分词

在上一篇博客我们给大家介绍了状态机的基本知识，本节我们将介绍一种基于状态机的分词技术。

上图为实现第一节分词而设计的一个状态机，这个状态机屏蔽了很多错误处理环节，目的是为了让我们的描述更加简洁，让大家能够更加关注核心问题。我们来看一下这个状态机是如何设计的。

DATA:起始状态。

当输入字符为'-1'表示已经到达字符串的结尾，此时识别到一个分词EOF。

当输入字符为'

输入字符为其他字符时，此时识别到一个分词Character。

TagOpen:

当输入字符为'/'进入到EndTagOpen状态。

检测当前字符是否为字母，如果是则进入TagName。

EndTagOpen:

检测当前字符是否为字母，如果是则进入TagName。

TagName:

该状态将一次性读取所有字母，直到遇到'/'或'>'为止。

当下一个输入字符为'>'，此时已经识别到一个HTML标签，并将进入到DATA。

接下来我们就将以一个实例来描述状态机的运行过程。

hello

当前输入为'

hello

TagOpen检测到下一个字符为字母'h'，进入TagName。

TagName一次性读取所有的字母"html"，此时识别到一个StartTag，并做token识别完成标记。下一个输入为'>'，进入DATA。

以上就是识别一个StartTag的流程。body和p类似，不再赘述。

hello

上述流程已经识别完成了三个StartTag分词，分别是、和< p>。

当前状态为DATA且下一个输入字符为'h'，一次性读取所有的字母'hello'。此时识别到一个分词Character，并做分词结束标记。

hello

当前状态为DATA且下一个输入字符为'

hello

当前状态为TagOpen，且下一个输入字符为'/'，进入EndTagOpen，当前标签类型为EndTag。

检测到下一个字符为字母，故进入TagName。

hello

TagName状态下不停的读取字母。当遇到字符'>'，标记这是一个分词，并进入到DATA。

3总结

本文介绍了一种基于状态机的分词技术，设计了一个能够识别HTML字符串中分词的状态机，并对状态机的运行流程做了细致的分析。

后续的DOM树生成将基于上述分词。下一讲我们将介绍如何利用Java语言实现这样的分词技术。如您在博客阅读的过程遇到任何的疑问，欢迎在下方留言。

本文所有代码可在以下git 库中 day02模块中找到，git 地址为：

https://gitee.com/gschen/sctu-treebuilder.git

感兴趣的同学可以提前阅读代码。

欢迎持续关注“算法与编程之美”微信公众号，了解更多。