Capstone 1: the parser
The parser takes the token stream of lesson 137 and builds a tree. One function per grammar rule, each consuming the tokens it recognises and returning the node it built: that is recursive descent, and JSON is small enough to fit in five functions.
The tokenizer on this page is the same loop as the previous lesson, reduced to the shape the parser needs: a text and a quoted flag, so that the string "42" is not the number 42. The project's full lexer with positions replaces it without changing the parser.
The parser stops at the first error, which is the right choice for a document that must be valid as a whole. A repair mode that skips to the next comma is a different program, and its tests would have to agree with its choices.
An object and its keys
parse reads one value and then requires the end of the stream. parse_object consumes the brace, reads a key, a colon and a value per pair, and returns the node when it meets the closing brace.
The program parses an object with two pairs and prints its kind, the number of children and the first key with the value behind it. The parser never looks at a character: the tokenizer has already decided where each token ends.
The node keeps the keys in one vector and the values in another, in the same order. That is enough for printing and for the tests; the value type of the next lesson turns the pair into a map.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int main()
{
parser read{split(R"({"name": "ada", "age": 36})")};
node document = read.parse();
std::cout << document.kind << ' ' << document.children.size() << ' ';
std::cout << document.keys[0] << '=' << document.children[0].text << '\n';
}
g++ -std=c++23 -Wall -Wextra object.cpp -o parse_object
./parse_object
object 2 name=ada
Arrays and nesting
parse_array is the object rule without the keys: values separated by commas until the closing bracket. A value can be an array or an object, so the recursion gives nesting for free.
The program parses an object that holds an array of a number, a number and an object, and prints the depth of the tree. The depth is 3: the outer object, the array and the object inside it.
The depth function is four lines and it is the first consumer of the tree, which is the sign that the parser produces something useful. The writer of lesson 140 walks the same shape in the other direction.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int depth(const node& value)
{
int best = 0;
for (const node& child : value.children) {
best = std::max(best, depth(child));
}
return best + 1;
}
int main()
{
parser read{split(R"({"items": [1, 2, {"deep": true}]})")};
node document = read.parse();
std::cout << document.children[0].kind << ' ';
std::cout << document.children[0].children.size() << ' ';
std::cout << depth(document) << '\n';
}
g++ -std=c++23 -Wall -Wextra array.cpp -o parse_array
./parse_array
array 3 4
The token that breaks the grammar
Each rule throws when the token it needs is not there, and the message names the rule that failed and the position in the token stream. The caller catches the exception and reports it.
The program parses {"a" 1} and prints the message: a key is followed by a colon in JSON, and the parser stopped at the token where the colon should be.
The token index is less friendly than the byte position of the lexer, and it is enough to find the problem. The next lesson keeps the byte position in the value type, which is what the final error messages of lesson 141 use.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int main()
{
parser read{split(R"({"a" 1})")};
try {
read.parse();
} catch (const std::runtime_error& error) {
std::cout << error.what() << '\n';
}
}
g++ -std=c++23 -Wall -Wextra missing.cpp -o parse_missing
./parse_missing
expected a colon at token 2
The document that stops too early
A document that ends before its closing brace gives the tokenizer no tokens left, and the parser reports the end of the document rather than a wrong token. That is a different message and a different bug.
The program parses {"a": 1 and prints the message from the object rule: the value was read, and the stream ended before the comma or the closing brace. The position in the message is one past the last token.
Both errors are exceptions of the same type, so the caller has one place to catch them. A parser that returned error codes would thread them through every rule and every caller, which is why lesson 145 uses expected for the layer above.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int main()
{
parser read{split(R"({"a": 1)")};
try {
read.parse();
} catch (const std::runtime_error& error) {
std::cout << error.what() << '\n';
}
}
g++ -std=c++23 -Wall -Wextra unclosed.cpp -o parse_unclosed
./parse_unclosed
expected a comma or a closing brace at token 4
Exercises
- Add a rule that rejects a trailing comma in an array.
- Make the parser record the byte position of every node and print it.
- Parse a document with an empty object and an empty array and print both kinds.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is recursive descent?
Answer
One function per grammar rule, calling each other for nested values
Each rule consumes its tokens and calls the rule for the values it contains.
-
Why does the token keep a
quotedflag?Answer
So the string 42 is not read as the number 42
The type of a JSON value depends on whether the text was quoted.
-
What does the parser require after the last value?
Answer
The end of the token stream
Trailing text would otherwise be ignored, and the program would accept an invalid document.
-
What does this program print?
#include <iostream> #include <string> #include <vector> int main() { std::vector<std::string> tokens{"{", "name", ":", "ada", "}"}; int pairs = 0; std::string first; for (std::size_t i = 0; i < tokens.size(); ++i) { if (tokens[i] == ":") { ++pairs; if (first.empty()) first = tokens[i - 1]; } } std::cout << "object " << pairs << " " << first << "=" << tokens[3]; }Answer
object 1 name=ada
The token list has one pair, whose key is name and whose value is ada, and the count is the number of colon tokens.
-
What does this program print for the array it parses?
#include <iostream> #include <string> #include <vector> int main() { std::vector<std::string> tokens{"[", "1", ",", "2", ",", "{", "deep", "}", "]"}; int values = 0, depth = 1, max_depth = 1; for (const auto& token : tokens) { if (token == "[" || token == "{") { ++depth; if (depth > max_depth) max_depth = depth; } else if (token == "]" || token == "}") --depth; else if (token != ",") ++values; } std::cout << "array " << values << ' ' << max_depth; }Answer
array 3 3
The array holds three values (1, 2 and the object), and the deepest level is three.
-
What does this program print?
#include <iostream> #include <stdexcept> #include <string> #include <vector> int main() { std::vector<std::string> tokens{"{", "a", "1", "}"}; int pos = 2; try { if (tokens[pos] != ":") throw std::runtime_error("expected a colon at token " + std::to_string(pos)); } catch (const std::runtime_error& error) { std::cout << error.what(); } }Answer
expected a colon at token 2
The token after the key is 1, not a colon, so the message names the colon and the position.
-
What does this program print?
#include <iostream> #include <stdexcept> #include <string> #include <vector> int main() { std::vector<std::string> tokens{"{", "a", ":", "1"}; int pos = 4; try { if (pos == static_cast<int>(tokens.size())) throw std::runtime_error("expected a comma or a closing brace at token " + std::to_string(pos)); } catch (const std::runtime_error& error) { std::cout << error.what(); } }Answer
expected a comma or a closing brace at token 4
The value is read and the stream ends inside the object, which is the rule that fails.
-
How are objects stored in the node?
Answer
A vector of keys and a vector of children in the same order
Two parallel vectors keep the order and are enough for printing and tests.
-
What does this program print for the nested document?
#include <iostream> #include <string> #include <vector> int main() { std::vector<std::string> tokens{"[", "1", ",", "[", "2", ",", "[", "3", "]", "]", "]"}; int depth = 0, max_depth = 0; for (const auto& token : tokens) { if (token == "[") { ++depth; if (depth > max_depth) max_depth = depth; } else if (token == "]") --depth; } std::cout << max_depth; }Answer
3
Three bracket levels are opened, so the deepest level is three.
-
Why does the parser throw instead of returning an error code?
Answer
So every rule can report without threading a result through each call
An error code would be a parameter or a return value in every rule and every caller.
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