Svelte を深く理解する（0）— 抽象構文木とは何か？

はじめに

この一連の記事では Svelte の原理と実装の探求を中心とし、読者が Svelte のコンパイルメカニズムとコード生成をより深く理解できるようにすることを目指している。Svelte のコンパイルプロセスにはコード解析が含まれるため、この記事ではまず抽象構文木とは何かについて議論し、抽象構文木が果たす役割と重要性を詳しく説明していく。

抽象構文木（AST）とは何か？

まずは Wikipedia の説明から始めよう：

コンピュータ科学において、抽象構文木（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 の抽象構文木を見てみよう：

抽象構文木の実装

抽象構文木の実装には主に2つのアプローチがある。1つは自分で構文を定義し、直接プログラムで実装する（手書きパーサー）方法。もう1つは構文規則（BNF）を定義した上で、yacc や PEG.js などのジェネレータを使ってパーサーを生成する方法だ。

僕も以前、ゼロから JSON パーサーを実装する方法についての記事を書いたことがあるので、興味があれば参考にしてほしい：

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

以前 linaria を紹介した記事でも AST の原理について少し触れているので、興味があればそちらも参照してほしい。

ただし、抽象構文木を正しく実装するのは簡単ではない。HTML のような比較的シンプルな構文のマークアップ言語であればまだ容易だが、C、Java、JavaScript といったプログラミング言語の場合、誤りのない抽象構文木を実装するには時間がかかる上、仕様書の記述に従って実装する必要がある。練習として行うのであれば、構文の一部だけを実装することをおすすめする。

実際、Svelte においても、HTML と Svelte のテンプレート構文はパーサーを自前で実装しているものの、JavaScript や CSS などは他者が作成した既存のパーサーを使って実装されている。今後の記事でシンプルな Svelte 構文パーサーの実装方法について触れる予定なので、ここではこれ以上深く立ち入らない。

もし実装を早く見たい場合は、僕の tiny-svelte での実装を参照するか、Svelte のソースコードを直接確認してみてほしい。

抽象構文木の用途

抽象構文木は非常に重要だが、構文木があるだけでは何もできない。コードをコンパイルするためには、コード生成（code generation）のステップを経る必要がある。コードのコンパイル以外にも、抽象構文木は以下のような用途に利用できる：

• シンタックスハイライト
• コードの自動補完
• コードのフォーマット（prettify）
• eslint

(以下は元同僚の @kai による追記）

• Babel プラグインの作成
• 静的解析 (TypeScript)
• コード変換・置換 (codemod)

これらのツールはすべて抽象構文木の上に成り立っており、それだけでも抽象構文木の重要性がよくわかるだろう。構文木をひとつ手に入れれば、まるで何でもできるように思えるほど、可能性は無限大だ。

結論

この記事では主に抽象構文木の存在とその用途について説明し、抽象構文木についての基本的な理解を深めてもらうことを目指した。Svelte のコンパイルプロセスでは、まずコードを抽象構文木に変換する必要があるため、抽象構文木が何であるかを事前に説明しておくことで、以降の記事も理解しやすくなるはずだ。