Design a JSON parser

01The design, in the six-step framework

1. Requirements and use cases

Given JSON text, return the equivalent Python value: objects as dicts, arrays as lists, strings, integers and floats, booleans and null. Reject malformed input with a message that says what was expected and at which offset. Handle nested structures of arbitrary depth, string escapes including \u sequences, and negative and exponent numbers.

Out of scope: streaming parse of inputs larger than memory, preserving key order beyond what dicts already do, duplicate-key policy beyond last-wins, and serialisation. A hand-written parser is the exercise; the standard library's json module is the thing you would use in production, and saying so is part of a good answer.

Constraints: one pass over the input; recursion depth bounded by nesting, so pathological inputs need a depth limit; errors carry a position because that is what makes the parser usable.

2. Core entities and relationships

• Lexer: turns characters into a stream of Tokens, each with a TokenKind, its text and its offset. It handles whitespace, strings and numbers so the parser never looks at characters.
• Parser: a recursive-descent parser with one token of lookahead; one method per grammar rule.
• ParseError: carries the offset; both stages raise it.
• The output is plain Python values, deliberately not a custom node class hierarchy: a JSON value is already a composite of dicts and lists.

The parser composes its lexer; the lexer yields tokens lazily, so the two stages run interleaved and memory holds one token at a time beyond the output itself.

3. Interfaces and key methods

class TokenKind(Enum):
    LBRACE = auto(); RBRACE = auto(); LBRACKET = auto(); RBRACKET = auto()
    COLON = auto(); COMMA = auto(); STRING = auto(); NUMBER = auto()
    TRUE = auto(); FALSE = auto(); NULL = auto(); EOF = auto()

@dataclass(frozen=True)
class Token:
    kind: TokenKind
    text: str
    pos: int                  # offset in the source, for error messages

class Lexer:
    def tokens(self) -> Iterator[Token]: ...

class Parser:
    def parse(self) -> object:
        """Returns dict / list / str / int / float / bool / None; raises ParseError with position."""

def loads(text: str) -> object: ...

Invariants: _tok always holds the next unconsumed token; every _expect either consumes exactly that kind or raises; after parse returns, the only remaining token was EOF, so trailing garbage is rejected.

4. Design patterns and the choices behind them

Two stages: tokens first

What varies is the lexical shape (quotes, escapes, whitespace) versus the structure (nesting, commas). Splitting them means the parser's grammar methods read like the grammar, and the lexer can be tested alone on tricky strings. A single character-level recursive parser was rejected because escape handling leaks into every rule (see parsing and tokenizing).

Recursive descent with one-token lookahead

JSON is designed so the first token decides the rule: brace means object, bracket means array, anything else is a scalar. That makes recursive descent the natural fit, and the composite shape of the output falls out of the recursion. A table-driven parser is more than this grammar needs.

Enum token kinds, not string comparisons

An enum for kinds keeps _expect messages exact and makes a typo a NameError rather than a silent mismatch. A class per token kind was rejected: tokens carry no behaviour, so a hierarchy would be ceremony.

Positioned errors at the boundary

Every raise includes the offset of the offending token or character. That turns "invalid JSON" into "expected COLON, found COMMA at offset 42", which is the difference between a parser people curse and one they use (see errors, exceptions and validation).

5. Core flow and code

1. loads('{"a": [1, 2.5, true], "b": null}') builds a Parser, which pulls the first token: LBRACE.
2. parse calls _value; it sees LBRACE and delegates to _object.
3. _object expects a STRING key "a", a COLON, then recurses into _value for the array.
4. _array collects 1 (int), 2.5 (float, because of the dot) and True, consuming commas between them, and expects RBRACKET.
5. Back in _object, a COMMA continues the loop; key "b" maps to None; RBRACE ends it.
6. parse expects EOF; the dict is returned. Had the input ended with a stray comma, _expect(STRING) would raise ParseError naming the offset of the closing brace.

from dataclasses import dataclass
from enum import Enum, auto
from typing import Iterator

class ParseError(Exception):
    def __init__(self, msg: str, pos: int) -> None:
        super().__init__(f"{msg} at offset {pos}"); self.pos = pos

class TokenKind(Enum):
    LBRACE = auto(); RBRACE = auto(); LBRACKET = auto(); RBRACKET = auto()
    COLON = auto(); COMMA = auto(); STRING = auto(); NUMBER = auto()
    TRUE = auto(); FALSE = auto(); NULL = auto(); EOF = auto()

@dataclass(frozen=True)
class Token:
    kind: TokenKind
    text: str
    pos: int

PUNCT = {"{": TokenKind.LBRACE, "}": TokenKind.RBRACE, "[": TokenKind.LBRACKET,
         "]": TokenKind.RBRACKET, ":": TokenKind.COLON, ",": TokenKind.COMMA}
WORDS = {"true": TokenKind.TRUE, "false": TokenKind.FALSE, "null": TokenKind.NULL}
ESCAPES = {'"': '"', "\\": "\\", "/": "/", "b": "\b", "f": "\f", "n": "\n", "r": "\r", "t": "\t"}

class Lexer:
    def __init__(self, src: str) -> None:
        self.src, self.i = src, 0

    def tokens(self) -> Iterator[Token]:
        s = self.src
        while True:
            while self.i < len(s) and s[self.i] in " \t\r\n":
                self.i += 1
            if self.i >= len(s):
                yield Token(TokenKind.EOF, "", self.i); return
            ch, start = s[self.i], self.i
            if ch in PUNCT:
                self.i += 1; yield Token(PUNCT[ch], ch, start)
            elif ch == '"':
                yield Token(TokenKind.STRING, self._string(), start)
            elif ch == "-" or ch.isdigit():
                yield Token(TokenKind.NUMBER, self._number(), start)
            elif ch.isalpha():
                j = self.i
                while j < len(s) and s[j].isalpha(): j += 1
                word = s[self.i:j]
                if word not in WORDS: raise ParseError(f"unknown literal {word!r}", start)
                self.i = j; yield Token(WORDS[word], word, start)
            else:
                raise ParseError(f"unexpected character {ch!r}", start)

    def _string(self) -> str:
        s, out = self.src, []
        self.i += 1                                   # opening quote
        while True:
            if self.i >= len(s): raise ParseError("unterminated string", self.i)
            ch = s[self.i]; self.i += 1
            if ch == '"': return "".join(out)
            if ch == "\\":
                esc = s[self.i]; self.i += 1
                if esc == "u":
                    out.append(chr(int(s[self.i:self.i + 4], 16))); self.i += 4
                elif esc in ESCAPES: out.append(ESCAPES[esc])
                else: raise ParseError(f"bad escape \\{esc}", self.i - 1)
            else:
                out.append(ch)

    def _number(self) -> str:
        s, j = self.src, self.i
        if s[j] == "-": j += 1
        while j < len(s) and (s[j].isdigit() or s[j] in ".eE+-"): j += 1
        text = s[self.i:j]; self.i = j
        return text

class Parser:
    def __init__(self, src: str) -> None:
        self._it = Lexer(src).tokens()
        self._tok = next(self._it)

    def _advance(self) -> Token:
        tok, self._tok = self._tok, next(self._it, self._tok)   # EOF stays current
        return tok

    def _expect(self, kind: TokenKind) -> Token:
        if self._tok.kind is not kind:
            raise ParseError(f"expected {kind.name}, found {self._tok.kind.name}", self._tok.pos)
        return self._advance()

    def parse(self) -> object:
        value = self._value()
        self._expect(TokenKind.EOF)
        return value

    def _value(self) -> object:
        k = self._tok.kind
        if k is TokenKind.LBRACE: return self._object()
        if k is TokenKind.LBRACKET: return self._array()
        tok = self._advance()
        if k is TokenKind.STRING: return tok.text
        if k is TokenKind.NUMBER:
            return float(tok.text) if any(c in tok.text for c in ".eE") else int(tok.text)
        if k is TokenKind.TRUE: return True
        if k is TokenKind.FALSE: return False
        if k is TokenKind.NULL: return None
        raise ParseError(f"unexpected {k.name}", tok.pos)

    def _object(self) -> dict:
        self._expect(TokenKind.LBRACE); out: dict = {}
        if self._tok.kind is TokenKind.RBRACE: self._advance(); return out
        while True:
            key = self._expect(TokenKind.STRING).text
            self._expect(TokenKind.COLON)
            out[key] = self._value()
            if self._tok.kind is TokenKind.COMMA: self._advance(); continue
            self._expect(TokenKind.RBRACE); return out

    def _array(self) -> list:
        self._expect(TokenKind.LBRACKET); out: list = []
        if self._tok.kind is TokenKind.RBRACKET: self._advance(); return out
        while True:
            out.append(self._value())
            if self._tok.kind is TokenKind.COMMA: self._advance(); continue
            self._expect(TokenKind.RBRACKET); return out

def loads(text: str) -> object:
    return Parser(text).parse()

6. Extensions, concurrency and what interviewers probe

• Depth limit: count nesting in _value and raise past, say, 1,000 levels; otherwise a few kilobytes of open brackets overflow the stack.
• Streaming: make the Lexer read from a file object a chunk at a time; the parser is unchanged because it only ever asks for the next token. Emitting values incrementally for a top-level array is a generator variant of _array.
• Typed values instead of dicts: when the interviewer wants an AST (for a visitor or a pretty-printer), introduce JsonValue node classes built by the same rules; an abstract factory passed to the parser lets one grammar produce either dicts or nodes.
• Numbers: the lexer accepts a loose number shape and lets int or float reject the rest; a strict grammar check belongs in _number for a production parser.
• Test first: the example above; every scalar alone; empty object and array; nested arrays; each error case asserting the offset, especially unterminated strings and trailing commas.
• Common mistake: parsing with regular expressions or string splitting, which cannot handle nesting, and swallowing errors into None so bad input looks like null.

02Where this question was reported

• LLD Mastery · Google-tagged (Easy); recursive descent, tokenization
• Codemia · Codemia Advanced 'Compiler Lexer and Parser'
• raw.githubusercontent.com · Build a streaming CSV importer with row validation; parse and evaluate a simple expression/DSL