JSON デコーダ (Wirth の表制御型構文解析法)

Wirth 教授の表制御下向き構文解析器に合成属性を組み込んで JSONデコーダとします。

https://gist.github.com/tociyuki/04875e7c78e86b701daca803c0c80789

文字エンコーディングUTF-8 入力エンコーディングUTF-8 内部エンコーディングとします。
JSON のデコード結果は再帰データ型になります。 これの基本型は数値・文字列・null 定数・true 定数・false 定数です。 複合型は連想配列 object 型・配列 array 型です。

JsonData = JSON_NULL | JSON_TRUE | JSON_FALSE
         | Number | String
         | [(String, JsonData)]
         | [JsonData]

今回は間接参照を使う簡易方式で再帰データ型を扱うことにします。 データ・オブジェクトに識別子を割り当てて、 複合型からは識別子で間接参照します。 識別子はデータの型定数とありかを整数にパックしたもので、 この手の実装の慣例にしたがいハンドルと呼ぶことにします。 ところで、 JSON の数値をどうするかですが、 C++ では様々な数値型がありえるので、 数値のデコード結果を文字列のままとして、 数値への変換は利用する側へ遅延させることにします。 もちろん、 文字列で表現してある数値は number 型として、 文字列そのものである string 型から区別するようにします。

データを間接参照すれば良いため、 データ表現は単純で、 それぞれのデータ型ごとにベクタに並べます。

// 例: (m_string[i] にある文字列データへのハンドル) == T_STRING + i 
enum {
    T_NUMBER = 0x10000000L, T_STRING = 0x20000000L, T_OBJECT = 0x30000000L,
    T_ARRAY  = 0x40000000L, T_NULL   = 0x50000000L, T_TRUE   = 0x60000000L,
    T_FALSE  = 0x70000000L
};

struct yybox_type {
    long m_root;
    std::vector<std::string> m_number;
    std::vector<std::string> m_string;
    std::vector< std::unordered_map<std::string, long> > m_object;
    std::vector< std::vector<long> > m_array;
};

デコーダは前稿の parse_loop を yybox_type でインスタンス化したものになります。

//@<decode_utf8 手続き定義@>
//@<encode_utf8 手続き定義@>
//@<decode_backslash_u4 手続き定義@>

bool
yydecode_json (std::string const& source, yybox_type& box)
{
    enum { NONTERMINAL = 1, EMPTY, TERMINAL, LOOKAHEAD, YIELD,
           NCODE = 77 };
    static unsigned long const yycode[NCODE] = {
//@<仮想コード@>
//  ↑前稿参照
    };
    std::vector<long> kont;

//前稿と同じなので途中略

    return matched;
}

合成属性は 14 通りあります。 すべての合成属性はスキャンポインタを mark に記録するため、 mark 合成属性では他におこなうことがないので、 switch 文に mark 以外の 13 通りを記述します。

//@<合成属性の作業変数定義@>=
    std::vector<long> value_stack;
    std::vector<std::string> key_stack;
    std::string literal;
    long value, item, before_ucode;
    std::string::const_iterator mark = source.cbegin ();

//@<合成属性の処理@>=
            switch (symbol) {
//@<        {save} (mark ... scanpos) の文字列を literal 変数へ@>
//@<        {litval} literal 変数から null、 true、 false 定数を value_stack へ@>
//@<        {numval} number データを作り、 ハンドルを value_stack へ@>
//@<        {strval} literal 変数から string データを作り、 ハンドルを value_stack へ@>
//@<        {aryval} array データを作り、 ハンドルを value_stack へ@>
//@<        {aryitem} value_stack から array データにハンドルを追加@>
//@<        {objval} object データを作り、 ハンドルを value_stack へ@>
//@<        {strkey} literal 変数を key_stack へ@>
//@<        {objmem} key_stack と value_stack から object データにハンドルを追加@>
//@<        {strlit} 文字列を literal 変数へ作る準備@>
//@<        {stra7} 7 ビット ASCII 文字を literal 変数へ追加@>
//@<        {stru8} UTF-8 の 1 コードポイントを literal 変数へ追加@>
//@<        {stre16} \uXXXX の 1 コードポイントを literal 変数へ追加@>
//@<        {strsng} \\ \/ \" \b 等を literal 変数へ追加@>
            }
            mark = scanpos;

//@<合成結果取り出し@>=
    box.m_root = (matched) ? value_stack.back () : 0;

save 合成属性は name 規則で用います。 これにより、 mark からスキャンポインタまでの名前部分を literal 作業変数へ格納します。

//@<        {save} (mark ... scanpos) の文字列を literal 変数へ@>=
            case 0x01: // {save}
                literal.assign (mark, scanpos);
                break;

litval 合成属性は literal 変数から、 3 つのリテラル定数のハンドルを value_stack へプッシュします。 literal 変数が定数でないときは、 解析状況を失敗にします。 value 規則では、 失敗を救済しないので、 これでデコード全体が失敗して打ちきられます。

//@<        {litval} literal 変数から null、 true、 false 定数を value_stack へ@>=
            case 0x02: // {litval}
                if (literal == "null")
                    value_stack.push_back (T_NULL);
                else if (literal == "true")
                    value_stack.push_back (T_TRUE);
                else if (literal == "false")
                    value_stack.push_back (T_FALSE);
                else
                    matched = false;
                break;

numval 合成属性は、 mark からスキャンポインタまでの数値部分を number オブジェクトとして切り出し、 value_stack へそれのハンドルをプッシュします。 既に述べたように、 number オブジェクトは文字列であり、 数値への変換はデコーダを利用する側へ遅延します。

//@<        {numval} number データを作り、 ハンドルを value_stack へ@>=
            case 0x03: // {numval}
                value_stack.push_back (box.m_number.size () + T_NUMBER);
                box.m_number.emplace_back (mark, scanpos);
                break;

strval 合成属性は、 literal 変数にデコード済みの文字列リテラルを string オブジェクトへ移動し、 value_stack へそれへのハンドルをプッシュします。

//@<        {strval} literal 変数から string データを作り、 ハンドルを value_stack へ@>=
            case 0x04: // {strval}
                value_stack.push_back (box.m_string.size () + T_STRING);
                box.m_string.emplace_back ();
                std::swap (box.m_string.back (), literal);
                break;

aryval 合成属性は、 空の配列データを作り、 value_stack へそれへのハンドルをプッシュします。 これは array 規則の先頭で実行されます。 配列に何もいれないときは空配列のままで、 値を入れたときは入れられた配列として value_stack に入ったままになります。

//@<        {aryval} array データを作り、 ハンドルを value_stack へ@>=
            case 0x05: // {aryval}
                value_stack.push_back (box.m_array.size () + T_ARRAY);
                box.m_array.push_back ({});
                break;

aryitem 合成属性は、 配列の末尾に一個の値へ追加します。 value_stack からポップしたものが値のハンドルで、 value_stack の先頭に配列のハンドルが露出するので、 それが間接参照する配列データ・オブジェクトへ値のハンドルをプッシュします。 この合成属性は array 規則で、 value ごとに実行されていきます。

//@<        {aryitem} value_stack から array データにハンドルを追加@>=
            case 0x06: // {aryitem}
                item = value_stack.back ();
                value_stack.pop_back ();
                value = value_stack.back ();
                box.m_array[value - T_ARRAY].push_back (item);
                break;

strkey 合成属性は、 literal 変数に入っている文字列を key_stack へプッシュします。 value_stack はハンドルを入れるので long のベクタであり、 std::string のキーをプッシュできないため、 別に key_stack を分けています。 この属性は object 規則で使います。

//@<        {strkey} literal 変数を key_stack へ@>=
            case 0x08: // {strkey}
                key_stack.emplace_back ();
                std::swap (key_stack.back (), literal);
                break;

objmem 合成属性は、 key_stack と value_stack からそれぞれキーとハンドルをポップして、 value_stack の先頭にある object データのキーにハンドルをセットします。 この属性は object 規則で使います。

//@<        {objmem} key_stack と value_stack から object データにハンドルを追加@>=
            case 0x09: // {objmem}
                std::swap (literal, key_stack.back ());
                key_stack.pop_back ();
                item = value_stack.back ();
                value_stack.pop_back ();
                value = value_stack.back ();
                box.m_object[value - T_OBJECT][literal] = item;
                break;

strlit 合成属性は、 string 規則の先頭で用いて、 literal 作業変数へ文字列リテラルを作っていく準備をします。 文字列リテラルにはバックスラッシュ u 記法で表した UTF-16 サロゲート・ペアが出現することがあるので、 ペアのシーケンスを扱うために、 直前の UTF-16 コードを before_ucode 変数へ覚えておきます。

//@<        {strlit} 文字列を literal 変数へ作る準備@>=
            case 0x0a: // {strlit}
                literal.clear ();
                before_ucode = 0;
                break;

stra7 合成属性は、 文字列リテラル表記中の 7 ビット ASCII 一文字を literal 変数へ追加します。 ここで、 match_octet には u00 終端記号にマッチしたオクテットが入っています。 この属性実行時の octet には、 u00 終端記号にマッチした次のオクテットが先読みされて入っているので、 match_octet の方を使います。

//@<        {stra7} 7 ビット ASCII 文字を literal 変数へ追加@>=
            case 0x0b: // {stra7}
                before_ucode = match_octet;
                literal.push_back (before_ucode);
                break;

stru8 合成属性は、 文字列リテラル表記中の UTF-8 エンコーディングのマルチバイトの 1 コードポイント分を literal 変数へ追加します。 追加する前に decode_utf8 手続きで正当な範囲の UTF-8 シーケンスなのかどうかをチェックします。 チェックで不正シーケンスだと判断さらたときは -1 をコードポイントが返されます。

//@<        {stru8} UTF-8 の 1 コードポイントを literal 変数へ追加@>=
            case 0x0c: // {stru8}
                before_ucode = decode_utf8 (mark);
                matched = (before_ucode >= 0);
                if (matched)
                    literal.append (mark, scanpos);
                break;

decode_utf8 手続きで範囲外チェックするのは、 それぞれのマルチバイト長さごとで表現できるコードポイントの下限を下回っていないかどうかと、 UTF-8 では存在するはずがないサロゲートペアではないことの 2 点です。 未定義コードポイントの判定はおこなっていません。

//@<decode_utf8 手続き定義@>=
static inline bool is_upair (long c)    { return 0xd800 <= c && c <= 0xdfff; }
static inline bool is_upair_hi (long c) { return 0xd800 <= c && c <= 0xdbff; }
static inline bool is_upair_lo (long c) { return 0xdc00 <= c && c <= 0xdfff; }

static long
decode_utf8 (std::string::const_iterator s)
{
    long c = static_cast<unsigned char> (s[0]);
    if (0xc0 == (0xe0 & c)) {
        c = ((0x1f & c) << 6)
          | (0x3f & static_cast<unsigned char> (s[1]));
        c = (0x80 <= c) ? c : -1;
    }
    else if (0xe0 == (0xf0 & c)) {
        c = ((((0x0f & c) << 6)
          | (0x3f & static_cast<unsigned char> (s[1]))) << 6)
          | (0x3f & static_cast<unsigned char> (s[2]));
        c = is_upair (c) ? -1 : 0x800 <= c ? c : -1;
    }
    else if (0xf0 == (0xf8 & c)) {
        c = ((((((0x07 & c) << 6)
          | (0x3f & static_cast<unsigned char> (s[1]))) << 6)
          | (0x3f & static_cast<unsigned char> (s[2]))) << 6)
          | (0x3f & static_cast<unsigned char> (s[3]));
        c = (0x10000 <= c && c <= 0x10ffff) ? c : -1;
    }
    return c;
}

stre16 は、 コードポイント値表記を解釈し、 UTF-8 エンコーディングエンコードして literal 変数へ追加します。 このとき、 JSON は U+FFFF より大きなコードポイントをサロゲート・ペアで表記すると RFC 7159 で決めてあるので、 その処理もおこないます。 before_ucode 変数にいちいちコードポイントを記録していく必要があるのは、 サロゲート・ペアのデコードのためです。

//@<        {stre16} \uXXXX の 1 コードポイントを literal 変数へ追加@>=
            case 0x0d: // {stre16}
                before_ucode = decode_backslash_u4 (before_ucode, mark);
                matched = (before_ucode >= 0);
                if (matched && ! is_upair (before_ucode))
                    encode_utf8 (before_ucode, literal);
                break;

コードポイント値表記の解釈は decode_backslash_u4 手続きでおこないます。 4桁の 16 進数表記からコードを求めて、 サロゲート・ペアからコード・ポイントを求めます。 不正なサロゲート・ペアのシーケンスへは、 -1 を返します。

//@<decode_backslash_u4 手続き定義@>=
static long
decode_backslash_u4 (long before, std::string::const_iterator mark)
{
    long c = 0;
    for (int i = 2; i < 6; ++i) {
        long const x = mark[i];
        c = (c << 4) + ( x <= '9' ? x - '0'
                       : 'a' <= x ? x - 'a' + 10 : x - 'A' + 10);
    }
    if (is_upair_hi (c))
        c = is_upair_hi (before) ? -1 : c;
    else if (is_upair_lo (c))
        c = is_upair_hi (before) ? ((before - 0xd800) << 10) + c + 0x2400 : -1;
    return c;
}

encode_utf8 手続きで、 UTF-8 エンコーディングして literal 変数へ追加します。 これに関してはひねりはありません。

//@<encode_utf8 手続き定義@>=
static void
encode_utf8 (long c, std::string& str)
{
    if (c < 0x80) {
        str.push_back (c);
    }
    else if (c < 0x800) {
        str.push_back (((c >>  6) & 0xff) | 0xc0);
        str.push_back (( c        & 0x3f) | 0x80);
    }
    else if (c < 0x10000) {
        str.push_back (((c >> 12) & 0x0f) | 0xe0);
        str.push_back (((c >>  6) & 0x3f) | 0x80);
        str.push_back (( c        & 0x3f) | 0x80);
    }
    else if (c < 0x110000) {
        str.push_back (((c >> 18) & 0x07) | 0xf0);
        str.push_back (((c >> 12) & 0x3f) | 0x80);
        str.push_back (((c >>  6) & 0x3f) | 0x80);
        str.push_back (( c        & 0x3f) | 0x80);
    }
}

最後の合成属性 strsng です。 これはバックスラッシュに続く一文字のエスケープ文字をデコードして、 literal 変数へ追加します。 この合成属性自体ではバックスラッシュに続く文字を制限していません。

//@<        {strsng} \\ \/ \" \b 等を literal 変数へ追加@>=
            case 0x0e: // {strsng}
                before_ucode = match_octet;
                switch (before_ucode) {
                case 'b': before_ucode = '\b'; break;
                case 'f': before_ucode = '\f'; break;
                case 'n': before_ucode = '\n'; break;
                case 'r': before_ucode = '\r'; break;
                case 't': before_ucode = '\t'; break;
                }
                literal.push_back (before_ucode);
                break;

バックスラッシュの後に許す文字に制限をつけたいときは、 終端記号と octet の比較部分でおこないます。 なお、 前稿では、 7 ビット ASCII のプリント文字とブランクのうち u, U, x の 3 文字以外をすべて許しています。 これを規格通りに制限するには、 esc00 の文字集合比較部分を書き直します。

//@<terminal のシンボルと octet を比較@>=
            switch (symbol) {
            case 0x100: matched = std::isspace (octet) && '\v' != octet; break;  // space
            case 0x101: matched = (octet < 0); break;                            // eof
            case 0x102: matched = std::isdigit (octet); break;                   // digit
            case 0x103: matched = (std::isalpha (octet) || '_' == octet); break; // nmfst
            case 0x104: matched = (std::isalnum (octet) || '_' == octet); break; // nmchar
            case 0x105: matched = (0x20 <= octet && octet <  0x7f); break;       // u00
            case 0x106: matched = (0x80 <= octet && octet <= 0xbf); break;       // u80
            case 0x107: matched = (0xc0 <= octet && octet <= 0xdf); break;       // uc0
            case 0x108: matched = (0xe0 <= octet && octet <= 0xef); break;       // ue0
            case 0x109: matched = (0xf0 <= octet && octet <= 0xf7); break;       // uf0
            case 0x10a: matched = std::isxdigit (octet); break;                  // xdigit
            case 0x10b: // esc00
                matched = ('\\' == octet || '/' == octet || '"' == octet || 'b' == octet
                            'f' == octet || 'n' == octet || 'r' == octet || 't' == octet);
#if 0
                matched = (0x20 <= octet && octet < 0x7f && 'U' != octet && 'x' != octet);
#endif
                break;
            default:    matched = (symbol == octet); break;
            }