Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 61 ยท Projects

Project: A JSON Parser and Pretty-Printer

Build a complete JSON parser and pretty-printer in Python: a lexer, a recursive descent parser, error messages with a caret, and a test against the json module.

JSON is the perfect first real-world language for a compiler project. Its whole grammar fits on one page, yet it has everything a front end needs: a lexer with strings, escapes and numbers, a recursive grammar, and a strong requirement for good error messages, because humans type JSON by hand and get it wrong all the time. There is also an authoritative answer key: Python's own json module. If your parser and json.loads ever disagree, you know which one has the bug.

In this project you build the whole thing from the ground up: a lexer that remembers where every token started, a recursive descent parser that produces Python values, an error reporter that points at the exact character, a pretty-printer, and a test run that compares your work with the standard library. If recursive descent is new to you, read Writing a Recursive Descent Parser first; the lexer ideas come from Writing a Complete Lexer.

The grammar

The JSON specification (RFC 8259) describes six kinds of values. In EBNF, the entire syntax is:

TEXT
value   = object | array | STRING | NUMBER | "true" | "false" | "null" ;
object  = "{" ( pair ( "," pair )* )? "}" ;
pair    = STRING ":" value ;
array   = "[" ( value ( "," value )* )? "]" ;

Everything else is lexical. A STRING is double-quoted with a fixed set of escapes. A NUMBER is an optional minus, an integer part with no leading zeros, and optional fraction and exponent parts. Whitespace (space, tab, newline, carriage return) may appear between any two tokens. That is all.

Two details trip up almost every first attempt, so decide on them early:

  • Numbers. 01, +1, .5 and 1. are all invalid JSON. -0 is valid. The pattern is -?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][+-]?[0-9]+)?.
  • No trailing commas, no comments, no single quotes. Many "JSON-like" formats allow them. Real JSON does not, and a strict parser must reject them.
flowchart LR
    T["Text"] --> L["Lexer<br/>tokens with positions"]
    L --> P["Parser<br/>recursive descent"]
    P --> V["Python value<br/>dict, list, str, int, float, bool, None"]
    V --> D["Pretty-printer"]
    L -. "JSONError(pos)" .-> E["Error reporter<br/>line, column, caret"]
    P -. "JSONError(pos)" .-> E

Both stages raise the same error type carrying a character offset; one function turns it into a friendly message.

Step 1: a lexer that remembers positions

Every token records the offset where it starts. Offsets are the cheapest position to track, and a single helper can convert an offset to a line and column later, only when an error needs it.

The lexer handles four families: punctuation ({ } [ ] : ,), strings (with escape processing), numbers, and the three keywords. Notice how the string reader is a small state machine of its own: it must handle \n-style escapes, a backslash followed by u and four hex digits, and the rule that raw control characters (like a real newline) may not appear inside a string. For characters outside the Basic Multilingual Plane, JSON writes a surrogate pair of two \u escapes, and the lexer combines them.

Python Step 1: the JSON lexer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the token list: every token knows its offset, and the string token for "Python" carries the already-decoded value. The second half shows the lexer rejecting four kinds of bad input, each with the offset of the offending character. Offsets are all you need from the lexer; turning them into something readable is a separate job.

Step 2: a recursive descent parser

The grammar has one rule per value shape, so the parser has one method per rule. parse_value looks at the current token and decides which rule applies. This is predictive parsing with one token of lookahead: { can only start an object, [ only an array, and so on, so the parser never has to guess or backtrack. (The grammar is LL(1), a property you can check with FIRST and FOLLOW sets.)

The parser builds Python values directly instead of a tree of nodes. For a data format that is the natural choice: the "AST" of JSON is just dicts and lists. For a programming language you would build node objects, as in Abstract Syntax Trees.

Two rules make a parser robust:

  1. Always say what was expected and what was found. "expected , or ] but found }" is a message a person can act on.
  2. Limit the nesting depth. A malicious document of 100,000 [ characters would otherwise overflow the Python call stack. A depth counter turns that into a clean error.

Step 3: error messages with a caret

A compiler is judged by its errors. The reporter below converts an offset into a line and column and prints the offending line with a ^ under the problem, the same layout compilers like GCC and rustc use. Run the full parser here, including the pretty-printer from step 4, which is only a few lines more.

Python Steps 2 to 4: parser, error reporter and pretty-printer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pretty-printer is the mirror image of the parser: one branch per value shape, recursion for containers. Empty containers print as [] and {} on one line. The error reporter shows how little is needed for a polished message: the offset, the text, and a line of spaces followed by a caret. Try adding your own broken documents to the list.

The parser stores each object in a Python dict, so a duplicate key such as {"a": 1, "a": 2} silently keeps the last value. The JSON standard says only that names "SHOULD be unique". Most parsers, including Python's, choose last-wins. A strict validator could instead report the duplicate with an error pointing at the second key.

Step 4: test against the answer key

Now the payoff. Python's json module is a trusted second implementation, which makes differential testing possible: feed both parsers the same input and compare. For valid documents, the results must be identical. For invalid documents, both must reject. Where they disagree, one of the two programs is wrong, and it is usually yours.

The comparison below uses repr instead of ==. That matters, because in Python True == 1 and 1 == 1.0. If your parser returned 1 where true was expected, an equality test would stay silent. Comparing repr strings catches it.

After the hand-written cases, a mutation fuzzer takes valid documents and damages them: it deletes a character, inserts a random one, or swaps one. Most mutants are invalid JSON, and some are still valid. For every mutant, both parsers must agree about accept or reject, and about the value when they accept. A fixed random seed keeps the run reproducible.

Python Differential test against the json module

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each mismatch printed by this harness is a bug report with a built-in minimal test case. In a real project you would copy it into your test file and fix the parser until the harness is silent. A later lesson on testing and debugging a compiler turns this habit into a complete toolbox.

Where to take it next

You have the skeleton of every parser in this track. To go further:

  • Extensions. Allow comments and trailing commas (the "JSON5" family), or report duplicate keys as errors.
  • Streaming. Build a parser that yields events (start_object, key, end_array) instead of one big value, so a 2 GB file does not need 2 GB of memory.
  • Better recovery. Instead of stopping at the first error, resynchronize at the next , or } and report all errors at once, as described in Syntax Errors and Error Recovery.
  • Speed. Replace the token list with a generator, or let the lexer use one big regular expression as in Regular Expressions for Lexers.

Note what Python's json module does differently: its core is written in C for speed, and by default it also accepts the non-standard values NaN and Infinity. Your strict parser rejects them, so the test harness passes parse_constant to make json.loads equally strict (the hand-written list includes NaN as an invalid case).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the lexer store a character offset in every token instead of a line and column?

    Tracking a single integer costs almost nothing. Converting it to a line and column (count the newlines before it) is done once, at error time.
  2. 2. Which of these is NOT valid JSON?

    JSON forbids trailing commas. The other three are valid: -0 is a legal number, and null is one of the three keywords.
  3. 3. Why does the differential test compare repr strings instead of using ==?

    Booleans are integers in Python, and 1 equals 1.0. Comparing repr output tells True, 1 and 1.0 apart.
  4. 4. What does a recursion depth limit protect the parser from?

    Each nested array or object adds a stack frame. Without a limit, hostile input could crash the parser; with one, it produces an ordinary error.
  5. 5. The parser is predictive with one token of lookahead. What does that mean here?

    An opening brace can only start an object and an opening bracket only an array, so no guessing or backtracking is needed.

Summary

  • JSON is a tiny but complete language: a lexer for strings, escapes and numbers, and a small recursive grammar.
  • Tokens carry character offsets, and one function converts an offset to a line, a column and a caret display.
  • A recursive descent parser has one method per grammar rule; one token of lookahead is enough.
  • Error messages should say what was expected and what was found; a depth limit protects against hostile nesting.
  • The pretty-printer mirrors the parser's structure, with one branch per value shape.
  • Differential testing against a trusted implementation, plus mutation fuzzing with a fixed seed, finds bugs quickly.

Next: Project: A Regex Engine