CSTからASTへの変換

Productionsまでの導出ルールでCSTを作る事が可能ですがCSTはかなり冗長な木構造になってしまいます。
例えば以下の導出規則でで数字一個をParseした場合を考えます。

expr =
   {term} term
 | {add} [left]:expr add [right]:term
 | {sub} [left]:expr sub [right]:term
;

term =
   {factor} factor
 | {mul} [left]:term mul [right]:factor
 | {div} [left]:term div [right]:factor
;

factor =
   {number} number
 | {parens} l_paren expr r_paren
;

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

ATermExpr root.term.factor.number.text

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

ANumberExpr root.number.text

SableCC 2.xはCSTしか作る事が出来ませんでしたが、3.0からはCSTをASTに変換するルールを書く事でASTを得る事が出来るようになりました。
ASTを得るためには現状の文法ファイルに以下の二つを追加する必要があります。

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

括弧付き四則演算のパーサーであれば、各ノードは演算子に対応し、その子ノードに演算対象が置かれる形になります。
実際にAbstract Syntax Tree Sectionを書くと以下の様な形になります。

//------+-------+-------+-------+-------+-------+-------+-------+-------+------
Abstract Syntax Tree

expr = {number} number
     | {add} [left]:expr [right]:expr
     | {sub} [left]:expr [right]:expr
     | {mul} [left]:expr [right]:expr
     | {div} [left]:expr [right]:expr
;

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

TNumberExpr(TNumber number)
AAddExpr(PExpr left, PExpr right)
ASubExpr(PExpr left, PExpr right)
AMulExpr(PExpr left, PExpr right)
ADivExpr(PExpr left, PExpr right)

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

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

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

CST導出名 =
   {CST規則名} [CST要素名]:CST要素識別子 [CST要素名]:CST要素識別子 ...
 | {CST規則名} [CST要素名]:CST要素識別子
 | ...
;

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

CST導出名 { -> AST導出名 } =
   {CST規則名} [CST要素名]:CST要素識別子 [CST要素名]:CST要素識別子 ... { -> New AST導出名.AST規則名(CST要素名.AST導出名, CST要素名.AST導出名, ...) }
 | {CST規則名} [CST要素名]:CST要素識別子 { -> CST要素名.AST導出名 }
 | ...
;

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

CST導出名 { -> AST導出名 } = ...;

これは”CST導出名”が見つかったら”AST導出名”のASTノードを作る事を指定しています。CSTとASTをマッピングしているという事です。
この情報だけでは具体的にどのようなノードを作るかが分かりませんので、CST規則名毎にASTノードの作り方を指示していきます。

{CST規則名} [CST要素名]:CST要素識別子 [CST要素名]:CST要素識別子 ... { -> New AST導出名.AST規則名(CST要素名.AST導出名, CST要素名.AST導出名, ...) }

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

{CST規則名} [CST要素名]:CST要素識別子 { -> CST要素名.AST導出名 }

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

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

expr { -> expr } =
   {term} term                        { -> term.expr }
 | {add} [left]:expr add [right]:term { -> New expr.add(left.expr, right.expr) }
 | {sub} [left]:expr sub [right]:term { -> new expr.sub(left.expr, right.expr) }
;

term { -> expr } =
   {factor} factor                      { -> factor.expr }
 | {mul} [left]:term mul [right]:factor { -> New expr.mul(left.expr, right.expr) }
 | {div} [left]:term div [right]:factor { -> New expr.div(left.expr, right.expr) }
;

factor { -> expr } =
   {number} number               { -> New expr.number(number) }
 | {parens} l_paren expr r_paren { -> expr.expr }
;

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

最後にもう一つ。
導出規則が要素を複数返す(List)ような場合、以下のような規則を定義するかと思います。

command_line =
   command arg*
;

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

//------+-------+-------+-------+-------+-------+-------+-------+-------+------
Productions /* parser definitions */

    command_line { -> command_line } =
        command arg* { -> New command_line(command, [arg]) };

//------+-------+-------+-------+-------+-------+-------+-------+-------+------
Abstract Syntax Tree

    command_line = [command]:command [args]:arg*;

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

//------+-------+-------+-------+-------+-------+-------+-------+-------+------
Productions /* parser definitions */

    command_line { -> command_line } =
        command args? { -> New command_line(command, [args.arg]) };
    args { -> arg* } =
        {single} arg { -> [arg] }
      | {multi}  arg comma args { -> [arg, args.arg] }
    ;

//------+-------+-------+-------+-------+-------+-------+-------+-------+------
Abstract Syntax Tree

    command_line = [command]:command [args]:arg*;

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

Leave a Reply

Your email address will not be published. Required fields are marked *