今時パーサコンビネータ？みたいなところはあるかと思いますが紹介をしたいと思います。
概要
現在絶賛ストール中のプロジェクトであるMapleLatteの内部で使用された独自のパーサコンビネータです。同様のものとしてctpgがありますが、ctpgはコンパイル時に文字列を処理してパーサコードを生成するのに対して今回紹介するものはUFCSとテンプレートを使用して、D言語の式で文法を表現するものとなります。
解析できる文法としてはPEGで表せる範囲となっています(Packrat Parsingを使用しています)。通常のPackrat Parsingと違ってトークン列を扱うようになっており、文法をシンプルに書き下すことが可能となっています。
用例
例えば
ImportStmt <- Import identifier ("." identifier)* ["." "*"] ";"
という規則があったとして、identifierおよびImportをトークン(TokenType.IdentifierおよびTokenType.Import)とするとソースコード中では次のように書くことができるようになっています。
auto parseImportStmt(ParseResult input)
{
return input.matchToken!(TokenType.Import).matchToken!(TokenType.Identifier)
.matchUntilFail!(r => r.matchToken!(TokenType.Period).matchToken!(TokenType.Identifier))
.ignorable!(r => r.matchToken!(TokenType.Period).matchToken!(TokenType.Asterisk))
.matchToken!(TokenType.Semicolon);
}
特徴
- 即時実行型(rangeのように遅延実行ではなく)なので実行が追いやすいようになっています
- Packrat Parsingを採用しているので分岐が書きやすくなっています(テンプレート引数を左から試していって成功したら抜けるような戦略を採用しているため書き方によって望みどおりの文法をパースできないことがあります)
- テンプレートをふんだんに使っているため実行時のパフォーマンスが期待できます
- ただし現状ではメモ化を行っていないので文法と対象次第では遅くなります
欠点/未実装
これがストールの原因になっているのですが、致命的な問題として還元処理を書くことができません。まずパーサの途中の状態を保持するParseResult構造体が値を保持できる状態になっていないのでそこから実装する必要がありそうです。それからmatchToken!Tでトークンを保存してほしいパターンと保存しないでほしいパターンの2通りを実装する必要があるのですが、保存してほしいパターンの場合は「前の値と合成するかどうか」という問題があるのでまだ未実装となっています(ただ、前の値を捨てるパターンが思いつかないので合成する方向(Tupleを使ってtuple(前の値, トークン)とまとめる)で実装してしまってもいいかもしれません)。
あとはトークン列を処理するようになっているため予めソースコードをトークンで分割しておく必要があります。そのため単独で利用するには若干つらい部分がありますが、ライブラリ化する際はなんとか両方まとめて使えるような仕組みを作る必要があります。
まとめ
自身のプロダクトでの用例という言語系Advent Calendarの記事としては異色(たぶん)なものになりましたが、以上で紹介を終わりにします。現在未実装の還元処理をうまい形で実装することができたら(あと需要があれば)ライブラリとしてまとめてdubに登録すると思います。