DSL / Tree Construction

DSL

木の構築 †

一言要約 †

ASTを作ってから（Semantic Modelがあれば）Semantic Modeに変換するのが良い。ASTを作っておけば前方参照ができるし後で何度も走査できる。（中村）

要約 †

仕組み †

• 解析を通して構文木を構築し、振る舞いを作成します。
• 意味論モデルを使用している場合は、構文木を捜査し、意味論モデルを生成するコードを実行します。
• 構文木とは入力データを解析する事によって得られる階層データ構造を表現するもの。
• 解析木とは入力を正確に表現するもの
• 抽象構文木（ AST ）とは、解析木を単純化したもの。（解析後に不要となったノイズを省いた構文木）
• 解析->解析木->AST->意味論モデル を生成するのが一般的。
• ファウラーは[解析木〜AST]を構文木と定義しています。

例）
 eventBlock   : Event-keyword eventDec* End-keyword;
 eventDec     : Identifier Identifier;
入力時は、''Event-keyword''、''End-keyword'' は識別する為に必要だが、解析後は不要。

• DSLが構文木を容易に作成しやすいような機能を提供するパーサーもあります。

  例）Antlr
  eventDec :   name=ID code=ID -> ^(EVENT_DEC $name $code);

• 構造だけでなく、振る舞いも表現した構文木を作成する場合は、Eventオブジェクトのようなオブジェクトを作成する事になります。
  （複雑さを避ける為、ファウラー的には、一気にEventオブジェクトは作成したくない。）

いつ使用するか †

• Embedded Translationとは最終モデルまで一気通貫で作成。
• Tree Constructionとは中間モデルとしてASTを踏んで最終モデルを作成。
• Tree ConstructionとEmbedded Translationの両方がSemantic Modelをパースしながら生成する便利な方法。
• ASTを扱う取り組みに価値があるかどうかは、変換の複雑さに依存する。
• 変換が複雑であればあるほど、ASTを使用することは役立つ。
• パーサツールが提供しているなら、ASTを使用しましょう。
• 同じASTを異なる方法で、異なる意味論モデルを生成する事もできますが、Tree Constructionが平易ならば、用途別に異なるASTを使用したほうが簡単でしょう。

例：グラント嬢のコントローラに対しAntlrの木構築構文を使用する（ JavaとAntlr ） †

• トークン化
  • Antlrでは、キーワードをリテラル文字として登録できるので、必要なのは識別子のレクサールールだけ。

    fragment LETTER  : ('a'..'z' | 'A'..'Z' | '_');
    fragment DIGIT  : ('0'..'9');
    ID      : LETTER (LETTER | DIGIT)* ;

  • レクサーでトークンを区別できないなら、レクサーでは一律に扱ってパーサーに区別させる。
  • ホワイトスペース（改行含む）はいらない。

    WHITE_SPACE   : (' ' |'\t' | '\r' | '\n')+ {skip();} ;
    COMMENT   : '#' ~'\n'* '\n' {skip();};

  • 文の終わりに改行や';'のようなものを必要とする多くの汎用目的言語とちがい、文の区切りを必要としないということに気づくのは重要。
    • 必要になるまで導入してはだめ。
  • ホワイトスペースを認識するのは通常不要。
    • しかし、エラー時に行番号や列番号が必要なら保持しておくのは便利。（Antlrにはそんな機能あり）

• パース
  • やっていることを一言でいうと
    • 適切なDSLの塊を集め、その塊が表しているものを表現するノードの下に入れる。
  • 結果として得られるものはAST(解析木にとても似ているがまったく同じではない)。
    • ASTを得る目的は、木の構築ルールを単純に保ち、構文木を走査しやすくするため。

• Semantic Modelを生成する
  • パーサが一度木を作ったら、木を走査し、Semantic Modelを生成できる。中心のロジックはこんなかんじ。

    class StateMachineLoader...
      public void run() {
        loadAST();       ...(a
        loadSymbols();   ...(b
        createMachine(); ...(c
      }

    1. 最初にAntlrが生成したパーサーをつかって入力ストリームをパースし、ASTを作成。
    2. それからASTを検索してSymbol Tablesを構築。
    3. オブジェクトをステートマシンへ組み立て。

ファウラーへのフィードバック †

担当者のつぶやき †

• 中村様、ありがとうございます　m(__)m
  • 池田さん？翻訳が朝までかかって（途中で寝てたけど）要約の着手が遅れたんですが、やっていただいたんですね。すみません（中村）。
• 皆さん、本当にゴメン！ミセスグラント。次回に回させて下さい。（池田）
  • ミセスグラントざっくりまとめてみました（中村）。
    • 中村さん、素敵過ぎる！！！（池田）
• 解析木（parse tree）と抽象構文木（AST）をまとめて構文木（syntax tree）と呼ぶファウラーの定義は一般的？
  • これまであんまり意識したことがなかったんですがわかりやすい定義に思えました。
• DSLが2種類登場してますね。アプリのDSLと構文木を作るためのAntlrの文法（ファウラーはDSLと呼んでいる）。
• DSLの文の終わりに改行や';'のようなものをつけるなってそんなに重要？ノイズになるから？

みんなの突っ込み †