使用状态机将HTML解析为AST
大熊•
前言
状态机通过将复杂对象的状态变化进行建模，采取工程化的方式来处理，方便理解与沟通。
状态机定义: finite-state machine 有限自动状态机 是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。有限状态机在很多不同领域被广泛应用，包括电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学。在计算机科学中，有限状态机被广泛用于建模、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。
状态机场景
软件开发中，也会经常遇到状态机的问题。
- 例如用户支付场景下订单的状态，订单状态可能经过这样的变化。
- 词法分析，以及下面我们将要讲到的HTML语法解析。
- 分布式系统中，保证分布式节点状态的一致性方法，分布式系统一致性算法是基于状态机实现的。
类似的场景很多，特别是在对象的状态比较多的时候，就变得越来越难以维护，同时还伴随着并发问题，一不留心就会出错。所以设计一个通用的状态机管理器就很有必要了。
状态机设计
状态机有以下的几个特征：
- 有限的状态，任一时候只能存在一个状态。
- 给定一个状态机，同时给定它的当前状态以及输入，那么输出状态时可以明确的运算出来的。
例如对于自动门，给定初始状态 closed ，给定输入“开门”，那么下一个状态时可以运算出来的。
结合下面自动闸机的状态例子，来理解下状态机。
状态机中有几个术语：state(状态) 、transition(转移) 、action(动作) 、transition condition(转移条件)
-
state(状态) ：一个状态机至少要包含两个状态。将一个系统离散化，可以得到很多种状态，这些状态是有限的。上图：门禁闸机可以划分为开启状态、关闭状态。 -
transition condition(转移条件)/Event（事件）：用于触发状态转移动作的“事件”，条件被满足（输入）就会触发相应动作。对于自动门，“按下开门按钮”就是一个事件。 -
action(动作)：事件发生以后要执行动作。例如事件是“按开门按钮”，动作是“开门”。编程的时候，一个 Action一般就对应一个函数。 -
transition(变换) ：也就是从一个状态变化为另一个状态。一个状态接收一个输入执行了某些动作到达了另外一个状态的过程就是一个transition(变换)。例如“开门过程”就是一个变换。
从定义上看action 和 transition的区别是什么?
Action 强调的是，Event触发后要执行的过程，包含Transiton的过程。
例如：关门动作事件触发后，自动门会检查当前门轨上是否有人，是否进行清理杂物动作，然后滑动门到指定位置。关闭后执行状态变换操作。
如上图，就定义了一个只有opened 和closed两种状态的状态机。当系统处于opened状态，在收到输入“关闭事件”，达到了状态机转移条件，系统就转移到了closed状态，并执行相应的动作，此例有一个进入动作(entry action)，进入closed状态，会执行close door动作
注意事项：
1、避免把某个“程序动作”当作是一种“状态”来处理。那么如何区分“动作”和“状态”？“动作”是不稳定的，即使没有条件的触发，“动作”一旦执行完毕就结束了；而“状态”是相对稳定的，如果没有外部条件的触发，一个状态会一直持续下去。
2、状态划分时漏掉一些状态，导致跳转逻辑不完整。所以在设计状态机时，我们需要反复的查看设计的状态图或者状态表，最终达到一种牢不可破的设计方案。
使用状态机实现HTML解析为AST
解析过程状态机图
下面状态机是简略版，省略的地方是对空格的粗暴处理。
处理方式是：（目的是让HMTL更加规范化）
this.html = this.html.replace(/<!doctype[\s\S]+?>/g, '')
this.html = this.html.replace(/<!--[\s\S]*?-->/g, '')
this.html = this.html.replace(/\n[ ]+/g, '') // 换行后边的空格清除掉
this.html = this.html.replace(/\n/g, '') // 清除掉换行
this.html = this.html.replace(/[ ]+/g, ' ') // 多个空格换成一个
this.html = this.html.replace(/<[\s]+/g, '<') // 尖括号后空白清空
this.html = this.html.replace(/[\s]+>/g, '>') // 尖括号空白清空
this.html = this.html.replace(/[\s]+\/>/g, '/>') // 闭合括号的空白
this.html = this.html.replace(/[\s]*=[\s]*"/g, '="') // 等号前后的空白 【这个地方有点盲目了，针对属性进行处理的】
原因
- 空格存在会导致状态下对空格处理很复杂，尤其是状态转移条件。
- 嘿嘿，个人在使用的使用的时候，空格对我清洗结果影响较小，考虑到ROI问题，没有做精细化处理。
下面是完整的状态机图：
代码实现
class Node {
constructor ({ tag }) {
// tag的名称
this.tag = tag
// 属性
this.attribute = {}
// 节点对应的文本，这里值针对叶子节点
this.text = ''
// 节点的子节点
this.children = []
}
}
// 定义状态
const INIT = 'init'
const TAG_START = 'tagStart'
const ATTRIBUTE_START = 'attributeStart'
const ATTRIBUTE_VALUE = 'attributeValue'
const ATTRIBUTE_END = 'attributeEnd'
const TAG_END = 'tagEnd'
const OPEN_TAG = 'openTag'
const CLOSE_TAG = 'closeTag'
const CLOSE_TAG_START = 'closeTagStart'
const CLOSE_TAG_END = 'closeTagEnd'
const regMap = {
isLetter: /[a-zA-Z0-9]/,
isEmpty: /[\s\n]/
}
const $reg = {}
Object.keys(regMap).forEach(key => {
const reg = regMap[key]
$reg[key] = (s) => reg.test(s)
})
const selfCloseTags = ['meta', 'link', 'br', 'hr', 'img', 'input']
export default class ParseHtml {
constructor (html) {
this.html = html // 不能一股脑儿的全部小写会导致问题
this.status = 'init'
this.index = 0
this.tagStack = []
this.text = ''
this.tagName = ''
this.$reg = $reg
this.node = null
this.currentNode = null
this.attributeName = ''
this.attributeValue = ''
}
// 预处理
preHandle () {
this.html = this.html.replace(/<!doctype[\s\S]+?>/g, '')
this.html = this.html.replace(/<!--[\s\S]*?-->/g, '')
this.html = this.html.replace(/\n[ ]+/g, '') // 换行后边的空格清除掉
this.html = this.html.replace(/\n/g, '') // 清除掉换行
this.html = this.html.replace(/[ ]+/g, ' ') // 多个空格换成一个
this.html = this.html.replace(/<[\s]+/g, '<') // 尖括号后空白清空
this.html = this.html.replace(/[\s]+>/g, '>') // 尖括号空白清空
this.html = this.html.replace(/[\s]+\/>/g, '/>') // 闭合括号的空白
this.html = this.html.replace(/[\s]*=[\s]*"/g, '="') // 等号前后的空白 【这个地方有点盲目了，针对属性进行处理的】
}
// 解析主流程
parse () {
this.preHandle()
for (this.index = 0; this.index < this.html.length; this.index += 1) {
const s = this.html[this.index]
const pre = this.html[this.index - 1]
const next = this.html[this.index + 1]
// console.log(this.index, '-------->', s, next, this.status)
switch (this.status) { // 当前解析状态
case INIT:
this.parseInit(s, pre, next)
break
case TAG_START: // 开始解析标签
this.parseTagStart(s, pre, next)
break
case ATTRIBUTE_START: // 属性开始
this.parseAttributeStart(s, pre, next)
break
case ATTRIBUTE_VALUE: // 进入解析属性阶段
this.parseAttributeValue(s, pre, next)
break
case ATTRIBUTE_END: // 属性标签结束
this.parseAttributeEnd(s, pre, next)
break
case TAG_END: // 里面会处理自闭合标签
this.parseTagEnd(s, pre, next)
break
case OPEN_TAG: // 开标签
this.parseOpenTag(s, pre, next)
break
case CLOSE_TAG_START: // 标签闭合
this.parseCloseTagStart(s, pre, next)
break
case CLOSE_TAG_END:
this.parseCloseTagEnd(s, pre, next)
break
default:
break
}
}
return this.node
}
// 解析初始状态
parseInit (s) {
if (s === '<') {
this.status = TAG_START
}
}
// 解析开始标签
parseTagStart (s, pre, next) {
const handle = (isSelfCloseTag) => { // 新的节点开始
if (!this.node) { // 创建新节点，可能是根节点
this.node = new Node({ tag: this.tagName })
this.currentNode = this.node
this.parentNode = null
} else {
this.parentNode = this.currentNode // 当前节点变为父节点
this.currentNode = new Node({ tag: this.tagName }) // 当前标签名
this.parentNode.children.push(this.currentNode)
}
this.tagStack.push(this.currentNode) // 标签开始的时候
}
if (this.$reg.isLetter(s)) { // 是否为合法字符
// 标签名
this.tagName += s // 获得标签名
} else if (this.$reg.isEmpty(s) && this.$reg.isLetter(next)) { // 当前是空格，后边是字符，标签解析到
// 解析属性
handle()
this.status = ATTRIBUTE_START
}
if (next === '>') { // <span> 可能在解析阶段就直接结束了
// 开始标签结尾
handle()
this.status = TAG_END
}
}
// 开始解析属性
parseAttributeStart (s, pre, next) {
if (s !== '=') { // 获得属性名
this.attributeName += s
}
// 一个属性结束 class="blue-button"
if (next === ' ' || next === '>' || (next === '/' && this.html[this.index + 2] === '>')) {
this.currentNode.attribute[this.attributeName] = this.attributeValue
this.attributeName = ''
this.attributeValue = ''
}
if (next === ' ') { // 属性结束
this.status = ATTRIBUTE_END
} else if (next === '>' || next === '' || (next === '/' && this.html[this.index + 2] === '>')) {
this.status = TAG_END
} else if (next === '"') { // 解析属性值
this.status = ATTRIBUTE_VALUE
}
}
// 解析属性值开始 "color: red;"
parseAttributeValue (s, pre, next) {
if (s !== '"') {
this.attributeValue += s // 属性名
}
if (next === '"') { // 属性名闭合
this.currentNode.attribute[this.attributeName] = this.attributeValue
this.attributeName = ''
this.attributeValue = ''
this.status = ATTRIBUTE_END
}
}
// 解析属性结束
parseAttributeEnd (s, pre, next) {
if (this.$reg.isEmpty(s)) { // 如果遇到了空格，那就重新开始属性解析
this.status = ATTRIBUTE_START
}
if (next === '>') {
this.status = TAG_END
}
}
// 解析开始标签结束
parseTagEnd (s, pre, next) {
// eslint-disable-next-line max-len
if ((pre === '/' && s === '>') || (selfCloseTags.includes(this.tagName) && s === '>')) {
// 自闭合标签
this.status = CLOSE_TAG_END
this.index -= 1// 回退一步，使关闭标签的索引落在>上以便正常解析
return
}
if (s === '>') {
this.tagName = ''
this.status = OPEN_TAG
}
}
// 打开了一个标签
parseOpenTag (s, pre, next) {
if (s === '<') {
if (next === '/') { // 闭合标签
this.status = CLOSE_TAG_START
} else { // 下一个标签开始
this.status = TAG_START
this.addTextTagNode()
}
} else { // 普通的文本
this.currentNode.text += s
}
}
// 解析完成一个标签，关闭
parseCloseTagStart (s, pre, next) {
if (this.$reg.isLetter(s)) {
// if (s !== '>' && s !== '/') {
this.tagName += s
} else if (this.$reg.isEmpty(s)) { // 遇到了空标签
throw new Error(`解析闭合标签失败: ${this.tagName}`)
}
if (next === '>') {
this.status = CLOSE_TAG_END
}
}
// 解析结束标签结束
parseCloseTagEnd (s, pre, next) {
if (s === '>') {
const stackTop = this.getTagStackTop()
if (stackTop.tag === this.tagName) {
this.addTextTagNode() // 生成文本结构
// this.currentNode = stackTop;
this.deleteEmptyProp(stackTop) // 节点上的空属性删除掉
this.tagStack.pop()
this.currentNode = this.getTagStackTop() // 切换当前的属性
this.tagName = '' // 新的开始当前标签为空
this.status = OPEN_TAG // 切换状态
} else {
throw new Error(`标签不能闭合:${stackTop.tag} ${this.tagName}, ${this.index}`)
}
}
}
// 删除空属性
deleteEmptyProp (node) {
if (!node.text) {
delete node.text
}
if (node.children.length === 0) {
delete node.children
}
if (Object.keys(node.attribute).length === 0) {
delete node.attribute
}
}
// 获取栈顶
getTagStackTop () {
return this.tagStack[this.tagStack.length - 1]
}
// <div>222<span>1111</span>3333</div> 为文本形成一个新的text节点
addTextTagNode () {
if (!this.currentNode?.text) {
return
}
const textNode = new Node({ tag: 'text' })
textNode.text = this.currentNode.text
this.deleteEmptyProp(textNode)
this.currentNode.text = ''
this.currentNode?.children.push(textNode)
}
}
相关参考：
上一篇：前端中指纹信息采集方式
下一篇：前端渲染模式与框架简介
