kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

入門fastparse(1) ~四則演算評価器を作ってみた~

fastparseというScala用パーザコンビネータライブラリがあります。このライブラリ、Scala標準のパーザコンビネータライブラリよりかなり速い(ここの説明によると100倍速いそうな)というウリらしく、Scala標準のパーザコンビネータライブラリから乗り換えてみるために、試してみました。

構文解析器界隈のHello, World!と言えば四則演算評価器だろうということで、四則演算(+変数あり)のパーザと評価器をfastparseで書いてみました。タイトルに入門とありますが、これは私がfastparseに入門してみたという意味で、読者にとっての入門というわけではないのであしからず。

とりあえずソースコードをさらしておきます。

github.com

gistバージョンはこちら:

gist.github.com

ASMを使ってバイトコードコンパイルする評価器を同梱するという、誰得なことしていますが、まあ気にしない方向で。

実行結果は以下のような感じ:

https://i.gyazo.com/571778a50f60c569373f2fe7adf54fa5.png

以下、メモ:

  • Pは構文規則になる式を囲むときに使う。Pで囲まれた式は遅延評価される。
  • "(" ~ exp ~ ")"のように書いたとき、文字列リテラル部分はデフォルトで無視してくれる(semantic valueはexpの部分のみになる。これ、Scala標準のパーザコンビネータライブラリ使うときにウザいなあと思っていた部分なので助かる。
  • (exp).rep(n)で最低n回のexpの繰り返しを表現する。semantic valueはSeq[exp]型になる。この辺の動作はだいたいScala標準のパーザコンビネータライブラリと同じ。
  • (exp).map(...) でsemantic valueを変換できる。^^より直感的でわかりやすい。
  • a ~/ baをパーズした後に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 ~ babの連接。Scala標準のと同じ。
  • a | babの選択(aを先に試してからbを試す)。これもScala標準のと同じ。
  • CharIn(Seq[Parser]...)は引数のいずれかを表す(正規表現などの文字クラスと同じ)
  • exp.!は、expを文字列としてパーズした場合の文字列パーザを返す(これは便利!)

こんなもんでしょうか。スペースを無視するいい方法とかScala標準ライブラリでParsers合成するのと同じ効果を持たせる方法とか、もうちょい考える必要のある部分はありますが、基本的にScala標準のパーザコンビネータライブラリとあまり変わらない使い勝手を提供してくれるものと考えてよいでしょう(Cutの導入など、むしろ便利になっている部分もある)。というわけで、安心して移行できそうです。