プログラム言語などの操作を行う上で、欠かせないデータ構造が抽象構文木（AST）です。
文法構造の特徴
多くのプログラミング言語は文脈自由文法に従って書かれるものですが、これは同じ構造のネストが可能となっています。
- 数式におけるカッコのネスト
- 連想配列の中に連想配列が入るようなネスト
- HTMLなどでのタグのネスト
というように、各種のデータ構造に普遍的に存在する構造です。
抽象構文木って…？
名前は仰々しいのですが、構文構造をデータ構造に起こしたものが抽象構文木です。DOMツリーもその1つと言って間違いはありません。
なお、「抽象」は「カッコなどを取っ払って、元のコードに完全に戻すことができない」という意味で、文法的意味を完全に保つ程度には具体的です。
実際にやってみた例
以前に、「同じオブジェクトを入れればキーの順序を含めて同じJSONを作る」ようなJSON.stringifyが必要になったことがあって、jkr2255/sorted-json-stringifyとして作成しました。JSONは
-
true/false null- 文字列
- 数値
- 配列
- オブジェクト
の組み合わせですが、並べ替えに必要なのはオブジェクトのキーだけなので、そこだけうまく取り出すようにして、文字列の値のエンコード・デコードすらサボっています。
JavaScriptのAST
JavaScriptでは、ASTが標準化されて、ASTレベルで加工していくことが一般化しているという、独自の文化圏となっています。このあたりも掘り下げてみると面白そうです（半ば投げやり）。