快捷導(dǎo)航

使用有限狀態(tài)機實現(xiàn)簡版的html解析器

更新時間：2023年11月29日 10:12:18 作者：咖啡教室

FSM(Finite State Machines) 有限狀態(tài)機,也叫有限狀態(tài)自動機,是為研究有限內(nèi)存的計算過程和某些語言類而抽象出的一種計算模型,本文將使用有限狀態(tài)機實現(xiàn)一個簡版的html解析器,有需要的小伙伴可以參考下

FSM(Finite State Machines) 有限狀態(tài)機，也叫有限狀態(tài)自動機，是為研究有限內(nèi)存的計算過程和某些語言類而抽象出的一種計算模型，它擁有有限個數(shù)量的狀態(tài)，每個狀態(tài)可以遷移到零個或多個狀態(tài)，輸入字串決定執(zhí)行哪個狀態(tài)的遷移。

有限狀態(tài)機有什么用

代碼編譯器在工作時就需要通過詞法分析、語法分析、語義分析來得到 AST(Abtract Syntaxt Tree) 抽象語法樹。需要先詞法分析拿到的所有 token 流，接著通過語法分析將 token 流進行文法校驗生成語法解析樹，這個過程一般有兩種：

邊分詞邊生成 AST，像解析 HTML、CSS
先分詞生成所有 token，再來進行語法分析生成 AST，像 js

我們在前端工作中經(jīng)常用到的：babel、typescript、eslint、postcss、prettier、uniapp、htmlparse、代碼編輯器的語法高亮...這些其實都是基于 AST 抽象語法樹來實現(xiàn)的，而為了得到 AST 我們需要先進行分詞，而分詞一個比較好的方式就是通過有限狀態(tài)機來實現(xiàn)。

代碼的本質(zhì)就是字符串，分詞就是把代碼字符串變成一個個最小單元到不能再拆分的單詞，也叫 token(注意不是咱們平時用到的登錄態(tài) token)，分詞器的英文 tokenizer。代碼其實跟我們一篇英文文章、一首中文古詩、一個數(shù)學運算...都是一樣的，我們一樣可以用分詞技術(shù)來拆分這些元素。

有限狀態(tài)機是怎么工作的

為了理解有限狀態(tài)機到底是怎么工作的，我們先來實現(xiàn)一個簡單的減法運算分詞。要求用狀態(tài)機把 500-250=250 這個減法運算分詞成一個數(shù)組，首先定義一共有2種狀態(tài)：number-數(shù)字、operator-運算符，每一個最小的 token 只能是這兩個當中的一個，代碼如下

// 500-250=250
// [
//   { type: 'number', value: '500' },
//   { type: 'operator', value: '-' },
//   { type: 'number', value: '250' },
//   { type: 'operator', value: '=' },
//   { type: 'number', value: '250' }
// ]

function mathTokenizer(text) {
  // 匹配數(shù)字正則
  const numberReg = /[0-9]/
  // 匹配運算符正則
  const operatorReg = /[-=]/
  // 存儲所有讀取到的 token 數(shù)組
  let tokens = []
  // 當前正在讀取的 token 信息
  let currentToken = {}

  // 初始狀態(tài)
  function init(e) {
    if (numberReg.test(e)) {
      currentToken = { type: 'number', value: e }
      return onNumber
    } else if (operatorReg.test(e)) {
      currentToken = { type: 'operator', value: e }
      return onOperator
    }
  }

  // 讀取到數(shù)字
  function onNumber(e) {
    if (numberReg.test(e)) {
      currentToken.value += e
      return onNumber
    }
    if (operatorReg.test(e)) {
      pushToken(currentToken)
      currentToken = { type: 'operator', value: e }
      return onOperator
    }
  }

  // 讀取到運算符
  function onOperator(e) {
    if (numberReg.test(e)) {
      pushToken(currentToken)
      currentToken = { type: 'number', value: e }
      return onNumber
    }
    if (operatorReg.test(e)) {
      pushToken(currentToken)
      currentToken = { type: 'operator', value: e }
      return onOperator
    }
  }

  // 每次讀取到完整的一個 token 后存入到數(shù)組中
  function pushToken(token) {
    tokens.push(token)
    currentToken = {}
  }

  // 遍歷讀取數(shù)組
  function parse(str) {
    const len = str.length
    let stateMachine = init
    for (let i = 0; i < len; i++) {
      const char = str[i]
      stateMachine = stateMachine(char)

      // 最后一個字符匹配完了要自己 pushToken
      if (i === len - 1) {
        pushToken(currentToken)
      }
    }

    return tokens
  }

  return parse(text)
}

const arr = mathTokenizer('500-250=250')
console.log(arr)

簡版的 html 解析器

詞法分析，生成 token 流

利用狀態(tài)機來生成 token 流，為了方便理解以下示例不考慮標簽屬性節(jié)點、自閉合標簽和一些異常情況。

我們先定義5個狀態(tài)：標簽開始、結(jié)束標簽開始、標簽名、標簽結(jié)束、文本，每次讀取到的內(nèi)容會在這5個狀態(tài)之間切換，每次讀取時只要不是標簽開始、結(jié)束標簽開始、標簽名、標簽結(jié)束這4個狀態(tài)的我們都當成文本來處理。

實際上我們只需要存儲：開始標簽、文本、結(jié)束標簽這3個狀態(tài)，所以定義的節(jié)點 type 分別為：startTag、text、endTag。你要按前面定義的5個狀態(tài)來儲存其實也是可以的，在下面生成 AST 直接忽略掉我們不需要的標簽開始、標簽結(jié)束這些狀態(tài)信息就行了，只不過這里我們直接在分詞這一步提前就給過濾了。

這里我們可以把狀態(tài)機理解成一個函數(shù)，每遍歷到一個字符我們都將這個字符傳到函數(shù)中，而函數(shù)中可以根據(jù)這個字符來判斷下一個狀態(tài)是什么，再返回出去下一個狀態(tài)函數(shù)就行了。

function htmlTokenizer(str){
  // 標簽開始
  const tagStartReg = /</
  // 結(jié)束標簽開始
  const closeTagReg = ///
  // 標簽結(jié)束
  const tagEndReg = />/
  // 標簽名
  const tagNameReg = /[a-zA-Z]/

    let tokens = []
    let currentToken = {}

  // 初始狀態(tài)
  function init(e) {
    if (tagStartReg.test(e)) {
      currentToken = { type: 'startTag', tagName: '' }
            return init
        }
    if (closeTagReg.test(e)) {
      currentToken = { type: 'endTag', tagName: '' }
            return onTagName
        }
    if (tagNameReg.test(e)) {
      currentToken.tagName += e
            return onTagName
        }

    // 不是上面3個狀態(tài)的都當成文本節(jié)點處理
    currentToken = { type: 'text', text: e }
    return onText
  }

  // 讀取到標簽名
  function onTagName(e) {
    if (tagEndReg.test(e)) {
      pushToken(currentToken)
            return init
        } else {
      currentToken.tagName = (currentToken.tagName || '') + e
            return onTagName
        }
  }

  // 讀取到文本
  function onText(e) {
    if (tagStartReg.test(e)) {
      pushToken(currentToken)
      currentToken = { type: 'startTag', tagName: '' }
            return init
        } else {
      currentToken.text = (currentToken.text || '') + e
            return onText
    }
  }

  // 每次讀取到完整的一個 token 后存入到數(shù)組中
    function pushToken(e) {
        tokens.push(e)
        currentToken = {}
    }

  // 遍歷讀取數(shù)組
  function parse(chars){
    let stateMachine = init
        for (const char of chars) {
            stateMachine = stateMachine(char)
        }
        return tokens
    }

  return parse(str)
}

const tokenList = htmlTokenizer('<div>靜夜思<p>鋤禾日當午</p>周小黑<p>粒粒皆辛苦</p>公元一七八八年</div>')
console.log(tokenList)

語法分析，生成 AST 抽象語法樹

這一步主要就怎么能把分詞得到的數(shù)組轉(zhuǎn)換成樹形 tree 數(shù)據(jù)結(jié)構(gòu)，日常開發(fā)中我們 array 轉(zhuǎn) tree 一般都是需要根據(jù)父親 id 之類的來實現(xiàn)遍歷生成，但是這里咱拿到的數(shù)組是沒有這個父 id 的，那要怎么實現(xiàn)呢？

先觀察數(shù)據(jù)結(jié)構(gòu)，雖然是一個數(shù)組，但是這個數(shù)組其實是個類似中心對稱結(jié)構(gòu)的，我們暫時先忽略掉數(shù)組里的 type 為 text 的文本內(nèi)容(因為這個其實我們是不能把它當成一個父節(jié)點的，它只能是某個標簽的子節(jié)點)，過濾掉文本后數(shù)組第1個元素和最后1個元素正好是1對，第2個元素和倒數(shù)第2個元素又是1對，我們要實現(xiàn)的就是把內(nèi)層獲取到的一對對標簽不斷掛載到它前面一對簽的 children 屬性上來實現(xiàn) tree 結(jié)構(gòu)。

那我們可以從數(shù)組第一項目開始遍歷，然后用一個數(shù)組來模擬 stack 棧存每次遍歷到的標簽信息(棧的特點是先進后出，類似我們往一個桶里放東西，放在最上面的可以最先拿出來，規(guī)定數(shù)組只能使用 push 和 pop 就能模擬棧了)。

當遇到開始標簽的時候就說明遇到一個新的標簽了，這時就往棧里 push 進去，當遇到結(jié)束標簽時就說明當前這個標簽的所有信息都已經(jīng)讀取處理完了，那我們就可以將它從棧里彈出來，然后現(xiàn)在棧里最上面的一個元素其實就是當前彈出來的父標簽了，直接掛載到 children 上就行了。整個過程其實主要就是理解下面2點：

用棧來緩存節(jié)點：嵌套在內(nèi)部的節(jié)點就可以先出棧，根節(jié)點最后出棧
用引用類型對象的特點，來不斷掛載節(jié)點

function htmlAst(tokenList) {
    let stack = []

  for (let i = 0; i < tokenList.length; i++) {
    const node = tokenList[i]

    // 開始標簽：入棧
        if (node.type === 'startTag'){
            stack.push(node)
        }

    // 結(jié)束標簽：出棧
        if (node.type === 'endTag') {
            const currentNode = stack.pop()
            const parent = stack[stack.length - 1]

            if (parent) {
                if (!parent.children) parent.children = []
        parent.children.push(currentNode)
            } else {
        const root = { type: 'document', children: [currentNode] }
                return root
            }
        }

    // 文本：加到父標簽的 children 上
        if (node.type === 'text') {
            const parent = stack[stack.length - 1]
      if (!parent.children) parent.children = []
      parent.children.push(node)
        }
  }
}

然后就能拿到我們需要的 AST 語法樹了，結(jié)構(gòu)如下：

{
  "type": "document",
  "children": [
    {
      "type": "startTag",
      "tagName": "div",
      "children": [
        {
          "type": "text",
          "text": "靜夜思"
        },
        {
          "type": "startTag",
          "tagName": "p",
          "children": [
            {
              "type": "text",
              "text": "鋤禾日當午"
            }
          ]
        },
        {
          "type": "text",
          "text": "周小黑"
        },
        {
          "type": "startTag",
          "tagName": "p",
          "children": [
            {
              "type": "text",
              "text": "粒粒皆辛苦"
            }
          ]
        },
        {
          "type": "text",
          "text": "公元一七八八年"
        }
      ]
    }
  ]
}

理解了狀態(tài)機就如給你按上了一雙翅膀，不管給你任何一段字符任容，都可以通過狀態(tài)機來拆分成我們想要的結(jié)構(gòu)，理解了上面這些再去看 vue 里的模板編譯，你就能知道它到底是怎么加進去那些語法糖的了。還比如小程序中的富文本解析，特定平臺的小程序?qū)嶋H上是不能識別瀏覽器里的 html 的，那我們就需要先將 html 通過狀態(tài)機轉(zhuǎn)成 AST，然后再按照小程序的語法來進行特定的轉(zhuǎn)換。

到此這篇關(guān)于使用有限狀態(tài)機實現(xiàn)簡版的html解析器的文章就介紹到這了,更多相關(guān)有限狀態(tài)機實現(xiàn)html解析器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: