BUILD AN INTERPRETER IN C++, THE WAY SATELLITE IS BUILT
satl is an interpreter: a program that reads another program and runs it. This post builds a small one in C++, about two hundred lines you can compile and run, with the same four stages satl has. Then it shows what satl does beyond it, and why.
The language it runs is tiny on purpose — one statement a line, numbers and text, + - * / with brackets, names that hold a value, and show to print one:
program.tinyTEXT Download
The language this interpreter runs
x = 1 + 2 * (3 - 1)
show x
name = "Ada"
show "hello, " + name
show x * 10 / 41. Read the file
Everything starts with the text. Read the whole file and cut it into lines — and treat \r\n and a lone \r as a line’s end too, or every program written on Windows fails for a character nobody can see. satl learned that the hard way: it refused every Windows file at its first line until 2026-09-25.
read.cppC++ Download
Stage one: the file, as lines
// tiny.cpp -- a small interpreter, built the way satellite is: read, lex, check, walk.
//
// clang++ -std=c++20 -O2 -o tiny tiny.cpp && ./tiny program.tiny
//
// The language: one statement a line --
// x = 1 + 2 * (3 - 1)
// show x
// show "text"
// -- numbers, strings, + - * / with the usual precedence, brackets, and names.
<cctype>
<fstream>
<iostream>
<map>
<memory>
<sstream>
<string>
<variant>
<vector>
// ---- 1. READ: the whole file, every line ending made \n ---------------------------------
std::vector<std::string> read_lines(const std::string &path)
{
std::ifstream in(path, std::ios::binary);
std::stringstream whole;
whole << in.rdbuf();
std::string text = whole.str(), line;
std::vector<std::string> lines;
for (std::size_t i = 0; i <= text.size(); ++i) {
if (i == text.size() || text[i] == '\n' || text[i] == '\r') {
lines.push_back(line);
line.clear();
if (i + 1 < text.size() && text[i] == '\r' && text[i + 1] == '\n') ++i; // \r\n is one end
} else {
line += text[i];
}
}
return lines;
}2. Lex: cut a line into tokens
A token is the smallest piece that means something: a number, a name, a string, a sign. The lexer walks the line one character at a time and decides what each run of characters is. It never guesses: a character it has no meaning for is refused, with the column where it stands, which is what every stage below does too.
lex.cppC++ Download
Stage two: characters become tokens
// ---- 2. LEX: a line becomes tokens ---------------------------------------------------------
enum class Kind { number, name, text, sign, end };
struct Token {
Kind kind;
std::string spelled;
std::size_t column;
};
struct Refusal { // what every stage throws when it says no
std::string why;
std::size_t column;
};
std::vector<Token> lex(const std::string &line)
{
std::vector<Token> tokens;
std::size_t i = 0;
while (i < line.size()) {
const char c = line[i];
if (c == ' ' || c == '\t') { ++i; continue; }
const std::size_t start = i;
if (std::isdigit(static_cast<unsigned char>(c))) {
while (i < line.size() && std::isdigit(static_cast<unsigned char>(line[i]))) ++i;
tokens.push_back({Kind::number, line.substr(start, i - start), start});
} else if (std::isalpha(static_cast<unsigned char>(c)) || c == '_') {
while (i < line.size() && (std::isalnum(static_cast<unsigned char>(line[i])) || line[i] == '_')) ++i;
tokens.push_back({Kind::name, line.substr(start, i - start), start});
} else if (c == '"') {
++i;
while (i < line.size() && line[i] != '"') ++i;
if (i == line.size()) throw Refusal{"this string has no closing \"", start};
tokens.push_back({Kind::text, line.substr(start + 1, i - start - 1), start});
++i;
} else if (std::string("+-*/()=").find(c) != std::string::npos) {
tokens.push_back({Kind::sign, std::string(1, c), start});
++i;
} else {
throw Refusal{std::string("'") + c + "' has no meaning here", start};
}
}
tokens.push_back({Kind::end, "", line.size()});
return tokens;
}3. Parse: tokens become a tree
1 + 2 * 3 has to mean 1 + (2 * 3). The parser turns the flat list of tokens into a tree where each operation’s two sides are its children, and precedence falls out of the shape of the functions: expression handles + and - and asks term for each side; term handles * and / and asks factor; factor is a single value or a bracketed expression — which calls expression again. That is recursive descent, and it is how most hand-written interpreters parse.
parse.cppC++ Download
Stage three: a recursive-descent parser
// ---- 3. PARSE: tokens become a tree ---------------------------------------------------------
struct Node {
Kind kind; // number, name, text -- or sign, for an operation
std::string spelled;
std::size_t column;
std::unique_ptr<Node> left, right;
};
class Parser {
public:
explicit Parser(std::vector<Token> tokens) : tokens_(std::move(tokens)) {}
// expression := term (('+' | '-') term)* -- lowest precedence first
std::unique_ptr<Node> expression()
{
auto left = term();
while (at("+") || at("-")) left = operation(std::move(left), &Parser::term);
return left;
}
const Token &peek() const { return tokens_[next_]; }
Token take() { return tokens_[next_++]; }
bool at(const char *sign) const { return peek().kind == Kind::sign && peek().spelled == sign; }
private:
// term := factor (('*' | '/') factor)* -- binds tighter, so it is asked for inside
std::unique_ptr<Node> term()
{
auto left = factor();
while (at("*") || at("/")) left = operation(std::move(left), &Parser::factor);
return left;
}
// factor := number | name | text | '(' expression ')'
std::unique_ptr<Node> factor()
{
const Token t = take();
if (t.kind == Kind::number || t.kind == Kind::name || t.kind == Kind::text)
return std::make_unique<Node>(Node{t.kind, t.spelled, t.column, nullptr, nullptr});
if (t.kind == Kind::sign && t.spelled == "(") {
auto inside = expression();
if (!at(")")) throw Refusal{"this ( is never closed", t.column};
take();
return inside;
}
throw Refusal{"a value was expected here", t.column};
}
std::unique_ptr<Node> operation(std::unique_ptr<Node> left, std::unique_ptr<Node> (Parser::*next)())
{
const Token sign = take();
auto node = std::make_unique<Node>(Node{Kind::sign, sign.spelled, sign.column, std::move(left), nullptr});
node->right = (this->*next)();
return node;
}
std::vector<Token> tokens_;
std::size_t next_ = 0;
};4. Walk: the tree becomes a value
The evaluator walks the tree from the top. A number is itself; a name is looked up; an operation works out its two children first and then combines them. A std::variant holds a value that may be a number or text, and + joins when either side is text — the same rule satellite has for a string and a number.
walk.cppC++ Download
Stage four: evaluating the tree
// ---- 4. WALK: a tree becomes a value --------------------------------------------------------
using Value = std::variant<long long, std::string>;
using Names = std::map<std::string, Value>;
std::string shown(const Value &v)
{
return std::holds_alternative<long long>(v) ? std::to_string(std::get<long long>(v)) : std::get<std::string>(v);
}
Value evaluate(const Node &n, const Names &names)
{
switch (n.kind) {
case Kind::number: return std::stoll(n.spelled);
case Kind::text: return n.spelled;
case Kind::name: {
const auto found = names.find(n.spelled);
if (found == names.end()) throw Refusal{n.spelled + " has no value yet", n.column};
return found->second;
}
default: break;
}
const Value a = evaluate(*n.left, names), b = evaluate(*n.right, names);
if (n.spelled == "+" && (std::holds_alternative<std::string>(a) || std::holds_alternative<std::string>(b)))
return shown(a) + shown(b); // text joins
if (!std::holds_alternative<long long>(a) || !std::holds_alternative<long long>(b))
throw Refusal{n.spelled + " works on two numbers", n.column};
const long long x = std::get<long long>(a), y = std::get<long long>(b);
if (n.spelled == "+") return x + y;
if (n.spelled == "-") return x - y;
if (n.spelled == "*") return x * y;
if (y == 0) throw Refusal{"a division by zero", n.column};
return x / y;
}5. Run each line, and say no with a caret
The last piece runs every line, and turns any refusal into a report that names the file, the line, and puts a ^ under the column where things went wrong.
run.cppC++ Download
Stage five: the loop, and the report
// ---- 5. RUN: each statement, and a report with a caret when one says no -------------------
int main(int argc, char **argv)
{
if (argc != 2) { std::cerr << "usage: tiny program.tiny\n"; return 2; }
const std::vector<std::string> lines = read_lines(argv[1]);
Names names;
for (std::size_t number = 0; number < lines.size(); ++number) {
const std::string &line = lines[number];
try {
Parser p(lex(line));
if (p.peek().kind == Kind::end) continue; // a blank line
if (p.peek().kind == Kind::name && p.peek().spelled == "show") {
p.take();
auto what = p.expression();
if (p.peek().kind != Kind::end) throw Refusal{"the line goes on after the value", p.peek().column};
std::cout << shown(evaluate(*what, names)) << "\n";
} else if (p.peek().kind == Kind::name) {
const Token name = p.take();
if (!p.at("=")) throw Refusal{"a name here is followed by =", p.peek().column};
p.take();
auto what = p.expression();
if (p.peek().kind != Kind::end) throw Refusal{"the line goes on after the value", p.peek().column};
names[name.spelled] = evaluate(*what, names);
} else {
throw Refusal{"a line starts with show or a name", p.peek().column};
}
} catch (const Refusal &r) {
std::cerr << argv[1] << ":" << number + 1 << ": " << r.why << "\n"
<< " " << line << "\n"
<< " " << std::string(r.column, ' ') << "^\n";
return 1;
}
}
return 0;
}Put the five boxes in one file, tiny.cpp, and build it:
build.shBASH Download
Build and run it
clang++ -std=c++20 -O2 -Wall -Wextra -o tiny tiny.cpp
./tiny program.tinyOUTPUT
5
hello, Ada
12And a mistake — show x / (2 - 2) on line 2 — is said like this:
OUTPUT
bad.tiny:2: a division by zero
show x / (2 - 2)
^What satl does beyond this
The shape is the same — read, lex, check, walk — and each stage is where satl spends its effort differently.
- Words, not keywords. satl’s words are a table (
words/words.tsv), each with a number:satellite.console.displayis1 5 1. Every word is its own small compiled library (a.sofile) that satl loads once when it starts, so running a word is one call into code already in memory. - Sixteen-bit codes, not token objects. satl’s lexer turns every line into a row of 16-bit codes; a string or a name is a code, a count, and then its characters. One row a file, and nothing allocated per node. The lines are lexed on many threads at once, because each line is lexed alone.
- A statement may span lines. Before lexing, satl joins the lines of one statement onto its first line — while a string, a bracket or a list is open, or when a line ends in an operator — and leaves the other lines empty, so every line number in a report is still the one your editor shows.
- A check before anything runs. tiny refuses a line only when it reaches it, after the lines above have run. satl walks the whole program first — every name declared, every word spelled right (“did you mean satellite.console.display?”), every bracket closed — so most mistakes stop the run before its first line prints.
- Tail calls and a stack that grows. A capsule whose last line calls itself is run as a loop, in constant memory. A call with work after it is an ordinary call, and when the C++ stack runs low satl continues on a fresh stack segment (
makecontext/swapcontext), so a million levels deep works; the limit is memory. - Reports are for people. Every refusal has an S-code, a sentence, the line, a caret, and is kept in
~/.satl/satellite.log.
Every one of these is in satellite’s source, and HOW SATELLITE 004 RUNS walks through them from the outside.
