半熟前端

軟體工程師 / 台灣人 / 在前端的路上一邊探索其他領域的可能性

前端

深入理解 Svelte(0)— 什麼是抽象語法樹?

深入理解 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

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

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

抽象語法樹的表示

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

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

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

Screenshot_2021-02-07 AST explorer(1)

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

Screenshot_2021-02-07 AST explorer(2)

抽象語法樹的實作

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

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

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

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

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

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

抽象語法樹的用途

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

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

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

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

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

結論

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