前言

虛擬語法樹(Abstract Syntax Tree, AST)是解釋器/編譯器進行語法分析的基礎, 也是眾多前端編譯工具的基礎工具, 比如webpack, postcss, less等. 對于ECMAScript, 由于前端輪子眾多, 人力過于充足, 早已經被人們玩膩了. 光是語法分析器就有 uglify , acorn , bablyon , typescript , esprima 等等若干種. 并且也有了AST的社區標準: ESTree。

這篇文章主要介紹如何去寫一個AST解析器, 但是并不是通過分析JavaScript, 而是通過分析 html5 的語法樹來介紹, 使用 html5 的原因有兩點: 一個是其語法簡單, 歸納起來只有兩種: Text 和 Tag , 其次是因為JavaScript的語法分析器已經有太多太多, 再造一個輪子毫無意義, 而對于 html5 , 雖然也有不少的AST分析器, 比如 htmlparser2 , parser5 等等, 但是沒有像 ESTree 那么標準, 同時, 這些分析器都有一個問題: 那就是定義的語法樹中無法對標簽屬性進行操作. 所以為了解決這個問題, 才寫了一個html的語法分析器, 同時定義了一個完善的AST結構, 然后再有的這篇文章。

AST定義

為了跟蹤每個節點的位置屬性, 首先定義一個基礎節點, 所有的結點都繼承于此結點:

export interface IBaseNode { 
  start: number;  // 節點起始位置 
  end: number;    // 節點結束位置 
} 

如前所述, html5的語法類型最終可以歸結為兩種: 一種是 Text , 另一種是 Tag , 這里用一個枚舉類型來標志它們.

export enum SyntaxKind { 
  Text = 'Text', // 文本類型 
  Tag  = 'Tag',  // 標簽類型 
} 

對于文本, 其屬性只有一個原始的字符串 value , 因此結構如下:

export interface IText extends IBaseNode { 
  type: SyntaxKind.Text; // 類型 
  value: string;         // 原始字符串 
} 

而對于 Tag , 則應該包括標簽開始部分 open , 屬性列表 attributes , 標簽名稱 name , 子標簽/文本 body , 以及標簽閉合部分 close :

export interface ITag extends IBaseNode { 
  type: SyntaxKind.Tag;  // 類型 
  open: IText;           // 標簽開始部分, 比如 <div id="1"> 
  name: string;          // 標簽名稱, 全部轉換為小寫 
  attributes: IAttribute[];  // 屬性列表 
  body: Array<ITag | IText> // 子節點列表, 如果是一個非自閉合的標簽, 并且起始標簽已結束, 則為一個數組 
    | void                  // 如果是一個自閉合的標簽, 則為void 0 
    | null;                 // 如果起始標簽未結束, 則為null 
  close: IText              // 關閉標簽部分, 存在則為一個文本節點 
    | void                  // 自閉合的標簽沒有關閉部分 
    | null;                 // 非自閉合標簽, 但是沒有關閉標簽部分 
} 

標簽的屬性是一個鍵值對, 包含名稱 name 及值 value 部分, 定義結構如下:

export interface IAttribute extends IBaseNode { 
  name: IText;  // 名稱 
  value: IAttributeValue | void; // 值 
} 

其中名稱是普通的文本節點, 但是值比較特殊, 表現在其可能被單/雙引號包起來, 而引號是無意義的, 因此定義一個標簽值結構:

export interface IAttributeValue extends IBaseNode { 
  value: string; // 值, 不包含引號部分 
  quote: '\'' | '"' | void; // 引號類型, 可能是', ", 或者沒有 
} 

Token解析

AST解析首先需要解析原始文本得到符號列表, 然后再通過上下文語境分析得到最終的語法樹.

相對于JSON, html雖然看起來簡單, 但是上下文是必需的, 所以雖然JSON可以直接通過token分析得到最終的結果, 但是html卻不能, token分析是***步, 這是必需的. (JSON解析可以參考我的另一篇文章: 徒手寫一個JSON解析器(Golang) ).

token解析時, 需要根據當前的狀態來分析token的含義, 然后得出一個token列表.

首先定義token的結構:

export interface IToken { 
  start: number;    // 起始位置 
  end: number;      // 結束位置 
  value: string;    // token 
  type: TokenKind;  // 類型 
} 

Token類型一共有以下幾種:

export enum TokenKind { 
  Literal     = 'Literal',      // 文本 
  OpenTag     = 'OpenTag',      // 標簽名稱 
  OpenTagEnd  = 'OpenTagEnd',   // 開始標簽結束符, 可能是 '/', 或者 '', '--' 
  CloseTag    = 'CloseTag',     // 關閉標簽 
  Whitespace  = 'Whitespace',   // 開始標簽類屬性值之間的空白 
  AttrValueEq = 'AttrValueEq',  // 屬性中的= 
  AttrValueNq = 'AttrValueNq',  // 屬性中沒有引號的值 
  AttrValueSq = 'AttrValueSq',  // 被單引號包起來的屬性值 
  AttrValueDq = 'AttrValueDq',  // 被雙引號包起來的屬性值 
} 

Token分析時并沒有考慮屬性的鍵/值關系, 均統一視為屬性中的一個片段, 同時, 視 = 為一個

特殊的獨立段片段, 然后交給上層的 parser 去分析鍵值關系. 這么做的原因是為了在token分析

時避免上下文處理, 并簡化狀態機狀態表. 狀態列表如下:

enum State { 
  Literal              = 'Literal', 
  BeforeOpenTag        = 'BeforeOpenTag', 
  OpeningTag           = 'OpeningTag', 
  AfterOpenTag         = 'AfterOpenTag', 
  InValueNq            = 'InValueNq', 
  InValueSq            = 'InValueSq', 
  InValueDq            = 'InValueDq', 
  ClosingOpenTag       = 'ClosingOpenTag', 
  OpeningSpecial       = 'OpeningSpecial', 
  OpeningDoctype       = 'OpeningDoctype', 
  OpeningNormalComment = 'OpeningNormalComment', 
  InNormalComment      = 'InNormalComment', 
  InShortComment       = 'InShortComment', 
  ClosingNormalComment = 'ClosingNormalComment', 
  ClosingTag           = 'ClosingTag', 
} 

整個解析采用函數式編程, 沒有使用OO, 為了簡化在函數間傳遞狀態參數, 由于是一個同步操作,

這里利用了JavaScript的事件模型, 采用全局變量來保存狀態. Token分析時所需要的全局變量列表如下:

let state: State          // 當前的狀態 
let buffer: string        // 輸入的字符串 
let bufSize: number       // 輸入字符串長度 
let sectionStart: number  // 正在解析的Token的起始位置 
let index: number         // 當前解析的字符的位置 
let tokens: IToken[]      // 已解析的token列表 
let char: number          // 當前解析的位置的字符的UnicodePoint 

在開始解析前, 需要初始化全局變量:

function init(input: string) { 
  state        = State.Literal 
  buffer       = input 
  bufSize      = input.length 
  sectionStart = 0 
  index        = 0 
  tokens       = [] 
} 

然后開始解析, 解析時需要遍歷輸入字符串中的所有字符, 并根據當前狀態進行相應的處理

(改變狀態, 輸出token等), 解析完成后, 清空全局變量, 返回結束.

export function tokenize(input: string): IToken[] { 
  init(input) 
  while (index < bufSize) { 
    char = buffer.charCodeAt(index) 
    switch (state) { 
    // ...根據不同的狀態進行相應的處理 
    // 文章忽略了對各個狀態的處理, 詳細了解可以查看源代碼 
    } 
    index++ 
  } 
  const _nodes = nodes 
  // 清空狀態 
  init('') 
  return _nodes 
} 

語法樹解析

在獲取到token列表之后, 需要根據上下文解析得到最終的節點樹, 方式與tokenize相似，均采用全局變量保存傳遞狀態, 遍歷所有的token, 不同之處在于這里沒有一個全局的狀態機。

因為狀態完全可以通過正在解析的節點的類型來判斷。

export function parse(input: string): INode[] { 
  init(input) 
  while (index < count) { 
    token = tokens[index] 
    switch (token.type) { 
      case TokenKind.Literal: 
        if (!node) { 
          node = createLiteral() 
          pushNode(node) 
        } else { 
          appendLiteral(node) 
        } 
        break 
      case TokenKind.OpenTag: 
        node = void 0 
        parseOpenTag() 
        break 
      case TokenKind.CloseTag: 
        node = void 0 
        parseCloseTag() 
        break 
      default: 
        unexpected() 
        break 
    } 
    index++ 
  } 
  const _nodes = nodes 
  init() 
  return _nodes 
} 

不太多解釋, 可以到GitHub查看源代碼.

結語

項目已開源, 名稱是 html5parser , 可以通過npm/yarn安裝:

npm install html5parser -S  
# OR  
yarn add html5parser 

或者到GitHub查看源代碼: acrazing/html5parser 。

目前對正常的HTML解析已完全通過測試, 已知的BUG包括對注釋的解析, 以及未正常結束的

輸入的解析處理(均在語法分析層面, token分析已通過測試).