50 行代碼的 HTML 編譯器

NeverSayNever 發(fā)布于2019-08-20 16:42 / 1359人閱讀

摘要：所以，將字符串轉(zhuǎn)換為對(duì)象的程序就是一個(gè)編譯器雖然十分簡陋。詞法分析器輸入的這些被輸入語法分析器中進(jìn)行語法分析。而類似這樣并列的標(biāo)簽則是語法樹中的兄弟節(jié)點(diǎn)。最后，這個(gè)玩具級(jí)的編譯器能支持的文法其實(shí)相當(dāng)有限，只是的一個(gè)子集而已。

虛擬 DOM 幾乎已經(jīng)是現(xiàn)代 JS 框架的標(biāo)配了。那么該怎樣將 HTML 字符串編譯為虛擬 DOM 呢？這樣的編譯器并不是什么黑科技，這里只用了不到 50 行 JS 就實(shí)現(xiàn)了一個(gè)。

Demo

在 HTML Toy Parser Demo 中，可以將輸入的 HTML 字符串編譯成虛擬 DOM 并渲染在頁面上。這個(gè)玩具項(xiàng)目的源碼在 Github 上。

作為一個(gè)玩具編譯器，它還不能支持一些常見的 HTML 格式，如類似

123456

這樣將值和標(biāo)簽混合的寫法。不過，這個(gè)玩具是能完善地解析多個(gè)并列標(biāo)簽或深層嵌套標(biāo)簽的。下面分享一下如何從頭開始搭建出這樣一個(gè)簡單的編譯器。

編譯器 101

編譯器和解釋器不同的地方在于，編譯器是將一種編程語言的代碼編譯為另一種（例如將高級(jí)語言編譯為機(jī)器語言），而解釋器則是將一種編程語言的代碼逐條解釋執(zhí)行（例如執(zhí)行各種腳本語言）。編譯器并不需要執(zhí)行編譯得到的代碼（如 gcc xxx.c 以后是通過 OS 來執(zhí)行編譯得到的 x86 機(jī)器碼）而解釋器是直接執(zhí)行語言代碼（如各種腳本語言都需要通過諸如 python xxx.py 或 node xxx.js 的方式來執(zhí)行）。

所以，將 HTML 字符串轉(zhuǎn)換為 DOM 對(duì)象的程序就是一個(gè)編譯器（雖然十分簡陋）。按照經(jīng)典的教科書，一般一個(gè)完整的編譯過程由三步組成：詞法分析、語法分析和語義分析。這三個(gè)流程各對(duì)應(yīng)一個(gè)模塊：詞法分析器、語法分析器和語義計(jì)算模塊。

以

123

這段字符串為例，對(duì)它的編譯過程，首先始于類似【分詞】操作的詞法分析。這個(gè)過程就是輸入一段字符串，輸出

/ 123 /

三個(gè)詞法 Token 的過程。這些 Token 都有各自的屬性（或類型），比如

是一個(gè)開始標(biāo)簽、而

是一個(gè)結(jié)束標(biāo)簽等。

詞法分析器輸入的這些 Token 被輸入語法分析器中進(jìn)行語法分析。語法分析，其實(shí)就是將輸入的一連串 Token 數(shù)組構(gòu)建為一棵抽象語法樹（AST）的過程。比如，類似

123

這樣嵌套的標(biāo)簽，解析成語法樹后，就是

的子節(jié)點(diǎn)。而類似 123
456 這樣并列的標(biāo)簽則是語法樹中的兄弟節(jié)點(diǎn)。構(gòu)建好這棵語法樹后，就可以進(jìn)行語義計(jì)算了。

最后的語義計(jì)算過程就是遍歷語法樹的過程。例如在遍歷一棵虛擬 DOM 語法樹的過程中，可以將每個(gè)語法樹上的節(jié)點(diǎn)都渲染為真實(shí)的 DOM 節(jié)點(diǎn)，從而將虛擬 DOM 綁定到真實(shí) DOM，這樣就實(shí)現(xiàn)了完整的從 HTML 字符串編譯到 DOM 元素的流程。

詞法分析

這里的詞法分析器 Lexer 就是一個(gè)切分 HTML 字符串的工具。在最簡化的情景下，HTML 字符串所包含的內(nèi)容可以分為這三種：

起始標(biāo)簽，如 /

/ 等

標(biāo)簽內(nèi)容，如 123 / abc/ !@#$% 等

結(jié)束標(biāo)簽，如 /

/ 等

一個(gè)學(xué)術(shù)上嚴(yán)謹(jǐn)?shù)脑~法分析器，需要用有限狀態(tài)機(jī)來將文本切分成以上的三種類型。這里為了簡單起見，使用了用正則表達(dá)式來切分文本。算法很簡單：

從字符串開頭開始，首先匹配一個(gè)結(jié)束標(biāo)簽 Token

如果沒有匹配到結(jié)束標(biāo)簽，那么從字符串開頭開始匹配一個(gè)開始標(biāo)簽 Token

如果還是沒有匹配到開始標(biāo)簽，那么匹配一段標(biāo)簽值 Token

每次匹配到一個(gè) Token，都記錄下這個(gè) Token 的類型和文本

將 Token 的 HTML 字符串去除掉，回到步驟 1 直到切完字符串為止

詞法分析完成后，所獲得的 Token 數(shù)組內(nèi)容大致如下：

tokens = [
    { type: "TagOpen", val: "" },
    { type: "Value", val: "hello" },
    { type: "TagClose", val: "" },
    { type: "TagOpen", val: "" },
    { type: "TagOpen", val: "" },
    { type: "TagOpen", val: "" },
    { type: "Value", val: "world" },
    { type: "TagClose", val: "" }
    // ...
]

語法分析

語法分析是將上面得到的 tokens 數(shù)組構(gòu)造為一棵語法樹的過程，實(shí)現(xiàn)語法分析器 Parser 也是實(shí)現(xiàn)簡單編譯器時(shí)的難點(diǎn)。Parser 的算法有自頂向下（LL）和自底向上（LR）之分，對(duì)比討論暫且略過，下面介紹這個(gè)簡單編譯器的 Parser 實(shí)現(xiàn)：

首先，詞法分析中得到的 Tokens 所得到的 TagOpen / Value / TagClose 這三種類型，在語法樹中的位置是有區(qū)別的。例如，只有 Value 能成為葉子節(jié)點(diǎn)，而 TagOpen 和 TagClose 這兩種類型只能用來包裹出一個(gè) HTML 標(biāo)簽 Tag 類型。而一個(gè)或多個(gè) Tag 類型又能夠組成 Tags 類型。而一棵語法樹的根節(jié)點(diǎn)則是一個(gè)只有一個(gè) Tags 子節(jié)點(diǎn)的 Html 類型。

現(xiàn)在我們有了五種類型：即 TagOpen / Value / TagClose / Tag / Tags。這五種類型中，前三種是從詞法分析直接得到的，稱他們?yōu)椤?strong>終止符】，而后兩種為構(gòu)建語法樹過程中的 “抽象” 類型，稱它們?yōu)椤?strong>非終止符】

這個(gè) Parser 采用了最簡單的遞歸下降算法來解析 Tokens 數(shù)組。遞歸下降的過程是這樣的：

首先從語法樹頂部的根節(jié)點(diǎn)開始，向前【匹配非終止符】。每個(gè)【匹配非終止符】的過程，都是調(diào)用一個(gè)函數(shù)的過程。例如匹配 Tag 需要調(diào)用 tag() 函數(shù)，匹配 Tags 需要調(diào)用 tags() 函數(shù)等

每個(gè)非終止符的函數(shù)中，都按照這個(gè)非終止符的語法結(jié)構(gòu)，依次匹配各種終止符或非終止符。例如 tag() 函數(shù)需要依次匹配 TagOpen - Value - TagClose 三個(gè)終止符，或者 TagOpen - Tag - TagClose 這樣兩個(gè)終止符和一個(gè)非終止符。如果在 tag() 函數(shù)中遇到了又需要匹配 Tag 的情況（這就是 HTML 標(biāo)簽嵌套的情形）時(shí)，就需要再次調(diào)用 tag() 函數(shù)來向下匹配一個(gè)新的 Tag，這也就是所謂的遞歸下降了。

當(dāng)所有的 Token 都被吃入并匹配后，完成匹配。

教科書級(jí)的代碼示例是這樣的（但是這不是偽代碼，是能夠?qū)嶋H執(zhí)行語法分析的）：

// 簡化的 parser.js

// tokens 為輸入的詞法 Token 數(shù)組
// currIndex 為當(dāng)前語法分析過程所匹配到的下標(biāo)，只會(huì)逐個(gè)向前遞增，不回退
// lookahead 為當(dāng)前語法分析遇到的 Token，即 tokens[currIndex]
var tokens, currIndex, lookahead

// 返回下一個(gè) token 并將下標(biāo)前移一位
function nextToken() {
  return tokens[++currIndex]
}

// 按照所需匹配的終止符類型，匹配下一個(gè)終止符
// 若下一個(gè)終止符和需要匹配的類型不一直，則說明代碼中存在語法錯(cuò)誤
// 如在解析  123  這三個(gè) Token 時(shí)，最后需要 match("TagClose")
// 但此時(shí)最后一個(gè) Token 類型為 TagOpen，這時(shí)就會(huì)拋出語法錯(cuò)誤
function match(terminalType) {
  if (lookahead && terminalType === lookahead.type) lookahead = nextToken()
  else throw "SyntaxError"
}

// LL 中的函數(shù)均是用于匹配非終止符的函數(shù)
// 如果有更復(fù)雜的非終止符，在此添加它們所對(duì)應(yīng)的函數(shù)即可
const LL = {
  // 匹配 Html 類型非終止符的函數(shù)
  html() {
    // 當(dāng)存在 lookahead 時(shí)，不停向前匹配 Tag 標(biāo)簽
    while (lookahead) LL.tag()
    // 當(dāng)完成對(duì)所有 Token 的匹配后，lookahead 為越界的 undefined
    // 這時(shí)退出循環(huán)，在此結(jié)束語法分析過程
    console.log("parse complete!")
  },
  // 匹配 Tag 類型非終止符的函數(shù)
  tag() {
    // HTML 標(biāo)簽的第一個(gè) Token 一定是 TagOpen 類型
    match("TagOpen")
    // 匹配完成 TagOpen 后，可能需要匹配一個(gè)嵌套的標(biāo)簽
    // 也可能需要匹配一個(gè)標(biāo)簽的 Value
    // 這時(shí)候就需要通過向前看符號(hào) lookahead 來判斷怎樣匹配
    // 若需要匹配嵌套的標(biāo)簽，那么下一個(gè)符號(hào)必然是 TagOpen 類型
    lookahead.type == "TagOpen" ? LL.tag() : match("Value")
    // 最后匹配一個(gè)結(jié)束標(biāo)簽，即 TagClose 類型的 Token
    match("TagClose")
    // 執(zhí)行到這里時(shí)，就完成了對(duì)一個(gè) HTML 標(biāo)簽的語法解析
    console.log("tag matched")
  }
}

export default {
  parse(inputTokens) {
    // 初始化各變量
    tokens = inputTokens, currIndex = 0, lookahead = tokens[currIndex]
    // 開始語法分析，目標(biāo)是將 Tokens 解析為一整個(gè) HTML 類型
    LL.html()
  }
}

語義分析

上面的語法分析過程中，并沒有顯式構(gòu)建一棵語法樹的代碼。實(shí)際上，語法樹是在 LL 中各個(gè)匹配非終止符的函數(shù)的互相調(diào)用中，隱式地構(gòu)建出來的。要將這棵語法樹轉(zhuǎn)換為虛擬 DOM，只需要在 tag() 和 html() 等互相調(diào)用的函數(shù)中傳入?yún)?shù)即可。

例如將 tag() 函數(shù)簽名修改為如下的形式，即可實(shí)現(xiàn)

tag(currNode) {
  match("TagOpen")
  // 在遇到嵌套標(biāo)簽的情況時(shí)，遞歸向下解析
  if (lookahead.type == "TagOpen") {
    // 將當(dāng)前節(jié)點(diǎn)作為參數(shù)，調(diào)用 tags 匹配掉嵌套的標(biāo)簽
    // 將會(huì)返回掛載完成了所有子節(jié)點(diǎn)的當(dāng)前節(jié)點(diǎn)
    currNode = NT.tags(currNode)
  } else {
    // 當(dāng)前標(biāo)簽是一個(gè)葉子節(jié)點(diǎn)，這時(shí)直接修改當(dāng)前節(jié)點(diǎn)的值
    // 這時(shí) lookahead 指向的已經(jīng)是一個(gè) Value 類型的 Token 了
    currNode.val = lookahead.val
    // 匹配掉這個(gè) Value 類型，
    match("Value")
    // 這時(shí)的 lookahead 指向 TagClose 類型
  }
  match("TagClose")
  // 最后返回計(jì)算完成的節(jié)點(diǎn)給上層
  return currNode
}

所以，這種語法分析方式下，語義計(jì)算的完整代碼實(shí)際上耦合在了語法分析器中。最后 html() 函數(shù)返回的結(jié)果，就是一棵虛擬 DOM 語法樹了。

要將獲得的虛擬 DOM 渲染為真實(shí) DOM，是非常容易的。只需要深度遍歷這棵虛擬 DOM 樹，將每個(gè)節(jié)點(diǎn)通過 API 插入 DOM 中即可：

// generator.js
function renderNode(target, nodes) {
  // nodes 由調(diào)用者傳入，是調(diào)用者的全部子節(jié)點(diǎn)
  nodes.forEach(node => {
    // trim 用于修剪標(biāo)簽的首尾文本，例如將  剪為 p
    // 然后生成一個(gè)全新的 DOM 節(jié)點(diǎn) newNode
    let newNode = document.createElement(trim(node.type))
    
    // node.val 不存在時(shí)，說明當(dāng)前節(jié)點(diǎn)不是子節(jié)點(diǎn)
    // 此時(shí)傳入 node 的子節(jié)點(diǎn)遞歸調(diào)用自己，深度優(yōu)先遍歷樹
    if (!node.val) newNode = renderNode(newNode, node.children)
    
    // node.val 存在時(shí)，說明當(dāng)前 node 是葉子節(jié)點(diǎn)
    // 此時(shí) node.val 就是當(dāng)前 DOM 元素的 innerHTML
    else newNode.innerHTML = node.val
    
    // 將新生成的節(jié)點(diǎn)掛載到 DOM 上
    target.appendChild(newNode)
  })
  // 向調(diào)用者返回掛載后的元素
  return target
}

TODO

上面的一套流程走完后，實(shí)際上就實(shí)現(xiàn)了從 HTML 字符串到虛擬 DOM 再到真實(shí) DOM 的流程了。由于虛擬 DOM 的抽象性，因此可以在 HTML 字符串中通過模板語法來綁定若干變量，然后在這些變量改變后，修改虛擬 DOM 對(duì)應(yīng)的位置，并將虛擬 DOM 的相應(yīng)部分重新渲染到真實(shí) DOM，從而減少手動(dòng)重新繪制 DOM 的冗余代碼，并通過盡量少地重繪 DOM 來提高性能。

當(dāng)然了，這個(gè)編譯器的語法分析部分采用的是教科書中最簡單的遞歸下降算法，遞歸的方式在很多時(shí)候性能都不是最好的。如果希望語法分析能夠有盡可能高的性能，那么表驅(qū)動(dòng)的 LR 分析可以做到這一點(diǎn)。不過 LR 分析中構(gòu)造分析表的過程是相當(dāng)復(fù)雜的，在此并沒有殺雞用牛刀的必要。

最后，這個(gè)玩具級(jí)的編譯器能支持的文法其實(shí)相當(dāng)有限，只是 HTML 的一個(gè)子集而已。希望它能夠?yàn)榫帉懫渌腥さ?Parser 提供一些啟發(fā)吧。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/83102.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

NeverSayNever

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

C語言之移位操作符、位操作符詳解

閱讀 1206·2021-11-24 09:39
立創(chuàng)EDA【訓(xùn)練營】ESP32物聯(lián)網(wǎng)時(shí)鐘9.26

閱讀 2714·2021-09-28 09:35
記一次雪花效果

閱讀 1102·2019-08-30 15:55
子元素相對(duì)于父元素百分比尺寸問題

閱讀 1405·2019-08-30 15:44
圖片上傳預(yù)覽轉(zhuǎn)壓縮并轉(zhuǎn)base64詳解（dShowImg64.js）

閱讀 906·2019-08-29 17:00
safari Iframe 溢出 body

閱讀 2004·2019-08-29 12:19
CSS學(xué)習(xí)筆記－元素水平垂直居中

閱讀 3337·2019-08-28 18:28
在 CSS 預(yù)編譯器之后：PostCSS

閱讀 720·2019-08-28 18:10

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

50 行代碼的 HTML 編譯器

123456

123

" }, { type: "TagOpen", val: "" }, { type: "Value", val: "world" }, { type: "TagClose", val: "" } // ... ]

相關(guān)文章