JSONのパーサーもどきを作る

久しぶりのアルゴリズム

今日は久しぶりにアルゴリズムっぽいものを作った。JSONのパーサーみたいなものである。

{
  "data": {
    "name": "Taro",
    "age": 24
  },
  "message": "hello",
  "isGood": false
}

例えば、こういうJSONがあったときにkey-valueの最小単位まで抽出したいということがある。要は、

data.name->"Taro"
data.age->24
message->"hello"
isGood->false

みたいな感じで、対応づけをデータにしたい。テストを書いていてこういう需要が出てきたが、他の場合もこんなことを考えることがあるかもしれない。 いい感じにしてくれるライブラリもたくさんあるとは思うのだが、せっかく自分で作ってみたので、その考え方を記録する。

できないこと

  • 正しくない？JSONのハンドリング
  • [ ] への対応
  • エスケープされた"への対応

JSONの公式の取り決めドキュメント（あるはず。。。）を見ていないので、そもそも正しい、正しくないの認識が曖昧とはなってしまうが、文法上正しくないJSONについてエラーが出力されることはない。また、配列への対応もしていない。（今度します）そしてエスケープされたダブルクオーテーションへの対応もしていないが、まぁこれは多分すぐになんとかなる？？？ただエスケープするための記号をさらにエスケープした場合の対応を考えると大変そう。よく分かりません。

方針

  1. JSONを読み込む。
  2. 改行とスペースを全て抜いて、一つの文字列にする
  3. key, value,left_bracket, right_bracket, comma, colonへとトークンにして分ける
  4. valueそれぞれに対してのkeyを見つける。 といった感じである。1も2も詳細にすると面倒だが、あまり細かくは考えなかった。なんとなく悩むのは4の、例えば最初に挙げた例だとdata.nameのような、入れ子のkeyにする方法だろうか。nameだけを考えるなら、単純にvalueの隣の隣のトークンがkeyなのだが。

トークン化

初めは、最初から読み込んで、スタック構造を作って云々とか考えていたが結構大変そうだなと思った。そこで、まず、"data"のようなダブルクオーテーションで囲まれているものだけ抽出することにした。

抽出されたものは全てのkeyといくつかのvalueを含む。そして、keyかどうかの判断はそのkeyの隣の文字がコロンかどうかで判断できる。また、keyじゃなければvalueになる。 keyで検索して、key-colon-valueと続かないところはkey-colon-???-commaとなるはずだから colonとcommaのダウルクオテーションで囲まれていないvalue（数字や、null、trueなど）を見つけることができる。

またkey-colon-left_bracketとなるところは飛ばして考えればいい。そうすると、全てのkeyとvalueは抽出できたことになる。

そして、まだ一つなぎの文字列でまだどこにも所属していない部分についてはどの文字か検索し、comma、colon、bracketのどれかになるのでそれで埋めてやる。

そうすれば、ひとまず全ての文字がいずれかのトークンに含まれる、もしくは割り振られることになる。そして、このtokenの配列を元にした文字が何文字目かを元にして、ソートしてやる。

少し説明を端折った気もするが、肝としてはダブルクオーテーションで囲まれているものを見つけるところである。

valueとkeyのペアを見つける

さて、tokenの配列が今手元にあるわけだが、これを最初から順に解析する。

key-colon-valueとなればめでたいがkey-colon-left_bracketとなるところもある。なので、ひとまず見つかったkeyについてはkey-stackというものに入れて、stackにすでに入っているkeyがあれば、pre-key.new-keyというように名前をそのkeyにつけてやる。

そうすれば、前の前の前のやつも含めて、名前がchainのようにつながっていく。そうして、valueが見つかれば、stackから一番上のkeyを消してやるという具合だ。

単純だがこれでうまくいった。配列も考えるようになるとまたややこしくなりそうだ。

最後に

久しぶりに頭を使った感じがあって楽しかった。競技プログラミングもしないので、スタックなんて意識して使ったこともなかったが、使えて嬉しかった。個人的には最初からトークン化をゴリゴリするのではなく、ダブルクオーテーションに着目したところがポイントだと思うが、結構当然のことなのだろうか。それともどこかこれだとまずいのだろうか。 任意のJSONに対して動作するように作る必要はなかったのでこれで今回は十分だったが、せめて配列ぐらいは実装しておきたい。