手把手教你寫一個AST

2019 年 12 月 16 日
筆記

AST 解析器工作中經常用到，Vue.js 中的 VNode 就是如此！其實如果有需要將非結構化數據轉換成結構化對象用來分析、處理、渲染的場景，我們都可以用此思想做轉換。

logo

如何解析成 AST ？

我們知道 HTML 源碼只是一個文本數據，儘管它裡面包含複雜的含義和嵌套節點邏輯，但是對於瀏覽器，Babel 或者 Vue 來說，輸入的就是一個長字元串，顯然，純粹的一個字元串是表示不出來啥含義，那麼就需要轉換成結構化的數據，能夠清晰的表達每一節點是幹嘛的。字元串的處理，自然而然就是強大的正則表達式了。

本文闡述 AST 解析器的實現方法和主要細節，簡單易懂~~~~~~~~，總共解析器程式碼不過百行！

目標

本次目標，一步一步將如下 HTML 結構文檔轉換成 AST 抽象語法樹

<div class="classAttr" data-type="dataType" data-id="dataId" style="color:red">我是外層div      <span>我是內層span</span>  </div>

結構比較簡單，外層一個 div,內層嵌套一個 span，外層有 class,data，stye 等屬性。麻雀雖小，五臟俱全，基本包含我們經常用到的了。其中轉換後的 AST 結構有哪些屬性，需要怎樣的形式顯示，都可以根據需要自己定義即可。本次轉換後的結構：

{      "node": "root",      "child": [{          "node": "element",          "tag": "div",          "class": "classAttr",          "dataset": {              "type": "dataType",              "id": "dataId"          },          "attrs": [{              "name": "style",              "value": "color:red"          }],          "child": [{              "node": "text",              "text": "我是外層div"          }, {              "node": "element",              "tag": "span",              "dataset": {},              "attrs": [],              "child": [{                  "node": "text",                  "text": "我是內層span"              }]          }]      }]  }

不難發現，外層是根節點，然後內層用 child 一層一層標記子節點，有 attr 標記節點的屬性，classStr 來標記 class 屬性，data 來標記 data- 屬性，type 來標記節點類型，比如自定義的 data-type="title" 等。

回顧正則表達式

先來看幾組簡單的正則表達式：

^ 匹配一個輸入或一行的開頭，/^a/匹配"ab"，而不匹配"ba"
匹配一個輸入或一行的結尾，/匹配"ba"，而不匹配"ab"
- 匹配前面元字元 0 次或多次，/ab*/將匹配 a,ab,abb,abbb
- 匹配前面元字元 1 次或多次，/ab+/將匹配 ab,abb,但是不匹配 a
[ab] 字符集匹配，匹配這個集合中的任一一個字元(或元字元)，/[ab]/將匹配 a,b,ab
w 組成單詞匹配，匹配字母，數字，下劃線，等於[a-zA-Z0-9]

匹配標籤元素

首先我們將如下的 HTML 字元串用正則表達式表示出來：

<div>我是一個div</div>

這個字元串用正則描述大致如下：

以 < 開頭跟著 div 字元，然後接著 > ，然後是中文「我是一個 div」，再跟著 </ ，然後繼續是元素 div 最後已 > 結尾。

div 是 HTML 的標籤，我們知道 HTML 標籤是已字母和下劃線開頭，包含字母、數字、下滑線、中劃線、點號組成的，對應正則如下：

const ncname = '[a-zA-Z_][w-.]*'

於是組合的正則表達式如下：

`<${ncname}>`

根據上面分析，很容易得出正則表達式為下：

`<${ncname}></${ncname}>`

我是一個div

標籤內可以是任意字元，那麼任意字元如何描述呢？ s 匹配一個空白字元 S 匹配一個非空白字元 w 是字母數字數字下劃線 W 是非w 的同理還有d 和D 等。我們通常採用s 和S 來描述任何字元（1、通用，2、規則簡單，利於正則匹配）：

`<${ncname}>[sS]*</${ncname}>`

匹配標籤屬性

HTML 標籤上的屬性名稱有哪些呢，常見的有 class,id,style,data-屬性，當然也可以用戶隨便定義。但是屬性名稱我們也需要遵循原則，通常是用字母、下劃線、冒號開頭(Vue 的綁定屬性用:開頭，通常我們不會這麼定義)的，然後包含字母數字下劃線中劃線冒號和點的。正則描述如下：

const attrKey = /[a-zA-Z_:][-a-zA-Z0-9_:.]*/

HTML 的屬性的寫法目前有以下幾種：

class="title"
class='title'
class=title

const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)=("([^"]*)"|'([^']*)'|([^s"'=<>`]+)/

attrKey 跟著 = ，然後跟著三種情況:

」開頭跟著多個不是 " 的字元，然後跟著」結尾
' 開頭跟著多個不是『的字元，然後跟著 ' 結尾
不是（空格，」，』,=,<,>）的多個字元

我們測試一下 attr 的正則

"class=abc".match(attr);  // output  (6) ["class=abc", "class", "abc", undefined, undefined, "abc", index: 0, input: "class=abc", groups: undefined]    "class='abc'".match(attr);  // output  (6) ["class='abc'", "class", "'abc'", undefined, "abc", undefined, index: 0, input: "class='abc'", groups: undefined]

我們發現，第二個帶單引號的，匹配的結果是"『abc』"，多了一個單引號『，因此我們需要用到正則裡面的非匹配獲取（?:）了。例子：

"abcde".match(/a(?:b)c(.*)/);   輸出 ["abcde", "de", index: 0, input: "abcde"]

這裡匹配到了 b，但是在 output 的結果裡面並沒有 b 字元。場景：正則需要匹配到存在 b，但是輸出結果中不需要有該匹配的字元。於是我么增加空格和非匹配獲取的屬性匹配表達式如下：

const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)s*=s*(?:"([^"]*)"|'([^']*)'|([^s"'=<>`]+))/

= 兩邊可以增加零或多個空格，= 號右邊的匹配括弧使用非匹配獲取，那麼類似 = 號右側的最外層大括弧的獲取匹配失效，而內層的括弧獲取匹配的是在雙引號和單引號裡面。效果如下：

從圖中我們清晰看到，匹配的結果的數組的第二位是屬性名稱，第三位如果有值就是雙引號的，第四位如果有值就是單引號的，第五位如果有值就是沒有引號的。

匹配節點

有了上面的標籤匹配和屬性匹配之後，那麼將兩者合起來就是如下：

/<[a-zA-Z_][w-.]*(?:s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)s*=s*(?:"([^"]*)"|'([^']*)'|([^s"'=<>`]+)))*>[sS]*</[a-zA-Z_][w-.]*>/

上述正則完整描述了一個節點，理解了簽名的描述，現在看起來是不是很簡答啦~

AST 解析實戰

有了前面的 HTML 節點的正則表達式的基礎，我們現在開始解析上面的節點元素。顯然，HTML 節點擁有複雜的多層次的嵌套，我們無法用一個正則表達式就把 HTML 的結構都一次性的表述出來，因此我們需要一段一段處理。我們將字元串分段處理，總共分成三段：

標籤的起始
標籤內的內容
標籤的結束

於是將上述正則拆分：

const DOM = /<[a-zA-Z_][w-.]*(?:s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)s*=s*(?:"([^"]*)"|'([^']*)'|([^s"'=<>`]+)))*>[sS]*</[a-zA-Z_][w-.]*>/;  // 增加()分組輸出  const startTag = /<([a-zA-Z_][w-.]*)((?:s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)s*=s*(?:"([^"]*)"|'([^']*)'|([^s"'=<>`]+)))*)s*(/?)>/;    const endTag = /</([a-zA-Z_][w-.]*)>/;    const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)s*=s*(?:"([^"]*)"|'([^']*)'|([^s"'=<>`]+))/g    // 其他的就是標籤裡面的內容了

不難發現，標籤已 < 開頭，為標籤起始標識位置，已 </ 開頭的為標籤結束標識位置。我們將 HTML 拼接成字元串形式，就是如下了。

let html = '<div class="classAttr" data-type="dataType" data-id="dataId" style="color:red">我是外層div<span>我是內層span</span></div>';

我們開始一段一段處理上面的 html 字元串吧~

const bufArray = [];  const results = {      node: 'root',      child: [],  };  let chars;  let match;  while (html&&last!=html){      last = html;      chars = true;// 是不是文本內容      // do something parse html  }

bufArray: 用了存儲未匹配完成的起始標籤 results: 定義一個開始的 AST 的節點。我們再循環處理 HTML 的時候，如果已經處理的字元，則將其刪除，這裡判斷 last!=html 如果處理一輪之後，html 還是等於 last，說明沒有需要處理的了，結束循環。

首先判斷是否是 </ 開頭，如果是則說明是標籤結尾標識

if(html.indexOf("</")==0){      match = html.match(endTag);      if(match){          chars = false;          html = html.substring(match[0].length);          match[0].replace(endTag, parseEndTag);      }  }

已 </ 開頭，且能匹配上實時截止標籤的正則，則該 html 字元串內容要向後移動匹配到的長度，繼續匹配剩下的。這裡使用了 replace 方法，parseEndTag 的參數就是"()"匹配的輸出結果了，已經匹配到的字元再 parseEndTag 處理標籤。

如果不是已 </ 開頭的，則判斷是否是 < 開頭的，如果是說明是標籤起始標識，同理，需要 substring 來剔除已經處理過的字元。

else if(html.indexOf("<")==0){      match = html.match(startTag);      if(match){          chars = false;          html = html.substring(match[0].length);          match[0].replace(startTag, parseStartTag);      }  }

如果既不是起始標籤，也不是截止標籤，或者是不符合起始和截止標籤的正則，我們統一當文本內容處理。

if(chars){      let index = html.indexOf('<');      let text;      if(index < 0){          text = html;          html = '';      }else{          text = html.substring(0,index);          html = html.substring(index);;      }      const node = {          node: 'text',          text,      };      pushChild(node);  }

如果是文本節點，我們則加入文本節點到目標 AST 上，我們著手 pushChild 方法，bufArray 是匹配起始和截止標籤的臨時數組，存放還沒有找到截止標籤的起始標籤內容。

function pushChild (node) {      if (bufArray.length === 0) {          results.child.push(node);      } else {          const parent = bufArray[bufArray.length - 1];          if (typeof parent.child == 'undefined') {              parent.child = [];          }          parent.child.push(node);      }  }

如果沒有 bufArray ，說明當前 Node 是一個新 Node，不是上一個節點的嵌套子節點，則新 push 一個節點；否則取最後一個 bufArray 的值，也就是最近的一個未匹配標籤起始節點，將當前節點當做為最近節點的子節點。

<div><div></div></div>

顯然，第一個 </div> 截止節點，匹配這裡的第二個起始節點

，即最後一個未匹配的節點。

在每一輪循環中，如果是符合預期，HTML 字元串會越來越少，直到被處理完成。

接下來我們來處理 parseStartTag 方法，也是稍微複雜一點的方法。

function parseStartTag (tag, tagName, rest) {      tagName = tagName.toLowerCase();        const ds = {};      const attrs = [];      let unary = !!arguments[7];        const node = {          node: 'element',          tag:tagName      };      rest.replace(attr, function (match, name) {          const value = arguments[2] ? arguments[2] :              arguments[3] ? arguments[3] :                  arguments[4] ? arguments[4] :'';          if(name&&name.indexOf('data-')==0){              ds[name.replace('data-',"")] = value;          }else{              if(name=='class'){                  node.class = value;              }else{                  attrs.push({                      name,                      value                  });              }          }      });      node.dataset = ds;      node.attrs = attrs;      if (!unary){           bufArray.push(node);      }else{          pushChild(node);      }  }

遇到起始標籤，如果該起始標籤不是一個結束標籤(unary 為 true，如：,如果本身是截止標籤，那麼直接處理完即可)，則將起始標籤入棧，等待找到下一個匹配的截止標籤。起始標籤除了標籤名稱外的屬性內容，我們將 dataset 內容放在 dataset 欄位，其他屬性放在 attrs

我們接下來看下處理截止標籤

function parseEndTag (tag, tagName) {      let pos = 0;      for (pos = bufArray.length - 1; pos >= 0; pos--){          if (bufArray[pos].tag == tagName){              break;          }      }      if (pos >= 0) {          pushChild(bufArray.pop());      }  }

記錄還未匹配到的起始標籤的 bufArray 數組，從最後的數組位置開始查找，找到最近匹配的標籤。比如：

<div class="One"><div class="Two"></div></div>

class One 的標籤先入棧，class Two 的再入棧，然後遇到第一個</div>，匹配的則是 class Two 的起始標籤，然後再匹配的是 class One 的起始標籤。

到此，一個簡單的 AST 解析器已經完成了。

當然，本文是實現一個簡單的 AST 解析器，基本主邏輯已經包含，完整版參考如下：

完整解析參考：vue-html-parse[1]

本文的 AST 解析器的完整程式碼如下：

easy-ast[2]

參考資料

[1]

完整解析參考：vue-html-parse: https://github.com/vuejs/vue/blob/dev/src/compiler/parser/html-parser.js

[2]

easy-ast: https://github.com/antiter/blogs/tree/master/code-mark/easy-ast.js