Build your own JSON parser

Most apps get their data from a server as JSON. You ask the server for a user, and the answer comes back as text:

{"name": "juno", "tags": ["go", "json"]}

To your program, that answer is a string of 40 characters. A string has no name and no tags. So before your code can use the data, it must turn the text into values that your language understands: objects, lists, strings, and numbers.

That is the job of a JSON parser. In JavaScript, you call JSON.parse:

const text = '{"name": "juno", "tags": ["go", "json"]}';
const user = JSON.parse(text);
console.log(user.tags[0]); // "go"

Python has json.loads, and Go has json.Unmarshal. Even fetch has one: if you write response.json(), it calls a JSON parser for you.

The call is one line. But inside it, the parser reads every character, checks it against the rules of JSON, and builds the result piece by piece. Let us build a JSON parser from scratch, and see how each of those parts works.

How a JSON parser works, in three steps

Before we write any code, watch a parser work once. Press Play.

{"name": "juno", "tags": ["go", "json"]} 

The box ran three steps:

1. First, the parser reads the text one character at a time. At this point, a {, a ", and a space are all the same to it. They are only characters.
2. Then it groups the characters into tokens. A token is a piece with a meaning, like "name", :, or [. The spaces disappear here, because they mean nothing.
3. Last, it builds a tree from the tokens. The tree shows what is inside what: the array is inside the object, and "go" is inside the array. We call this tree an abstract syntax tree, or AST.

That is a JSON parser in a nutshell. One part of the code, the lexer, does steps 1 and 2. Another part, the parser, does step 3. The rest of this post builds both of them.

Try this:

• Press Tokens, and look for the spaces. Where did they go?
• Press Tree. Which characters did not make it into the tree?
• Pick “broken”. The tokens look fine, but no tree comes out. Why not?

From here on, the code samples are in Go. You do not need to know Go to follow them.

What our JSON parser must do

Before we build it, we need a clear goal. Our parser has three jobs:

1. Build a tree from valid JSON.
2. Reject invalid JSON.
3. Say where the problem is, and how to fix it.

The third job is the easiest one to skip. An error that gives only a character position sends you counting characters by hand.

What is JSON? Six kinds of value

Before we parse JSON, we need to know exactly what it is.

JSON has a standard, ECMA-404. It is 16 pages long, and most of the pages are diagrams. If you are not sure about a detail, the spec has the answer.

A JSON value is one of six kinds:

Two of the kinds hold other values. An object holds members, and a member is a name and a value, like "name": "juno". An array holds values in order.

Objects and arrays can contain more objects and arrays, to any depth. That nesting is the reason a parser builds a tree, and not a list.

JSON looks like JavaScript, but its rules are stricter. Each rule below is a check that our parser must make:

• Strings use double quotes. 'hello' is not JSON.
• A comma after the last item is an error: [1, 2,].
• JSON has no comments.
• A number has no leading zero, so 01 is an error. It cannot start with + or . either. But 0, 0.5, and -0 are valid.
• JSON has no NaN, no Infinity, and no undefined.
• Only four characters are whitespace: the space, the tab, \n, and \r.

Tokens: the words of JSON

When you read this sentence, you do not read it letter by letter. You see words. A parser needs words too, so its first real job is to group characters into tokens.

A token is the smallest piece of input that has a meaning, like {, "name", or 42. Here are the tokens of {"a": [1, true]}:

Look at what is gone. The spaces are not tokens, and each quote is now part of a string token.

JSON needs only 11 kinds of token. Six are symbols: { } [ ] : ,. The other five are STRING, NUMBER, TRUE, FALSE, and NULL.

Our parser adds two more kinds for itself. EOF marks the end of the input. ILLEGAL marks input that is not a valid token, so a bad character becomes a token with a complaint, not a crash.

In Go, a token is a small struct:

type Token struct {
	Type    Type   // STRING, NUMBER, "{", and so on
	Literal string // the source text, like 42

	StartPosition int    // byte offset where the token starts
	EndPosition   int    // byte offset just after the token
	Line          int    // starts at 1
	Column        int    // starts at 1, counts characters
	Reason        string // why the token is ILLEGAL
}

The parser needs only the first two fields. The other five are for error messages. A token that knows its line and column lets an error say “line 3, col 8”.

That is job 3 from our list, and it starts here, long before any error happens.

The lexer: from characters to tokens

The code that makes tokens is the lexer, also called the tokenizer. It reads one character at a time, and it knows nothing about structure.

To the lexer, [1,] is four valid tokens: [, 1, ,, and ]. Only the parser can see that the order is wrong.

Here is the main loop of the lexer, in pseudo-code:

nextToken():
    skip whitespace
    look at the current character
    { } [ ] : ,      → make a symbol token, move one character
    "                → read a string up to the closing "
    a letter         → read a word, it must be true, false, or null
    a digit - + .    → read a number, check it against the grammar
    end of input     → make an EOF token
    anything else    → make an ILLEGAL token

Each call returns one token. The parser calls nextToken each time it wants the next token, so the lexer never builds the whole list at once.

Now watch the lexer work. Press “Watch it read”, and follow the highlight through the text.

{"name": "juno", "tags": ["go", "json"]} 

token.Token{
    Type:          "{",
    Literal:       "{",
    StartPosition: 0,
    EndPosition:   1,
    Line:          1,
    Column:        1,
    Reason:        "",
}

Try this:

• Point at a token. The card shows the same fields as the Go struct.
• Pick “numbers”. Which numbers become ILLEGAL tokens?
• Type [1,]. Why does the lexer not complain?

Most of that loop is easy. The hard parts are in the details below.

Characters are not bytes

In UTF-8, one character can take more than one byte. é takes 2 bytes, and ☕ takes 3. A Go string is a sequence of bytes, so the lexer cannot step through it one byte at a time.

The lexer keeps two offsets, position and nextPosition. The gap between them is the width of the current character.

func (l *Lexer) readChar() {
	// ... count lines and columns ...
	l.position = l.nextPosition
	if l.nextPosition >= len(l.input) {
		l.char = eof
		return
	}

	decodedChar, width := utf8.DecodeRuneInString(l.input[l.nextPosition:])
	l.char = decodedChar
	l.nextPosition += width
}

utf8.DecodeRuneInString returns one character, which Go calls a rune, and its width in bytes.

You can see the bytes in the widget above. Pick “unicode” and point at "café". Its StartPosition is 1 and its EndPosition is 8. That is 7 bytes for 6 characters, because é takes 2.

Strings

A string starts at " and ends at the next " that is not escaped. An escape is a backslash and one more character, like \n or \".

The backslash is the tricky part. In "a\"b", the backslash escapes the quote, so the string continues. In "a\\", the first backslash escapes the second one, so the last quote ends the string.

The lexer checks that each escape is valid, but it does not decode it yet. A raw newline or tab inside a string is an error. JSON wants \n and \t.

Numbers

Numbers have the most rules in JSON. The whole grammar fits in one regular expression:

-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][+-]?[0-9]+)?

Read it in four parts: an optional minus, the integer part, an optional fraction, and an optional exponent. The integer part is a lone 0, or a digit from 1 to 9 with more digits after it. That one rule makes 01 an error and -0 valid.

A regular expression is hard to read, so ECMA-404 also draws the grammar as a railroad diagram. A valid number is a path from the left end of the track to the right end. Type a number, and follow the dot.

Try this:

• Type 01. Where does the dot stop, and why?
• Type 6.02e23. Watch the dot go around each digit loop.

Our lexer reads the whole run of number characters first. Then it checks the run against the grammar. So 01 becomes one ILLEGAL token, not a 0 and a 1.

This choice gives a better error. With one token, the message says “invalid number: 01”. With two tokens, it says “expected ’,’ or ’]’, got number 1”, and you must work out the problem yourself.

Words, and bad input

A word must be true, false, or null, in lowercase. True and nul are ILLEGAL tokens.

When the lexer meets bad input, it does not stop. It makes an ILLEGAL token, writes the reason inside the token, and continues. The lexer only says what each piece is. The parser decides what to do about it.

The tree: abstract syntax tree

The lexer gave us a flat list of tokens. But JSON is not flat. In {"a": [1, true]}, the 1 and the true are inside the array, and the array belongs to "a".

A flat list cannot show that. A tree can:

Object
└── "a": Array
    ├── Number 1
    └── Bool true

This is the abstract syntax tree, or AST, from step 3 of the nutshell.

{"name": "juno", "tags": ["go", "json"], "stars": 0} 

Try this:

• Press CST, and count the extra tokens. Then press AST again.
• Point at a row. The text that the node came from lights up.

JSON has six kinds of value, so our AST has six kinds of node. Object and Array are containers, because they hold other nodes. String, Number, Bool, and Null are leaves, because they hold nothing.

Go has no enum that carries data, so we use an interface, with one struct for each kind of node:

type Node interface {
	Pos() int // where the node starts in the input
	End() int // where it ends
	node()    // unexported
}

The unexported method node() seals the interface. Only types in the ast package can implement it, so nobody can add a seventh kind of node. The go/ast package in the Go standard library uses the same pattern.

Three choices in the tree matter later:

1. Object members are a list, not a map. The spec allows {"a": 1, "a": 2}, and a map keeps only one of the two.
2. Numbers stay text. A float64 holds about 16 digits, and 12345678901234567890 has 20. Text keeps every digit.
3. Every node knows its position in the input. That is how the widget lights up the text, and how an error points at a line.

The parser: from tokens to a tree

Now we need the code that turns the tokens into that tree. It starts with rules.

A grammar is a set of rules that says which orders of tokens are valid. JSON needs only three:

value  → object | array | STRING | NUMBER | TRUE | FALSE | NULL
object → "{" ( STRING ":" value ( "," STRING ":" value )* )? "}"
array  → "[" ( value ( "," value )* )? "]"

The * means “zero or more”, and the ? means “zero or one”. Read the array rule aloud: a [, then values with commas between them, then a ].

Here is the idea that keeps the parser short: write one function for each rule. We call this a recursive descent parser.

A rule can contain another rule, so the functions call each other. parseArray calls parseValue for each element. If parseValue sees a [, it calls parseArray. That loop handles nesting to any depth, with no special case for it.

parseValue():
    look at the current token
    {                      → return parseObject()
    [                      → return parseArray()
    STRING, NUMBER, TRUE,
    FALSE, NULL            → take it, return a leaf node
    anything else          → error: expected a value

parseArray():
    take the [
    if the current token is ]   → take it, return an empty array
    repeat:
        add parseValue() to the elements
        if the current token is ,   → take it, then repeat
        if the current token is ]   → take it, return the array
        otherwise                   → error: expected ',' or ']'

parseObject has the same shape, with a name and a : before each value. Here is parseArray in Go, without the depth limit:

func (p *parser) parseArray() (ast.Node, error) {
	array := &ast.Array{Open: p.tok}
	p.next()

	if p.tok.Type == token.RightSquareBracket { // empty array
		array.Close = p.tok
		p.next()
		return array, nil
	}

	for {
		element, err := p.parseValue()
		if err != nil {
			return nil, err
		}
		array.Elements = append(array.Elements, element)

		switch p.tok.Type {
		case token.Comma:
			p.next()
		case token.RightSquareBracket:
			array.Close = p.tok
			p.next()
			return array, nil
		default:
			hint := p.separatorHint(array.Open, "values")
			return nil, p.fail(hint, "expected ',' or ']', got %s", describe(p.tok))
		}
	}
}

Go has no exceptions. A function returns an error next to its result, and the caller must check it. That is the reason for each if err != nil.

One token of lookahead

Look at parseValue again. It decides what to do from one token. A { always starts an object, and a [ always starts an array.

So our parser keeps only one token at a time, the current one. The name for a grammar like this is LL(1), for one token of lookahead.

Now watch the functions call each other. Press Play, or use the arrow buttons.

{"a": [1, true]} 

Try this:

• When a [ appears, watch the call stack. A new frame goes on top.
• Pick “trailing comma”, and find the exact step where the parser stops.

Each function returns its node to the function that called it, so the tree grows from the bottom up. Number 1 is complete before the array that holds it.

One more rule: a JSON text is exactly one value. After the first parseValue returns, the next token must be EOF. So 1 2 is an error, but "hello" alone is a valid JSON text.

A limit on depth

Each nested [ adds one function call to the stack. A million brackets can fill the stack and crash the program, and an attacker can send that input on purpose.

A depth limit is a security feature. Our parser stops at 10,000 levels, the same as encoding/json, the JSON package in the Go standard library.

A Go stack starts small. If it needs more space, it grows, up to 1 GB on a 64-bit system. A browser gives much less, so the widgets on this page stop at 100 levels. That is low enough to reach by hand: pick “101 brackets” in the next widget.

If you are building a parser at work and you want a second pair of eyes, write to me.

Error messages that point at the problem

Remember job 3: say where the problem is, and how to fix it. Here is what that looks like for a trailing comma:

line 3, col 25: expected a value, got ']'

 2 |   "name": "juno",
 3 |   "tags": ["go", "json",],
   |                         ^
hint: Remove the ',' at line 3, col 24. JSON does not allow a trailing comma.

The first line says where and what. The two lines of source show the place, with a ^ under the bad token. The hint says how to fix it.

The line and column come straight from the token. That is the reason the token carried them all along.

Often more than one hint fits an error. The parser picks the most exact one, in this order:

1. For an ILLEGAL token, the hint is the reason from the lexer. True gets “Write true in lowercase.”
2. If the input ends inside an object or array, the hint names the bracket that is still open.
3. If a ] or } comes after a comma, the hint names the trailing comma.
4. Otherwise, the hint comes from the parser function that found the error.

To name the open bracket, the parser keeps a stack. Each { or [ goes on top, and each } or ] removes the top one. At the end of the input, the top of the stack is the bracket that is still open.

The length of that stack is also the depth. So the same stack runs the depth limit.

Some hints are guesses. [tru] gets “Did you mean true?”. But in {f: 1}, the f is more likely a name without quotes than the start of false. So the parser guesses a word only from three letters or more.

Pick a mistake and read the hint. Then fix the mistake in the box, and watch the panel turn into a tree.

{
  "name": "juno",
  "tags": ["go", "json",]
} 

Try this:

• Pick “tru”, then “True”. Why are the two hints different?
• Pick “not closed”. Which bracket does the hint name?

From the tree to values

The three steps give us a tree. But JSON.parse goes one step further, and gives you values.

The tree still holds raw text. A string node holds the two characters \n, not a newline. A number node holds the text 42, not a number. The last step, decoding, turns the tree into plain Go values:

ECMA-404 describes only the syntax. It does not say what a program does with the values, so every decoder makes some choices. Ours makes each one the same way as encoding/json:

• If a name is in an object two times, the last value wins.
• 1e999 is too large, so it is an error. But 1e-400 becomes 0, and 12345678901234567890 becomes 12345678901234567168, with no error. The tree keeps the raw text for a program that needs the exact number.
• A \uXXXX escape names a character up to U+FFFF. A character above that, like 𝄞, needs two escapes, a surrogate pair: \uD834\uDD1E. Half of a pair alone becomes �.

Test yourself: valid JSON or not?

Every rule in this quiz is somewhere above. Is each example valid JSON? Guess first, then read the answer.

Build your own JSON parser: steps and tips

You can use any language. The steps are the same:

1. Read ECMA-404.
2. Write the token types, then the lexer. Print the tokens for every input that you can think of.
3. Write the parser, with one function for each rule of the grammar.
4. Write error messages that say where, what, and how to fix.

The next time JSON.parse throws an error at you, you will know which step gave up. Either the lexer met a character that it did not know, or the parser met a token that it did not expect.