JSON Parser (Recursive Descent)

Start from brute force

The obvious approach works on substrings. To parse an array, strip the outer brackets, split the inside on the commas at depth 0 (counting brackets and braces, and skipping commas inside quotes), and parse each piece recursively; an object splits the same way, then splits each piece at its first colon. It works, because every piece is itself a complete JSON value. But every level rescans and copies its whole substring, so a character nested d levels deep is scanned d times: O(n · d) time and space, which is O(n²) for input like [[[[…]]]]. Forget the quote rule and ["a,b"] splits into two broken pieces.

The approach

One cursor, one pass. JSON is designed so that the first non-whitespace character decides what comes next: { is an object, [ an array, " a string, t, f or n a keyword, anything else a number. So there is no backtracking and no need for a separate tokenizer; the reference parses straight from characters. The invariant every function keeps: it starts with pos on the first character of its construct and returns with pos just past it, so no caller ever rescans.

In the reference, value() calls skip() for whitespace and dispatches. string() steps over the opening quote, scans to the next " and slices, which is safe only because this exercise has no escapes. number() takes an optional - and the digits after it. obj() and arr() consume the opening bracket, return early if it closes at once, then loop: read an item (for an object, a string() key, the : and a value()), then continue on , or step over the closing bracket and stop. Nesting needs nothing special, because an item is a value().

Walk through an example

Trace the first example, parse_json('{"a":[1,2,true],"b":null}'), a 25-character string, watching pos only ever move forward.

Complexity

Optimal: O(n) time, because pos only moves forward, each character is examined a constant number of times (a keyword check looks at most five characters ahead), and each string or number is sliced once; O(n) space for the result plus an O(d) call stack for nesting depth d. Brute force (split and recurse on substrings): O(n · d) time and space, O(n²) when deeply nested.

Edge cases to test

• Empty containers with whitespace: [ ] → [] and { } → {}. The early-return check has to come after skip().
• Structural characters inside a string: {"a":"}]"} → {"a": "}]"} and ["a,b"] → ["a,b"]. string() scans to the next quote, so braces and commas inside it are just characters.
• A top-level scalar: the text "hello", quotes included, → the string hello, and false → False. Valid JSON does not have to be an object or an array.
• Malformed input the reference accepts: [1 2] → [1], because whatever is not a comma is consumed as the closing bracket; [1]x → [1] and trueish → True, because nothing checks pos == len(text); 01 → 1, although JSON forbids leading zeros.
• Duplicate keys: {"a":1,"a":2} → {"a": 2}. The last value wins, as it does in Python’s json.loads and JavaScript’s JSON.parse; the JSON standard only says that names should be unique.
• Deep nesting: each level costs two Python frames (value and arr), so about 500 nested brackets exceed the default recursion limit and raise RecursionError.

Common mistakes

• Not recursing for nested objects/arrays — the parser must call itself for values inside values.
• Scanning a string to the next " is correct here only because this exercise rules out escape sequences. A full parser must treat \" as part of the string and decode \n, \\ and \u00e9-style escapes.
• Silently accepting malformed input instead of raising a clear parse error. The reference does this for [1 2]; it fails on [1,] only by accident, when int("") raises.
• Calling skip() in too few places: whitespace may appear before and after every token, including just inside { } and on both sides of a colon.

Follow-ups an interviewer asks next

How would you support escapes and real numbers?

In string(), on a backslash read the next character and map it: \", \\, \/, \b, \f, \n, \r, \t, or \u plus four hex digits, combining two \u escapes when they form a surrogate pair. In number(), accept an optional fraction and exponent, return a float when either is present, and reject leading zeros.

How would you report errors usefully?

Replace every silent pos += 1 with a check of the expected character, such as expect(":"), and raise if pos has not reached the end after the top-level value(). Turn pos into a line and column for the message: the line is the number of newlines before pos plus one, and the column is the distance from the last one.

What if the JSON is a 10 GB file?

Do not build the tree. A streaming parser reads the input in chunks and emits events, such as start of object, key, value and end of array, as soon as each is complete, so memory is bounded by the nesting depth rather than the file size. Python’s ijson library works this way; the caller keeps only the parts it needs.

How do you avoid stack overflow on hostile input?

Either enforce a maximum depth and raise past it, or make the parser iterative: keep an explicit stack of open containers and push or pop on brackets instead of recursing. The second never hits a recursion limit; the first is simpler and also caps the memory an attacker can make one request consume.

Where this shows up

Writing a JSON parser is the classic introduction to recursive-descent parsing, and the same dispatch-then-recurse structure underlies real programming-language parsers, database query engines, and config loaders. It demystifies exactly how any structured text becomes an in-memory data structure.

Reference solution

def parse_json(text):
    pos = 0

    def skip():
        nonlocal pos
        while pos < len(text) and text[pos] in " \t\n\r":
            pos += 1

    def value():
        nonlocal pos
        skip()
        c = text[pos]
        if c == "{": return obj()
        if c == "[": return arr()
        if c == '"': return string()
        if text.startswith("true", pos):  pos += 4; return True
        if text.startswith("false", pos): pos += 5; return False
        if text.startswith("null", pos):  pos += 4; return None
        return number()

    def string():
        nonlocal pos
        pos += 1                    # opening quote
        start = pos
        while text[pos] != '"':
            pos += 1
        res = text[start:pos]
        pos += 1                    # closing quote
        return res

    def number():
        nonlocal pos
        start = pos
        if text[pos] == "-":
            pos += 1
        while pos < len(text) and text[pos].isdigit():
            pos += 1
        return int(text[start:pos])

    def obj():
        nonlocal pos
        pos += 1                    # "{"
        d = {}
        skip()
        if text[pos] == "}":
            pos += 1; return d
        while True:
            skip()
            key = string()
            skip()
            pos += 1                # ":"
            d[key] = value()
            skip()
            if text[pos] == ",":
                pos += 1; continue
            pos += 1                # "}"
            break
        return d

    def arr():
        nonlocal pos
        pos += 1                    # "["
        a = []
        skip()
        if text[pos] == "]":
            pos += 1; return a
        while True:
            a.append(value())
            skip()
            if text[pos] == ",":
                pos += 1; continue
            pos += 1                # "]"
            break
        return a

    return value()


print(parse_json('{"a":[1,2,true],"b":null}'))   # -> {'a': [1, 2, True], 'b': None}
print(parse_json('[1, -2, 3]'))                   # -> [1, -2, 3]

function parseJson(text: string): any {
  let pos = 0;
  const skip = () => { while (pos < text.length && " \t\n\r".includes(text[pos])) pos++; };

  function value(): any {
    skip();
    const c = text[pos];
    if (c === "{") return obj();
    if (c === "[") return arr();
    if (c === '"') return str();
    if (text.startsWith("true", pos))  { pos += 4; return true; }
    if (text.startsWith("false", pos)) { pos += 5; return false; }
    if (text.startsWith("null", pos))  { pos += 4; return null; }
    return number();
  }
  function str(): string {
    pos++;                          // opening quote
    const start = pos;
    while (text[pos] !== '"') pos++;
    const res = text.slice(start, pos);
    pos++;                          // closing quote
    return res;
  }
  function number(): number {
    const start = pos;
    if (text[pos] === "-") pos++;
    while (pos < text.length && text[pos] >= "0" && text[pos] <= "9") pos++;
    return parseInt(text.slice(start, pos), 10);
  }
  function obj(): any {
    pos++;                          // "{"
    const d: any = {};
    skip();
    if (text[pos] === "}") { pos++; return d; }
    while (true) {
      skip();
      const key = str();
      skip();
      pos++;                        // ":"
      d[key] = value();
      skip();
      if (text[pos] === ",") { pos++; continue; }
      pos++;                        // "}"
      break;
    }
    return d;
  }
  function arr(): any[] {
    pos++;                          // "["
    const a: any[] = [];
    skip();
    if (text[pos] === "]") { pos++; return a; }
    while (true) {
      a.push(value());
      skip();
      if (text[pos] === ",") { pos++; continue; }
      pos++;                        // "]"
      break;
    }
    return a;
  }
  return value();
}

console.log(JSON.stringify(parseJson('{"a":[1,2,true],"b":null}'))); // -> {"a":[1,2,true],"b":null}
console.log(JSON.stringify(parseJson('[1, -2, 3]')));                // -> [1,-2,3]