Elixir: パーサコンビネータライブラリNimbleParsec

Elixirの開発者José Valim氏がパーサコンビネータライブラリNimbleParsecを公開しています。2018年3月3日にリリースされ、2018年8月4日付の最新バージョンは0.4.0です。本稿は、GitHubのREADME.mdをもとに、このライブラリと簡単なサンプルコードについてご説明します(詳しくは「NimbleParsec」参照)。

NimbleParsecとは

NimbleParsecは、テキストベースのパーサコンビネータを提供するシンプルで高速なライブラリです。コンビネータは実行時に構築され、バイナリマッチングを用いた複数の節にコンパイルされます。特徴はつぎのとおりです。

• パフォーマンス
  • バイナリマッチングにコンパイルされているので、Erlang VMの多くの最適化を活用して、極めて高速でメモリ使用量の少ないパーサコードを生成します。
• 合成可能
  • パーサを構築するときマクロに依存しません。そのため、完全に合成ができます。用いるマクロはdefparsec/3とdefparsecp/3だけで、このマクロはコンパイル済みのバイナリマッチングの節を出力します。
• 実行時の依存性なし
  • コンパイルして生成されたパーサの節は、実行時はNimbleParsecにまったく依存しません。そのため、コンパイルしたパーサを他のライブラリに使っても、依存は生じません。
• フットプリントなし
  • NimbleParsecはモジュールにインポートするだけです。use NimbleParsecは要りませんので、フットプリント（自動生成された余分な関数）がモジュールに残りません。

NimbleParsecライブラリは、効率的なパーサコンビネータを書くためのプリミティブに焦点を当てています。構成の点からいえば、プリミティブを用いて高レベルのコンビネータが実装できるということです。

このライブラリは低レベルのバイナリ解析は扱いません。そうした場合には、Elixirのビットストリングの構文をお使いください。

ひな形のプロジェクトにライブラリをインストールする

NimbleParsecの「Examples」を試してみましょう。そのために、まずひな形のMixプロジェクトをつくります。

$ mix new my_parser

つぎに、NimbleParsecのインストールです。mix.exsのdepsリストにnimble_parsecを加えます。

defp deps do
  [
    {:nimble_parsec, "~> 0.4", runtime: false} # 追加
  ]
end

そして、mix deps.getコマンドでnimble_parsecを取得してください。

$ mix deps.get
Resolving Hex dependencies...
Dependency resolution completed:
New:
  nimble_parsec 0.4.0
* Getting nimble_parsec (Hex package)

サンプルコードを試す

ひな形のlib/my_parser.exに、「Examples」のコードをコピーします。

defmodule MyParser do
  import NimbleParsec

  date =
    integer(4)
    |> ignore(string("-"))
    |> integer(2)
    |> ignore(string("-"))
    |> integer(2)

  time =
    integer(2)
    |> ignore(string(":"))
    |> integer(2)
    |> ignore(string(":"))
    |> integer(2)
    |> optional(string("Z"))

  defparsec :datetime, date |> ignore(string("T")) |> concat(time), debug: true
end

IExセッションをiex -S mixで開いて、以下のコードをお試しください。なお、GitHubのnimble_parsec/examples/にもサンプルコードが納められています。

$ iex -S mix

iex> MyParser.datetime("2018-04-01T01:23:45Z")
{:ok, [2018, 4, 1, 1, 23, 45, "Z"], "", %{}, {1, 0}, 20}

defparsec/3のオプション

前掲コードはdefparsec/3にdebug: trueのオプションが定められていました。その場合、コンパイルすると、生成される節がつぎのように出力されます(フォーマットは整えました)。手でインライン化したのと変わらないレベルのコードを出力します。他のコンビネータと比べて、高いパフォーマンスが得られるでしょう(次項参照)。オプションにinline: trueを加えると、さらに強くインライン化することでパフォーマンスが高められます。

[追記: 2019/04/05] defparsec/3でオプションに、debug: trueとinline: trueをともに与えるとコンパイルエラーとなる問題がありました。2018年12月12日リリースのv0.5.0で修正されました。v0.5.0にはほかにもいくつかの改善と変更が加えられています。

defp datetime__0(<<x0::integer, x1::integer, x2::integer, x3::integer, "-", x4::integer,
      x5::integer, "-", x6::integer, x7::integer, "T", x8::integer, x9::integer, ":",
      x10::integer, x11::integer, ":", x12::integer, x13::integer, rest::binary>>,
      acc, stack, context, comb__line, comb__offset)
  when x0 >= 48 and x0 <= 57 and (x1 >= 48 and x1 <= 57) and
      (x2 >= 48 and x2 <= 57) and (x3 >= 48 and x3 <= 57) and
      (x4 >= 48 and x4 <= 57) and (x5 >= 48 and x5 <= 57) and
      (x6 >= 48 and x6 <= 57) and (x7 >= 48 and x7 <= 57) and
      (x8 >= 48 and x8 <= 57) and (x9 >= 48 and x9 <= 57) and
      (x10 >= 48 and x10 <= 57) and (x11 >= 48 and x11 <= 57) and
      (x12 >= 48 and x12 <= 57) and (x13 >= 48 and x13 <= 57) do
  datetime__1(
    rest,
    [x13 - 48 + (x12 - 48) * 10, x11 - 48 + (x10 - 48) * 10,
      x9 - 48 + (x8 - 48) * 10, x7 - 48 + (x6 - 48) * 10, x5 - 48 + (x4 - 48) * 10, 
      x3 - 48 + (x2 - 48) * 10 + (x1 - 48) * 100 + (x0 - 48) * 1000] ++ acc,
    stack,
    context,
    comb__line,
    comb__offset + 19
  )
end

defp datetime__0(rest, _acc, _stack, context, line, offset) do
  {:error, "...[略]...", rest, context, line, offset}
end

defp datetime__1(<<"Z", rest::binary>>, acc, stack, context, comb__line, comb__offset) do
  datetime__2(rest, ["Z"] ++ acc, stack, context, comb__line, comb__offset + 1)
end

defp datetime__1(rest, acc, stack, context, line, offset) do
  datetime__2(rest, acc, stack, context, line, offset)
end

defp datetime__2(rest, acc, _stack, context, line, offset) do
  {:ok, acc, rest, context, line, offset}
end

他のパーサコンビネータとの比較

「NimbleParsec - a simple and fast parser combinator for Elixir」は、NimbleParsecの処理速度を、他のパーサコンビネータとベンチマークで比べています。日時の解析ではnimbleが、ex_spiritの約8倍、combineの約14倍高速と計測されました(表001)。コンパイル時間については、日時の30回の解析がcombineでは約1秒でした。これはランタイムベースだからでしょう。nimbleは約2秒、ex_spiritが約6秒でした。

表001■日時の解析

パーサコンビネータ	入力/秒	比率
nimble	1425.75 K	1.00
ex_spirit	177.70 K	8.02
combine	95.83 K	14.88

整数の場合には、速度の差は縮まります。nimbleの速さは、ex_spiritとcombineのともに約2倍でした(表002)。けれど、NimbleParsecの整数パーサは、既存のコンビネータをもとに書かれています。他のふたつは手で書かれたパーサコンビネータであることを考慮してください。それでも、nimbleの方が速いということです。

表002■整数の解析

パーサコンビネータ	入力/秒	比率
nimble	949.95 K	1.00
ex_spirit	463.71 K	2.05
combine	338.62 K	2.81

メモリ使用量については、ベンチマークの計測はされていません。けれど、nimbleはバイナリマッチングを用いていますので、軽減できているはずです。nimbleにはすでに多くのプリミティブが備わっていますので、ほとんどの場合に対応できるでしょう。