logo

新编程学习网
使用状态机将HTML解析为AST
首页>内容详情

使用状态机将HTML解析为AST

大熊••

状态机场景

软件开发中，也会经常遇到状态机的问题。

  • 例如用户支付场景下订单的状态，订单状态可能经过这样的变化。
  • 词法分析，以及下面我们将要讲到的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问题，没有做精细化处理。

下面是完整的状态机图：
image.png

代码实现

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)
  }
}

相关参考：

关于我
loading
在线编辑器

Copyright © 2024 编程学习网，帮助新手快速入门，高级编程的工具箱。  版权所有 ICP证：京ICP备15048378号-3联系作者