Build a regex engine from scratch. Turn expressions into automata with backtracking, groups and character classes without using a regex library.
Build it in your language
The tester treats your program as a black box: any language works. These are just the most convenient ones for this project.
Regular expressions look like an esoteric language until you build the engine that runs them. Then they become what they are: a small tree and a machine that walks it.
You'll parse the expression, turn it into an automaton and run it against text. You'll implement groups, quantifiers and character classes, and see first-hand why certain expressions take forever.
8 stages across 4 phases. Every stage comes with its guide and its tests: you move on when they pass.
Literals, the dot, anchors, and a first minimal recursive engine.
A parser for quantifiers, alternation, character classes and groups.
Captured groups, lazy quantifiers and substitution.
NFA simulation and a performance comparison against the backtracking engine.
Build a JSON parser from scratch. Tokenize input, parse the grammar, construct a syntax tree and report useful errors for invalid JSON.
TypeScript · Python · Go · Java
Build a Lisp interpreter from scratch. Write a tokenizer, parser and evaluator, then add closures to discover how a language executes your code.
Python · JavaScript · TypeScript
Build a compiler from scratch. Turn source code into bytecode with lexing, an AST, semantic analysis, code generation and a virtual machine.
Rust · C++ · TypeScript