CSTからASTへの変換

January 21, 2012

Productionsまでの導出ルールでCSTを作る事が可能ですがCSTはかなり冗長な木構造になってしまいます。

例えば以下の導出規則でで数字一個をParseした場合を考えます。

以下のようにrootノードからターミナルまでの木となります。

これは明らかに冗長です。

パーサを利用する側としては以下の様にASTとして一つのノードとそのプロパティとして数値が得られれば良いだけです。

SableCC 2.xはCSTしか作る事が出来ませんでしたが、3.0からはCSTをASTに変換するルールを書く事でASTを得る事が出来るようになりました。

ASTを得るためには現状の文法ファイルに以下の二つを追加する必要があります。

Abstract Syntax TreeのSectionでASTの木構造を作るノードとその構造を定義
ProductionsのSectionにCSTをASTに変換するルールを追加する

括弧付き四則演算のパーサーであれば、各ノードは演算子に対応し、その子ノードに演算対象が置かれる形になります。

実際にAbstract Syntax Tree Sectionを書くと以下の様な形になります。

この場合木はPExprの以下の様に派生クラスで構成されるようになります。

このセクションはProductionsと同じ様な書き方をしますが、実際には文法を定義するのではなくASTの木構造がどのように構成されるかだけに着目して書く事になります。

Abstract Syntax Tree節を書き終えたら今度はProductions節にASTへの変換ルールを記入していく事になります。

Productions節は以下の様に記載する事になっていました。

ここに対して以下のように{}で括ったアノテーションで行います。

まずは一行目、CSTの導出名に着けられたアノテーションです。

これは”CST導出名”が見つかったら”AST導出名”のASTノードを作る事を指定しています。CSTとASTをマッピングしているという事です。

この情報だけでは具体的にどのようなノードを作るかが分かりませんので、CST規則名毎にASTノードの作り方を指示していきます。

これは”CST規則名”を見つけたあら、New 以下に書かれているASTノードを新規に作る事を指示します。

CST規則は要素をいくつか持っていますが、各要素が必ずしもASTで必要とは限らないため必要な要素だけをAST側の引数に書きます。引数はトークンかASTノードにマップされる必要があります。CST要素名.AST導出名と書いて指定のCST要素をAST導出にマッピングした要素でノードを作る事を宣言します。なお、このCST要素がトークン(ターミナル)の場合は単純にトークン名を書きます。

これはASTノードを新規に作らず、規則の特定の要素をASTノードにマップして使います。ASTはCSTでは作成される冗長なクラスを省略しますので、このようにして冗長なノンターミナルを省略する事が出来ます。

上記を踏まえて前述のCSTの導出定義にASTアノテーションを追加してみます。

これでASTが作成される形になります。

なお、CSTの導出規則とASTの導出規則は名前空間が別ですので同じ名前を使う事が出来ます（ただし、expr.exprといったCST導出名.AST導出名の記述がぱっと見で混乱しやすくなるように思いますが^_^;）

最後にもう一つ。

導出規則が要素を複数返す（List）ような場合、以下のような規則を定義するかと思います。

この様な場合、以下のように括弧で括られた形で定義する形となります。

再帰で複数パラメータを表す場合は括弧の中にカンマ,区切りで要素を羅列する形になります。

これでASTを得る事が可能となります。