深入理解 Svelte（0）— 什麼是抽象語法樹？

前言

這一系列的文章以探討 Svelte 原理實作為主，希望能讓讀者對於 Svelte 的編譯機制與程式碼生成有更深入的理解。由於 Svelte 編譯過程涉及程式碼解析，因此這一篇文章主要會先討論抽象語法樹是什麼，並進一步說明抽象語法樹扮演的角色與重要性。

什麼是抽象語法樹（AST）？

我們先以維基百科的說明作為開頭：

在電腦科學中，抽象語法樹（abstract syntax tree 或者縮寫為 AST），或者語法樹（syntax tree），是原始碼的抽象語法結構的樹狀表現形式，這裡特指程式語言的原始碼。樹上的每個節點都表示原始碼中的一種結構。之所以說語法是「抽象」的，是因為這裡的語法並不會表示出真實語法中出現的每個細節。

抽象語法樹之所以重要，是因為我們希望有一種有結構的方式來描述程式語言（或者標記語言）方便讓電腦操作。在這邊我們先來看看一個 HTML：

<h1>這是一個標題</h1>
<p>這是一個段落</p>
<ul>
  <li data-item="1">清單列表</li>
  <li data-item="2">清單列表</li>
  <li data-item="3">清單列表</li>
</ul>

對於 <xxx> 這樣的標記，在 HTML 中稱作 tag，就像衣服上的標籤一樣簡述了衣服的資訊。tag 當中也紀錄了這個 HTML 代表的資訊。

之所以需要從字串轉為樹狀結構，是因為對於人類來說，HTML 這種標記語言容易理解且有架構，但對電腦來說只是字串而已，所以我們需要事先將字串解析後，建立一個樹狀的資料結構方便操作。上面的 HTML 可以用抽象語法樹表示：

將 HTML 轉變成樹狀結構之後，我們就可以透過樹遍歷等演算法來走訪每個節點來做對應操作，方便尋找對應的節點，舉例來說，我想要搜尋樹裡面的 li，就可以透過樹遍歷的演算法走訪，當 tagName 等於 li 時回傳結果。

不止 HTML，像是其他程式語言根據他們所定義的語法也有類似的步驟，還有像是 SQL、GraphQL 等等也會先將字串轉換為抽象語法樹之後再做其他操作。

抽象語法樹的表示

在前一個段落中我們用圖來表示一個抽象語法樹，不過除此之外一個抽象語法樹可能還會存放其他資訊，以 HTML 為例的話：

• 是否有 attributes，如果有的話也要存放在節點當中
• 是否為 self-closing （像 <input /> <video /> 等）標籤
• 解析的位置（在第幾行第幾列）

如果想更近一步觀察實際的抽象語法樹，可以從 AST Explorer，裡頭有各式各樣的程式語言可以解析為抽象語法樹，在這邊我們用 HTML 為例：

接下來看看 JavaScript 的抽象語法樹：

抽象語法樹的實作

抽象語法樹的實作主要分為兩種，一種自己定義語法，並且直接透過程式實作（手寫）；另外一種則是定義語法規則（BNF）之後，透過像是 yacc 或 PEG.js 等等的 generator 生成解析器。

我在之前也有寫過如何從無到有實現 JSON 解析器的文章，有興趣的話可以參考：

• 從無到有寫一個 JSON 解析器 (1)
• 從無到有寫一個 JSON 解析器 (2)

之前介紹 linaria 的文章也有提到一些關於 AST 的原理，有興趣也可以參考。

不過正確實作一個抽象語法樹並不容易，對於像 HTML 語法較為單純的標記語言來說還算簡單，但是對於 C、Java、JavaScript 等程式語言來說，要實作出一個正確無誤的抽象語法樹需要時間，而且還要按照規格書描述來實作，如果要當作練習的話，建議可以實作一部分的語法即可。

事實上，在 Svelte 當中除了 HTML 與 Svelte 樣板語法是自己寫解析器實作之外，其他像是 JavaScript 跟 CSS 也都是用其他人寫好的解析器來實作。在之後的文章會提到一個簡單的 Svelte 語法解析器怎麼實作，這邊就先不多提。

如果已經迫不及待想看實作的話，可以參考我在 tiny-svelte 的實作，或是直接到 Svelte 的原始碼查看實作。

抽象語法樹的用途

雖然抽象語法樹很重要，但只有語法樹其實是沒辦法做到什麼事情的，為了編譯程式碼還需要經過程式碼生成（code generation）的步驟。除了編譯程式碼之外，抽象語法樹也可以用來：

• 程式碼 highlight
• 程式碼自動補全
• prettify
• eslint

(以下由前同事 @kai 補充）

• 撰寫 babel plugin
• 靜態分析 (typescript)
• 程式碼替換 (codemod)

這些工具的基礎都是建立在抽象語法樹之上，足以說明抽象語法樹的重要性。一顆語法樹在手好像什麼事情都可以做一樣，想像力無窮。

結論

這一篇文章主要是在說明了抽象語法樹的存在與用途，希望可以讓大家對抽象語法樹有一個基本的認識。由於 Svelte 編譯過程需要會先將程式碼變成抽象語法樹，所以需要先說明抽象語法樹為何，對於之後的文章才會有比較好的理解。