A few years ago whilst in class, writing Python, I was messing around in the REPL and typed 1 + 2 * 5, and immediately wondered: how is this being evaluated? At this moment, I was sent down a rabbit hole I have been stuck in ever since.
To the eye 1 + 2 * 5 means one plus two times five, simple maths. However, to the computer it means absolutely nothing, it doesn’t know what + or * means, we need to give it meaning - semantic value. To even begin with giving text meaning, we need to feed it through a pipeline. Firstly, a lexer breaks the string into tokens. Then a parser takes those tokens and produces an AST which represents the structure and meaning we care about.
If you’re not familiar with what lexer, token and parser means; I’ll briefly explain before we go any further. A lexer is the first component of any compiler or interpreter - it reads through a string (source code) and categorises each word and symbol into token types. For example, 1 becomes an Int token, + becomes a Plus token.
A token is a single categorised piece of your source code. Each token carries its own type (e.g. Int, Plus), its lexeme or value (the textual value of the token), and its source location (line and column) for error reporting.
A parser takes these tokens generated by the lexer, and creates an AST (abstract syntax tree) which represents the structure and meaning of our source code. More specifically, a parser encodes grammar rules - for 1 + 2 * 5 it knows for certain that * binds tighter than + so it builds the AST accordingly: 2 * 5 is evaluated first, then added to 1. In the AST for 1 + 2 * 5, * sits deeper in the tree than + - the depth encodes the precedence.
Below is the AST for 1 + 2 * 5, take note that * sits lower than +.
The type of parser we’ll be implementing is a recursive descent parser, it handles operator precedence elegantly and is simple enough to write by hand. Binding power determines how tightly an operator grabs its operands. For example, * has higher binding power than +, so it pulls 2 and 5 to itself first - sitting deeper in the tree (as seen in the diagram above). + has lower binding power, so it sits further up the tree, at the root and is the last thing evaluated. The deeper the node sits, the earlier it evaluates.
Lexical Analysis
Our goal right now is to tokenize the following: 1 + 2 * 5. We don’t care about the meaning, let’s just define a set of token types our parser expects so we can give it the meaning we want. But first, we need to create the lexer.
In this guide, I will be using C++23, you can follow along in any language you’d like, all these concepts apply similarly across most languages.
Let’s think about what we need before writing any code. To tokenize 1, +, * we need three token types: Int, Plus, Mul. Numbers need a small algorithm to catch them; operators are trivial as they’re single characters. We can extend this later to add more to the language.
To keep things simple and contained, I will include the implementations alongside the definitions inside the header files.
// lexer.hpp
#pragma once
#include <cstdint>
enum class TokenType : std::uint8_t {
Int,
Plus,
Mul,
EOF_,
};
Now that we have our token types defined (with EOF), we can define our token struct. For this guide, each token will own an std::string to keep it simple, however the technique for storing lexemes can be changed later on.
EOF_is a special token, it means “end of file”; it can be useful for the parser to know when to stop parsing.
// lexer.hpp
#pragma once
#include <cstdint>
#include <string>
/* TokenType definition omitted for brevity */
struct Token {
TokenType ty;
std::string value;
};
If you noticed, we’ve left out source location metadata such as line and column, at this stage it is not important to us, but later on we will add them to the token struct for error handling.
Now that we have the data types we need, the lexer can be implemented. My approach is very straightforward and trivial, you’ll see why I’ve designed it this way when we move on to the parser:
// lexer.hpp
#pragma once
#include <cstdint>
#include <string>
#include <string_view>
/* Definitions omitted for brevity */
class Lexer {
public:
explicit Lexer(std::string_view source) : m_source { source } { }
/* Get the next token in the source code */
Token next() { }
private:
std::string_view m_source { };
std::size_t m_position { };
void advance() {
if (!is_eof()) m_position++;
}
char current() const {
return is_eof() ? '\0' : m_source[m_position];
}
bool is_eof() const {
return m_position >= m_source.length();
}
};
advancein theLexerclass increments the position (m_position) bound checked so it never advances out of the source code.currentreturns either\0(which is the null terminator of a string) or the character in the source code atm_position.is_eofreturns true if the position exceeds the length of the source.
Alright, we have the skeleton of our parser defined, let’s move onto implementing next; but before we do, let’s think about how we’re going to approach it.
So for the character at m_position in m_source, match it against what token types we have, so let’s do that for + and *.
// lexer.hpp
/* Class omitted for brevity */
Token next() {
switch (current()) {
case '+': advance(); return Token { TokenType::Plus, "+" };
case '*': advance(); return Token { TokenType::Mul, "*" };
default: return Token { TokenType::EOF_, "" };
}
}
Very simple, if the current character matches +, advance the lexer to the next character and return a token of the type Plus.
We can quickly test our lexer like this:
// main.cpp
#include <lexer.hpp>
#include <print>
int main() {
Lexer lexer { "+*+" };
auto nx { lexer.next() };
while (nx.ty != TokenType::EOF_) {
std::println("{}, {}", static_cast<std::uint8_t>(nx.ty), nx.value);
nx = lexer.next();
}
}
We can expect to see the output:
1, +
2, *
1, +
Great! We’ve tokenized +*+, our next step is to handle integers. They can be handled in the default: case, however let’s refactor the switch statement so we can read the current character being switched on inside the default: case, and check if the current character is a digit.
// lexer.hpp
/* Class omitted for brevity */
Token next() {
switch (const auto cur { current() }; cur) {
case '+': advance(); return Token { TokenType::Plus, "+" };
case '*': advance(); return Token { TokenType::Mul, "*" };
default: {
if (std::isdigit(cur)) {
/// ...
}
return Token { TokenType::EOF_, "" };
}
}
}
Now our lexer can handle integers, but when it sees one it doesn’t do anything! We need to implement the logic of reading and building an integer. Let’s think of it like this: whilst we’re not at the end of the source, and the current character is a digit, advance the position. My approach to building the integer value will be different, I will record the start position of the first integer and sub string on the last position of integers. It’ll look like this:
// switch statement omitted for brevity
if (std::isdigit(cur)) {
const auto start { m_position };
while (!is_eof() && std::isdigit(m_source[m_position]))
advance();
const auto end { m_position };
const std::string value { m_source.substr(start, end - start) };
return Token { TokenType::Int, value };
}
Very simple, we record the first and last position of the integer and sub string on the source and return an Int token. Let’s test our original source 1 + 2 * 5. Wait a minute, this source has whitespaces and our lexer treats anything which isnt a number or +, * as an EOF_ token, let’s quickly add a heuristic guard at the top of the next method to skip any whitespaces.
Token next() {
while (!is_eof() && current() == ' ') advance();
/// ...
}
Now we can test 1 + 2 * 5. The expected output should be:
0, 1
1, +
0, 2
2, *
0, 5
We can clearly see all of our characters are being tokenized correctly, we’re ready to move onto the parser now!
Parser
Before we write our parser, we need to define our AST. An AST is an Abstract Syntax Tree, a representation of the structure of our source code. As shown before, when we write 1 + 2 * 5 the AST for this expression will look like:
Abstract in this context means anything irrelevant to the syntax such as parenthesis, semicolons or whitespaces are dropped from the tree, only the semantic structure remains in the tree. Typically, each node is tagged with a type (e.g. BinaryExpr, Literal) and carries the data needed (e.g. value, type information). We need an AST because working on raw string source code is painful and inefficient, an AST allows us to traverse a tree of nodes which holds structure and meaning; which is useful for: semantic analysis (e.g. type checking, linting), transformations (e.g. optimisations, desugaring), emission (e.g. codegen, lowered to an IR).
Now that we understand what an AST is, we can begin defining our types. In C++23, I will define the AST types using smart pointers and variants; this will be translatable to any language of your choice. Before we start, let’s think of what node types we’ll need.
We’ve successfully tokenised the source 1 + 2 * 5, we clearly need a node to hold an integer value and a binary operation. Because we have another binary operation on the right hand side of the first one (1 + ...) we need our node to hold two expressions, on the left and the right.
The approach I will continue with for this guide will be a simple inheritence pattern, it isn’t the best; but in my opinion it is ideal for learning.
// ast.hpp
#pragma once
#include <cstdint>
#include <memory>
template <typename T>
using Box = std::unique_ptr<T>;
struct Expr {
virtual ~Expr() = default;
};
struct Literal : Expr {
int64_t value { };
explicit Literal(const int64_t v) : value { v } { }
};
enum class BinaryOp : uint8_t { Add, Mul };
struct BinaryExpr : Expr {
BinaryOp op { };
Box<Expr> lhs, rhs;
BinaryExpr(
BinaryOp op,
Box<Expr> lhs,
Box<Expr> rhs
) : op { op }, lhs { std::move(lhs) }, rhs { std::move(rhs) } { }
};
Both Literal and BinaryExpr are descendants of Expr, BinaryExpr holds two unique pointers for LHS and RHS, these are each side of the binary operation.
Before writing the parser, let’s add - and /. Operators fall into two precedence categories: additive (+, -) and multiplicative (*, /). Multiplicative operators bind tighter, 1 + 2 * 5 means 1 + (2 * 5). The parser needs to know these categories to get precedence correct.
Back in lexer.hpp:
enum class TokenType : std::uint8_t {
Int,
Plus,
Mul,
Minus,
Slash,
EOF_,
};
/// rest of function omitted for brevity.
switch (const auto cur { current() }; cur) {
case '+': advance(); return Token { TokenType::Plus, "+" };
case '-': advance(); return Token { TokenType::Minus, "*" };
case '*': advance(); return Token { TokenType::Mul, "*" };
case '/': advance(); return Token { TokenType::Slash, "*" };
default: {
/// ...
}
}
Now lets update BinaryOp:
enum class BinaryOp : uint8_t { Add, Sub, Mul, Div };
Great, now our parser is ready! As mentioned earlier, the parser we’ll be implementing is a recursive descent parser, or a top-down parser - so let’s sketch it out!
/// parser.hpp
#pragma once
#include <format>
#include <stdexcept>
#include <vector>
#include "ast.hpp"
#include "lexer.hpp"
constexpr std::string_view format_token_type(const TokenType ty) {
switch (ty) {
case TokenType::Int: return "int";
case TokenType::Plus: return "+";
case TokenType::Minus: return "-";
case TokenType::Mul: return "*";
case TokenType::Slash: return "/";
case TokenType::EOF_: return "eof";
}
return "?";
}
class Parser {
public:
explicit Parser(std::string_view input) : m_lexer { input } {
m_current = m_lexer.next();
}
std::vector<Box<Expr>> parse() {
std::vector<Box<Expr>> exprs;
while (m_current.ty != TokenType::EOF_)
exprs.push_back(parse_expr());
return exprs;
}
private:
Lexer m_lexer;
Token m_current;
Token advance() {
return std::exchange(m_current, m_lexer.next());
}
Token expect(const TokenType ty) {
if (m_current.ty != ty) {
throw std::runtime_error(
std::format("expected {}, got {}", format_token_type(ty), format_token_type(m_current.ty)));
}
return advance();
}
Box<Expr> parse_expr() {
return parse_additive();
}
Box<Expr> parse_additive() {}
Box<Expr> parse_multiplicative() {}
Box<Expr> parse_primary() {}
};
Here we go, this is decent structure for a recursive descent parser. parse calls parse_expr which calls parse_additive, so we have the flow of logic defined already, we just now need to implement it. Now parse_primary will handle things such as Literal and BinaryOp, since thats all we have we can implement parse_primary right away, we can also handle grouped expressions nicely in parse_primary (e.g. (1 + 2)).
Let’s quickly add LParen and RParen to the lexer:
enum class TokenType : std::uint8_t {
Int,
Plus,
Mul,
Minus,
Slash,
LParen,
RParen,
EOF_,
};
...
switch (const auto cur { current() }; cur) {
case '+': advance(); return Token { TokenType::Plus, "+" };
case '-': advance(); return Token { TokenType::Minus, "-" };
case '*': advance(); return Token { TokenType::Mul, "*" };
case '/': advance(); return Token { TokenType::Slash, "/" };
case '(': advance(); return Token { TokenType::LParen, "(" };
case ')': advance(); return Token { TokenType::RParen, ")" };
default: {
...
}
}
There was a typo in the switch cases, we were setting each of these single character token lexemes to
*
Now let’s implement parse_primary:
Box<Expr> parse_primary() {
switch (m_current.ty) {
case TokenType::Int: {
int64_t value { };
auto [ptr, ec] = std::from_chars(
m_current.value.data(),
m_current.value.data() + m_current.value.size(),
value);
if (ec != std::errc()) throw std::runtime_error("failed to parse integer literal");
advance();
return std::make_unique<Literal>(value);
}
case TokenType::LParen: {
advance();
auto expr = parse_expr();
expect(TokenType::RParen);
return expr;
}
default: throw std::runtime_error(
std::format("expected primary, got {}", format_token_type(m_current.ty)));
}
}
Here it is, we parse integer tokens and grouped expressions correctly; now lets work up the chain. parse_multiplicative needs a lhs and a rhs, and we should only parse the rhs if the operators match that category, so * and /. We can think of it like this: first parse lhs from parse_primary, then whilst the current token is either * or /, choose the correct BinaryOp, advance, and parse rhs from parse_primary, then set lhs to a new BinaryExpr with lhs and rhs:
We can define a helper method for brevity:
template <typename... T>
bool matches(T... types) const {
return ((m_current.ty == types) || ...);
}
If you’re using Rust, you can use matches! or implement this in your language of choice.
Box<Expr> parse_multiplicative() {
auto lhs = parse_primary();
while (matches(TokenType::Mul, TokenType::Slash)) {
auto op = m_current.ty == TokenType::Mul ? BinaryOp::Mul : BinaryOp::Div;
advance();
auto rhs = parse_primary();
lhs = std::make_unique<BinaryExpr>(op, std::move(lhs), std::move(rhs));
}
return lhs;
}
Look at that! Very simple, it follows exactly what I explained and the helper methods brings this together nicely. parse_additive is identical, however instead of calling parse_primary we call parse_multiplicative and match on TokenType::Plus and TokenType::Minus:
Box<Expr> parse_additive() {
auto lhs = parse_multiplicative();
while (matches(TokenType::Plus, TokenType::Minus)) {
auto op = m_current.ty == TokenType::Plus ? BinaryOp::Add : BinaryOp::Sub;
advance();
auto rhs = parse_multiplicative();
lhs = std::make_unique<BinaryExpr>(op, std::move(lhs), std::move(rhs));
}
return lhs;
}
That’s it, thats our whole parser pipeline done. So simple right? Now let’s test it:
/// main.cpp
#include <print>
#include "parser.hpp"
constexpr std::string format(const Expr* expr, const int indent = 0) {
std::string fmt(indent * 2, ' ');
if (auto* lit = dynamic_cast<const Literal*>(expr))
return std::format("{}Literal({})\n", fmt, lit->value);
if (auto* bin = dynamic_cast<const BinaryExpr*>(expr)) {
std::string op;
switch (bin->op) {
case BinaryOp::Add: op = "+"; break;
case BinaryOp::Sub: op = "-"; break;
case BinaryOp::Mul: op = "*"; break;
case BinaryOp::Div: op = "/"; break;
}
return std::format("{}Binary({})\n", fmt, op)
+ format(bin->lhs.get(), indent + 1)
+ format(bin->rhs.get(), indent + 1);
}
return fmt + "?\n";
}
int main() {
Parser parser { "1 + 2 * 5" };
auto exprs = parser.parse();
for (auto& expr : exprs)
std::print("{}", format(expr.get()));
}
We have a simple node formatter, and we’re testing our source 1 + 2 * 5, you should see the result:
Binary(+)
Literal(1)
Binary(*)
Literal(2)
Literal(5)
If you do, you’ve successfully written your first recursive descent parser, and are one step closer to writing your own programming language.
Let’s do something cool before we move on, let’s test (1 + 2) * 5 and see if it changes the structure of the node:
Binary(*)
Binary(+)
Literal(1)
Literal(2)
Literal(5)
Now you can clearly see operator precedence kicking into effect!
What’s Next?
In this post, we’ve built two core components of a programming language from scratch: a lexer that tokenises source code, and a recursive descent parser that produces an AST.
In part 2, we’ll walk the AST we’ve built and evaluate it, turning 1 + 2 * 5 into 11. From there we can look at extending the language with variables and let bindings, which means introducing a symbol table and a new node type.