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

  1. Parse {}[] and read the error. Which token does it name, and why is a parser that accepts it dangerous?
  2. Parse {"a":1,"a":2} and read the position. Which rule would a merge of two documents need instead?
  3. 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.

  1. What kind of parser is this?

    Answer

    A recursive descent parser with one token of lookahead

    One function per rule, each calling the next.

  2. What does Parse do after the value?

    Answer

    Rejects any token except the end of input

    One document per call.

  3. What does next do at the end of input?

    Answer

    Sets the token to Invalid

    The value switch handles one case.

  4. Which rule does this parser add to the grammar?

    Answer

    No duplicate keys

    The standard library keeps the last value.

  5. What is a trailing comma in an object?

    Answer

    An error with the position of the closing brace

    JSON forbids it.

  6. What does a missing key return from Get?

    Answer

    The null value and false

    The accessors are total.

  7. What does the parser NOT check?

    Answer

    A schema, required fields and ranges

    That belongs to the caller.

  8. Which risk does a parser of untrusted input add?

    Answer

    Deep nesting exhausting the stack

    A depth counter bounds it.

  9. Why sort the keys in an object value?

    Answer

    The encoding is stable between runs

    Go map order is random.

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

Banner image