Capstone 1: a JSON tokenizer
The first capstone is a JSON reader and writer in six lessons. It starts here, with the layer that turns text into tokens, and each lesson adds one layer on top: the parser builds a tree, the value type stores it, the writer prints it and the tests check all of it.
A lexer reads the document once, left to right, and emits a token per punctuation mark, string, number or word. The parser of lesson 138 never looks at a character again, which is the point of the split.
The lexer is also the layer where a byte-order mark or a Windows line ending appears. The whitespace skip already handles both, which is why the tokenizer never needs to know where the file came from.
The token type and the loop
A token is a kind, the text it came from and the byte position where it started. The kind is an enum class, so the compiler keeps the cases apart, and name turns it into a word for the output.
The program scans the six punctuation characters of JSON and prints one line per token, including the end marker. The loop is the whole shape of the lexer: skip whitespace, look at one character, consume what belongs to the token, repeat.
The end token is part of the stream on purpose. The parser stops on it without a special case for the end of the buffer, and the position of the end token is the length of the document.
#include <cctype>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
enum class kind
{
open_brace,
close_brace,
open_bracket,
close_bracket,
colon,
comma,
string,
number,
word,
end
};
struct token
{
kind type;
std::string text;
std::size_t position;
};
const char* name(kind type)
{
switch (type) {
case kind::open_brace: return "open_brace";
case kind::close_brace: return "close_brace";
case kind::open_bracket: return "open_bracket";
case kind::close_bracket: return "close_bracket";
case kind::colon: return "colon";
case kind::comma: return "comma";
case kind::string: return "string";
case kind::number: return "number";
case kind::word: return "word";
case kind::end: return "end";
}
return "unknown";
}
class lexer
{
public:
explicit lexer(std::string text) : text_(std::move(text)) {}
std::vector<token> scan()
{
std::vector<token> tokens;
while (true) {
skip_space();
if (position_ == text_.size()) {
tokens.push_back({kind::end, "", position_});
return tokens;
}
std::size_t start = position_;
char current = text_[position_];
if (current == '{') {
++position_;
tokens.push_back({kind::open_brace, "{", start});
} else if (current == '}') {
++position_;
tokens.push_back({kind::close_brace, "}", start});
} else if (current == '[') {
++position_;
tokens.push_back({kind::open_bracket, "[", start});
} else if (current == ']') {
++position_;
tokens.push_back({kind::close_bracket, "]", start});
} else if (current == ':') {
++position_;
tokens.push_back({kind::colon, ":", start});
} else if (current == ',') {
++position_;
tokens.push_back({kind::comma, ",", start});
} else if (current == '"') {
tokens.push_back(read_string());
} else if (current == '-' || std::isdigit(static_cast<unsigned char>(current))) {
tokens.push_back(read_number());
} else if (std::isalpha(static_cast<unsigned char>(current))) {
tokens.push_back(read_word());
} else {
throw std::runtime_error("unexpected character at " + std::to_string(start));
}
}
}
private:
void skip_space()
{
while (position_ < text_.size()
&& std::isspace(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
token read_string()
{
std::size_t start = position_;
++position_;
std::string value;
while (position_ < text_.size() && text_[position_] != '"') {
char current = text_[position_];
if (current == '\\') {
++position_;
if (position_ == text_.size()) {
break;
}
char escaped = text_[position_];
switch (escaped) {
case 'n': value.push_back('\n'); break;
case 't': value.push_back('\t'); break;
default: value.push_back(escaped); break;
}
} else {
value.push_back(current);
}
++position_;
}
if (position_ == text_.size()) {
throw std::runtime_error("unterminated string at " + std::to_string(start));
}
++position_;
return token{kind::string, value, start};
}
token read_number()
{
std::size_t start = position_;
if (text_[position_] == '-') {
++position_;
}
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
if (position_ < text_.size() && text_[position_] == '.') {
++position_;
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
return token{kind::number, text_.substr(start, position_ - start), start};
}
token read_word()
{
std::size_t start = position_;
while (position_ < text_.size()
&& std::isalpha(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
return token{kind::word, text_.substr(start, position_ - start), start};
}
std::string text_;
std::size_t position_ = 0;
};
int main()
{
lexer scan{"{ [ ] : , }"};
for (const token& item : scan.scan()) {
std::cout << name(item.type) << ' ' << item.text << '\n';
}
}
g++ -std=c++23 -Wall -Wextra lexer.cpp -o lexer
./lexer
open_brace {
open_bracket [
close_bracket ]
colon :
comma ,
close_brace }
end
Strings and their escapes
A JSON string starts and ends with a quote and may contain a backslash escape. The lexer removes the quotes and turns \" into a quote and \n into a newline, so the parser receives the value, not the source text.
The program scans a small array of strings and prints the decoded text of each one. The quoted string in the middle arrives as two "quoted", with the escape already resolved.
The escape handling is a small table, and the default branch keeps the character after the backslash. That is enough for the project; a complete JSON reader also handles the \u form, which is four hex digits and one more piece of state.
#include <cctype>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
enum class kind
{
open_brace,
close_brace,
open_bracket,
close_bracket,
colon,
comma,
string,
number,
word,
end
};
struct token
{
kind type;
std::string text;
std::size_t position;
};
const char* name(kind type)
{
switch (type) {
case kind::open_brace: return "open_brace";
case kind::close_brace: return "close_brace";
case kind::open_bracket: return "open_bracket";
case kind::close_bracket: return "close_bracket";
case kind::colon: return "colon";
case kind::comma: return "comma";
case kind::string: return "string";
case kind::number: return "number";
case kind::word: return "word";
case kind::end: return "end";
}
return "unknown";
}
class lexer
{
public:
explicit lexer(std::string text) : text_(std::move(text)) {}
std::vector<token> scan()
{
std::vector<token> tokens;
while (true) {
skip_space();
if (position_ == text_.size()) {
tokens.push_back({kind::end, "", position_});
return tokens;
}
std::size_t start = position_;
char current = text_[position_];
if (current == '{') {
++position_;
tokens.push_back({kind::open_brace, "{", start});
} else if (current == '}') {
++position_;
tokens.push_back({kind::close_brace, "}", start});
} else if (current == '[') {
++position_;
tokens.push_back({kind::open_bracket, "[", start});
} else if (current == ']') {
++position_;
tokens.push_back({kind::close_bracket, "]", start});
} else if (current == ':') {
++position_;
tokens.push_back({kind::colon, ":", start});
} else if (current == ',') {
++position_;
tokens.push_back({kind::comma, ",", start});
} else if (current == '"') {
tokens.push_back(read_string());
} else if (current == '-' || std::isdigit(static_cast<unsigned char>(current))) {
tokens.push_back(read_number());
} else if (std::isalpha(static_cast<unsigned char>(current))) {
tokens.push_back(read_word());
} else {
throw std::runtime_error("unexpected character at " + std::to_string(start));
}
}
}
private:
void skip_space()
{
while (position_ < text_.size()
&& std::isspace(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
token read_string()
{
std::size_t start = position_;
++position_;
std::string value;
while (position_ < text_.size() && text_[position_] != '"') {
char current = text_[position_];
if (current == '\\') {
++position_;
if (position_ == text_.size()) {
break;
}
char escaped = text_[position_];
switch (escaped) {
case 'n': value.push_back('\n'); break;
case 't': value.push_back('\t'); break;
default: value.push_back(escaped); break;
}
} else {
value.push_back(current);
}
++position_;
}
if (position_ == text_.size()) {
throw std::runtime_error("unterminated string at " + std::to_string(start));
}
++position_;
return token{kind::string, value, start};
}
token read_number()
{
std::size_t start = position_;
if (text_[position_] == '-') {
++position_;
}
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
if (position_ < text_.size() && text_[position_] == '.') {
++position_;
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
return token{kind::number, text_.substr(start, position_ - start), start};
}
token read_word()
{
std::size_t start = position_;
while (position_ < text_.size()
&& std::isalpha(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
return token{kind::word, text_.substr(start, position_ - start), start};
}
std::string text_;
std::size_t position_ = 0;
};
int main()
{
lexer scan{R"(["one", "two \"quoted\""])"};
for (const token& item : scan.scan()) {
if (item.type == kind::string) {
std::cout << item.text << '\n';
}
}
}
g++ -std=c++23 -Wall -Wextra strings.cpp -o lexer_strings
./lexer_strings
one
two "quoted"
Numbers, words and positions
A number is an optional minus, digits and an optional fraction; a word is a run of letters, which covers true, false and null. Both keep the position of their first character, and the parser uses it in an error message.
The program scans an object and prints position:kind:text for every token except the end. The positions are what a text editor needs to point at the character that broke a document.
The lexer does not validate the words: a word that is not a JSON literal is the parser's error, not the scanner's. Each layer checks what it can see, and the parser is the one that knows the grammar.
#include <cctype>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
enum class kind
{
open_brace,
close_brace,
open_bracket,
close_bracket,
colon,
comma,
string,
number,
word,
end
};
struct token
{
kind type;
std::string text;
std::size_t position;
};
const char* name(kind type)
{
switch (type) {
case kind::open_brace: return "open_brace";
case kind::close_brace: return "close_brace";
case kind::open_bracket: return "open_bracket";
case kind::close_bracket: return "close_bracket";
case kind::colon: return "colon";
case kind::comma: return "comma";
case kind::string: return "string";
case kind::number: return "number";
case kind::word: return "word";
case kind::end: return "end";
}
return "unknown";
}
class lexer
{
public:
explicit lexer(std::string text) : text_(std::move(text)) {}
std::vector<token> scan()
{
std::vector<token> tokens;
while (true) {
skip_space();
if (position_ == text_.size()) {
tokens.push_back({kind::end, "", position_});
return tokens;
}
std::size_t start = position_;
char current = text_[position_];
if (current == '{') {
++position_;
tokens.push_back({kind::open_brace, "{", start});
} else if (current == '}') {
++position_;
tokens.push_back({kind::close_brace, "}", start});
} else if (current == '[') {
++position_;
tokens.push_back({kind::open_bracket, "[", start});
} else if (current == ']') {
++position_;
tokens.push_back({kind::close_bracket, "]", start});
} else if (current == ':') {
++position_;
tokens.push_back({kind::colon, ":", start});
} else if (current == ',') {
++position_;
tokens.push_back({kind::comma, ",", start});
} else if (current == '"') {
tokens.push_back(read_string());
} else if (current == '-' || std::isdigit(static_cast<unsigned char>(current))) {
tokens.push_back(read_number());
} else if (std::isalpha(static_cast<unsigned char>(current))) {
tokens.push_back(read_word());
} else {
throw std::runtime_error("unexpected character at " + std::to_string(start));
}
}
}
private:
void skip_space()
{
while (position_ < text_.size()
&& std::isspace(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
token read_string()
{
std::size_t start = position_;
++position_;
std::string value;
while (position_ < text_.size() && text_[position_] != '"') {
char current = text_[position_];
if (current == '\\') {
++position_;
if (position_ == text_.size()) {
break;
}
char escaped = text_[position_];
switch (escaped) {
case 'n': value.push_back('\n'); break;
case 't': value.push_back('\t'); break;
default: value.push_back(escaped); break;
}
} else {
value.push_back(current);
}
++position_;
}
if (position_ == text_.size()) {
throw std::runtime_error("unterminated string at " + std::to_string(start));
}
++position_;
return token{kind::string, value, start};
}
token read_number()
{
std::size_t start = position_;
if (text_[position_] == '-') {
++position_;
}
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
if (position_ < text_.size() && text_[position_] == '.') {
++position_;
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
return token{kind::number, text_.substr(start, position_ - start), start};
}
token read_word()
{
std::size_t start = position_;
while (position_ < text_.size()
&& std::isalpha(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
return token{kind::word, text_.substr(start, position_ - start), start};
}
std::string text_;
std::size_t position_ = 0;
};
int main()
{
lexer scan{R"({"ok": true, "n": -12.5})"};
for (const token& item : scan.scan()) {
if (item.type == kind::end) {
break;
}
std::cout << item.position << ':' << name(item.type) << ':' << item.text << '\n';
}
}
g++ -std=c++23 -Wall -Wextra positions.cpp -o lexer_positions
./lexer_positions
0:open_brace:{
1:string:ok
5:colon::
7:word:true
11:comma:,
13:string:n
16:colon::
18:number:-12.5
23:close_brace:}
The character it cannot read
Anything the lexer does not recognise is a std::runtime_error with the position of the character. The parser of the next lesson catches the exception and reports it as a syntax error with the same position.
The program scans a document with an @ inside and prints the message of the exception. The position is 6, the index of the character in the string, which is the number a reader can count to.
An unterminated string takes the same path with a different message. Both are errors of the text, not of the program, and both carry the position that the caller needs to explain them.
#include <cctype>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
enum class kind
{
open_brace,
close_brace,
open_bracket,
close_bracket,
colon,
comma,
string,
number,
word,
end
};
struct token
{
kind type;
std::string text;
std::size_t position;
};
const char* name(kind type)
{
switch (type) {
case kind::open_brace: return "open_brace";
case kind::close_brace: return "close_brace";
case kind::open_bracket: return "open_bracket";
case kind::close_bracket: return "close_bracket";
case kind::colon: return "colon";
case kind::comma: return "comma";
case kind::string: return "string";
case kind::number: return "number";
case kind::word: return "word";
case kind::end: return "end";
}
return "unknown";
}
class lexer
{
public:
explicit lexer(std::string text) : text_(std::move(text)) {}
std::vector<token> scan()
{
std::vector<token> tokens;
while (true) {
skip_space();
if (position_ == text_.size()) {
tokens.push_back({kind::end, "", position_});
return tokens;
}
std::size_t start = position_;
char current = text_[position_];
if (current == '{') {
++position_;
tokens.push_back({kind::open_brace, "{", start});
} else if (current == '}') {
++position_;
tokens.push_back({kind::close_brace, "}", start});
} else if (current == '[') {
++position_;
tokens.push_back({kind::open_bracket, "[", start});
} else if (current == ']') {
++position_;
tokens.push_back({kind::close_bracket, "]", start});
} else if (current == ':') {
++position_;
tokens.push_back({kind::colon, ":", start});
} else if (current == ',') {
++position_;
tokens.push_back({kind::comma, ",", start});
} else if (current == '"') {
tokens.push_back(read_string());
} else if (current == '-' || std::isdigit(static_cast<unsigned char>(current))) {
tokens.push_back(read_number());
} else if (std::isalpha(static_cast<unsigned char>(current))) {
tokens.push_back(read_word());
} else {
throw std::runtime_error("unexpected character at " + std::to_string(start));
}
}
}
private:
void skip_space()
{
while (position_ < text_.size()
&& std::isspace(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
token read_string()
{
std::size_t start = position_;
++position_;
std::string value;
while (position_ < text_.size() && text_[position_] != '"') {
char current = text_[position_];
if (current == '\\') {
++position_;
if (position_ == text_.size()) {
break;
}
char escaped = text_[position_];
switch (escaped) {
case 'n': value.push_back('\n'); break;
case 't': value.push_back('\t'); break;
default: value.push_back(escaped); break;
}
} else {
value.push_back(current);
}
++position_;
}
if (position_ == text_.size()) {
throw std::runtime_error("unterminated string at " + std::to_string(start));
}
++position_;
return token{kind::string, value, start};
}
token read_number()
{
std::size_t start = position_;
if (text_[position_] == '-') {
++position_;
}
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
if (position_ < text_.size() && text_[position_] == '.') {
++position_;
while (position_ < text_.size()
&& std::isdigit(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
}
return token{kind::number, text_.substr(start, position_ - start), start};
}
token read_word()
{
std::size_t start = position_;
while (position_ < text_.size()
&& std::isalpha(static_cast<unsigned char>(text_[position_]))) {
++position_;
}
return token{kind::word, text_.substr(start, position_ - start), start};
}
std::string text_;
std::size_t position_ = 0;
};
int main()
{
lexer scan{R"({"a": @})"};
try {
scan.scan();
} catch (const std::runtime_error& error) {
std::cout << error.what() << '\n';
}
}
g++ -std=c++23 -Wall -Wextra error.cpp -o lexer_error
./lexer_error
unexpected character at 6
Exercises
- Add the `\u` escape with four hex digits to the lexer and print the decoded character.
- Make the lexer reject a number with a trailing dot and report its position.
- Print the line and column of the error instead of the byte position.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a token store in this project?
Answer
A kind, the text and the position
The three fields are what the parser and the error messages need from the scanner.
-
Why does the lexer emit an end token?
Answer
So the parser has a marker instead of a special end-of-buffer case
The end token turns the end of the input into an ordinary token the parser can match.
-
What happens to the quotes of a JSON string in the lexer?
Answer
They are removed and the escapes are resolved
The parser needs the value, and the quotes are syntax rather than content.
-
What does this program print?
#include <iostream> #include <string> int main() { std::string text = "{}"; for (char c : text) { if (c == '{') std::cout << "open_brace\n"; if (c == '}') std::cout << "close_brace\n"; } std::cout << "end"; }Answer
open_brace / close_brace / end
Each character becomes one token, and the end marker follows the two braces.
-
What does this program print?
#include <iostream> #include <string> int main() { std::string raw = "two \\\"quoted\\\""; std::string out; for (std::size_t i = 0; i < raw.size(); ++i) { if (raw[i] == '\\' && i + 1 < raw.size()) { ++i; out += raw[i]; } else out += raw[i]; } std::cout << "one\n" << out; }Answer
one / two "quoted"
The escape is removed by the loop, so the second string contains real quotes.
-
What is the position of the
@in{"a": @}?Answer
6
The characters before it are a brace, three string characters, a colon and a space.
-
Which error does an unterminated string raise?
Answer
A runtime_error that names the start of the string
The lexer notices that the closing quote is missing and reports where the string began.
-
Who decides that a word is not a JSON literal?
Answer
The parser, not the lexer
The scanner only knows the shape of a word; the grammar decides which words are allowed.
-
What does the position field count?
Answer
Bytes from the start of the document
The index into the string is the simplest position to carry, and it can be converted to a line later.
-
Why is the lexer a separate class from the parser?
Answer
So the parser works on tokens and never re-reads characters
Each layer is simpler when it only solves one problem.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev