Capstone 1: the parser
The parser takes the token stream of the last lesson and gives it structure. It is a recursive descent parser: one function per grammar rule, each calling the next, with one token of lookahead. The result is the Value type of lesson 115, so this lesson shows the parser and enough of the value to run it; the next lesson takes the value apart.
The parser in the project
Parse is the only exported function. It creates a parser over the source, reads the first token, parses one value and then insists that nothing but white space follows, which is what makes {}{} an error instead of two documents. The error is a *SyntaxError with the position of the token that did not fit.
type parser struct {
lex *Lexer
tok Token
}
// Parse reads one JSON value from src and rejects trailing data.
func Parse(src []byte) (Value, error) {
p := &parser{lex: NewLexer(src)}
if err := p.next(); err != nil {
return NullValue(), err
}
v, err := p.value()
if err != nil {
return NullValue(), err
}
if p.tok.Kind != Invalid {
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: fmt.Sprintf("unexpected %s after the value", p.tok.Kind)}
}
return v, nil
}
func (p *parser) next() error {
tok, err := p.lex.Next()
if err != nil {
if err == io.EOF {
p.tok = Token{Kind: Invalid}
return nil
}
return err
}
p.tok = tok
return nil
}
func (p *parser) value() (Value, error) {
switch p.tok.Kind {
case String:
v := StringValue(p.tok.Text)
return v, p.next()
case Number:
var f float64
if _, err := fmt.Sscanf(p.tok.Text, "%g", &f); err != nil {
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: "invalid number " + p.tok.Text}
}
return NumberValue(f), p.next()
case True:
return BoolValue(true), p.next()
case False:
return BoolValue(false), p.next()
case Null:
return NullValue(), p.next()
case BraceOpen:
return p.object()
case BracketOpen:
return p.array()
case Invalid:
return NullValue(), &SyntaxError{Pos: p.lex.pos(), Msg: "unexpected end of input"}
default:
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: fmt.Sprintf("unexpected %s", p.tok.Kind)}
}
}
One token ahead
parser holds the lexer and the current token. next advances one token and turns the end of input into Invalid, so the value switch has a single case for it. value dispatches on the kind: a scalar returns itself and advances, an object or an array recurses.
Objects
An object is an opening brace, then a key string, a colon and a value, with commas between the pairs. The loop handles the empty object, the trailing comma and the duplicate key, and each of those is an error with a position. The keys are collected in a map and sorted by the value constructor, so the encoding later is stable.
func (p *parser) object() (Value, error) {
open := p.tok.Pos
if err := p.next(); err != nil {
return NullValue(), err
}
fields := map[string]Value{}
first := true
for {
if p.tok.Kind == BraceClose {
if !first {
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: "trailing comma in object"}
}
return ObjectValue(fields), p.next()
}
first = false
if p.tok.Kind != String {
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: fmt.Sprintf("expected a key, got %s", p.tok.Kind)}
}
key := p.tok.Text
keyPos := p.tok.Pos
if err := p.next(); err != nil {
return NullValue(), err
}
if p.tok.Kind != Colon {
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: fmt.Sprintf("expected ':' after %q", key)}
}
if err := p.next(); err != nil {
return NullValue(), err
}
value, err := p.value()
if err != nil {
return NullValue(), err
}
if _, exists := fields[key]; exists {
return NullValue(), &SyntaxError{Pos: keyPos, Msg: fmt.Sprintf("duplicate key %q", key)}
}
fields[key] = value
if p.tok.Kind == Comma {
if err := p.next(); err != nil {
return NullValue(), err
}
continue
}
if p.tok.Kind == BraceClose {
return ObjectValue(fields), p.next()
}
return NullValue(), &SyntaxError{Pos: open, Msg: "unterminated object"}
}
}
A duplicate key is an error here, and the position is the second key, which is the one to delete. The standard library keeps the last value instead; a strict parser is the better teaching choice and the page says which rule it chose. A trailing comma is the other strictness: JSON forbids it and the loop reports it rather than accepting it silently.
Arrays
An array is the same shape with brackets, a value instead of a key and no colons. The empty array is allowed, a trailing comma is not, and an input that ends in the middle is an unterminated array error at the opening bracket, which is the position a reader can find.
func (p *parser) array() (Value, error) {
open := p.tok.Pos
if err := p.next(); err != nil {
return NullValue(), err
}
var items []Value
first := true
for {
if p.tok.Kind == BracketClose {
if !first {
return NullValue(), &SyntaxError{Pos: p.tok.Pos, Msg: "trailing comma in array"}
}
return ArrayValue(items), p.next()
}
first = false
item, err := p.value()
if err != nil {
return NullValue(), err
}
items = append(items, item)
if p.tok.Kind == Comma {
if err := p.next(); err != nil {
return NullValue(), err
}
continue
}
if p.tok.Kind == BracketClose {
return ArrayValue(items), p.next()
}
return NullValue(), &SyntaxError{Pos: open, Msg: "unterminated array"}
}
}
The two loops are five lines apart in shape, which is the cost of a hand-written parser and the reason the code is readable. A general grammar library would remove the repetition and hide the positions, and a JSON parser is small enough that the hand-written version is the one to learn from.
The demo
The command parses a document with an object, an array and a boolean and reads the fields back through the accessors. It is the first use of the value type, which the next lesson covers in full.
package main
import (
"fmt"
"example.com/jsonx/jsonx"
)
func main() {
src := []byte(`{"id": 1, "tags": ["a", "b"], "ok": true}`)
v, err := jsonx.Parse(src)
fmt.Println("error:", err)
fmt.Println("kind:", v.Kind(), "fields:", v.Len())
id, ok := v.Get("id")
fmt.Println("id:", id.Float(), "present:", ok)
tags, _ := v.Get("tags")
fmt.Println("tags kind:", tags.Kind(), "count:", tags.Len())
for i := 0; i < tags.Len(); i++ {
fmt.Println("tag:", tags.Index(i).Str())
}
okValue, _ := v.Get("ok")
fmt.Println("ok:", okValue.Bool())
}
go run ./cmd/l114
error: <nil>
kind: object fields: 3
id: 1 present: true
tags kind: array count: 2
tag: a
tag: b
ok: true
The document became an object with three fields, the number came back as a float, the array as an array of strings and the boolean as a bool. The accessors are total: a missing key returns the null value and false rather than a panic, which is what a program reading a foreign document wants.
What a parser checks
This parser checks the grammar and three rules beyond it: no trailing commas, no duplicate keys and no data after the value. It does not check a schema, a required field or a range; those belong to the code that uses the document. It also does not limit the nesting depth, which is the one thing a parser of untrusted input must add: a document of ten thousand brackets is a stack overflow, and the capstone service adds a depth counter in its handler.
The next lesson takes the value type: kinds, constructors, accessors and the null that stands for a missing field.
Exercises
- Parse {}[] and read the error. Which token does it name, and why is a parser that accepts it dangerous?
- Parse {"a":1,"a":2} and read the position. Which rule would a merge of two documents need instead?
- Add a depth counter to value and return an error past a thousand levels. Which field does the counter need, and why is a global not safe?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What kind of parser is this?
Answer
A recursive descent parser with one token of lookahead
One function per rule, each calling the next.
-
What does Parse do after the value?
Answer
Rejects any token except the end of input
One document per call.
-
What does next do at the end of input?
Answer
Sets the token to Invalid
The value switch handles one case.
-
Which rule does this parser add to the grammar?
Answer
No duplicate keys
The standard library keeps the last value.
-
What is a trailing comma in an object?
Answer
An error with the position of the closing brace
JSON forbids it.
-
What does a missing key return from Get?
Answer
The null value and false
The accessors are total.
-
What does the parser NOT check?
Answer
A schema, required fields and ranges
That belongs to the caller.
-
Which risk does a parser of untrusted input add?
Answer
Deep nesting exhausting the stack
A depth counter bounds it.
-
Why sort the keys in an object value?
Answer
The encoding is stable between runs
Go map order is random.
-
What does an unterminated array error name?
Answer
The position of the opening bracket
It is the place a reader can find.
The code on this page was run with go 1.26.10 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev