Posts

In the previous post on this series, we went over parsing let declarations (let <name> = <expr>) and wrapping expressions in statements. This set us up for extending our grammar further - in this part, we’ll add identifier expressions then compile our AST to bytecode and execute it in a stack VM. Alright, let’s move on to adding our new AST node type, VarExpr: /// ast.hpp struct Expr { virtual ~Expr() = default; }; struct VarExpr : Expr { std::string name; explicit VarExpr(std::string name) : name { std::move(name) } { } }; struct Literal : Expr { ... }; Here we go, nice and simple. VarExpr owns a std::string which refers to an identifier in the source code. Let’s parse this now, but where should we do it? Since it’s an expression, and we’re expecting the token Ident, it should be handled in parse_primary: ...

If you have not read part 1 of this blog series, I advise you read it here to continue with part 2. Previously, we parsed the expression 1 + 2 * 5 with operator precedence in a recursive descent parser. Now we can look at expanding the grammar of our language to accept more constructs, our first new addition will be let bindings (e.g. let sum = 1 + 2 * 5). To implement this we will be introducing three new token types: Ident, Let and Equal. Ident refers to identifiers, an alphanumeric textual value, such as keywords. ...

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. ...

Introduction Whilst designing my functional programming language Lam, I wondered about applications - how can I annotate this application in such a weird way but it still works as intended? If you don’t know anything about what I just said, just know an application is just a function call e.g. (+ 1 2) => 3. This was a good thought experiment for me, because I ended up accidentally creating a positional notation system for numbers based on their relationships in the natural number line. That was a mouthful. ...

Introduction I was tweaking my functional language’s parser one evening, and I became frustrated with the messiness of my code. It wasn’t something I intended, but a natural occurrence which happens from writing parsers like this, I really couldn’t do much to fix it without sacrificing hours into rewriting it. The most annoying issue I was facing was the constant consumption of ignored tokens such as parenthesis, I would call “consume” every single line which added onto the pile of mess the parser created already - it distracted me from reading the grammar flow of the parse function. And just like any other programmer, I decided to fix this; and i didn’t go the easy route I spent a weekend learning about different parsing algorithms, ones I’ve never heard of before, that’s when I came across Earley parsing - an algorithm for context free grammars. ...