JSONパーサを自作する

何を作るか

作るのは、JSON文字列を受け取り、対応するデータ構造（辞書・配列・文字列・数値・真偽・null）へ変換する最小のパーサです。{"n":[1,true,null]} のような入力を、ネストした辞書と配列に組み立てて返します。既製の json.loads を使えば1行ですが、あえて自作すると、あらゆる言語処理系の土台である「字句解析」と「構文解析」の2段構成が体で分かります。

得られる理解は3つです。第一に、なぜ処理を2段に割るのか。文字を1文字ずつ見る仕事（トークン化）と、トークンの並びが文法に合うか見る仕事（構文組み立て）を分けると、それぞれが単純になります。第二に、再帰的な文法（値の中に値が入る構造）を、再帰する関数へそのまま写し取る技法。これはJSONに限らずプログラミング言語のパーサにも通じます。第三に、エラー位置の報告をどう仕込むか。実務のパーサはエラーメッセージの質が価値を左右します。

最小実装の全体像

横にスクロール

パイプラインは2段です。入力文字列はまず字句解析器（レキサ）へ渡り、意味のある最小単位であるトークンの列になります。{"a":12} は [ '{', 文字列"a", ':', 数値12, '}' ] という6個のトークン列に変わります。空白はここで捨てます。次にそのトークン列を構文解析器（パーサ）が読み、文法に沿って構文木（ここではネストした辞書・配列）へ組み上げます。

なぜ分けるかというと、関心が別だからです。レキサは「どこからどこまでが1つの数値か」「文字列のエスケープをどう解くか」という文字レベルの面倒を引き受けます。パーサは個々の文字を一切見ず、トークンの種別だけを見て「今は値が来るはず」「配列なら次はカンマか閉じ括弧」と文法を判断します。役割を混ぜると、どちらの視点も同時に扱う複雑なコードになります。

トークンには種別と、後の報告のために元テキスト上の行・列を持たせます。

from dataclasses import dataclass

@dataclass
class Token:
    kind: str        # '{' '}' '[' ']' ':' ',' 'str' 'num' 'bool' 'null' 'eof'
    value: object     # 文字列や数値の実体。記号なら None
    line: int
    col: int

種別（kind）を記号そのものの文字にしておくと、パーサ側で tok.kind == ',' のように直感的に比較できます。文字列・数値・真偽・nullは実体を value に持ちます。入力の終端には番兵として eof トークンを置くと、パーサが末尾を特別扱いせずに済みます。

段階を追って作る

1. 字句解析器を書く

レキサは位置カーソルを1つ持ち、現在の文字を見て種別を判定しながら前進します。記号（{ } [ ] : ,）は1文字で即トークン化。空白（スペース・タブ・改行）は読み飛ばします。文字列・数値・リテラルはそれぞれ専用の読み取りへ分岐します。

def tokenize(s):
    i, line, col = 0, 1, 1
    tokens = []
    while i < len(s):
        c = s[i]
        if c in ' \t\r':
            i, col = i + 1, col + 1
        elif c == '\n':
            i, line, col = i + 1, line + 1, 1
        elif c in '{}[]:,':
            tokens.append(Token(c, None, line, col))
            i, col = i + 1, col + 1
        elif c == '"':
            start = col                                  # トークン開始位置を控える
            i, col, val = read_string(s, i, line, col)
            tokens.append(Token('str', val, line, start))
        elif c == '-' or c.isdigit():
            start = col
            i, col, val = read_number(s, i, line, col)
            tokens.append(Token('num', val, line, start))
        else:
            i, col, tok = read_literal(s, i, line, col)  # true/false/null
            tokens.append(tok)
    tokens.append(Token('eof', None, line, col))
    return tokens

数値の読み取りが山場です。JSONの数値は「省略可能な符号、整数部、省略可能な小数部、省略可能な指数部」という形で、正規表現 -?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][+-]?[0-9]+)? に一致します。先頭ゼロの連続（01）や小数点で終わる形（1.）は不正です。実装では該当する文字が続く限りカーソルを進め、切り出した部分文字列を数値へ変換します。小数点や指数が含まれれば浮動小数点、なければ整数として扱うのが自然です。

文字列はエスケープが要点です。開き引用符の次から閉じ引用符まで読みますが、途中の \ は次の1文字と組で特殊文字を表します。\n は改行、\t はタブ、\" は引用符そのもの、\uXXXX は16進4桁のコードポイントです。

ESCAPES = {'"': '"', '\\': '\\', '/': '/', 'n': '\n',
           't': '\t', 'r': '\r', 'b': '\b', 'f': '\f'}

def read_string(s, i, line, col):
    i, col = i + 1, col + 1       # 開き " を飛ばす
    out = []
    while s[i] != '"':
        if s[i] == '\\':
            nxt = s[i + 1]
            if nxt == 'u':
                code = int(s[i+2:i+6], 16)   # \uXXXX を4桁16進で解釈
                out.append(chr(code))
                i, col = i + 6, col + 6
            else:
                out.append(ESCAPES[nxt])
                i, col = i + 2, col + 2
        else:
            out.append(s[i])
            i, col = i + 1, col + 1
    return i + 1, col + 1, ''.join(out)   # 閉じ " の次へ

2. 再帰下降パーサを書く

ここで文法を見ます。JSONの構造を簡略化した文法規則（BNF風）はこうです。

value  = object | array | string | number | 'true' | 'false' | 'null'
object = '{' ( pair ( ',' pair )* )? '}'
pair   = string ':' value
array  = '[' ( value ( ',' value )* )? ']'

再帰下降パーサの核心は、この文法規則1つを関数1つに機械的に写すことです。value を解析する parse_value、object を解析する parse_object、array を解析する parse_array を作ります。value が object を含み object が value を含むという文法の再帰が、関数の相互再帰にそのまま対応します。パーサはトークン列に対する1つのカーソルを持ち、「現在のトークン」を見て次の一手を決めます。

class Parser:
    def __init__(self, tokens):
        self.toks, self.pos = tokens, 0

    def peek(self):  return self.toks[self.pos]        # 見るだけ
    def next(self):
        t = self.toks[self.pos]; self.pos += 1; return t
    def expect(self, kind):                            # 種別を確認して消費
        t = self.next()
        if t.kind != kind:
            raise JsonError(f"{kind} を期待", t)
        return t

    def parse_value(self):
        t = self.peek()
        if   t.kind == '{':   return self.parse_object()
        elif t.kind == '[':   return self.parse_array()
        elif t.kind == 'str': return self.next().value
        elif t.kind == 'num': return self.next().value
        elif t.kind in ('bool', 'null'): return self.next().value
        raise JsonError("値を期待", t)

parse_value は先頭トークンの種別だけで分岐を1つに確定できます。JSONでは各値の種類が最初のトークンで一意に決まる（{ なら必ずオブジェクト）ため、1トークン先読みで迷いなく進めます。この「1つ見れば規則が決まる」性質が再帰下降を素直にします。

オブジェクトと配列は、開き括弧・要素の並び・閉じ括弧という同じ骨格です。空でなければ「要素、その後カンマがある限り要素を繰り返す」という形を、while でカンマを消費するループに写します。

    def parse_object(self):
        self.expect('{')
        obj = {}
        if self.peek().kind == '}':      # 空オブジェクト
            self.next(); return obj
        while True:
            key = self.expect('str').value
            self.expect(':')
            obj[key] = self.parse_value()    # ここで再帰
            if self.peek().kind == ',':
                self.next(); continue
            self.expect('}'); return obj

obj[key] = self.parse_value() の一行が再帰の要です。値の位置で再び parse_value を呼ぶことで、ネストしたオブジェクトや配列がいくらでも深く入れ子になっても、同じ関数群が自然に降りていきます。配列も parse_array で [ を消費し、要素として parse_value を呼ぶ点だけが違い、骨格は同一です。最後に、入力全体を消費し終えたら次が eof であることを確認します。{}} のような末尾のゴミは、値を1つ読んだ後に eof が来ないことで検出できます。

3. エラー位置を報告する

パースの失敗を「不正なJSON」とだけ返すのは実務では不十分です。レキサが各トークンへ行・列を仕込んであるので、パーサは失敗したトークンの位置をそのまま添えられます。

class JsonError(Exception):
    def __init__(self, msg, tok):
        super().__init__(f"{tok.line}行{tok.col}列: {msg} (実際は {tok.kind})")

{"a" 12} を食わせると、コロンを期待する expect(':') が数値トークンで失敗し、1行6列: : を期待 (実際は num) と、どこで何を期待して何が来たかを返せます。位置情報を字句解析の時点で全トークンに持たせておくのが、質の高いエラー報告の下準備です。

発展と本物との違い

この最小実装は原理を通すことを優先し、実運用のパーサが持つ要素をいくつも省いています。

最大の違いはストリーミングです。数GBのJSONを全文メモリに載せるのは非現実的なので、実装（例: SAX的な逐次パーサ）は入力を少しずつ読みながら「オブジェクト開始」「キー」「値」といったイベントを呼び出し側へ流し、木を丸ごとは保持しません。カーソルを配列添字ではなくストリーム上の位置に置き換える発想です。

数値も差が出ます。JSONの仕様上は数値の桁数に上限がなく、10^400 のような値も書けます。多くの言語の浮動小数点はこれを表現できず精度が落ちるため、金額など正確さが要る用途では任意精度の整数・小数型へ写すか、あえて文字列のまま保持する実装があります。整数の範囲を超える値の扱いは、JSONを使う系の間で相互運用性の落とし穴になりがちです。

原理をさらに掘るなら、文字とバイトの境界や文字コードの扱いはプログラミングの各トピックが、パースしたデータをどう保存・交換するかはWeb側のデータ形式の解説が土台になります。まずは手元でこの200行強を写経し、{"nested":{"a":[1,2,{"b":true}]}} のような深いネストが同じ関数群だけで解けることを確かめると、再帰下降の効き目が一番よく分かります。