shonen.hateblo.jp

やったこと,しらべたことを書く.

jsonのparserを書く

JSONとは

javascriptをベースに設計された,軽量のデータ交換フォーマット.

詳しくは,https://www.json.org/json-ja.html

目的

構文解析を頑張るC++で書いたら型がだるかったのでRubyで書く.

jsonを読み込みたいだけならrequire 'json'

縛り

  • テスト目的以外での json モジュールの使用禁止.
  • #to_i 禁止.ただし1文字の変換を除く.
  • Regex禁止.ただし文字判定を除く.
  • `置換操作メソッドの禁止.

hexadecimalでズルしました…

仕様

  • json文字列末尾に到達する前にparseに成功したならば,parse成功とし,以降の文字を読み込まない.
  • 小数は実装しない

実装

先にコード全体を見たい方はこちら https://ideone.com/q9bdiG

例外

適当

class MyJSONError < StandardError; end

文字判定

空白文字かどうか,数字かどうかを判定するメソッドを書く.

  • text 入力文字列
  • ptr 今見ている文字のインデックス
  • return: 該当する文字ならtrue,それ以外ならfalse
def is_space_char(text, ptr = 0)
    !!(text[ptr]=~/^\s/)
end
def is_digit_char(text, ptr = 0)
    !!(text[ptr]=~/^[0-9]/)
end

parse_json メソッド

利用者は,json_parse('{"foo":1,"bar":null}') の様にメソッドを呼び出すと想定する.

def json_parse(text, ptr = 0)

end

true, false, null

jsonは,最初の1文字目だけ見れば,どの型のデータか判別出来る.例えば1文字目がtならばtrue型.同様に,falsenullを実装する.

  • text 入力文字列
  • ptr 今見ている文字のインデックス
  • return: [value, ptr] 解析結果value,解析後の位置ptr.
def json_parse_true(text, ptr = 0)
    if text[ptr..(ptr+3)] == 'true'
        return [true, ptr+4]
    else
        throw MyJSONError.new("invalid keyword at #{ptr}")
    end
end

def json_parse_false(text, ptr = 0)
    if text[ptr..(ptr+4)] == 'false'
        return [false, ptr+5]
    else
        throw MyJSONError.new("invalid keyword at #{ptr}")
    end
end

def json_parse_null(text, ptr = 0)
    if text[ptr..(ptr+3)] == 'null'
        return [nil, ptr+4]
    else
        throw MyJSONError.new("invalid keyword at #{ptr}")
    end
end

# 作業中
def json_parse(text, ptr = 0)
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == 't'
            return json_parse_true(text, ptr)
        elsif text[ptr] == 'f'
            return json_parse_false(text, ptr)
        elsif text[ptr] == 'n'
            return json_parse_null(text, ptr)
        else
            abort "hogehoge" # todo
        end
    end
end

string

"が来たら,それは文字列.

エスケープ中かどうかの状態を持つ必要があるので,変数stateで管理する.次の状態を取りうる.

  • :string エスケープ中でない
  • :escape \\ が来た直後
  • :hexadec エスケープ\\u の処理状態.\\u直後の4文字を読み込んでいる.
def json_parse_string(text, ptr = 0)
    abort "json_parse_string" if text[ptr] != '"'
    ptr += 1
    state = :string
    str = ""
    hex4 = ""
    while text[ptr]
        if state == :string
            if text[ptr] == '"'
                return [str, ptr+1]
            elsif text[ptr] == "\\" 
                state = :escape
                ptr += 1
            else
                str << text[ptr]
                ptr += 1
            end
        elsif state == :escape
            if text[ptr] == '"'
                str << '"'; state = :string; ptr += 1
            elsif text[ptr] == "\\"
                str << "\\"; state = :string; ptr += 1
            elsif text[ptr] == "/"
                str << "/"; state = :string; ptr += 1
            elsif text[ptr] == "b"
                str << "\b"; state = :string; ptr += 1
            elsif text[ptr] == "f"
                str << "\f"; state = :string; ptr += 1
            elsif text[ptr] == "n"
                str << "\n"; state = :string; ptr += 1
            elsif text[ptr] == "r"
                str << "\r"; state = :string; ptr += 1
            elsif text[ptr] == "t"
                str << "\t"; state = :string; ptr += 1
            elsif text[ptr] == "u"
                hex4 = ""; state = :hexadec; ptr += 1
            end
        elsif state == :hexadec
            hex4 << text[ptr]
            if hex4.size == 4
                str << [hex4.to_i(16)].pack("U")
                state = :string
            end
            ptr += 1
        end
    end
    throw MyJSONError.new("invalid 4 hexadecimal digits at #{ptr}") if state == :hexadec
    throw MyJSONError.new("not found \" at #{ptr}")
    # メモ:シングルクオートはエスケープしないが,
    #       エディタがエスケープするので'\'ではなく"\\"に...
end

def json_parse(text, ptr = 0)
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == 't'
            return json_parse_true(text, ptr)
        elsif text[ptr] == 'f'
            return json_parse_false(text, ptr)
        elsif text[ptr] == 'n'
            return json_parse_null(text, ptr)
        elsif text[ptr] == '"'
            return json_parse_string(text, ptr)
        else
            abort "hogehoge"
        end
    end
end

number

- または数字が来たら,numberである.小数を実装しない分,楽ができる.

def json_parse_number(text, ptr = 0)
    sgn = 1
    val = 0
    if text[ptr] == '-'
        sgn = -1
        ptr += 1
    end
    while is_digit_char(text, ptr)
        val = val*10 + text[ptr].to_i
        ptr += 1
    end
    return [sgn*val, ptr]
end

def json_parse(text, ptr = 0)
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == 't'
            return json_parse_true(text, ptr)
        elsif text[ptr] == 'f'
            return json_parse_false(text, ptr)
        elsif text[ptr] == 'n'
            return json_parse_null(text, ptr)
        elsif text[ptr] == '"'
            return json_parse_string(text, ptr)
        elsif text[ptr] == '-'
            return json_parse_number(text, ptr)
        elsif is_digit_char(text, ptr)
            return json_parse_number(text, ptr)
        else
            abort "hogehoge"
        end
    end
end

array

[が来たら,それは配列.[1, 3, 5, ]のような,無駄なコンマはsyntax errorとした.

文字列と同様,状態を管理しながら解析する.

  • :initial [ を読み込んだ直後
  • :value 文字列やnull等の値を読み込んだ後
  • :comma コンマを読み込んだ後
def json_parse_array(text, ptr = 0)
    abort "json_parse_array" if text[ptr] != '['
    ptr += 1
    arr = []
    state = :initial
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == ']'
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [arr, ptr+1]
        elsif text[ptr] == ','
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :value
            state = :comma
            ptr += 1
        else
            v, ptr = json_parse(text, ptr)
            arr << v
            state = :value
        end
    end
    throw MyJSONError.new("not found ']' at #{ptr}")
end

def json_parse(text, ptr = 0)
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == 't'
            return json_parse_true(text, ptr)
        elsif text[ptr] == 'f'
            return json_parse_false(text, ptr)
        elsif text[ptr] == 'n'
            return json_parse_null(text, ptr)
        elsif text[ptr] == '"'
            return json_parse_string(text, ptr)
        elsif text[ptr] == '-'
            return json_parse_number(text, ptr)
        elsif is_digit_char(text, ptr)
            return json_parse_number(text, ptr)
        elsif text[ptr] == '['
            return json_parse_array(text, ptr)
        else
            abort "hogehoge"
        end
    end
end

object

{が来たら,object.

文字列と同様,状態を管理しながら解析する.

  • :initial { を読み込んだ直後
  • :key pairのキー文字列を読み込んだ後
  • :colon :を読み込んだ後
  • :value 文字列やnull等のpairの値を読み込んだ後
  • :comma ,を読み込んだ後

ん,よく見たらkeyが来ずにいきなりvalueが来た場合の例外処理やってないですね…

def json_parse_object(text, ptr = 0)
    abort "json_parse_object" if text[ptr] != '{'
    ptr += 1
    hash = {}
    key = nil
    state = :initial
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == '}'
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [hash, ptr+1]
        elsif text[ptr] == ','
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :value
            state = :comma
            ptr += 1
        elsif text[ptr] == ':'
            throw MyJSONError.new("invalid ':' at #{ptr}") if state != :key
            state = :colon
            ptr += 1
        elsif text[ptr] == '"' && (state == :comma || state == :initial)
            key, ptr = json_parse(text, ptr)
            state = :key
        else
            # TODO: 
            val, ptr = json_parse(text, ptr)
            hash[key] = val
            state = :value
        end
    end
    throw MyJSONError.new("not found '}' at #{ptr}")
end

def json_parse(text, ptr = 0)
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == 't'
            return json_parse_true(text, ptr)
        elsif text[ptr] == 'f'
            return json_parse_false(text, ptr)
        elsif text[ptr] == 'n'
            return json_parse_null(text, ptr)
        elsif text[ptr] == '"'
            return json_parse_string(text, ptr)
        elsif text[ptr] == '-'
            return json_parse_number(text, ptr)
        elsif is_digit_char(text, ptr)
            return json_parse_number(text, ptr)
        elsif text[ptr] == '['
            return json_parse_array(text, ptr)
        elsif text[ptr] == '{'
            return json_parse_object(text, ptr)
        else
            throw MyJSONError.new("invalid at #{ptr}")
        end
    end
end

完成

https://ideone.com/q9bdiG

class MyJSONError < StandardError; end
    
# - - - - - - - - - - -

def is_space_char(text, ptr = 0)
    !!(text[ptr]=~/^\s/)
end

def is_digit_char(text, ptr = 0)
    !!(text[ptr]=~/^[0-9]/)
end

# - - - - - - - - - - -

def json_parse_true(text, ptr = 0)
    if text[ptr..(ptr+3)] == 'true'
        return [true, ptr+4]
    else
        throw MyJSONError.new("invalid keyword at #{ptr}")
    end
end

def json_parse_false(text, ptr = 0)
    if text[ptr..(ptr+4)] == 'false'
        return [false, ptr+5]
    else
        throw MyJSONError.new("invalid keyword at #{ptr}")
    end
end

def json_parse_null(text, ptr = 0)
    if text[ptr..(ptr+3)] == 'null'
        return [nil, ptr+4]
    else
        throw MyJSONError.new("invalid keyword at #{ptr}")
    end
end

def json_parse_string(text, ptr = 0)
    abort "json_parse_string" if text[ptr] != '"'
    ptr += 1
    state = :string
    str = ""
    hex4 = ""
    while text[ptr]
        if state == :string
            if text[ptr] == '"'
                return [str, ptr+1]
            elsif text[ptr] == "\\" 
                state = :escape
                ptr += 1
            else
                str << text[ptr]
                ptr += 1
            end
        elsif state == :escape
            if text[ptr] == '"'
                str << '"'; state = :string; ptr += 1
            elsif text[ptr] == "\\"
                str << "\\"; state = :string; ptr += 1
            elsif text[ptr] == "/"
                str << "/"; state = :string; ptr += 1
            elsif text[ptr] == "b"
                str << "\b"; state = :string; ptr += 1
            elsif text[ptr] == "f"
                str << "\f"; state = :string; ptr += 1
            elsif text[ptr] == "n"
                str << "\n"; state = :string; ptr += 1
            elsif text[ptr] == "r"
                str << "\r"; state = :string; ptr += 1
            elsif text[ptr] == "t"
                str << "\t"; state = :string; ptr += 1
            elsif text[ptr] == "u"
                hex4 = ""; state = :hexadec; ptr += 1
            end
        elsif state == :hexadec
            hex4 << text[ptr]
            if hex4.size == 4
                str << [hex4.to_i(16)].pack("U")
                state = :string
            end
            ptr += 1
        end
    end
    throw MyJSONError.new("invalid 4 hexadecimal digits at #{ptr}") if state == :hexadec
    throw MyJSONError.new("not found '\"' at #{ptr}")
    # メモ:シングルクオートはエスケープしないが,
    #       エディタがエスケープするので'\'ではなく"\\"に...
end

def json_parse_number(text, ptr = 0)
    sgn = 1
    val = 0
    if text[ptr] == '-'
        sgn = -1
        ptr += 1
    end
    while is_digit_char(text, ptr)
        val = val*10 + text[ptr].to_i
        ptr += 1
    end
    return [sgn*val, ptr]
end

def json_parse_array(text, ptr = 0)
    abort "json_parse_array" if text[ptr] != '['
    ptr += 1
    arr = []
    state = :initial
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == ']'
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [arr, ptr+1]
        elsif text[ptr] == ','
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :value
            state = :comma
            ptr += 1
        else
            v, ptr = json_parse(text, ptr)
            arr << v
            state = :value
        end
    end
    throw MyJSONError.new("not found ']' at #{ptr}")
end

def json_parse_object(text, ptr = 0)
    abort "json_parse_object" if text[ptr] != '{'
    ptr += 1
    hash = {}
    key = nil
    state = :initial
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == '}'
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [hash, ptr+1]
        elsif text[ptr] == ','
            throw MyJSONError.new("invalid ',' at #{ptr}") if state != :value
            state = :comma
            ptr += 1
        elsif text[ptr] == ':'
            throw MyJSONError.new("invalid ':' at #{ptr}") if state != :key
            state = :colon
            ptr += 1
        elsif text[ptr] == '"' && (state == :comma || state == :initial)
            key, ptr = json_parse(text, ptr)
            state = :key
        else
            val, ptr = json_parse(text, ptr)
            hash[key] = val
            state = :value
        end
    end
    throw MyJSONError.new("not found '}' at #{ptr}")
end

def json_parse(text, ptr = 0)
    while text[ptr]
        if is_space_char(text, ptr)
            ptr += 1
        elsif text[ptr] == 't'
            return json_parse_true(text, ptr)
        elsif text[ptr] == 'f'
            return json_parse_false(text, ptr)
        elsif text[ptr] == 'n'
            return json_parse_null(text, ptr)
        elsif text[ptr] == '"'
            return json_parse_string(text, ptr)
        elsif text[ptr] == '-'
            return json_parse_number(text, ptr)
        elsif is_digit_char(text, ptr)
            return json_parse_number(text, ptr)
        elsif text[ptr] == '['
            return json_parse_array(text, ptr)
        elsif text[ptr] == '{'
            return json_parse_object(text, ptr)
        else
            throw MyJSONError.new("invalid at #{ptr}")
        end
    end
end



# - - - - - - - - - - -

def test_sub
    abort "is_space_char" unless is_space_char(" ") == true
    abort "is_space_char" unless is_space_char("t") == false
end
test_sub

def test_main
    abort "failed: true" unless json_parse('true')[0] == true
    abort "failed: false" unless json_parse('false')[0] == false
    abort "failed: null" unless json_parse('null')[0] == nil
    abort "failed: string" unless json_parse('"str"')[0] == 'str'
    abort "failed: escape" unless json_parse('"foo\nbar"')[0] == "foo\nbar"
    abort "failed: hexadecimal" unless json_parse('"\u7D05\u7389"')[0] == "紅玉"
    abort "failed: number" unless json_parse('1234567890')[0] == 1234567890
    abort "failed: negative number" unless json_parse('-1')[0] == -1
    abort "failed: array 1" unless json_parse('[1,2,3]')[0] == [1,2,3]
    abort "failed: array 2" unless json_parse('[1,"foo",null]')[0] == [1,'foo',nil]
    abort "failed: matrix" unless json_parse('[[1,2],[3,4],[5,6]]')[0] == [[1,2],[3,4],[5,6]]
    abort "failed: russian array" unless json_parse('[0,[1,[2,[3,[4]]]]]')[0] == [0,[1,[2,[3,[4]]]]]
    abort "failed: object 1" unless json_parse('{"key":"val"}')[0] == {"key"=>"val"}
    abort "failed: object 2" unless json_parse('{"a":null,"b":[1,2],"c":true,"d":{"x":"\t"}}')[0] == {"a"=>nil,"b"=>[1,2],"c"=>true,"d"=>{"x"=>"\t"}}
end
test_main