2018/08/05 致命的なミスを修正しました

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型．同様に，false，nullを実装する．

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
        raise 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
        raise 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
        raise 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
    raise MyJSONError.new("invalid 4 hexadecimal digits at #{ptr}") if state == :hexadec
    raise 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] == ']'
            raise MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [arr, ptr+1]
        elsif text[ptr] == ','
            raise 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
    raise 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] == '}'
            raise MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [hash, ptr+1]
        elsif text[ptr] == ','
            raise MyJSONError.new("invalid ',' at #{ptr}") if state != :value
            state = :comma
            ptr += 1
        elsif text[ptr] == ':'
            raise 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
    raise 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
            raise 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
        raise 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
        raise 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
        raise 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
    raise MyJSONError.new("invalid 4 hexadecimal digits at #{ptr}") if state == :hexadec
    raise 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] == ']'
            raise MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [arr, ptr+1]
        elsif text[ptr] == ','
            raise 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
    raise 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] == '}'
            raise MyJSONError.new("invalid ',' at #{ptr}") if state != :initial && state != :value
            return [hash, ptr+1]
        elsif text[ptr] == ','
            raise MyJSONError.new("invalid ',' at #{ptr}") if state != :value
            state = :comma
            ptr += 1
        elsif text[ptr] == ':'
            raise 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
    raise 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
            raise 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

shonen.hateblo.jp

やったこと，しらべたことを書く．

jsonのparserを書く