Svelte (0) についての深い理解—抽象構文ツリーとは?

前言

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

抽象構文木（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などのジェネレーターを使用してパーサーを生成する方法です。

私は以前、ゼロから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のコンパイルプロセスは、コードを抽象構文木に変換することから始まるため、抽象構文木についての理解が今後の記事をより良く理解する上で重要です。