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
にはすでに多くのプリミティブが備わっていますので、ほとんどの場合に対応できるでしょう。
Top comments (0)