Writing a Programming Language From Scratch - Part 2

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.

So let’s go ahead and define these new token types:

/// lexer.hpp

/// includes omitted for brevity

enum class TokenType : std::uint8_t {
    Int,
    Plus,
    Mul,
    Minus,
    Slash,
    LParen,
    RParen,
    Ident,
    Let,
    Equal,
    EOF_,
};

Now recognising = is trivial, adding a new branch matching that character alongside the other ones, but identifiers have to be handled just like integers are:

switch (const auto cur { current() }; cur) {
    ...
    case '=': advance(); return Token { TokenType::Equal,  "=" };
    ...
}

Now handling identifiers is the exact same pattern as the integer processing is:

if (std::isalpha(cur)) {
    const auto start { m_position };
    while (!is_eof() && std::isalnum(m_source[m_position]))
        advance();

    const auto end { m_position };
    const std::string value { m_source.substr(start, end - start) };

    return Token { TokenType::Ident, value };
}

You may have noticed we can handle keyword tokens right in here, and you’re right. Let’s think of this efficiently, we could write a long if statement branch on value for each keyword and mapping it to the correct token type, unmanageable when we have more keywords. Maybe we can use a map of strings to token types? This approach is more manageable and all it requires is adding a new entry to the map:

    ...
    EOF_,
};

static const std::unordered_map<std::string_view, TokenType> keywords {
    { "let", TokenType::Let },
};

struct Token {
    ...

Great! So now we have a map of strings to token types which allows for easy lookup, let’s make our identifier processor query the map for the token type, if it doesn’t exist we’ll just use TokenType::Ident:

if (std::isalpha(cur)) {
    const auto start { m_position };
    while (!is_eof() && std::isalnum(m_source[m_position]))
        advance();

    const auto end { m_position };
    const std::string value { m_source.substr(start, end - start) };

    const auto iter = keywords.find(value);
    const auto ty = iter != keywords.end() ? iter->second : TokenType::Ident;

    return Token { ty, value };
}

There we go, now we tokenize identifiers, keywords and equals. I think we’re ready to parse let <name> = <expr>, and this tells us what we need to do already, if we see let advance, expect an identifier for the name, expect an equals symbol, then parse an expression for the value of the variable. Very simple, we’ve basically implemented it already just from reading it. So let’s do that, but first we need to define the AST node for a let declaration:

/// 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, Sub, Mul, Div };

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) } { }
};

struct Stmt {
    virtual ~Stmt() = default;
};

struct LetDecl : Stmt {
    std::string name;
    Box<Expr>   init;

    LetDecl(std::string name, Box<Expr> init)
        : name { std::move(name) }, init { std::move(init) } { }
};

There are two new nodes, Stmt and LetDecl, because let <name> = <expr> is a statement, we need a new base node to inherit it from. Implementing this in the parser is trivial, but we need to change a few things:

First let’s update the format_token_type function:

/// parser.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::LParen:return "(";
        case TokenType::RParen:return ")";
        case TokenType::Ident: return "ident";
        case TokenType::Let:   return "let";
        case TokenType::Equal: return "=";
        case TokenType::EOF_:  return "eof";
    }

    return "?";
}

Now we need to change parse to return std::vector<Box<Stmt>>:

std::vector<Box<Stmt>> parse() {
    std::vector<Box<Stmt>> stmts;
    while (m_current.ty != TokenType::EOF_)
        stmts.push_back(parse_stmt());

    return stmts;
}

Let’s define parse_stmt:

Box<Stmt> parse_stmt() {
    
}

So what is parse_stmt supposed to do now? It’s a top level dispatch method meaning in this language, statements are top level bits of code, expressions are no longer parsed first; statements are built with expressions. Our first statement to parse a let declaration, like we discussed before the implementation is trivial, so let’s parse it when we see Let:

Box<Stmt> parse_stmt() {
    switch (m_current.ty) {
        case TokenType::Let: return parse_let();
        default: throw std::runtime_error("unexpected token found in parse_stmt");
    }
}

We could make a better error message, but it’s fine for now; we’ll worry about that later. Let’s go ahead and define parse_let:

Box<Stmt> parse_let() {
    
}

Okay, our first step is to advance, because we already know we’re at the Let token so we can simply move past it:

Box<Stmt> parse_let() {
    advance();
}

At this stage, we can expect the source code to be at an identifier, but we can’t be sure so we’ll call expect to error if it isn’t:

Box<Stmt> parse_let() {
    advance();
    auto name = expect(TokenType::Ident).value;
}

We can directly grab the value out of the token so we can move it to LetDecl. Alright, now we should expect to see = right? Let’s add that:

Box<Stmt> parse_let() {
    advance();
    auto name = expect(TokenType::Ident).value;
    expect(TokenType::Equal);
}

Perfect, right now we’ve parsed let <name> =, we’re one step closer to fully parsing a let declaration:

Box<Stmt> parse_let() {
    advance();
    auto name = expect(TokenType::Ident).value;
    expect(TokenType::Equal);
    auto init = parse_expr();
    return std::make_unique<LetDecl>(name, std::move(init));
}

Here we go, we’ve successfully parsed let <name> = <expr>, in my opinion this was very simple, we walked through it in our head without writing any code and used the functions we had to express those thoughts programmatically. That’s basically what parsing is in a nutshell.

We should test it now, and see if it produces what we expect:

int main() {
    Parser parser { "let sum = 1 + 2" };

    for (const auto stmts = parser.parse(); auto& stmt : stmts) {
        if (auto* let = dynamic_cast<const LetDecl*>(stmt.get())) {
            std::println("LetDecl.name = {}", let->name);
            std::println("LetDecl.init = {}", format(let->init.get()));
        }
    }
}

You should see the output:

LetDecl.name = sum
LetDecl.init = Binary(+)
  Literal(1)
  Literal(2)

If you see this, that means our parser is working! This is great, we now parse statements, and those statements are built with expressions.

Right now, our parser only parses one statement, which is a let decl, we cannot parse simple expressions. So we should introduce a statement level expression, we do this by creating a ExprStmt which wraps an Expr, this allows for expressions to be top level statements:

/// ast.hpp

/// Definitions omitted for brevity

struct ExprStmt : Stmt {
    Box<Expr> expr;

    explicit ExprStmt(Box<Expr> expr) : expr { std::move(expr) } { }
};

Now we can handle this in parse_stmt as such:

/// parser.hpp

Box<Stmt> parse_stmt() {
    switch (m_current.ty) {
        case TokenType::Let: return parse_let();
        default: return std::make_unique<ExprStmt>(parse_expr());
    }
}

Let’s test if it works:

/// main.cpp

int main() {
    Parser parser { "1 + 2" };

    for (const auto stmts = parser.parse(); auto& stmt : stmts) {
        if (auto* let = dynamic_cast<const LetDecl*>(stmt.get())) {
            std::println("LetDecl.name = {}", let->name);
            std::println("LetDecl.init = {}", format(let->init.get()));
        }

        if (auto* expr = dynamic_cast<const ExprStmt*>(stmt.get())) {
            std::println("{}", format(expr->expr.get()));
        }
    }
}

The expected output should be:

Binary(+)
  Literal(1)
  Literal(2)

If you see this, that means we now parse expressions as top level statements!

What’s Next?

In part 3, we’ll introduce identifier expressions for reference bindings, then we’ll compile the AST to bytecode and build a stack VM to execute it.

What’s Next?#

What’s Next?