50 行代碼的 HTML 編譯器

MingjunYang 發布于2019-08-01 16:51 / 1933人閱讀

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

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

Demo

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

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

123456

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

編譯器 101

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

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

以

123

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

/ 123 /

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

是一個開始標簽、而

是一個結束標簽等。

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

123

這樣嵌套的標簽，解析成語法樹后，就是

的子節點。而類似 123
456 這樣并列的標簽則是語法樹中的兄弟節點。構建好這棵語法樹后，就可以進行語義計算了。

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

詞法分析

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

起始標簽，如 /

/ 等

標簽內容，如 123 / abc/ !@#$% 等

結束標簽，如 /

/ 等

一個學術上嚴謹的詞法分析器，需要用有限狀態機來將文本切分成以上的三種類型。這里為了簡單起見，使用了用正則表達式來切分文本。算法很簡單：

從字符串開頭開始，首先匹配一個結束標簽 Token

如果沒有匹配到結束標簽，那么從字符串開頭開始匹配一個開始標簽 Token

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

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

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

詞法分析完成后，所獲得的 Token 數組內容大致如下：

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 數組構造為一棵語法樹的過程，實現語法分析器 Parser 也是實現簡單編譯器時的難點。Parser 的算法有自頂向下（LL）和自底向上（LR）之分，對比討論暫且略過，下面介紹這個簡單編譯器的 Parser 實現：

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

現在我們有了五種類型：即 TagOpen / Value / TagClose / Tag / Tags。這五種類型中，前三種是從詞法分析直接得到的，稱他們為【終止符】，而后兩種為構建語法樹過程中的 “抽象” 類型，稱它們為【非終止符】

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

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

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

當所有的 Token 都被吃入并匹配后，完成匹配。

教科書級的代碼示例是這樣的（但是這不是偽代碼，是能夠實際執行語法分析的）：

// 簡化的 parser.js

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

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

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

語義分析

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

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

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

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

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

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

TODO

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

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

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

云服務器 GPU云服務器 html代碼行數統計編譯的html 命令行編譯編譯的html格式

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/50791.html

50 行代碼的 HTML 編譯器

摘要：所以，將字符串轉換為對象的程序就是一個編譯器雖然十分簡陋。詞法分析器輸入的這些被輸入語法分析器中進行語法分析。而類似這樣并列的標簽則是語法樹中的兄弟節點。最后，這個玩具級的編譯器能支持的文法其實相當有限，只是的一個子集而已。虛擬 DOM 幾乎已經是現代 JS 框架的標配了。那么該怎樣將 HTML 字符串編譯為虛擬 DOM 呢？這樣的編譯器并不是什么黑科技，這里只用了不到 50 行 J...

NeverSayNever 2019-08-20 16:42 評論0 收藏0
自己動手擼個簡易模板引擎（50行左右）

摘要：寫在前面模板的誕生是為了將顯示與數據分離，模板技術多種多樣，但其本質是將模板文件和數據通過模板引擎生成最終的代碼。目前有著很多這種模板引擎，諸如的，，的。當然在用過這么多的模板引擎后，也有著自己實現一個簡易模板引擎的沖動。寫在前面模板的誕生是為了將顯示與數據分離，模板技術多種多樣，但其本質是將模板文件和數據通過模板引擎生成最終的HTML代碼。目前有著很多這種模板引擎，諸如Node的...

ixlei 2019-08-20 11:18 評論0 收藏0
50道JavaScript基礎面試題（附答案）

摘要：事件中屬性等于。響應的狀態為或者。同步在上會產生頁面假死的問題。表示聲明的變量未初始化，轉換為數值時為。但并非所有瀏覽器都支持事件捕獲。它由兩部分構成函數，以及創建該函數的環境。 1 介紹JavaScript的基本數據類型Number、String 、Boolean 、Null、Undefined Object 是 JavaScript 中所有對象的父對象數據封裝類對象：Object、...

huaixiaoz 2019-08-22 18:04 評論0 收藏0
Top 10 JavaScript編輯器，你在用哪個？

摘要：在這個編輯器中，和是其中排名靠前的兩個。是一個免費的輕量級編輯器和，用于和開發。對于免費的代碼編輯器來說，是一個很好的選擇。可以安裝兩個命令行實用程序，用于從啟動編輯器，用于管理的軟件包。對于JavaScript程序員來說，目前有很多很棒的工具可供選擇。本文將會討論10個優秀的支持javascript，HTML5和CSS開發，并且可以使用Markdown進行文檔編寫的文本編輯器。為什...

zombieda 2019-08-21 11:45 評論0 收藏0