wstring な JSON 処理系 (その4)

ローダのための JSON構文解析を LR オートマトンで書くことにします。

  1. json クラスのコンストラクタとデスタラクタ
  2. json クラスのコピー・コンストラクタとムーブ・コンストラクタ
  3. dump
  4. load の構文解析 (本稿)
  5. load の字句解析

2015 年 10 月 15 日 還元アクションの dstack の扱いのバグを修正しました。

まず、RFC 7159JSON の EBNF から、 LALR (1) 文法に書き直します。

    json : value
    value : SCALAR | STRING | array | object
    array : '[' ']' | '[' value_list ']'
    value_list : value_list ',' value | value
    object : '{' '}' | '{' member_list '}'
    member_list : member_list ',' STRING ':' value |  STRING ':' value

ここで、SCALAR は null、 true、 false、 number を字句解析でまとめたものです。 字句間の空白も字句解析が読み飛ばすものとします。 これから作成した LR オートマトン構文解析表を今回使います。

loader クラスに、構文解析と字句解析を組み合わせてあります。 parse メンバ関数構文解析を担当します。 他のメンバ関数は字句解析を担当します。

//@<loader クラスを定義します@>=
class loader final {
public:
    typedef std::wstring::const_iterator cursor;
    loader () {}
    ~loader () {}
    bool parse (std::wstring const& src, json& node);

private:
    loader (loader const& x);
    loader& operator=(loader const& x);

    int next_token (cursor& s, cursor const& eos, json& node);
    bool scan_number (cursor& s, cursor const& eos, json& node);
    bool scan_string (cursor& s, cursor const& eos, json& node);
    bool decode_u16 (cursor& s, cursor const& eos, wchar_t& c);

    bool isjsonspace (wchar_t const c)
    {
        return L' ' == c || L'\n' == c || L'\t' == c || L'\r' == c || L'\f' == c;
    }

    bool isjsondigit (wchar_t const c)
    {
        return L'0' <= c && c <= L'9';
    }
};

//@<loader クラスのメンバ関数を定義します@>=
//@<構文解析 parse メンバ関数を定義します@>
//@<字句解析 next_token メンバ関数を定義します@>
//@<字句解析 scan_number メンバ関数を定義します@>
//@<字句解析 scan_string メンバ関数を定義します@>
//@<字句解析 decode_u16 メンバ関数を定義します@>

parse メンバ関数は、 構文解析表をもち、 LR オートマトンになっています。 今回は yacc/bison のやりかたを真似して、 還元アクションを switch 文でオートマトンのループの中に埋め込んでいます。データ・スタックと状態スタックの 2 本のスタックを使って、構文解析をおこないます。データ・スタックの要素に json オブジェクトが入ります。この構文解析ではエラー回復処理をせず、エラーを見つけると直ちに false を返します。dstack の番兵は、還元アクションで yacc/bison 風に右辺の第一項を添字 1 で表すためのダミーとして置いています。

//@<構文解析 parse メンバ関数を定義します@>=
bool loader::parse (std::wstring const& src, json& node)
{
//@<構文解析表 grammar を定義します@>
    std::deque<int> sstack {1};
    std::deque<json> dstack {json (nullptr)}; // 番兵
    std::wstring::const_iterator s = src.cbegin ();
    std::wstring::const_iterator eos = src.cend ();
    json token_value;
    int token_type = next_token (s, eos, token_value);
    for (;;) {
        int ctrl = grammar[sstack.back ()][token_type];
        if (ERROR == ctrl)
            break;
        else if (ctrl > 0) {    // シフト
            sstack.push_back (ctrl);
            dstack.push_back (std::move (token_value));
            token_value = json (nullptr);
            token_type = next_token (s, eos, token_value);
        }
        else if (ctrl < 0) {    // 還元、受理
            int expr = -(ctrl + 1);
            int nrhs = size_rhs[expr];
            json value;
//@<        還元アクションを定義します@>
            for (int i = 0; i < nrhs; ++i) // 先頭一個を GOTO 先の状態へ入れ換えます
                sstack.pop_back ();
            for (int i = 0; i < nrhs; ++i) // 先頭一個を value へ入れ換えます
                dstack.pop_back ();
            int next_state = grammar[sstack.back ()][gotocol[expr]];
            sstack.push_back (next_state);
            dstack.push_back (value);
        }
    }
    return false;
}

構文解析表は疎な行列のままで圧縮データ構造にしていません。 一行が状態に対応し、開始状態は 1 で、ゼロの状態はエラー扱いになります。 一行に ACTION と GOTO を並べてあるものとします。 終了記号の $ までが ACTION で、それより後が GOTO です。 ACTION では、 ゼロはエラー、 正はシフト先の状態番号、 負は還元か受理を表します。 GOTO も、ゼロがエラーで、 正で GOTO 先の状態番号を表します。gotocol 配列で、還元時に使う GOTO 欄を指定し、生成規則の左辺から求めたものになっています。 size_rhs 配列はその名の通りで、還元に使う生成規則の右辺の長さを記録してあります。

//@<構文解析表 grammar を定義します@>=
    enum {NSTATE = 25, LRCOL = 15, ERROR = 0, ACC = -99};
    static int const gotocol[12] = {10, 10, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14};
    static int const size_rhs[12] = {1, 1, 1, 1, 2, 3, 3, 1, 2, 3, 5, 3};
    static int const grammar[NSTATE][LRCOL] = {
        //    [    ]    {    }    :    ,   SC  STR    $  :v  :a :vl  :o :ml
        {0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,  0,  0,  0,  0},//状態
        {0,   7,   0,   8,   0,   0,   0,   3,   4,   0,  2,  5,  0,  6,  0},//1
        {0,   0,   0,   0,   0,   0,   0,   0,   0, ACC,  0,  0,  0,  0,  0},//2
        {0,   0,  -1,   0,  -1,   0,  -1,   0,   0,  -1,  0,  0,  0,  0,  0},//3
        {0,   0,  -2,   0,  -2,   0,  -2,   0,   0,  -2,  0,  0,  0,  0,  0},//4
        {0,   0,  -3,   0,  -3,   0,  -3,   0,   0,  -3,  0,  0,  0,  0,  0},//5
        {0,   0,  -4,   0,  -4,   0,  -4,   0,   0,  -4,  0,  0,  0,  0,  0},//6
        {0,   7,   9,   8,   0,   0,   0,   3,   4,   0, 11,  5, 10,  6,  0},//7
        {0,   0,   0,   0,  12,   0,   0,   0,  14,   0,  0,  0,  0,  0, 13},//8
        {0,   0,  -5,   0,  -5,   0,  -5,   0,   0,  -5,  0,  0,  0,  0,  0},//9
        {0,   0,  15,   0,   0,   0,  16,   0,   0,   0,  0,  0,  0,  0,  0},//10
        {0,   0,  -8,   0,   0,   0,  -8,   0,   0,   0,  0,  0,  0,  0,  0},//11
        {0,   0,  -9,   0,  -9,   0,  -9,   0,   0,  -9,  0,  0,  0,  0,  0},//12
        {0,   0,   0,   0,  17,   0,  18,   0,   0,   0,  0,  0,  0,  0,  0},//13
        {0,   0,   0,   0,   0,  19,   0,   0,   0,   0,  0,  0,  0,  0,  0},//14
        {0,   0,  -6,   0,  -6,   0,  -6,   0,   0,  -6,  0,  0,  0,  0,  0},//15
        {0,   7,   0,   8,   0,   0,   0,   3,   4,   0, 20,  5,  0,  6,  0},//16
        {0,   0, -10,   0, -10,   0, -10,   0,   0, -10,  0,  0,  0,  0,  0},//17
        {0,   0,   0,   0,   0,   0,   0,   0,  21,   0,  0,  0,  0,  0,  0},//18
        {0,   7,   0,   8,   0,   0,   0,   3,   4,   0, 22,  5,  0,  6,  0},//19
        {0,   0,  -7,   0,   0,   0,  -7,   0,   0,   0,  0,  0,  0,  0,  0},//20
        {0,   0,   0,   0,   0,  23,   0,   0,   0,   0,  0,  0,  0,  0,  0},//21
        {0,   0,   0,   0, -12,   0, -12,   0,   0,   0,  0,  0,  0,  0,  0},//22
        {0,   7,   0,   8,   0,   0,   0,   3,   4,   0, 24,  5,  0,  6,  0},//23
        {0,   0,   0,   0, -11,   0, -11,   0,   0,   0,  0,  0,  0,  0,  0},//24
    };

還元アクションで、 データ・スタックに JSON の array と object を組み立てます。データ・スタックの末尾側を利用するため、記述の煩雑さを避けるために、ランダムアクセス・イテレータ v を利用しています。 v の添字 1 は生成規則右辺の先頭シンボルに対応するように割り振ってあります。 v の添字 1 へ組み立てた json ノードを戻し、 入れ子の場合、 次々に親のノードへ追加していきます。 受理 (ACC) では、 データ・スタックの先頭の JSON ノードを取り出して、 parse メンバ関数に参照渡しされているノードの格納場所へ移します。

//@<        還元アクションを定義します@>=
            std::deque<json>::iterator v = dstack.end () - nrhs - 1;
            if (nrhs > 0)
                value = v[1];   // 生成規則の右辺が空でないときのデフォルト値は v[1]
            switch (ctrl) {
            //case  -1: break;  // value : SCALAR
            //case  -2: break;  // value : STRING
            //case  -3: break;  // value : array
            //case  -4: break;  // value : object
            case  -5:   // value : '[' ']'
                value = json (json::array {});
                break;
            case  -6:   // array : '[' value_list ']'
                value = std::move (v[2]);
                break;
            case  -7:   // value_list : value_list ',' value
                v[1].as<json::array> ().push_back (std::move (v[3]));
                break;
            case  -8:   // value_list : value
                {
                    json::array a;
                    a.push_back (std::move (v[1]));
                    value = json (std::move (a));
                }
                break;
            case  -9:   // object : '{' '}'
                value = json (json::object {});
                break;
            case -10:   // object : '{' member_list '}'
                value = std::move (v[2]);
                break;
            case -11:   // member_list : member_list ',' STRING ':' value
                v[1].as<json::object> ()[std::move(v[3].as<std::wstring> ())] = std::move (v[5]);
                break;
            case -12:   // member_list : STRING ':' value
                {
                    json::object h;
                    h[std::move (v[1].as<std::wstring> ())] = std::move (v[3]);
                    value = json (std::move (h));
                }
                break;
            case ACC:
                node = std::move (dstack.back ());
                return true;
            default: break;
            }