fastparseというScala用パーザコンビネータライブラリがあります。このライブラリ、Scala標準のパーザコンビネータライブラリよりかなり速い(ここの説明によると100倍速いそうな)というウリらしく、Scala標準のパーザコンビネータライブラリから乗り換えてみるために、試してみました。
構文解析器界隈のHello, World!と言えば四則演算評価器だろうということで、四則演算(+変数あり)のパーザと評価器をfastparseで書いてみました。タイトルに入門とありますが、これは私がfastparseに入門してみたという意味で、読者にとっての入門というわけではないのであしからず。
とりあえずソースコードをさらしておきます。
gistバージョンはこちら:
ASMを使ってバイトコードにコンパイルする評価器を同梱するという、誰得なことしていますが、まあ気にしない方向で。
実行結果は以下のような感じ:
以下、メモ:
- Pは構文規則になる式を囲むときに使う。Pで囲まれた式は遅延評価される。
"(" ~ exp ~ ")"
のように書いたとき、文字列リテラル部分はデフォルトで無視してくれる(semantic valueはexp
の部分のみになる。これ、Scala標準のパーザコンビネータライブラリ使うときにウザいなあと思っていた部分なので助かる。(exp).rep(n)
で最低n
回のexp
の繰り返しを表現する。semantic valueはSeq[exp]
型になる。この辺の動作はだいたいScala標準のパーザコンビネータライブラリと同じ。(exp).map(...)
でsemantic valueを変換できる。^^
より直感的でわかりやすい。a ~/ b
はa
をパーズした後にCutを発動する。ドキュメントFastParse 0.3.4 読むと
Although in theory it allows you to save on memory usage by discarding earlier portions of the input
と書いてあり、どうも自分の論文のCutから命名したようだ(自分の研究以前で、discarding earlier portions of the input
を目的にしたCutはないはず)
a ~ b
はa
とb
の連接。Scala標準のと同じ。a | b
はa
とb
の選択(a
を先に試してからb
を試す)。これもScala標準のと同じ。CharIn(Seq[Parser]...)
は引数のいずれかを表す(正規表現などの文字クラスと同じ)exp.!
は、exp
を文字列としてパーズした場合の文字列パーザを返す(これは便利!)
こんなもんでしょうか。スペースを無視するいい方法とかScala標準ライブラリでParsers
合成するのと同じ効果を持たせる方法とか、もうちょい考える必要のある部分はありますが、基本的にScala標準のパーザコンビネータライブラリとあまり変わらない使い勝手を提供してくれるものと考えてよいでしょう(Cutの導入など、むしろ便利になっている部分もある)。というわけで、安心して移行できそうです。