🙌

JSONパーサを実装してみる

2022/11/13に公開約9,600字

はじめに

C++に慣れるためにcxxjpというJSONパーサライブラリを作りました.この記事では振り返りも兼ねてJSONパーサを実装する流れを簡単に説明してみようと思います.

実装の流れ

ざっくりと以下のような順番で説明します.これに加えて一部の処理を関数として切り出したり,JSONの値を管理するクラスを作成したりします.

  1. {"hoge": "huga"}をパースする
  2. {"bar": 111}をパースする
  3. {"hoge": "huga", "bar": 111}をパースする
  4. {"hoge": "huga", "bar": 111, "bazz": [10, "piyo"]}をパースする
  5. {"hoge": "huga", "bar": 111, "bazz": [10, "piyo"], "popo": {"titi": "tete", "tutu": 111}}をパースする

実用レベルのJSONパーサを作るならもっとやることはありますが,この7つのオブジェクトがパースできれば後は気合で何とかなると思います.

1. {"hoge":"huga"}をパースする

ということで, {"hoge":"huga"}のパース処理を書いていきましょう .ここは本当にやるだけです.とりあえず「1つ目の"から2つ目の"までがキーになり,3つ目の"から4つ目の"までが対応する値になる」と考えて実装してみます.

main.cxx
#include <iostream>

int main() {
    std::string s = R"({"hoge":"huga"})";
    int k_start = 0;
    int k_end = 0;
    int v_start = 0;
    int v_end = 0;

    while(s[k_start] != '"') ++k_start;
    k_end = k_start + 1;
    while(s[k_end] != '"') ++k_end;
    v_start = k_end + 1;
    while(s[v_start] != '"') ++v_start;
    v_end = v_start + 1;
    while(s[v_end] != '"') ++v_end;

    std::cout << s.substr(k_start+1, k_end-k_start-1) << std::endl;
    std::cout << s.substr(v_start+1, k_end-k_start-1) << std::endl;
    
    return 0;
}
output
 hoge
 huga

2. {"bar": 111}をパースする

次は文字列ではなく数値を値にもつオブジェクトをパースしてみましょう.せっかくなので,値が文字列なのか数値なのか判別して1つのコードで{"hoge": "huga"}{"bar": 111}のどちらもパースできるようにします.まずは小数や負数や十六進数は全部無視して,123のようなシンプルな自然数のみのパースを目標とします.

空白がない前提で:の次の値に注目して考えると,文字列であれば"であり,数値であれば1〜9の値になっていることが分かります.つまり,

  1. :を見つける
  2. :の次の空白でない要素をみつける
  3. "なら文字列で1〜9の値なら数値

とすればいけそうです.これをコードにすると以下のようになります.

main.cxx
#include <iostream>

int main() {
    std::string s = R"({"hoge": 333})"; // R"({"hoge": "huga"})"
    int k_start = 0;
    int k_end = 0;
    int v_start = 0;
    int v_end = 0;
    int i_colon = 0;

    while(s[k_start] != '"') ++k_start;
    k_end = k_start + 1;
    while(s[k_end] != '"') ++k_end;
    i_colon = k_end + 1;
    // 1. ':'を見つける
    while(s[i_colon] != ':') ++i_colon;
    v_start = i_colon + 1;
    // 2. ':'の次の空白でない要素を探す
    while(s[v_start] == ' ') ++v_start;
 
    std::cout << s.substr(k_start, k_end-k_start+1) << std::endl;
   // 3. '"'なら文字列,0〜9なら数値
    if (s[v_start] == '"') {
        v_end = v_start + 1;
        while(s[v_end] != '"') ++v_end;

        std::cout << s.substr(v_start+1, v_end-v_start+1) << std::endl;
    } else if (s[v_start] >= '0' && s[v_start] <= '9') {
        v_end = v_start;
        while(s[v_end] >= '0' && s[v_end] <= '9') ++v_end;

        std::cout << s.substr(v_start, v_end-v_start) << std::endl;
    } else {
        std::cout << "Neither string nor number" << std::endl;
    }
    
    return 0;
}
output
// 文字列の場合
"hoge"
"huga"
// 数値の場合
"hoge"
333

2.1 パース処理を関数として切り出す

{"hoge": "huga"}{"bar": 111}がパースできるようになりました.ここまでくると,nullやbooleanを値にもつオブジェクトのパースは同じ要領で実装できそうです.このままそれらの実装を進めてもよいのですが,ここでは一度コードを整理しましょう.

ここまでで書いたコードは,主に以下の4つの処理に分解することができそうです.

  1. キーを見つける
  2. キーに対応する値の最初の空白でない文字を見つける
  3. 最初の文字によって値が文字列か数値か判定する
  4. 部分文字列を取り出す

1〜4をそれぞれ関数として切り出しても良いのですが,3に関しては切り出す旨味が無さそうなのでとりあえず保留とします.よって,1, 2, 4の処理を関数として切り出します.具体的には,以下のようになります.

main.cxx
#include <iostream>

int skip_whitespaces(std::string& s, int i) {
    while(s[i] == ' ') i++;
    return i;
}

int skip_colon(int i) {
    return ++i;
}

void parse_string(std::string& s, int& i) {
    int end = i;

    ++end;

    while(s[end] != '"') ++end;

    std::cout <<  "value: " << s.substr(i, end-i+1) << std::endl;
}

void parse_number(std::string& s, int& i) {
    int end = i;

    while(s[end] >= '0' && s[end] <= '9') ++end;

    std::cout << "value: " << s.substr(i, end-i) << std::endl;
}

std::string get_key(std::string& s, int& i) {
    int start = i+1;
    int end;

    while(s[start] != '"') ++start;
    end = start + 1;
    while(s[end] != '"') ++end;

    i = end + 1;
    
    return s.substr(start, end-start+1);
}

int main() {
    std::string s = R"({"hoge": "huga"})"; // or R"({"bar": 111})"
    int current_index = 0;
    // 1. キーを見つける(+取り出す)
    std::string key = get_key(s, current_index);

    std::cout << "key: " << key << std::endl;
    // 2. 値の空白でない最初の文字を見つける
    current_index = skip_whitespaces(s, current_index);
    current_index = skip_colon(current_index);
    current_index = skip_whitespaces(s, current_index);
   // 3. 文字列か数値か判定する
    if (s[current_index] == '"') {
        // 4. 部分文字列を取り出す
        parse_string(s, current_index);
    } else if (s[current_index] >= '0' && s[current_index] <= '9') {
        // 4. 部分文字列を取り出す
	parse_number(s, current_index);
    } else {
        std::cout << "Neither string nor number" << std::endl;
    }
    
    return 0;
}

1の処理がget_key,2の処理がskip_whitespacesskip_colon,4の処理がparse_XXに対応しています.skip_whitespacesskip_colonに関しては可読性を優先して関数として切り出していますが,必ずしも切り出す必要はないですし,切り出すならインライン展開して関数呼び出しのオーバーヘッドを減らす工夫は必要かなと思います.

3. {"hoge": "huga", "bar": 111}をパースする

基本的には繰り返すだけですね.ポイントは以下の通りです(正直ここらへんのインデックスの帳尻合わせみたいなのはもっとスマートにできる方法を探しているので,どなたか教えて頂けると嬉しいです).

  • ループの最初の++current_index{または,をスキップする.
  • ループの最後の1行前の++current_indexは値の最後の文字をスキップする.
  • ループの最後の行のskip_whitespacesはインデックスを,まで進める.

また,省略していますが「parse_XX関数は値の最後の文字のインデックスを返す」というルールに沿ってparse_XX関数も少し変更しています.

main.cxx
#include <iostream>

...

int main() {
    std::string s = R"({"hoge": "huga", "bar": 111})";
    int current_index = 0;

+    while(s[current_index] != '}') {
+       ++current_index;

        std::string key = get_key(s, current_index);

        std::cout << "key: " << key << std::endl;
        
        current_index = skip_whitespaces(s, current_index);
        current_index = skip_colon(current_index);
        current_index = skip_whitespaces(s, current_index);

        if (s[current_index] == '"') {
            parse_string(s, current_index);
        } else if (s[current_index] >= '0' && s[current_index] <= '9') {
            parse_number(s, current_index);
        } else {
            std::cout << "Neither string nor number" << std::endl;
        }

+      ++current_index;
+     current_index = skip_whitespaces(s, current_index);
+  }
    return 0;
}

少し話は逸れますが,個人的には構造化された文字列のパースでは以下の2点が重要だと感じました.

  • 要素(オブジェクトならキーや値)の始点と終点を見つけること
  • 要素の区切りを見つけること(オブジェクトなら,

始点と終点は要素を取り出すために必要で,要素の区切りはループの終了条件と密接に関わってくるからです(...まあJSON以外のパーサはまだ実装したことがないので,ここらへんは今後YAMLパーサなどを実装することで確かめてみたいなと思っています).パーサの実装ではここが重要だよ,とかあればコメント頂けると嬉しいです.

3.1 valueクラスを作成する

ここでちょっと寄り道をして,JSONの値を管理するvalueクラスを作成します.次にパースしたいのは{"hoge": "huga", "bar": 111, "bazz": [10, "piyo"]}な訳ですが,見ての通り,JSONの配列はstringnumberなど異なる型を要素に持つことができます.今後画面に出力するだけでなくライブラリとして便利に値の読み書きができるようにするためには,データ構造上はこれをどうにか型が統一された配列として扱いたくなってきます.そこで,JSONの各値をラップして良い感じに読み書き(や値の追加や削除)をやってくれるクラスがあったら便利だなあ...と思うわけです(ゴリ押し).という訳で,以下ではvalueクラスについて簡単に説明したいと思います.JSONの仕様を確認すると,JSONの値は以下の6種類の値を取ります.

  • object
  • array
  • string
  • number
  • boolean (true, false)
  • null

valueクラスの役割はこれらの6種類の値の型を隠蔽し,値をすべてvalueクラスで統一的に扱う仕組みを提供することです.他にも「JSONの値をすべてコンソールに出力する」といった関数を実装したくなったときにやはりvalueクラスがあると便利です.実際にcxxjpではJSONの値がオブジェクトだろうと配列だろうとvalue.dump()という関数でJSON全体を文字列に変換できる関数があります.

使い方のイメージはこんな感じです.

std::string s = R"({"hoge": "huga", "bar": 111})";
value v;
object o;
err_t err = parse(s, v);

o = value.get<object>();
// Read value
std::cout << o["hoge"].get<std::string>() << std::endl;
std::cout << o["bar"].get<number>() << std::endl;
// Add new value
o["bazz"] = "piyo";
// Update value
o["bar"] = 222;

std::cout << value.dump() << std::endl;
"huga"
111
{"hoge": "huga", "bar": 222, "bazz": "piyoyo"}

valueクラスを作成する上でいくつかポイントがあります.個人的には,valueクラスを作るところが一番C++の勉強になりました.

  • valueクラスのコンストラクタは複数の型を許容する
    • object["hoge"] = value("huga")object["hoge"] = value(111)の両方に対応したいということです.C++ではコンストラクタを多重定義できるので実装は簡単です.
  • =演算子は複数の型を許容する
    • o["bazz"] = "piyo"o["bar"] = 222の両方に対応したいということです.C++では=演算子のオーバーロード及び多重定義が可能なので,これも実装は簡単です.

valueクラスを定義すると,main関数内を以下のように書き換えることができます.
valueクラスの実装の詳細に関してはリポジトリを見てもらえればと思います.

main.cxx
---valueクラスの実装は省略----

int main() {
    std::string s = R"({"hoge": "huga", "bar": 111})";
    int current_index = 0;
    object o;

    while(s[current_index] != '}') {
        ++current_index;

        std::string key = get_key(s, current_index);

        std::cout << "key: " << key << std::endl;
        
        current_index = skip_whitespaces(s, current_index);
        current_index = skip_colon(current_index);
        current_index = skip_whitespaces(s, current_index);

        if (s[current_index] == '"') {
            o[key] = parse_string(s, current_index);
        } else if (s[current_index] >= '0' && s[current_index] <= '9') {
            o[key] = parse_number(s, current_index);
        } else {
            // error
        }

        ++current_index;
        current_index = skip_whitespaces(s, current_index);
    }
    // 上に貼った使用イメージのコードではテンプレートを利用した
    // get関数を実装していますが,ここでは少し手抜きをしています.
    std::cout << o["hoge"].s << std::endl;
    std::cout << o["bar"].n << std::endl;

4. {"hoge": "huga", "bar": 111, "bazz": [10, "piyo"]}をパースする

いよいよ配列のパースです.ここではまずオブジェクトと配列の構造的な類似性に注目します.

  • オブジェクトの構造:{...,...,...}
  • 配列の構造:[...,...,...]

改めて確認してみると,両者に

  • 始点と終点に特定の記号が使用されている
  • 要素を,で区切る

という特徴があることが分かります(当たり前といえば当たり前ですが).ということで,オブジェクトのパースとかなり似たようなコードになりそうです.

5. {"hoge": "huga", "bar": 111, "bazz": [10, 20], "piyo": {"titi": "tete", "tutu": 111}}をパースする

一旦力尽きたのでWIP

Discussion

ログインするとコメントできます