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.

  • 4
    That's pretty cool! Do you know about lexer/parser generators like ANTLR? I believe ANTLR4 has a C++ target - you could have a formal grammar generate a lexer+parser for you, and dive straight into implementing parse tree visitors to evaluate expressions and implement your interpreter - if this tokenizer is part of something much bigger, you could be reinventing-the-wheel a bit here. – Mathieu Guindon Sep 18 '16 at 17:57
  • 1
    @Mat's Mug yes, I definitely know about them (ANTLR is new to me but I heard about yacc, flex, bison and so on), but I think it's a bit of an overkill to use them where I could just code it like above. It was also a good learning experience to do it on my own so why not? – user6245072 Sep 18 '16 at 18:29
  • 2
    @user6245072: I think you have the overkill the wrong way around. Why reinvent the wheel (that's overkill). When you can reuse an existing wheel and get the job done in about 1/10 the space and complexity. I will give you its a good learning experience. But in real life you should use the available tools. – Martin York Sep 18 '16 at 23:28
  • I now have to confess it. Using a third party tool is difficult for me because I'm programming from Android. Yes that's right. Using a Linux emulator. And so I have access to flex and bison but it's not really easy for me to use them. I will try maybe. – user6245072 Sep 19 '16 at 5:00
  • 1
    @pacmaninbw well, it is not meant to work on Android only, it's just that I can only code from my Android. – user6245072 Sep 19 '16 at 15:00
up vote 5 down vote accepted

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.

  • Wow I never expected someone to review the EBNF part too, but I guess you took the issue of reinventing the wheel to heart. patch::to_string is a substition for std::to_string, which seems to be not found. For the last part, what do you mean by "C++ cast"? You mean casting the union to one of the two types? Also will I still have to use a pointer to the union? – user6245072 Sep 19 '16 at 5:10
  • C++ has four cast operators. Each has a specific job. The C cast operator is a sledge hammer that just says obey me without any validation. C++ casts are: reinterpret_cast<>() const_cast<>() static_cast<>() and dynamic_cast<>() – Martin York Sep 19 '16 at 7:12
  • No you will not have to use pointers in the union (not for the double anyway). – Martin York Sep 19 '16 at 7:15
  • But I have to dinamically allocate the values in the lambda functions or they will be deleted, right? – user6245072 Sep 19 '16 at 8:14
  • @user6245072 This is code. There is no "have to" you can make the code do what you want. What you have to consider is lifetime. Because strings require an unknown amount of memory they need to be dynamically allocated. But floating point values have a fixed size and can thus use the space in the object without dynamically allocating. – Martin York Sep 19 '16 at 15:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.