Brain, a small programming language
problem
I could write programs but I could not say what happened to them between the file and the machine. Compilers were the widest gap between what I used every day and what I could actually explain.
approach
Brain is a small language supporting arithmetic and variables, with a compiler written from scratch in Rust: a hand written lexer that turns source text into tokens, a recursive descent parser that turns tokens into a syntax tree, and a semantic pass that walks the tree to check that names exist and types agree before anything runs.
It is laid out as an ordinary Cargo project with the lexer, parser, and analysis as separate modules, because keeping the phases apart is most of what makes a compiler readable.
tradeoffs
- choice The parser is recursive descent, written by hand.cost More code, and the grammar lives in the parser rather than in a grammar file where you can read it in one sitting. In exchange I understood every line, and the error messages are mine to write instead of something generated.
- choice Rust, with each node in the tree owning its children outright.cost The borrow checker rejected the first two designs I tried, in particular anything where a node wanted a reference back to its parent. Strictly downward ownership was the shape the language pushed me into, and it turned out to be the clearer one.
- choice The compiler stops at the first semantic error.cost A file with five mistakes takes five runs to clear, which is genuinely annoying to use. Error recovery is the right answer and I did not build it.
what broke
Error positions were off by a token. The parser reported where it noticed the problem rather than where the problem started, so a missing bracket blamed whatever came after it.
Recording the span as the parser enters a construct, instead of reading the current position when it fails, fixed it.
what I learned
I had treated error messages as an afterthought, and they are most of what the program actually outputs.
Keeping lexing and parsing in separate modules meant every bug had an obvious place to start looking.