jsonのparserを書く
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
で管理する.次の状態を取りうる.
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
完成
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