Build your own JSON parser

Your code calls JSON.parse all the time. This tutorial shows what happens inside it, and how to build a JSON parser yourself.

How a JSON parser works, in three steps

What our JSON parser must do

What is JSON? Six kinds of value

Tokens: the words of JSON

The lexer: from characters to tokens

The tree: abstract syntax tree

The parser: from tokens to a tree

Error messages that point at the problem

From the tree to values

Test yourself: valid JSON or not?

Build your own JSON parser: steps and tips

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.

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

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

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

objectarraynestedbroken

TextTokensTree

Play

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

40 characters. To a computer, that is all JSON is: a row of characters.

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.

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

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

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

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.

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:

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.

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 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"]}

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

objectnumbersunicodeescapesJavaScript habitstrailing comma

Watch it read14 tokens

Point at a token, or click in the text, to see its fields.

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

Try this:

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

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.

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 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.

A number to check-12.5e3-06.02e2301.51.+1

-12.5e3

signinteger-01-9digitfractionexponent.digite E+ -digit

Valid numberThe dot reached the end.

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.

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 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}

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

objectnestedsame name twicebig numberonly a string

Valid JSON6 nodes

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.

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.

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]}

{"a": [1, true]}

objectnested arraystrailing commamissing colon

{STRING"a":[NUMBER1,TRUEtrue]}EOF

Call stackEvery call returned.

The current token is end of input. The text holds exactly one value, so the par