Capstone 1: a JSON tokenizer
Part 10 builds a JSON library in eight lessons: a tokenizer, a parser, a value type, a writer, errors with positions, tests and fuzzing, a command line tool and a benchmark against encoding/json. The project is a module named example.com/jsonx with a package jsonx and a few commands under cmd/; every page shows the real files and the real output of running them in this container.
This first lesson is the tokenizer. It reads a byte slice and returns one token per call: a punctuation character, a string, a number, or one of the three literals. Each token carries the line and column where it started, which is what the errors of lesson 117 use. The tokenizer does not validate structure; that is the parser's job.
Kinds and tokens
A Kind is an integer constant per token type, with a String method so a test failure reads want number, got string. A Token holds the kind, the text and the position. The file is jsonx/token.go in the project.
type Kind int
const (
Invalid Kind = iota
BraceOpen
BraceClose
BracketOpen
BracketClose
Colon
Comma
String
Number
True
False
Null
)
// String names a Kind for a message or a test.
func (k Kind) String() string {
switch k {
case BraceOpen:
return "{"
case BraceClose:
return "}"
case BracketOpen:
return "["
case BracketClose:
return "]"
case Colon:
return ":"
case Comma:
return ","
case String:
return "string"
case Number:
return "number"
case True:
return "true"
case False:
return "false"
case Null:
return "null"
default:
return "invalid"
}
}
// Token is one lexical unit with the place it started.
type Token struct {
Kind Kind
Text string
Pos Position
}
The constants start at one so the zero value is Invalid, which the parser uses as "no more tokens". The text of a string token is already decoded: the lexer turns \n into a newline and a \u00e9 into the character, so the parser never sees an escape.
The lexer loop
The lexer keeps the source, the offset, the line and the column. Next skips white space, remembers the position, and dispatches on the first byte: punctuation is one byte and one token, a quote starts a string, a digit or a minus starts a number, and the three letters start the literals. End of input is io.EOF, which is not an error.
func (l *Lexer) Next() (Token, error) {
for l.i < len(l.src) {
switch l.peek() {
case ' ', '\t', '\r', '\n':
l.advance()
continue
}
break
}
if l.i >= len(l.src) {
return Token{Kind: Invalid, Pos: l.pos()}, io.EOF
}
start := l.pos()
switch c := l.peek(); c {
case '{':
l.advance()
return Token{Kind: BraceOpen, Text: "{", Pos: start}, nil
case '}':
l.advance()
return Token{Kind: BraceClose, Text: "}", Pos: start}, nil
case '[':
l.advance()
return Token{Kind: BracketOpen, Text: "[", Pos: start}, nil
case ']':
l.advance()
return Token{Kind: BracketClose, Text: "]", Pos: start}, nil
case ':':
l.advance()
return Token{Kind: Colon, Text: ":", Pos: start}, nil
case ',':
l.advance()
return Token{Kind: Comma, Text: ",", Pos: start}, nil
case '"':
s, err := l.readString()
if err != nil {
return Token{}, err
}
return Token{Kind: String, Text: s, Pos: start}, nil
case 't':
if err := l.readLiteral("true"); err != nil {
return Token{}, err
}
return Token{Kind: True, Text: "true", Pos: start}, nil
case 'f':
if err := l.readLiteral("false"); err != nil {
return Token{}, err
}
The dispatch is a switch on a byte, which is fast and exact because every JSON token begins with one of these characters. The position is taken before the first byte is consumed, so a token points at its first character and not after it. An unknown byte is a syntax error with its position, and that error is the type the next lessons extend.
Strings and escapes
A JSON string may contain the escapes \", \\, \/, \b, \f, \n, \r, \t and \uXXXX. A control character below 0x20 is not allowed raw, and a u escape can be a surrogate pair, which the lexer combines with utf16.DecodeRune. The loop below builds the decoded string as it goes.
func (l *Lexer) readString() (string, error) {
start := l.pos()
l.advance()
var b strings.Builder
for {
if l.i >= len(l.src) {
return "", &SyntaxError{Pos: start, Msg: "unterminated string"}
}
c := l.advance()
switch c {
case '"':
return b.String(), nil
case '\\':
if l.i >= len(l.src) {
return "", &SyntaxError{Pos: start, Msg: "unterminated escape"}
}
esc := l.advance()
switch esc {
case '"', '\\', '/':
b.WriteByte(esc)
case 'b':
b.WriteByte('\b')
case 'f':
b.WriteByte('\f')
case 'n':
b.WriteByte('\n')
case 'r':
b.WriteByte('\r')
case 't':
b.WriteByte('\t')
case 'u':
r, err := l.readUnicode()
if err != nil {
return "", err
}
b.WriteRune(r)
default:
return "", &SyntaxError{Pos: start, Msg: fmt.Sprintf("invalid escape %q", string(esc))}
}
default:
if c < 0x20 {
return "", &SyntaxError{Pos: start, Msg: "control character in string"}
}
b.WriteByte(c)
}
}
}
func (l *Lexer) readUnicode() (rune, error) {
start := l.pos()
if l.i+4 > len(l.src) {
return 0, &SyntaxError{Pos: start, Msg: "short unicode escape"}
}
hex := string(l.src[l.i : l.i+4])
v, err := strconv.ParseUint(hex, 16, 16)
if err != nil {
return 0, &SyntaxError{Pos: start, Msg: "invalid unicode escape"}
}
l.advance()
l.advance()
l.advance()
l.advance()
r := rune(v)
if utf16.IsSurrogate(r) {
if l.i+6 > len(l.src) || l.src[l.i] != '\\' || l.src[l.i+1] != 'u' {
return utf8.RuneError, nil
}
hex2 := string(l.src[l.i+2 : l.i+6])
v2, err := strconv.ParseUint(hex2, 16, 16)
if err != nil {
return 0, &SyntaxError{Pos: start, Msg: "invalid unicode escape"}
}
l.advance()
l.advance()
l.advance()
l.advance()
l.advance()
l.advance()
r = utf16.DecodeRune(r, rune(v2))
}
return r, nil
}
An unterminated string or an unknown escape is a syntax error at the opening quote, which is the position a user needs. The readUnicode helper reads four hex digits, and for a high surrogate it reads the following \u pair. A lone surrogate becomes the replacement rune rather than a failure, which is the tolerant choice the standard library also makes.
The number grammar
JSON numbers are stricter than Go floats: no leading plus, no leading zero, no NaN, no hex, and the exponent needs digits. The lexer builds the longest valid prefix, then hands it to strconv.ParseFloat to catch an overflow, and stores the text exactly as written.
func (l *Lexer) readNumber() (string, error) {
start := l.pos()
begin := l.i
if l.peek() == '-' {
l.advance()
}
if l.i >= len(l.src) {
return "", &SyntaxError{Pos: start, Msg: "short number"}
}
if l.peek() == '0' {
l.advance()
} else if l.peek() >= '1' && l.peek() <= '9' {
for l.i < len(l.src) && l.peek() >= '0' && l.peek() <= '9' {
l.advance()
}
} else {
return "", &SyntaxError{Pos: start, Msg: "invalid number"}
}
if l.peek() == '.' {
l.advance()
if l.i >= len(l.src) || l.peek() < '0' || l.peek() > '9' {
return "", &SyntaxError{Pos: start, Msg: "invalid fraction"}
}
for l.i < len(l.src) && l.peek() >= '0' && l.peek() <= '9' {
l.advance()
}
}
if l.peek() == 'e' || l.peek() == 'E' {
l.advance()
if l.peek() == '+' || l.peek() == '-' {
l.advance()
}
if l.i >= len(l.src) || l.peek() < '0' || l.peek() > '9' {
return "", &SyntaxError{Pos: start, Msg: "invalid exponent"}
}
for l.i < len(l.src) && l.peek() >= '0' && l.peek() <= '9' {
l.advance()
}
}
text := string(l.src[begin:l.i])
if _, err := strconv.ParseFloat(text, 64); err != nil {
return "", &SyntaxError{Pos: start, Msg: "invalid number"}
}
return text, nil
}
When a character does not fit the grammar the lexer returns an error instead of guessing where the number ends, so 1.2.3 fails at the second dot instead of becoming two numbers. The text is kept because a JSON value may need to survive a round trip with its exact digits, which the value type in lesson 115 does not promise but the error message and the tests rely on.
The project layout
The module has one package and a command per lesson under cmd/. The file is 310 lines; this page shows the parts that carry the design, and the small helpers peek, advance and readLiteral are the one-line functions a reader can fill in. The demo below imports the package and prints every token of a small document with its position. go build ./... and go vet ./... are clean, and the output is from go run ./cmd/l113 in this container.
package main
import (
"fmt"
"io"
"example.com/jsonx/jsonx"
)
func main() {
src := []byte(`{"a": 1, "b": [true, null, "x\n"]}`)
lex := jsonx.NewLexer(src)
for {
tok, err := lex.Next()
if err == io.EOF {
break
}
if err != nil {
fmt.Println("error:", err)
return
}
fmt.Printf("%-6s %q at %s\n", tok.Kind, tok.Text, tok.Pos)
}
}
go run ./cmd/l113
{ "{" at line 1, column 1
string "a" at line 1, column 2
: ":" at line 1, column 5
number "1" at line 1, column 7
, "," at line 1, column 8
string "b" at line 1, column 10
: ":" at line 1, column 13
[ "[" at line 1, column 15
true "true" at line 1, column 16
, "," at line 1, column 20
null "null" at line 1, column 22
, "," at line 1, column 26
string "x\n" at line 1, column 28
] "]" at line 1, column 33
} "}" at line 1, column 34
The decoded string token shows a newline as \n because the print uses %q. The columns count bytes from the start of the line, and the text after the column is the token as a reader would write it. The parser of the next lesson takes exactly this stream and gives it structure.
Exercises
- Tokenize [1e3, -0.5, 2E-2] and read the number texts. Which of them would strconv.Atoi accept, and why does the lexer use ParseFloat?
- Add an unterminated string to the demo input and print the error. Which position does it name, and which one would a user expect?
- Tokenize a string with an emoji written as a surrogate pair and print the decoded text. How many runes does it hold, and why?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a Token carry?
Answer
A kind, the text and the position
The position is what errors use.
-
What is the zero value of Kind?
Answer
Invalid, which the parser reads as no more tokens
The constants start at one.
-
What does the lexer return at the end of the input?
Answer
io.EOF, which is not a syntax error
The parser treats EOF as the end.
-
Is the text of a string token escaped?
Answer
No, it is decoded already
The parser sees real characters.
-
Which number forms does JSON allow?
Answer
A minus, digits, an optional fraction and exponent
The grammar is stricter than Go floats.
-
Why keep the number text?
Answer
The exact digits and the error messages use it
The value type stores a float.
-
What does a \u escape become?
Answer
The character, with surrogate pairs combined
utf16.DecodeRune combines the pair.
-
When is a token position taken?
Answer
Before its first byte is consumed
The position names the first character.
-
What does the tokenizer not do?
Answer
Check the structure of objects and arrays
That is the parser.
-
Which command builds the whole module?
Answer
go build ./...
It builds every package and command.
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