ねらい

• 言語の文法をクラスの木構造で表現する
• 抽象構文木(AST: Abstract Syntax Tree)であらわされる文を翻訳する

モチベーション

• 同じような類の問題が頻出するので、それに特化した言語をつくりたくなることがある

  • BNFで表されるような言語

つかいどころ

• 文法が簡潔であること

  • 複雑な文法には不向き

    • 文法を表現するクラス構造が巨大で管理不能になる

    • ASTを作らずに翻訳を行うような別のしくみを適用したほうがいい

      • 例) パーサジェネレータ … パーサを生成するプログラム

• 実行効率があまり重要でない

  • 高効率な実装は、ふつう直接ASTを処理せず、中間形式を経由する
  • ASTから中間形式への変換にはInterpreter Patternが利用できる

登場人物

• AbstractExpression

  • ASTのすべてのノード共通のインタフェースを定義

    • Interpret()処理を定義

• TerminalExpression

  • ASTの葉ノード

    • 翻訳対象の言語でいうとリテラルとか

• NonterminalExpression

  • ASTの中間ノード

  • BNFの左辺に来るようなヤツ

    • 翻訳対象の言語でいうと、演算子とか
  • Interpret()の中では、子ノードのInterpret()を再帰的に呼び出したりする

• Context

  • 翻訳時にグローバルな状態を保持する

    • ノードからextrinsicな状態を外出し
    • 【補】プリペアドステートメントのバインディングとか

• Client

  • TerminalExpression/NonterminalExpressionオブジェクトからなるASTに対し、Interpret()を呼び出す

クライアントコードからの利用

• contextを初期化し、ASTのInterpret(context)を実行

結果

• 文法の変更・拡張が容易

  • 継承・override

• 複雑な文法はメンテ困難

  • BNFの1式ごとにクラスが必要

• Interpret()以外にもいろいろできる

  • ASTのpretty printing
  • 型チェック

実装にあたり考えるべきこと

• ASTの生成

  • パース処理についてはInterpreterパターンの守備範囲外

    • Clientがパースする？
    • Clientはパースされたものを受け取る？
    • Clientの中でASTを組み立てる？

• Interpret()の実装

  • Expressionに実装すると、処理が散らばる

  • Visitorパターンを併用し、visitorオブジェクトに実装してまとめる方法もある

    • 各Expression派生は、Visitorのどの処理でInterpretされればよいかを知っている

• TerminalExpressionオブジェクトの共用

  • Flyweightパターン
  • extrinsicな状態はContextに外出しする

Compositeとどうちがうの

• 見方の問題

  • Composite: 再帰構造
  • Interpret: CompositeでASTを表現し、Contextにextrinsicな状態を外出しし、再帰的に翻訳する一連のふるまい

関連するパターン

• Composite

  • ASTがCompositeパターン

• Flyweight

  • TerminalExpressionに適用可能

• Iterator

  • 木の走査に適用可能

    • 先行順 (preorder)
    • 中間順 (inorder)
    • 後行順 (postorder)

• Visitor

  • 翻訳処理を各Expression派生クラスに散らばらせず、知識をひとまとめに

よくわかんなかったやつ

• parser generator
• compiler generator
• table-driven parser