50 行代碼的 HTML 編譯器

MingjunYang 發(fā)布于2019-08-01 16:51 / 1994人閱讀

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

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

Demo

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

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

123456

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

編譯器 101

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

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

以

123

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

/ 123 /

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

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

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

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

123

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

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

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

詞法分析

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

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

/ 等

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

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

/ 等

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

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

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

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

每次匹配到一個 Token，都記錄下這個 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)造為一棵語法樹的過程，實現(xiàn)語法分析器 Parser 也是實現(xiàn)簡單編譯器時的難點。Parser 的算法有自頂向下（LL）和自底向上（LR）之分，對比討論暫且略過，下面介紹這個簡單編譯器的 Parser 實現(xiàn)：

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

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

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

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

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

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

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

// 簡化的 parser.js

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

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

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

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

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

語義分析

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

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

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

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

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

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

TODO

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

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

最后，這個玩具級的編譯器能支持的文法其實相當(dāng)有限，只是 HTML 的一個子集而已。希望它能夠為編寫其它更有趣的 Parser 提供一些啟發(fā)吧。

GPU云服務(wù)器云服務(wù)器 html代碼行數(shù)統(tǒng)計編譯的html 命令行編譯編譯的html格式

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

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/50791.html

發(fā)表評論

登陸后可評論

0條評論

MingjunYang

男|高級講師

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

TA的文章

tensorflow怎么訓(xùn)練

閱讀 2809·2023-04-26 02:28
STM32學(xué)習(xí)——半天學(xué)完正點原子入門篇例程，STM32：學(xué)會了嗎？我：學(xué)廢了?

閱讀 2697·2021-09-27 13:36
一、初識c語言

閱讀 3197·2021-09-03 10:29
Sharktech：美國洛杉磯公有云產(chǎn)品上線/16核32GB內(nèi)存/超大存儲和流量，最多16個IP/月

閱讀 2854·2021-08-26 14:14
CSS布局

閱讀 2174·2019-08-30 15:56
筆記：flex 的完備性與正交性

閱讀 909·2019-08-29 13:46
這些Zepto中實用的方法集

閱讀 2677·2019-08-29 13:15
水平垂直居中

閱讀 510·2019-08-29 11:29

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

50 行代碼的 HTML 編譯器

123456

123

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

相關(guān)文章