本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列博客。
在上一篇一种基于状态机的 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
感兴趣的同学可以提前阅读代码。
欢迎持续关注“算法与编程之美”微信公众号,了解更多。
领取专属 10元无门槛券
私享最新 技术干货