DSL/Syntax Directed Translation

構文主導の変換 †

一言要約 †

文法を定義し、それをうまく使ってDSLスクリプトを解析、変換する。

要約 †

コンピュータ言語は、親要素と子要素の対応を記した文法で表現できる。
構文主導の変換では、この文法を使ってパーサーを生成する。

仕組み †

言語を表す文法の利用方法には2つある。パーサーを手動で作る際の仕様や実装のガイドとして使う方法と、文法定義からパーサーを生成する方法だ。
- パーサジェネレータは、もちろん後者のアプローチ。
しかし、生成されたパーサーを通してもツリーができるだけで、これだけでは目的は達成できない。独自のプログラムを追加する必要がある。
伝統的なアプローチでは、文法定義を外部DSLとして扱い、これを解析してパーサを生成する。
- 面白いのは、文法定義自体が外部DSLであるということ。この見方では、パーサジェネレータは外部DSLの解析ツールであり、ASTは意味論モデルと言えるのかもしれない。そして、これをもとにソースを生成した結果、パーサーができる。うーん、スノーグローブ。
パーサコンビネータを使うアプローチも関数型言語のコミュニティで人気だが、これは文法を内部DSLとして表現するものと考えて良い。
- 例を見せると面白いと思う。Scalaな人持ってないかな

字句解析器

パーサジェネレータを使うと、たいていはパーサとは分離したレクサが生成される。
レクサは、パーサが動作する前の段階を担い、文字列をトークンに分解する。
パーサから分離されているのは…
- パーサをシンプルにできるから
- そもそも必要な実装メカニズムが違うから
構文手動の変換では、ホワイトスペースはどうでもいい要素
- デリミタ手動の変換では、逆にホワイトスペースが重要になる
字句解析は単純にしておくのがベスト
- 凝ったことをするには情報が足りない => 構文解析でやれ

ファウラーが好きなトークン

句読点
- キーワード、演算子、括弧や文の区切り文字など、固定的な要素
ドメインテキスト
- 識別子やリテラルなど、動的な要素。
無視できる要素
- ホワイトスペースやコメント

レクサとパーサのやり取り

独自のレクサをかくと、パーサとのやり取りで柔軟性が増す。
モード切り替えが必要な場面で有用。

構文解析器

字句解析の次に行われるパース処理は以下の２つのセクションからできている。
- 構文解析
- アクション
アクションはパースツリーが構築されるのと平行して実行される。
まずは構文解析から見ていく。
同一の入力を異なる文法で解析した場合にできあがる２つのツリーの例
- 構文主導の変換において、文法が定義しているのは入力がどのようなツリーに変換されるかということ
普通はパースツリーを全て構築することは無く、随時アクションを実行したら破棄していく。
- Tree Constructionを行う場合でも、作られるのはパースツリー全体ではなく、単純化された抽象シンタックスツリー
「パース」という用語が、字句解析と構文解析の両方を含んでいることもあるが、ソフトウェアの用語というものはそんなに正確なもんじゃないからキニスンナ。

組み込みアクション

パースツリーを使って何かを実行するために、Foreign Codeによってコードを文法内に埋め込む。埋め込まれたコードはそのルール認識された際に実行される。
eventDecを用いた例：その１
- パーサの解析に合わせてコードが実行される。
- 情報をアクションに渡すのに、トークンの位置情報を使う。
パーサジェネレータが異なれば、コードをどのように組み込み、アクションをどのようにルールに結びつけるのかも変わる。
"eventDecを用いた例：その２（Antlr）"
- eventDecルールはより高次のルールに値を返せる。
- サブルールに対して引数を渡すこともできる。
- いつアクションが実行されるかは場所によって決まる。
アクションをどう書くかはDSLのアプローチに関わるので詳細な具体例はそっちを参照
- Tree Construction, Embedded Interpretation, Embedded Translation

トップダウンパースとボトムアップパース

パーサの違いについて詳細には踏み込まないが、トップダウンとボトムアップの違いについては見ておこうと思う。
トップダウンはルールを見て探すものを決める。
ボトムアップはその逆。読みながら整合するルールを探す。
- shifting；整合するルールが無い時に一旦よけておく
- reduce：整合するルールが見つかった時にシフトしておいたものを戻す
トップダウンパーサはLLパーサとも呼ばれ、ボトムアップパーサはLRパーサとも呼ばれる。
ボトムアップパーサの方が、ルールが処理される順番が分かりにくい分難しい。
トップダウンパーサの最大の欠点は左再帰を処理できないこと
- expr : expr '+' expr ;
left-factoringを用いて、無限再帰を回避する方法もあるが、文法は分かりにくくなる。
重要なのは文法をDSLにおける固定化された定義と考えないこと。文法は何がやりたいのかによって変わってくる。

使いどころ †

構文主導の変換は、デリミタ主導の変換の替わりになるもの。文法の方が覚えるのは難しいが、慣れてしまえば有利。
文法ファイルはDSLの構造を明確に定義したドキュメントになり得るもの。

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

ステートマシンDSLの文法の例、完全な例じゃないから読んでもわからないのがいまいちだと思うんですが。＜How it worksの直後

担当者のつぶやき †

話としては非常に面白いです。なんとか時間をひねり出して、自分で何か作りたいですね。（わち）

せっかくなのでパーサコンビネータの例もはっておく †

BNF

expr   ::= term {'+' term | '-' term}
term   ::= factor {'*' factor | '/' factor}
factor ::= floatingPointNumber | '(' expr ')'

Scala Parser Combinator

   object ArithParser extends JavaTokenParsers
   {
     def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
     def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
     def factor : Parser[Any] = floatingPointNumber | "("~expr~")" 
     
     def parse(text : String) =
     {
       parseAll(expr, text)
     }
   }

expr, term, factorは、それ自体が小さなパーサーになっているらしい。これらを組み合わせて、パーサを構成する…が、これだけだと字句解析して終わってしまう。ASTを構築するためには、マッチした際にASTを構成するトークンを生成するよう、拡張しなくてはいけない。拡張すると、以下のようになる。

 object Calc
 {
   object ExprParser extends JavaTokenParsers
   {
     def expr: Parser[Expr] =
       (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
       (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
       term 

     def term: Parser[Expr] =
       (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
       (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
       factor

     def factor : Parser[Expr] =
       "(" ~> expr <~ ")" |
       floatingPointNumber ^^ {x => Number(x.toFloat) }
      
     def parse(text : String) = parseAll(expr, text)
   }
 
   def parse(text : String) =
     ExprParser.parse(text).get

   // ...
 }

^^ {...} の部分は、その前のパターンにマッチした場合に呼び出される部分関数。ここでASTの構成要素を作って返している。

DSL / Syntax Directed Translation

Menu

最新の20件