最近、パーサーを実装したい欲が高まっています。
というのもRui Ueyamaさんの「低レイヤを知りたい人のためのCコンパイラ作成入門」を読み進めて、再帰下降構文解析をはじめとしてパワフルな実装に非常に魅力を感じているからです。
資料に合わせてCコンパイラを作るのは楽しいですが、どうしても写経になってしまうため、何か自分でパーサーを作りたいと思っていました。
先日はbullet.logをパースするgemを作成してリリースしましたが、あっさりと作れてしまったので、もう少し難易度の高いテーマを探していました。
どういうわけか「JSONファイルがいいんじゃ...」と思ったのでJSONパーサーを実装してみました。
完成したもの
完成したものはgithubにて公開しています。parser_v2.rbが最終的に完成したパーサーです。
json.orgがサンプルとして公開している全てのjsonデータのパースができたので、完成したと判断しました。
もしかしたら、特定の形式だとエラーになってしまうかもしれません...。
元々はparser.rbを実装していたのですが、最初に何も考えずに作り出した結果、どう頑張っても上手くパースできなかったのでver1.0として破棄しました。
結果的に、実装には約10時間はかかりました。
「すぐ実装できるだろう」と謎の自信がありましたが、構造がネストしていたり、キーバリューのペアをパースし続けたり...と思っていたよりも考えないといけないことが多かったです。
実装方針
ファイルから一文字ずつ読み取って、Rubyのハッシュ形式に記録するという方法を採用しました。
nilがgetcから返ってきたらeofとなりファイルのデータを全て確認したということになります。
file = File.open('sample.json') puts file.getc # { : puts file.getc # } puts file.getc # nil
今になって思うと、一度、トークンに変換しておけば良かったなと思っています。
一文字ずつ読み取りながらパースをすると、特定文字をスキップする処理とパース処理が混在するため、非常に複雑度が高くなってしまいました。多くのコンパイラが一度、トークンに変換しているのはこういう問題を回避するためだったんですね。
出来ているのか分かりませんが、再帰下降構文解析を使って、再帰呼び出しでゴリゴリとパースしていく実装は、やはりパワフルです。
初めてパースできた時には、感動となぜパースできたのか、自分でもよく分からない気持ちになりました。
パースの順序
パースする順序はシンプルでkeyとvalueをそれぞれ分離してパースするようにしています。
まずはkeyをパースするために"から"までに登場した文字列を取得して結合させます。valueについても同様です。keyをパース後、:の後の空白をスキップして登場する値を,か\nが登場するまで文字列を取得して結合させています。
# { "name" : "John" } key: name value: John
ただしvalueは文字列、数値、null、boolean、配列、オブジェクト...とさまざまなパータンがあるので、それぞれに対応したパース関数を用意することで対応しています。配列とオブジェクトは再帰的にパースする必要があるため、実装が難しかったです。
def p_value char = @file.getc until /^[a-zA-Z0-9\p{P}]$/.match?(char) char = @file.getc end case char when '{' p_nest_key_value() when '"' p_value_string() when '[' p_value_array() when 'n' p_value_null(char) when 't', 'f' p_value_boolean(char) else p_value_number(char) end end
json-parser/parser_v2.rb at master · okabe-yuya/json-parser · GitHub
パフォーマンスについて
Rubyが標準ライブラリとして提供しているjsonのJSON.parseとパフォーマンスを比較してみました。
user system total real --------- Default JSON parse(json/glossary.json) 0.000022 0.000013 0.000035 ( 0.000033) My JSON parser V2(json/glossary.json) 0.000526 0.000038 0.000564 ( 0.000569) --------- Default JSON parse(json/menu.json) 0.000011 0.000018 0.000029 ( 0.000031) My JSON parser V2(json/menu.json) 0.000050 0.000008 0.000058 ( 0.000058) --------- Default JSON parse(json/minimum.json) 0.000006 0.000012 0.000018 ( 0.000018) My JSON parser V2(json/minimum.json) 0.000013 0.000007 0.000020 ( 0.000020) --------- Default JSON parse(json/nest.json) 0.000006 0.000018 0.000024 ( 0.000025) My JSON parser V2(json/nest.json) 0.000018 0.000006 0.000024 ( 0.000025) --------- Default JSON parse(json/nest_in_nest.json) 0.000006 0.000013 0.000019 ( 0.000020) My JSON parser V2(json/nest_in_nest.json) 0.000025 0.000007 0.000032 ( 0.000032) --------- Default JSON parse(json/web-app.json) 0.000043 0.000035 0.000078 ( 0.000084) My JSON parser V2(json/web-app.json) 0.000691 0.000027 0.000718 ( 0.000717) --------- Default JSON parse(json/widget.json) 0.000015 0.000016 0.000031 ( 0.000031) My JSON parser V2(json/widget.json) 0.000091 0.000010 0.000101 ( 0.000105) ---------
圧倒的完敗です...。用意した全てのデータでパフォーマンスが標準のパーサーに劣っています。
そりゃそうだよねと思いつつ、少し残念です。調べてみると標準のJSONパーサーはC言語で実装されていたので、Ruby実装のJSONパーサーがパフォーマンスで劣るのは当然のことでしょう。
最後に
今回はJSONパーサーを実装してみました。
謎の自信からスタートしたものの、考えることが非常に多くて実装には時間がかかりました。
とはいえ、何とかJSONパーサーを実装しきれたのは嬉しいです。ver1.0で実装に失敗したのは、実装前に生成規則をきちんと考えていなかったのが原因だと感じています。v2の実装時は、なんちゃって生成規則を考えました。
# 見よう見まねの生成規則(笑)
expr = { key(string) : value | expr }
expr = { (key : expr)* | }
value = string | number(integer, float), null | boolean | array
次はまた別のパーサーを実装してみようと思います。
少しでも「ええな〜」と思ったらはてなスター・はてなブックマーク・シェアを頂けると励みになります。
