勉強日記

チラ裏

GoF本 Interpreter

勉強メモ デザインパターン GoF

ねらい

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

モチベーション

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

つかいどころ

  • 文法が簡潔であること
    • 複雑な文法には不向き
      • 文法を表現するクラス構造が巨大で管理不能になる
      • ASTを作らずに翻訳を行うような別のしくみを適用したほうがいい
        • 例) パーサジェネレータ ... パーサを生成するプログラム
  • 実行効率があまり重要でない
    • 高効率な実装は、ふつう直接ASTを処理せず、中間形式を経由する
    • ASTから中間形式への変換にはInterpreter Patternが利用できる

登場人物

  • AbstractExpression
    • ASTのすべてのノード共通のインタフェースを定義
      • Interpret()処理を定義
  • TerminalExpression
    • ASTの葉ノード
  • NonterminalExpression
    • ASTの中間ノード
    • BNFの左辺に来るようなヤツ
      • 翻訳対象の言語でいうと、演算子とか
    • Interpret()の中では、子ノードのInterpret()を再帰的に呼び出したりする
  • Context
  • 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