C++ - Lexer for the Monkey Programming Language from the book "Writing An Interpreter In Go"

Question

Below is a C++ version of a lexer for the Monkey programming language, originally written in Go, as presented in the book Writing An Interpreter In Go.

LOC: 262. (Excluding the tests.)

Language:

Copy pasting from the book:

Here is how we bind values to names in Monkey:

let age = 1; 
let name = "Monkey"; 
let result = 10 * (20 / 2);

Besides integers, booleans and strings, the Monkey interpreter we’re going to build will also support arrays and hashes. Here’s what binding an array of integers to a name looks like:

let myArray = [1, 2, 3, 4, 5]; 

And here is a hash, where values are associated with keys:

let thorsten = {"name": "Thorsten", "age": 28}; 

Accessing the elements in arrays and hashes is done with index expressions:

myArray[0] // => 1 
thorsten["name"] // => "Thorsten" 

The let statements can also be used to bind functions to names. Here’s a small function that adds two numbers:

let add = fn(a, b) { return a + b; };

But Monkey not only supports return statements. Implicit return values are also possible, which means we can leave out the return if we want to:

let add = fn(a, b) { a + b; }; 

And calling a function is as easy as you’d expect:

add(1, 2); 

A more complex function, such as a fibonacci function that returns the Nth Fibonacci number, might look like this:

let fibonacci = fn(x) { 
    if (x == 0) { 
        0
    } else { 
        if (x == 1) {
             1 
        } else { 
             fibonacci(x - 1) + fibonacci(x - 2);
        }
    }
}; 

Note the recursive calls to fibonacci itself! Monkey also supports a special type of functions, called higher order functions. These are functions that take other functions as arguments. Here is an example:

let twice = fn(f, x) { return f(f(x)); }; 
let addTwo = fn(x) { return x + 2; }; 
twice(addTwo, 2); // => 6

Directory Structure:

.
├── lexer
│   ├── lexer.cpp
│   └── lexer.hpp
├── LICENSE
├── Makefile
├── README.md
├── repl
│   └── repl.cpp
├── test
│   ├── lexer_test.cpp
└── token
    ├── token.cpp
    └── token.hpp

4 directories, 9 files

Code:

lexer.hpp:

#ifndef LEXER_HPP
#define LEXER_HPP 1

#include <cstddef>
#include <string_view>

#include "../token/token.hpp"

class Lexer {
    std::string_view input;
    std::size_t pos{};
    std::size_t read_pos{};
    char ch;

    void read_char();
    char peek_char() const;
    bool is_letter(char c) const;
    void skip_whitespace();
    std::string_view read_ident();
    std::string_view read_int();
    std::string_view read_string();

  public:
    Lexer(const std::string_view &input);
    Token next();
};

#endif /* LEXER_HPP */

lexer.cpp:

#include "lexer.hpp"

#include <cctype>
#include <cstddef>
#include <string>
#include <string_view>

void Lexer::read_char()
{
    ch = read_pos >= input.length() ? '\0' : input[read_pos];
    pos = read_pos++;
}

char Lexer::peek_char() const
{
    return read_pos >= input.length() ? '\0' : input[read_pos];
}

bool Lexer::is_letter(char c) const
{
    return c == '_' || std::isalpha(static_cast<unsigned char>(c));
}

void Lexer::skip_whitespace()
{
    for (; std::isspace(static_cast<unsigned char>(ch)); read_char())
        ;
}

std::string_view Lexer::read_ident()
{
    const std::size_t orig_pos{pos};
    for (; is_letter(ch); read_char())
        ;
    return input.substr(orig_pos, pos - orig_pos);
}

std::string_view Lexer::read_int()
{
    const std::size_t orig_pos{pos};
    for (; isdigit(static_cast<unsigned char>(ch)); read_char())
        ;
    return input.substr(orig_pos, pos - orig_pos);
}

std::string_view Lexer::read_string()
{
    /* Monkey doesn't support escape characters.
     * XXX: How to signal EOF? Returning an empty string can not be an error.
     *      Raise an exception?
     */
    const std::size_t orig_pos{pos + 1};
    do {
        read_char();
    } while (ch != '"' && ch != '\0');
    return input.substr(orig_pos, pos - orig_pos);
}

Lexer::Lexer(const std::string_view &input) : input(input) { read_char(); }

Token Lexer::next()
{
    skip_whitespace();

    switch (ch) {
        case '\0':
            return Token(Token::Type::Eof, "");

        case '=':
            if (peek_char() == '=') {
                read_char();
                read_char();
                return Token(Token::Type::Eq, "==");
            }
            read_char();
            return Token(Token::Type::Assign, "=");

        case '+':
            read_char();
            return Token(Token::Type::Plus, "+");

        case '-':
            read_char();
            return Token(Token::Type::Minus, "-");

        case '!':
            if (peek_char() == '=') {
                read_char();
                read_char();
                return Token(Token::Type::Not_eq, "!=");
            }
            read_char();
            return Token(Token::Type::Bang, "!");

        case '*':
            read_char();
            return Token(Token::Type::Asterisk, "*");

        case '/':
            read_char();
            return Token(Token::Type::Slash, "/");

        case '<':
            read_char();
            return Token(Token::Type::Lt, "<");

        case '>':
            read_char();
            return Token(Token::Type::Gt, ">");

        case ',':
            read_char();
            return Token(Token::Type::Comma, ",");

        case ';':
            read_char();
            return Token(Token::Type::Semicolon, ";");

        case ':':
            read_char();
            return Token(Token::Type::Colon, ":");

        case '(':
            read_char();
            return Token(Token::Type::Lparen, "(");

        case ')':
            read_char();
            return Token(Token::Type::Rparen, ")");

        case '{':
            read_char();
            return Token(Token::Type::Lbrace, "{");

        case '}':
            read_char();
            return Token(Token::Type::Rbrace, "}");

        case '[':
            read_char();
            return Token(Token::Type::Lbracket, "[");

        case ']':
            read_char();
            return Token(Token::Type::Rbracket, "]");

        case '"': {
            const std::string_view ident{read_string()};
            read_char();
            return Token(Token::Type::String, ident);
        }

        default:
            if (is_letter(ch)) {
                const std::string_view ident{read_ident()};
                return Token(Token::lookup_ident(ident), ident);
            } else if (std::isdigit(static_cast<unsigned char>(ch))) {
                return Token(Token::Type::Int, read_int());
            }

            Token t{Token(Token::Type::Illegal, std::string{1, ch})};
            read_char();
            return t;
    }
}

token.hpp:

#ifndef TOKEN_H
#define TOKEN_H 1

#include <string>
#include <string_view>
#include <vector>

/* This solution is vastly superior to any switch case or array based one,
 * because it doesn't duplicate the names, making it easy to change the
 * enumeration.
 */
#define FOREACH_TOKEN(_)    \
    _(Illegal)              \
    _(Eof)                  \
    _(Ident)                \
    _(Int)                  \
    _(String)               \
    _(Assign)               \
    _(Plus)                 \
    _(Minus)                \
    _(Asterisk)             \
    _(Slash)                \
    _(Bang)                 \
    _(Lt)                   \
    _(Gt)                   \
    _(Eq)                   \
    _(Not_eq)               \
    _(Comma)                \
    _(Semicolon)            \
    _(Colon)                \
    _(Lparen)               \
    _(Rparen)               \
    _(Lbrace)               \
    _(Rbrace)               \
    _(Lbracket)             \
    _(Rbracket)             \
    _(Function)             \
    _(Let)                  \
    _(True)                 \
    _(False)                \
    _(If)                   \
    _(Else)                 \
    _(Return)               \

#define GEN_ENUM(ENUM) ENUM,

class Token {
    // FIXME: This shouldn't be a vector. How do we write an array without
    // providing a size?
    static const std::vector<std::string_view> token_strs;
    static int token_strs_count;

  public:
    enum class Type { FOREACH_TOKEN(GEN_ENUM) };

    Token::Type type;
    std::string lit;

    Token(Token::Type type, const std::string_view &lit) : type(type), lit(lit)
    {
    }
    static Token::Type lookup_ident(const std::string_view &ident);
    static std::string_view to_str(Token::Type t);
};

#undef GEN_ENUM

#endif /* TOKEN_H */

token.cpp:

#include "token.hpp"

#include <string_view>
#include <unordered_map>
#include <vector>

#define GEN_STRING(STRING) #STRING,

const std::vector<std::string_view> Token::token_strs{
    FOREACH_TOKEN(GEN_STRING)};

int Token::token_strs_count{static_cast<int>(token_strs.size())};

Token::Type Token::lookup_ident(const std::string_view &ident)
{
    static const std::unordered_map<std::string_view, Token::Type> kws{
        {"fn", Token::Type::Function},   {"let", Token::Type::Let},
        {"true", Token::Type::True},     {"false", Token::Type::False},
        {"if", Token::Type::If},         {"else", Token::Type::Else},
        {"return", Token::Type::Return},
    };

    auto it{kws.find(ident)};
    return it != kws.end() ? it->second : Token::Type::Ident;
}

std::string_view Token::to_str(Token::Type t)
{
    // XXX: Is returning "" an okay decision?
    const int idx{static_cast<int>(t)};
    return idx < 0 || idx > token_strs_count
               ? ""
               : token_strs[static_cast<std::size_t>(idx)];
}

#undef GEN_STRING
#undef FOREACH_TOKEN

REPL:

repl.cpp:

#include <iostream>
#include <string>
#include <system_error>

#include "../lexer/lexer.hpp"
#include "../token/token.hpp"

int main()
{
    std::cout << "Hello! This is the Monkey Programming Language!\n"
              << "Type in commands:\n";

    while (true) {
        std::cout << ">> " << std::flush;
        std::string input{};

        if (!std::getline(std::cin, input)) {
            if (std::cin.bad()) {
                std::cerr
                    << "error: failed to read input: "
                    << std::error_code{errno, std::generic_category()}.message()
                    << ".\n";
                return EXIT_FAILURE;
            }
            break;
        }

        Lexer l{input};

        for (Token t{l.next()}; t.type != Token::Type::Eof; t = l.next()) {
            std::cout << "{Type: " << Token::to_str(t.type)
                      << ", Literal: " << t.lit << "}\n";
        }
    }
}

Tests:

And some tests for the lexer; lexer_test.cpp:

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stddef.h>
#include <string_view>
#include <vector>

#include "../lexer/lexer.hpp"
#include "../token/token.hpp"

static std::size_t tests_run = 0;

static void run_test(const std::string_view &input,
                     const std::vector<Token> &tests)
{
    ++tests_run;
    fprintf(stderr, "[INFO]: Running test suite %zu...\n", tests_run);
    Lexer l{input};

    for (std::size_t i = 0; i < std::size(tests); ++i) {
        const Token tt = tests[i];
        const Token t{l.next()};

        if (t.type != tt.type) {
            std::cerr << "[FAIL]: tests[" << i + 1 << "] - Token::Type wrong. "
                      << "Expected '" << Token::to_str(tt.type) << "'. Got '"
                      << Token::to_str(t.type) << "'.\n",
                std::exit(EXIT_FAILURE);
        }

        /* The strncmp() is for illegal tokens; they are non-null terminated,
         * whilst the expected tokens are null-terminated.
         */
        if (t.lit != tt.lit &&
            (t.type == Token::Type::Illegal &&
             strncmp(t.lit.c_str(), tt.lit.c_str(), 1) == 0)) {
            std::cerr << "[FAIL]: tests[" << i + 1 << "] - Literal wrong. "
                      << "Expected '" << tt.lit << "'. Got '" << t.lit
                      << "'.\n",
                std::exit(EXIT_FAILURE);
        }
    }

    std::cerr << "[INFO]: All tests passed!\n";
}

int main()
{
    /* FIXME: These shouldn't need to be a vector either. */
    static const std::vector<Token> test_suite1{
        {Token::Type::Assign, "="},  {Token::Type::Plus, "+"},
        {Token::Type::Lparen, "("},  {Token::Type::Rparen, ")"},
        {Token::Type::Lbrace, "{"},  {Token::Type::Rbrace, "}"},
        {Token::Type::Comma, ","},   {Token::Type::Semicolon, ";"},
        {Token::Type::Illegal, "#"}, {Token::Type::Eof, ""},
    };

    run_test("=+(){},;#", test_suite1);

    static const std::vector<Token> test_suite2{
        {Token::Type::Let, "let"},     {Token::Type::Ident, "five"},
        {Token::Type::Assign, "="},    {Token::Type::Int, "5"},
        {Token::Type::Semicolon, ";"}, {Token::Type::Let, "let"},
        {Token::Type::Ident, "ten"},   {Token::Type::Assign, "="},
        {Token::Type::Int, "10"},      {Token::Type::Semicolon, ";"},
        {Token::Type::Let, "let"},     {Token::Type::Ident, "add"},
        {Token::Type::Assign, "="},    {Token::Type::Function, "fn"},
        {Token::Type::Lparen, "("},    {Token::Type::Ident, "x"},
        {Token::Type::Comma, ","},     {Token::Type::Ident, "y"},
        {Token::Type::Rparen, ")"},    {Token::Type::Lbrace, "{"},
        {Token::Type::Ident, "x"},     {Token::Type::Plus, "+"},
        {Token::Type::Ident, "y"},     {Token::Type::Semicolon, ";"},
        {Token::Type::Rbrace, "}"},    {Token::Type::Semicolon, ";"},
        {Token::Type::Let, "let"},     {Token::Type::Ident, "result"},
        {Token::Type::Assign, "="},    {Token::Type::Ident, "add"},
        {Token::Type::Lparen, "("},    {Token::Type::Ident, "five"},
        {Token::Type::Comma, ","},     {Token::Type::Ident, "ten"},
        {Token::Type::Rparen, ")"},    {Token::Type::Semicolon, ";"},
        {Token::Type::Eof, ""},
    };

    run_test("let five = 5;"
             "let ten = 10;"
             "let add = fn(x, y) { x + y; };"
             "let result = add(five, ten);",
             test_suite2);

    static const std::vector<Token> test_suite3{
        {Token::Type::Let, "let"},
        {Token::Type::Ident, "five"},
        {Token::Type::Assign, "="},
        {Token::Type::Int, "5"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Let, "let"},
        {Token::Type::Ident, "ten"},
        {Token::Type::Assign, "="},
        {Token::Type::Int, "10"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Let, "let"},
        {Token::Type::Ident, "add"},
        {Token::Type::Assign, "="},
        {Token::Type::Function, "fn"},
        {Token::Type::Lparen, "("},
        {Token::Type::Ident, "x"},
        {Token::Type::Comma, ","},
        {Token::Type::Ident, "y"},
        {Token::Type::Rparen, ")"},
        {Token::Type::Lbrace, "{"},
        {Token::Type::Ident, "x"},
        {Token::Type::Plus, "+"},
        {Token::Type::Ident, "y"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Rbrace, "}"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Let, "let"},
        {Token::Type::Ident, "result"},
        {Token::Type::Assign, "="},
        {Token::Type::Ident, "add"},
        {Token::Type::Lparen, "("},
        {Token::Type::Ident, "five"},
        {Token::Type::Comma, ","},
        {Token::Type::Ident, "ten"},
        {Token::Type::Rparen, ")"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Bang, "!"},
        {Token::Type::Minus, "-"},
        {Token::Type::Slash, "/"},
        {Token::Type::Asterisk, "*"},
        {Token::Type::Int, "5"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Int, "5"},
        {Token::Type::Lt, "<"},
        {Token::Type::Int, "10"},
        {Token::Type::Gt, ">"},
        {Token::Type::Int, "5"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::If, "if"},
        {Token::Type::Lparen, "("},
        {Token::Type::Int, "5"},
        {Token::Type::Lt, "<"},
        {Token::Type::Int, "10"},
        {Token::Type::Rparen, ")"},
        {Token::Type::Lbrace, "{"},
        {Token::Type::Return, "return"},
        {Token::Type::True, "true"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Rbrace, "}"},
        {Token::Type::Else, "else"},
        {Token::Type::Lbrace, "{"},
        {Token::Type::Return, "return"},
        {Token::Type::False, "false"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Rbrace, "}"},
        {Token::Type::Int, "10"},
        {Token::Type::Eq, "=="},
        {Token::Type::Int, "10"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Int, "10"},
        {Token::Type::Not_eq, "!="},
        {Token::Type::Int, "9"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::String, "\"foobar\""},
        {Token::Type::String, "\" foo bar \""},
        {Token::Type::Lbracket, "["},
        {Token::Type::Int, "1"},
        {Token::Type::Comma, ","},
        {Token::Type::Int, "2"},
        {Token::Type::Rbracket, "]"},
        {Token::Type::Semicolon, ";"},
        {Token::Type::Lbrace, "{"},
        {Token::Type::String, "\"foo\""},
        {Token::Type::Colon, ":"},
        {Token::Type::String, "\"bar\""},
        {Token::Type::Rbrace, "}"},
        {Token::Type::Eof, ""},
    };

    run_test("let five = 5;"
             " let ten = 10;"
             "let add = fn(x, y) { x + y; };"
             "let result = add(five, ten);"
             "!-/*5;"
             "5 < 10 > 5;"
             "if (5 < 10) {"
             "return true;"
             "} else {"
             "return false;"
             "}"
             "10 == 10;"
             "10 != 9;"
             "\"foobar\""
             "\" foo bar \""
             "[1, 2];"
             "{\"foo\": \"bar\"}",
             test_suite3);
}

Makefile:

CXX := clang++-18

CXXFLAGS    += -std=c++17
CXXFLAGS    += -g3
CXXFLAGS    += -ggdb
CXXFLAGS    += -fPIC
CXXFLAGS    += -gdwarf-4
CXXFLAGS    += -Wall
CXXFLAGS    += -Wextra
CXXFLAGS    += -Wwrite-strings
CXXFLAGS    += -Wno-parentheses
CXXFLAGS    += -Wpedantic
CXXFLAGS    += -Warray-bounds
CXXFLAGS    += -Wconversion
CXXFLAGS    += -Wno-unused-function

BINDIR      := bin
TEST_BINDIR := test/bin

SRCDIRS     := lexer repl token 
SRCS        := $(filter-out repl/repl.cpp, $(wildcard $(addsuffix /*.cpp, $(SRCDIRS))))

TESTDIR     := test
TEST_SRCS   := $(wildcard $(TESTDIR)/*.cpp)

TARGET      := $(BINDIR)/repl
TEST_TARGET := $(TEST_BINDIR)/lexer_test

all: $(TARGET)

$(TARGET): repl/repl.cpp $(SRCS) | $(BINDIR)
    $(CXX) $(CXXFLAGS) -o $@ $^

$(TEST_TARGET): $(SRCS) $(TEST_SRCS) | $(TEST_BINDIR)
    $(CXX) $(CXXFLAGS) -o $@ $^

test: $(TEST_TARGET)
    @echo "Running tests..."
    @./$<   

$(BINDIR) $(TEST_BINDIR):
    mkdir -p $@

rclean:
    rm -rf $(BINDIR)

tclean:
    rm -rf $(TEST_BINDIR)

fclean_repl:
    rm $(TARGET) 

fclean_test:
    rm $(TEST_TARGET)

.PHONY: all test clean fclean_repl fclean_test

.DELETE_ON_ERROR:

All the code was formatted with:

clang-format --style={"IndentWidth: 4,BreakBeforeBraces: Stroustrup}"

Review Request:

• project structure
• filenaming/code splitting
• naming and design
• makefile
• general coding comments
• anything, everything

For ease, here's the github repository: lexer-cpp.

Run make to build the REPL (it'll be in the bin directory), and make test to build and run the tests.

For the curious, here's the Go version: lexer-go.

The lexer was previously rewritten in C as well: C99 - Lexer for the Monkey Programming Language from the book "Writing An Interpreter In Go"

(Side-note: I am completely new to C++ and OOP, so judge accordingly and feel free to critique, but refrain from suggesting grotesque, highly-obfuscated, and overly-complicated templated and range-based code snippets that would make me run for the hills.)

Answer 1

For someone new to C++ and OOP, your code is pretty good!

Can you really lex one line at a time?

Your Lexer only processes one line at a time, at least that's how your REPL and tests work. But are you sure that no tokens can span multiple lines? What about strings? And even if there are no multi-line tokens, you do have multi-token lines. How long can a line be? Would it fit into memory? Perhaps a silly question today, but in the past computers came with memory sizes measured in kilobytes, and they still came with programming language interpreters that had to lex and parse.

To solve this issue, you want Lexer to deal with the input stream directly. Instead of passing it a std::string_view, pass it a reference to a std::istream, and use member functions like get()/peek()/read() to get the characters. Then you can pass it a concrete stream object, like std::cin, a std::ifstream, or if you want to force lexing one line at a time, you could still read a line into a string and adapt it into a stream using std::istringstream, or more efficiently using C++23's std::ispanstream.

Let the read_*() functions return Tokens

You have functions like read_int() and read_string() that just return a std::string_view, and conversion to a Token happens in next(). However, you run into a problem in read_string(), where you indeed cannot handle an error, because returning an empty string might be confused with a valid empty string. So instead, do the conversion to Token into those functions; that way you can return Token::Type::Illegal from it if it's not a valid string.

Avoiding the big switch-statement

Lexer::next() contains a huge switch-statement. However, there is a lot of code duplication for all the operators. This can be avoided. Ideally, you would write something like:

class TokenTrie {
    …
    Token get();
};

static const TokenTrie operators = {
    {"=", Token::Type::Eq},
    {"==", Token::Type::Assign},
    {"+", Token::Type::Plus},
    …
}

Token Lexer::next() {
    if (is_letter(ch)) {
        …
    } else if (is_digit(ch)) {
        …
    } else {
        return operators.get(…);
    }
}    

Where TokenTrie implements a trie that allows efficient lookups of operators. The get() function could then either return the token belonging to the longest string matching the input, or a Token::Type::Illegal if nothing matched.

This simplifies Lexer::next() a lot, makes adding or changing operators very simple, at the cost of having to implement TokenTrie of course. You could then use it for kws as well though.

If performance isn't an issue, then you could also just use a std::map<std::string, Token::Type> and use equal_range() to do a lookup in \$O(\log N)\$ time, the advantage is that it only takes a few lines of code.

Writing an array without providing a size

You have a problem declaring token_strs as an array. This is quite easy however:

class Token {
    static constexpr std::array token_strs = {
        #define GEN_STRING_COMMA(STRING) #STRING,
        FOREACH_TOKEN(GEN_STRING_COMMA)
        #undef GEN_STRING_COMMA
    };
    …
};

There are other solutions here as well, you can use static inline const instead of static constexpr, you can write const char* token_strs[] instead of std::array token_strs, you could even have done something like:

class Token {
    #define ADD_ONE(STRING) + 1
    static constexpr std::size_t token_strs_count = 0 FOREACH_TOKEN(ADD_ONE);
    #undef ADD_ONE
    static const char* token_strs[token_strs_count];
    …
};

Use std::size_t for sizes, counts and indices

Instead of using int, make it a habit to use std::size_t for sizes, counts and indices. It is guaranteed to be able to count and index anything that could fit into memory, while int is not. You probably noticed you got compiler warnings when you wrote token_strs[idx] when idx was an int; instead of static_casting it to std::size_t, you could have avoided that by making it a std::size_t to begin with.

Naming things

The names you gave things are mostly fine, however you are abbreviating some things unnecessarily, and sometimes even using one-letter variables. One-letter variables are only fine for some very well-known cases, like using i for an integer loop index, or x and y for coordinates. ch and it are also fine as they are. I suggest these changes:

• t -> token
• token_strs -> token_strings, or maybe better token_names
• lit -> literal
• kws -> keywords
• to_str -> to_string, or maybe more precisely to_string_view
• idx -> index
• l -> lexer
• tt -> expected_token

Don't mix C and C++ style I/O

You use both fprintf(stderr, …) and std::cerr << …. Pick one style and stick with it. Preferrably, use C++ functions over C functions. Nowadays formatting strings in C++ is easy, using C++20's std::format() and even better, C++23's std::print().