Simple lexer in C++

Question

I haven't written anything in C++ in a couple of years, so I have both forgotten a lot and also wasn't exposed to the modern C++. I am working on a toy programming language and while other parts are pretty large, so probably hard for a review, the lexer is fairly isolated. I would appreciate advice on how the code could be improved.

lexer.h

#ifndef LEXER_H
#define LEXER_H

#include "common.h"
#include "compilation_context.h"
#include "lexer_common.h"

#include <deque>
#include <fstream>
#include <iostream>

namespace schwifty {

struct Token {
    enum class Type {
        eof = 1,
        eol = 2,
        indentation = 3,
        identifier = 4,
        def = 5,
        symbol = 6,
        string = 7,
        class_ = 8,
        import = 9,
        if_ = 10,
        int_ = 11,
        return_ = 12,
        type_identifier = 13,
        extern_ = 14,
        own = 15,
        else_ = 16,
        elif = 17,
        while_ = 18,
        mut = 19,
        and_ = 20,
        or_ = 21
    };

    explicit Token(Type type, const LexingContext& lexing_context)
        : type(type), integer(0), lexing_context(lexing_context) {
        CHECK(type != Type::symbol);
        CHECK(type != Type::int_);
    }

    explicit Token(Type type, const string& value,
                   const LexingContext& lexing_context)
        : type(type), value(value), integer(0), lexing_context(lexing_context) {
        CHECK(!value.empty());
    }

    explicit Token(int integer, const LexingContext& lexing_context)
        : type(Type::int_),
          value(""),
          integer(integer),
          lexing_context(lexing_context) {}

    explicit Token(const Token& token)
        : type(token.type),
          value(token.value),
          integer(token.integer),
          lexing_context(token.lexing_context) {}

    bool is_symbol(const string& expected_symbol = "") const {
        return type == Type::symbol &&
               (expected_symbol.empty() || value == expected_symbol);
    }

    string type_to_string() const {
        switch (type) {
            case Type::eof:
                return "token_eof";
            case Type::eol:
                return "token_eol";
            case Type::indentation:
                return "token_indentation";
            case Type::identifier:
                return "token_identifier";
            case Type::def:
                return "token_def";
            case Type::symbol:
                return "token_symbol";
            case Type::string:
                return "token_string";
            case Type::class_:
                return "token_class";
            case Type::import:
                return "token_import";
            case Type::if_:
                return "token_if";
            case Type::int_:
                return "token_int";
            case Type::return_:
                return "token_return";
            case Type::type_identifier:
                return "token_type_identifier";
            case Type::extern_:
                return "extern";
            case Type::own:
                return "own";
            case Type::else_:
                return "else";
            case Type::elif:
                return "elif";
            case Type::while_:
                return "while";
            default:
                return std::to_string(static_cast<int>(type));
        }
    }

    string to_string() const {
        return "type: " + type_to_string() +
               (value.empty() ? "" : ", value: " + value) +
               (type == Type::int_
                      ? (string(", integer: ") + std::to_string(integer))
                      : "") +
               "\n " + lexing_context.to_string();
    };

    string to_string_for_error() const {
        switch (type) {
            case Type::int_:
                return std::to_string(integer);
            default:
                return value;
        }
    }

    const Type type;
    const string value;
    const int integer;
    const LexingContext lexing_context;
};

bool operator==(const Token& first, const Token& second);

class InputSource {
public:
    virtual string get_file_name() = 0;

    virtual bool has_next_file() = 0;

    bool open_next_file() {
        line_no_ = 0;
        return do_open_next_file();
    }

    virtual bool do_open_next_file() = 0;

    bool get_line(string* line) {
        bool result = do_get_line(line);
        if (result) {
            line_no_++;
        }
        return result;
    }

    virtual bool do_get_line(string* line) = 0;

    int get_line_no() { return line_no_; }

protected:
    int line_no_ = 0;
};

class StandardInputSource : public InputSource {
public:
    string get_file_name() override { return "<stdin>"; }

    bool has_next_file() override { return !started_reading_; }

    bool do_open_next_file() override { return !started_reading_; }

    bool do_get_line(string* line) override;

private:
    bool started_reading_ = false;
};

class FileInputSource : public InputSource {
private:
    int current_ = 0;
    std::ifstream input_stream_;
    vector<string> file_names_;

public:
    FileInputSource() {}
    ~FileInputSource() {
        if (input_stream_.is_open()) {
            input_stream_.close();
        }
    }

    void add_file(const string& path) { file_names_.push_back(path); }

    bool do_open_next_file() override {
        if (input_stream_.is_open()) {
            input_stream_.close();
        }
        if (current_ >= file_names_.size()) {
            return false;
        }
        input_stream_.open(file_names_[current_]);
        current_++;
        return (bool) input_stream_;
    }

    bool do_get_line(string* line) override {
        if (!input_stream_) {
            return false;
        }
        return (bool) std::getline(input_stream_, *line);
    }

    bool has_next_file() override { return current_ < file_names_.size(); }

    string get_file_name() override {
        if (current_ < 0 || current_ > file_names_.size()) {
            return "";
        }
        return file_names_[current_ - 1];
    }
};

class Lexer {
public:
    Lexer(CompilationContext& context, InputSource* source);

    const Token* get_token();

    const Token* peek_token();

    const Token* peek_token_skip_indentation();

    const int peek_indentation();

private:
    CompilationContext& context_;
    int line_counter_;
    string current_line_;
    InputSource* source_;
    std::deque<const Token*> tokens_;

    bool parse_line();

    bool read_line();

    LexingContext create_lexing_context();

    void push_symbol(const string& symbol);

    bool is_a_number(int index);

    std::set<char> single_char_symbols_;
};

}  // namespace schwifty

#endif  // LEXER_H

lexer.cc

#include "lexer.h"

#include <iostream>

#include "errors.h"
#include "utils.h"

namespace schwifty {

const static int INDENT_SPACES = 4;

bool StandardInputSource::do_get_line(string* line) {
    if (!started_reading_) {
        return false;
    }
    return (bool) getline(std::cin, *line);
}

Lexer::Lexer(CompilationContext& context, InputSource* source)
    : context_(context), line_counter_(0), source_(source) {
    single_char_symbols_.insert('(');
    single_char_symbols_.insert(')');
    single_char_symbols_.insert('{');
    single_char_symbols_.insert('}');
    single_char_symbols_.insert('>');
    single_char_symbols_.insert('<');
    single_char_symbols_.insert('-');
    single_char_symbols_.insert('+');
    single_char_symbols_.insert('*');
    single_char_symbols_.insert('/');
    single_char_symbols_.insert(':');
    single_char_symbols_.insert(',');
    single_char_symbols_.insert('.');
    single_char_symbols_.insert('[');
    single_char_symbols_.insert(']');
}

const Token* Lexer::get_token() {
    if (tokens_.empty()) {
        if (!parse_line()) {
            return new Token(Token::Type::eof, create_lexing_context());
        }
    }
    const Token* result = tokens_.front();
    tokens_.pop_front();
    VLOG(3) << result->to_string();
    return result;
}

const int Lexer::peek_indentation() {
    if (tokens_.empty()) {
        if (!parse_line()) {
            return 0;
        }
    }
    int i = 0;
    for (; i < tokens_.size() && tokens_[i]->type == Token::Type::indentation;
         i++)
        ;
    return i;
}

const Token* Lexer::peek_token() {
    if (tokens_.empty()) {
        if (!parse_line()) {
            return new Token(Token::Type::eof, create_lexing_context());
        }
    }
    return tokens_.front();
}

const Token* Lexer::peek_token_skip_indentation() {
    if (tokens_.empty()) {
        if (!parse_line()) {
            return new Token(Token::Type::eof, create_lexing_context());
        }
    }
    int i = 0;
    for (; i < tokens_.size() && tokens_[i]->type == Token::Type::indentation;
         i++)
        ;
    CHECK(i < tokens_.size())
          << utils::join(utils::to_string_ptr(tokens_), "\n");
    return tokens_[i];
}

bool Lexer::read_line() {
    if (source_->get_line(&current_line_)) {
        return true;
    }
    return source_->has_next_file() && source_->open_next_file() &&
           source_->get_line(&current_line_);
};

bool Lexer::parse_line() {
    if (!read_line()) {
        return false;
    }
    int i = 0;
    while (isspace(current_line_[i])) {
        if (current_line_[i] != ' ') {
            context_.add_error(make_unique<Error>(
                  Error::INDENTATION_ONLY_SPACES, source_->get_file_name(),
                  current_line_, source_->get_line_no(), false));
        }
        i++;
    }
    if (i % INDENT_SPACES) {
        std::cout << "line " << line_counter_
                  << ": one indent is always 4 spaces long. Treating " << i
                  << " spaces as " << i / INDENT_SPACES + 1 << "indents";
    }
    int indents = (i + INDENT_SPACES - 1) / INDENT_SPACES;
    for (int j = 0; j < indents; j++) {
        tokens_.push_back(
              new Token(Token::Type::indentation, create_lexing_context()));
    }
    while (i < current_line_.size()) {
        if (isalpha(current_line_[i])) {
            const int start = i;
            while (i < current_line_.size() &&
                   (isalnum(current_line_[i]) || current_line_[i] == '_')) {
                i++;
            }
            string identifier = current_line_.substr(start, i - start);
            if (identifier == "def") {
                tokens_.push_back(
                      new Token(Token::Type::def, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "class") {
                tokens_.push_back(
                      new Token(Token::Type::class_, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "import") {
                tokens_.push_back(
                      new Token(Token::Type::import, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "if") {
                tokens_.push_back(
                      new Token(Token::Type::if_, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "return") {
                tokens_.push_back(
                      new Token(Token::Type::return_, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "extern") {
                tokens_.push_back(
                      new Token(Token::Type::extern_, create_lexing_context()));
                // no space afterwards
            } else if (identifier == "own") {
                tokens_.push_back(
                      new Token(Token::Type::own, create_lexing_context()));
                i++;  // space aftwards
            } else if (identifier == "elif") {
                tokens_.push_back(
                      new Token(Token::Type::elif, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "else") {
                tokens_.push_back(
                      new Token(Token::Type::else_, create_lexing_context()));
                // no space afterwards
            } else if (identifier == "while") {
                tokens_.push_back(
                      new Token(Token::Type::while_, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "mut") {
                tokens_.push_back(
                      new Token(Token::Type::mut, create_lexing_context()));
                i++;  // space afterwards
            } else if (identifier == "and") {
                tokens_.push_back(
                      new Token(Token::Type::and_, create_lexing_context()));
                i++;
            } else if (identifier == "or") {
                tokens_.push_back(
                      new Token(Token::Type::or_, create_lexing_context()));
                i++;
            } else {
                if (isupper(identifier[0])) {
                    tokens_.push_back(new Token(Token::Type::type_identifier,
                                                identifier,
                                                create_lexing_context()));
                } else {
                    tokens_.push_back(new Token(Token::Type::identifier,
                                                identifier,
                                                create_lexing_context()));
                }
            }
        } else if (is_a_number(i)) {
            // Not alpha, but num. Must be a number.
            const int start = i;
            do {
                i++;
            } while (i < current_line_.size() && isdigit(current_line_[i]));
            tokens_.push_back(
                  new Token(std::stoi(current_line_.substr(start, i - start)),
                            create_lexing_context()));
        } else if (current_line_[i] == '\'' || current_line_[i] == '"') {
            const char mark = current_line_[i];
            i++;
            int start = i;
            while (current_line_[i] != mark) {
                i++;
            }
            tokens_.push_back(new Token(Token::Type::string,
                                        current_line_.substr(start, i - start),
                                        create_lexing_context()));
            i++;
        } else {
            if (current_line_[i] == ' ') {
                i++;
            } else {
                if (utils::contains(single_char_symbols_, current_line_[i])) {
                    push_symbol(string(1, current_line_[i]));
                    i++;
                } else if (current_line_[i] == '!' &&
                           i + 1 < current_line_.size() &&
                           current_line_[i + 1] == '=') {
                    push_symbol("!=");
                    i += 2;
                } else if (current_line_[i] == '=') {
                    if (i + 1 < current_line_.size() &&
                        current_line_[i + 1] == '=') {
                        push_symbol("==");
                        i += 2;
                    } else {
                        push_symbol("=");
                        i++;
                    }
                } else {
                    context_.add_error(make_unique<Error>(
                          Error::UNRECOGNIZED_SYMBOL, source_->get_file_name(),
                          current_line_, source_->get_line_no(), false));
                    i++;
                }
            }
        }
    }
    tokens_.push_back(new Token(Token::Type::eol, create_lexing_context()));
    return true;
}

void Lexer::push_symbol(const string& symbol) {
    tokens_.push_back(
          new Token(Token::Type::symbol, symbol, create_lexing_context()));
}

LexingContext Lexer::create_lexing_context() {
    LexingContext context(source_->get_file_name(), current_line_,
                          source_->get_line_no());
    return context;
}

bool Lexer::is_a_number(int index) {
    return isdigit(current_line_[index]) ||
           (current_line_[index] == '-' && index + 1 < current_line_.size() &&
            isdigit(current_line_[index + 1]));
}

bool operator==(const Token& first, const Token& second) {
    return first.type == second.type && first.value == second.value &&
           first.integer == second.integer;
};
}  // namespace schwifty

Answer 1

Aside from the remarks of Frank (which are valid):

C++ remarks

Possible message rot

if (i % INDENT_SPACES) {
    std::cout << "line " << line_counter_
              << ": one indent is always 4 spaces long. Treating " << i
              << " spaces as " << i / INDENT_SPACES + 1 << "indents";
}
int indents = (i + INDENT_SPACES - 1) / INDENT_SPACES;

Here you do the calculations for indents twice, and from experience they tend to get out of sync. Here the fix is straightforward: just swap the lines and use the indents variable when printing.

Don't return const int

There is no point in that (and is not enforceable). Just return int...

Use less dynamic allocations

context_.add_error(make_unique<Error>( /* ... */ ));

This will cost a lost with sources that contain loads of errors, and also adds unecessary allocations. I think for this case you can go with value directly (this was already said by Frank).

On the algorithm

General

From reading the code, it seems your language is not free-form (that is, indentation and new lines matters). I don't know if this is wanted, but it completely disallow tabulations.

On a general note, lexers can be treated as very simple compilers that take a string as input, and output an array of lexemes, which are usually all determined by the value of an enumeration (except identifiers). Since they are just the entry - and you want your language tokens to be easily distinguishable by humans - the lexer "language" should be also simple. This is one of the reason why lexer "languages" are usually regular languages. Important: only the "language" of the lexer is regular, your toy language is probably not regular (but that does not matter, as it is a separate phase of compilation).

The corollary is that to efficiently parse a regular language you need a DFA. You can write it by hand (tedious, but good for learning purposes), or use a tool for that.

More modular code

First, I would separate the lexing of the indentation in its own function:

void parse_indentation()
{
    int i = 0;
    while (isspace(current_line_[i]))
    {
        if (current_line_[i] != ' ')
        {
            context_.add_error(make_unique<Error>(
                  Error::INDENTATION_ONLY_SPACES, source_->get_file_name(),
                  current_line_, source_->get_line_no(), false));
        }
        i++;
    }
    int indents = (i + INDENT_SPACES - 1) / INDENT_SPACES;
    if (i % INDENT_SPACES)
        std::cout << "line " << line_counter_
                  << ": one indent is always 4 spaces long. Treating " << i
                  << " spaces as " << indents << "indents";

    for (int j = 0; j < indents; j++)
        tokens_.push_back(new Token(Token::Type::indentation, create_lexing_context()));
}

By the way, what you did with while (isspace(current_line_[i])) is good: you allow more (i.e., tabs and \r even if they should not appear), so your error reports are better.

Deterministic Finite Automaton

Now, the remaining while loop can be changed in a DFA. Here is a small example for numbers, elif, else, and strings with single quotes:

Obviously, there are links from the K * states to Error for unrecognized characters, but I partially hid them for readability. Once you have an automaton, you try to advance states until you can't (either you reach a final state or you would hit the Error state). What you have before stopping is what you want.

Just repeat that several times, until the whole line is transformed into lexemes.

Misc

Try to avoid heavy tokens. If you can use std::string_view (c++17), do it, because std::string will do dynamic allocations (and that costs a lot !)

Answer 2

Good work!

After a quick first pass, here's the main items I've found, in no particular order. I'm sure there's more to find in there, but these should improve your code a lot:

overuse of explicit

Edit: see comments below, this not not correct in every single scenarios.

explicit is only useful on constructors with a single non-default parameter. adding it to constructors with more arguments is useless.

Weird use of pointers

const Token* peek_token();

Returning by pointer makes no sense here. It's not like you are expecting anyone to store a long-term reference to a token. You should be returning by reference instead.

Do not use raw pointers

std::deque<const Token*> tokens_;

should be

std::deque<std::unique_ptr<const Token>> tokens_;

But it doesn't matter because:

Don't use dynamic memory where unnecessary

std::deque<std::unique_ptr<const Token>> tokens_;

should actually be:

std::deque<const Token> tokens_;

STL containers already store objects in the heap, and do a good job at managing them unless they have a sizeof() that's ridiculusly massive (which would be super suspicious in the first place). You are wasting a lot more performance on hitting the memory system like a madman and inferior cache performance than you are gaining from marginally faster container resizing.

Speaking of resizing...

Deque is for fast front insertion, not fast resizing.

you do not push_front() on tokens_, so you shouldn't be using a deque here. Once again, the marginal increase in container resizing is almost certainly not worth the decreased cache performance. std::vector<> has an amortized push_back() time of O(1), it'll be fine.

InputSource design is dodgy

It's hard to tell because InputSource seems to be designed to accomodate code that is not being shown here, but in general any "inherit to extend" design is suspect.

Really, as far as I can tell from here, your lexer should probably just operate on a std::istream, and let the calling code handle concatenating token streams from different files. This would lessen the responsability on the lexer, and let it do just on thing: Lex.

Big ugly if else if block:

  if (identifier == "def") {
    tokens_.push_back(
      new Token(Token::Type::def, create_lexing_context()));
    i++;  // space afterwards
  } else if (identifier == "class") {
    tokens_.push_back(
      new Token(Token::Type::class_, create_lexing_context()));
    i++;  // space afterwards
  } else if (identifier == "import") {
...

Could simply be:

std::unordered_map<std::string, Token::Type> tokens_;
...
auto found_token = tokens_.find(identifier);
if(found_token != tokens_.end()) {
  tokens_.push_back(
      new Token(found_token->second, create_lexing_context()));
    i++;  // space afterwards
}

Answer 3

If I can make a recommendation, while it is virtuous to write your own parser, there are parser-generators for implementing new languages that help you focus on the end application instead of a great deal of the implementation details. I have used ANTLR successfully. They have bindings for C++, which may just suit your needs. If you choose this route, I would also recommend the Antlr Reference Manual from Pragmatic Programmers. In a couple of days you should be able to implement what you're looking for.

Answer 4

Don't make member fields const. This creates issues when you go and copy an object. Just drop the const on the fields and instead pass const ref around if something needs a view.

You make a very strict statement about indentation (spaces only and 4 at a time) and whitespace. Instead you can follow python's scheme: if new line is longer then prefix must be exactly equal to the previous line's indentation (push current to stack). If shorter then look backwards in the indentation stack until you find a match and pop until that point. Number of indentation tokens is equal to the size of the stack.

You don't have any way to express escaped characters in your string literals.

Is would also consider adding offsets in the line for each token. Having error into down to the proper token is much easier for the user than only the line. especially when they go for obtuse one-liners.

Answer 5

Use less dynamic allocation use maps to store tokens OtherWise very good code