Tokenizer for my programming language

Question

Here's my attempt at porting the Lua codebase for my programming language to C++(11). This is just the first step, the tokenizer, and I wanted to remove all the bad performance / practices / code before passing to the next steps.

I'm also still learning C++ as I go through this experience, so I wanted to get it reviewed to have a feedback on how I am going and to learn more.

Here's a formal definition of what a token is in my programming language in a syntax I hope looks like EBNF:

token ::= symbol | string | number | name;

symbol ::= '{' | '}' | '[' | ']' | '(' | ')' | '.' | ',' | ';' | ':' | '$' | '?' | '!' | '#' | '_' | '\'';

string ::= '"' {(any_character | string_escape)} '"';

string_escape ::= c_escape | ('\\' digit [digit] [digit]);

number ::= [('+' | '-')] {digit} ('.' [digit] {digit});

digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

name ::= name_char {(name_char | digit)};

name_char ::= //all printable characters which aren't a symbol, a digit or " and ~

A single line comment starts with a ~ and ends with a new line character. A block comment instead starts with ~{ and ends with ~}. Each opening bracket must have a matching closing bracket (they can be nested): an an example, a string like ~{ ~{ ~{ ~} ~{ ~{ ~} ~} won't be accepted because there are some unmatched opening brackets.

Strings aren't single-line: they can span multiple lines without the need to escape the newline with \ like in most languages.

But here's my actual code:

Path/include/error.hpp

#ifndef ERROR_HPP_INCLUDED
#define ERROR_HPP_INCLUDED

#include <string>
#include <sstream>

namespace patch {
    template <typename T>
    std::string to_string(const T &n) {
        std::stringstream stm;
        stm << n;
        return stm.str();
    }
}

class Error {
    public:
        std::string message;

        Error(std::string);
};

#endif//ERROR_HPP_INCLUDED

Path/src/error.cpp

#include "../include/error.hpp"

#include <string>

Error::Error(std::string new_message):
    message(new_message)
{}

Path/include/types.hpp

#ifndef TYPES_HPP_INCLUDED
#define TYPES_HPP_INCLUDED

#include <string>

enum token_type { //not sure about how I should name this thing
    none,
    symbol,
    number,
    name,
    string
};

class Token {
    public:
        void* value = nullptr;
        token_type type = none;
        int line;

        Token() = default;
        Token(void*, token_type, int);
        ~Token();
};

std::string stringof_value(Token*);
std::string stringof_type(Token*);

#endif//TYPES_H_INCLUDED

Path/src/types.cpp

#include "../include/types.hpp"
#include <string>
#include "../include/error.hpp"

Token::Token(void* new_value, token_type new_type, int new_line):
    value(new_value), type(new_type), line(new_line)
    {}

Token::~Token() {
    if (!value) {
        switch (type) {
            case number:
                delete (double*) value;
                break;
            default:
                delete (std::string*) value;
        }
    }
}

std::string stringof_value(Token* t) {
    void* value = t->value;
    switch (t->type) {
        case number:
            return patch::to_string(*(double *) value);
        default:
            return *(std::string*) value;
    }
}

std::string stringof_type(Token* t) {
    switch (t->type) {
        case symbol:
            return std::string("symbol");
        case number:
            return std::string("number");
        case name:
            return std::string("name");
        case string:
            return std::string("string");
        case none:
            //(no Token should get here)
            throw t->type;
    }
}

Path/include/syntax.hpp

#ifndef SYNTAX_HPP_INCLUDED
#define SYNTAX_HPP_INCLUDED

#include "error.hpp"

enum syntax_subtype {
    escape_sequence,
    decimal_escape_sequence,
    unfinished_obj
};

//escape_sequence
template <syntax_subtype>
Error SyntaxError(char, int);

//decimal_escape_sequence
template <syntax_subtype>
Error SyntaxError(int, int);

//unfinished_obj
template <syntax_subtype>
Error SyntaxError(const char*, int);

#endif//SYNTAX_HPP_INCLUDED

Path/src/syntax.cpp

#include "../include/error.hpp"
#include "../include/syntax.hpp"
#include <string>

template <>
Error SyntaxError<escape_sequence>(char c, int line) {
    return Error(
        std::string("SyntaxError: invalid escape sequence '\\") + patch::to_string(c) + "' (at line " + patch::to_string(line) + ")."
    );
}

template <>
Error SyntaxError<decimal_escape_sequence>(int code, int line) {
    return Error(
        std::string("SyntaxError: decimal escape sequence too large (") + patch::to_string(code) + " used at line " + patch::to_string(line) + ")."
    );
}

template <>
Error SyntaxError<unfinished_obj>(const char* type, int line) {
    return Error(
        std::string("SyntaxError: unfinished ") + type + "(starting at line " + patch::to_string(line) + " until End Of File)."
    );
}

Path/include/lexer.hpp

#ifndef LEXER_HPP_INCLUDED
#define LEXER_HPP_INCLUDED

#include <list>
#include "types.hpp"
#include <string>

std::list<Token*> lexer(std::string);

#endif

Path/src/lexer.cpp

#include "../include/lexer.hpp"
#include <list>
#include "../include/types.hpp"
#include <string>
#include "../include/syntax.hpp"
#include <cstdlib>

bool is_symbol(char x) {
    switch(x) {
        case '{':
        case '}':
        case '[':
        case ']':
        case '(':
        case ')':
        case '.':
        case ',':
        case ';':
        case ':':
        case '$':
        case '?':
        case '!':
        case '#':
        case '_':
        case '~':
        case '"':
        case '\'':
            return true;
        default:
            return false;
    }
}

char escape(char seq, int line) {
    switch (seq) {
        case '"': return '"';
        case '\\': return '\\';
        case '0': return '\0';
        case 'a': return '\a';
        case 'b': return '\b';
        case 'f': return '\f';
        case 'n': return '\n';
        case 'r': return '\r';
        case 't': return '\t';
        case 'v': return '\v';
        default:
                throw SyntaxError<escape_sequence>(seq, line);
    }
}

std::list<Token*> lexer(std::string source) {
    std::list<Token*> tokens;

    int line = 1;

    const char* i = source.c_str();
    char end = '\0';

    auto next = [&i, &line] () -> void {
        if (*(++i) == '\n') {
            ++line;
        }
    };

    //these lambda functions are just here to keep organizated the main loop, but it wouldn't be difficult to manually inline them within the loop if necessary

    //builds a new Token of type symbol, assumes first character is a valid symbol
    auto buildsymbol = [&i, &line, &next] () -> Token* {
        std::string* symbolstr = new std::string(1, *i);
        Token* new_symbol = new Token((void*) symbolstr, symbol, line);

        next();

        return new_symbol;
    };

    //builds a new Token of type number, assumes first character is either +, -, ., or a digit
    auto buildnumber = [&line, &i] () -> Token* {
        Token* new_number = new Token(nullptr, number, line);

        char* after_number = nullptr;
        double* value = new double(std::strtod(i, &after_number));

        if (*value == 0.0 && i == after_number) {
            delete value;
            delete new_number;
            return nullptr;
        }

        new_number->value = (void*) value;
        i = after_number;

        return new_number;
    };

    //builds a new Token of type name, assumes the first character is printable but not a digit or symbol
    auto buildname = [&line, &i, &next, &end] () -> Token* {
        Token* new_name = new Token(nullptr, name, line);
        std::string* value = new std::string("");

        while (*i != end) {
            if (isspace(*i) || is_symbol(*i)) {
                break;
            }
            *value += *i;
            next();
        }

        new_name->value = (void*) value;
        return new_name;
    };

    //builds a new Token of type string, assumes first character is the opening "
    auto buildstring = [&line, &next, &i, &end] () -> Token* {
        Token* new_string = new Token(nullptr, string, line);
        std::string* value = new std::string("");

        next();

        bool finished = false;

        while (*i != end) {
            char to_push = *i;

            if (to_push == '\\') {
                next();
                if (!isdigit(*i)) {
                     try {
                         *value += escape(*i, line);
                     }
                     catch (Error err) {
                         delete value;
                         delete new_string;
                         throw;
                     }
                     next();
                 }

                 else {
                     std::string digits = "";
                     for (int d = 0; *i != end && d < 3 && isdigit(*i); d++) {
                         digits += *i;
                         next();
                     }
                     int code = atoi(digits.c_str());
                     if (code > 255) {
                         delete new_string;
                         delete value;
                         throw SyntaxError<decimal_escape_sequence>(code, line);
                     }
                     *value += (char) code;
                     if (*i == '"') {
                         finished = true;
                         next();
                         break;
                     }
                }
            }

            else {
                *value += to_push;
                next();
                if (*i == '"') {
                     finished = true;
                     next();
                     break;
                }

            }
        }
        if (!finished) {
            delete value;
            Error err = SyntaxError<unfinished_obj>("string", new_string->line);
            delete new_string;
            throw err;
        }
        new_string->value = (void*) value;
        return new_string;
    };

    //skips all whitespace characters (\n, \t, ...), assumes first character is a whitespace character
    auto skipspaces = [&i, &end, &next] () -> void {
        do {
            next();
        } while (*i != end && !isprint(*i));
    };

    //skips a comment (single or multi line), assumes first character is ~
    auto skipcomment = [&next, &i, &end, &line] () -> void {
        next();

        //single line comment
        if (*i != '{') {
            while (*i != end) {
                if (*i == '\n') {
                     next();
                     break;
                }
                next();
            }
        }

        //multi line comment
        else {
            int line_start = line;
            int nest = 1;
            while (*i != end) {
                if (*i == '~') {
                     next();
                     if (*i == '{') {
                         ++nest;
                     }
                     else if (*i == '}') {
                         --nest;
                         if (!nest) {
                             next();
                             break;
                         }
                     }
                }
                next();
            }
            if (nest) {
                throw SyntaxError<unfinished_obj>("block comment", line_start);
            }
        }
    };

    try {
        //main loop
        while (*i != end) {
            if (*i == '"') {
                tokens.push_back(buildstring());
            }
            else if (*i == '~') {
                skipcomment();
            }
            else if (isspace(*i)) {
                skipspaces();
            }
            else if (is_symbol(*i)) {
                 tokens.push_back(buildsymbol());
            }
            else {
                Token* try_number = buildnumber();
                if (try_number) {
                     tokens.push_back(try_number);
                }
                else {
                     tokens.push_back(buildname());
                }
            }
        }
    }
    catch (Error err) {
        for (std::list<Token*>::iterator i = tokens.begin(), e = tokens.end(); i != e; ++i) {
            delete *i;
        }
        throw;
    }
    return tokens;
}

I won't include main.cpp here because it's just a test which prompts the user for input, tokenizes it and outputs the type and value of the tokens it got. Nothing to review really.

Answer 1

Issues with EBNF

string ::= '"' {(any_character | string_escape)} '"';

Here for "any_character" you probably meant any character except " but that is not made explicit.

number ::= [('+' | '-')] {digit} ('.' [digit] {digit});
                         ^^^A^^^  ^^^^^^^B^^^^^^^^^^^^

For A: This means zero or more digits. Thats fine.
For B: Thats zero or one digit followed by zero or more digits.

So the following is a valid number +.

I believe you meant:

number ::= ['+' | '-'] {digit} ['.' digit {digit}];

Because this still allows + and - to be parsed as numbers. You really need to break this up into a couple of expressions to fully parse numbers.

number        ::= ['+' | '-'] NumberPart

NumberPart    ::= NumberInteger | NumberFloat
NumberInteger ::= digit {digit}
NumberFloat   ::= {digit} '.' digit {digit};

You can do it in one line if you really must. But I find it easier to read when you split it up a bit. Note: This is still not as comprehensive as those done by the C language as a decimal point must be followed by a digit but its pretty good.

An equivalent FLEX file

%x BLOCKCOMMENT
%x LINECOMMENT

/* You probably meant any character except " */
AnyStringCharacter          [^"]
Digit                       [0-9]
CEscape                     \\.

StringEscape                {CEscape}|\\{Digit}{Digit}{Digit}
Character                   {AnyStringCharacter}|{StringEscape}
LiteralString               "{Character}*"

Sign                        [+-]
NumberInteger               {Digit}+
NumberFloat                 {Digit}*\.{Digit}+
NumberPart                  {NumberInteger}|{NumberFloat}
LiteralNumber               {Sign}?{NumberPart}

IdentifierChar_First        [^]{}().,;:$?!#_\\[0123456789~"]
IdentifierChar              {IdentifierChar_First}|{Digit}
Identifier                  {IdentifierChar_First}{IdentifierChar}*

LineComment                 [^\n]*
BlockComment                [^~\n]*
EndOfLine                   \n

%%

<INITIAL>\~                     {BEGIN(LINECOMMENT);}
<INITIAL>\~\{                   {BEGIN(BLOCKCOMMENT);}

<BLOCKCOMMENT>\~\}              {BEGIN(INITIAL);}
<BLOCKCOMMENT>{EndOfLine}       {/*++line;*/}
<LINECOMMENT>{EndOfLine}        {BEGIN(INITIAL);/*++line;*/}

<BLOCKCOMMENT>{BlockComment}    {/* Ignore Comment */}
<BLOCKCOMMENT>\~                {/* Ignore ~ not followed by { */}
<LINECOMMENT>{LineComment}      {/* Ignore Comment */}

\{                          {return '{';}
\}                          {return '}';}
\[                          {return '[';}
\]                          {return ']';}
\(                          {return '(';}
\)                          {return ')';}
\.                          {return '.';}
\,                          {return ',';}
\;                          {return ';';}
\:                          {return ':';}
\$                          {return '$';}
\?                          {return '?';}
\!                          {return '!';}
\#                          {return '#';}
\_                          {return '_';}
\\                          {return '\\';}

{LiteralString}             {return yy::lex::literal_string;}
{LiteralNumber}             {return yy::lex::literal_number;}
{Identifier}                {return yy::lex::identifier;}

.                           {/* ERROR */}

That's 67 lines compared to the nearly 500 for writing it yourself. And I am being generous as I could collapse all the symbols into a single line. This code is basically readable BNF so any computer scientist should be able to maintain it.

Code Review

There are so many of these lying around. You could have picked up a nearly standard one from boost boost::lexical_cast<>

namespace patch {
    template <typename T>
    std::string to_string(const T &n) {
        std::stringstream stm;
        stm << n;
        return stm.str();
    }
}

If this is an exception you should probably enhirit from one of the standard exceptions (like std::runtime_error).

class Error {
    public:
        std::string message;

        Error(std::string);  // Pass by const reference.
                             // If it needs building from a literal it works.
                             // But if already a string it will prevent the copy.
};

Seriously. That could have been inlined in the header file.

Error::Error(std::string new_message):
    message(new_message)
{}

Rather than use a void* to store your data use a union.

class Token {
    public:
        void* value = nullptr;
};

It expresses intent more clearly and also will remove all the casting issues that you are going to have in the rest of your code.

Never use C casts. Always use a C++ cast. They are easier to spot in the code and express intent much better.

                delete (double*) value;
                delete (std::string*) value;

Being easy to spot is a good thing. Because I want to check more closely the dangerous casts but ignore the simpler casts.