Overhauled tokenizer for markargs

Question

In the previous post I've started writing a tokenizer for my imaginary programming language (which I decided to name markargs; trivia at the end of the post).

---

Problem definition:

Read the line and divide input into groups and tag them:

• +, -, = -> operators

• identifiers (underscores, non leading numbers are allowed) -> names. Examples of valid names: variable, variable1, first_variable.

• Any integer values -> numbers

---

Since usually they are streamed, the code will try to imitate a stream, especially idiomatic while (stream >> variable). It turned out to be weird to implement, since it will need a separate bit for state, whereas I thought I could just cast the stream to bool and return it. The problem is that for expression a=b+5, 5 will not be included in the loop, because when it is read, the stream is already exhausted.

I've also added iterator, so that on semantics analysis I could write something like that:

template <typename InputIterator>
std::pair<symbol_table, abstract_syntax_tree> analyze(InputIterator first, InputIterator last)

---

Code:

main.cpp:

#include <iostream>
#include <vector>
#include <stdexcept>
#include <sstream>
#include <algorithm>

#include "tokenizer.hpp"

std::ostream& operator<<(std::ostream& os, const std::vector<markargs::token>& tokens)
{
    std::string initial_expr;
    for (const markargs::token& t : tokens)
    {
        std::string type_str;
        switch (t.tp)
        {
        case markargs::token::token_type::NAME:
            type_str = "name";
            break;
        case markargs::token::token_type::NUMBER:
            type_str = "number";
            break;
        case markargs::token::token_type::OP:
            type_str = "operator";
            break;
        default:
            throw std::logic_error("unknown token encountered");
        }
        os << "token type: " << type_str << '\n' 
            << "payload: " << t.payload << "\n--------------------\n";
        initial_expr += t.payload;
    }
    std::cout << "initial expression: " << initial_expr << '\n';

    return os;
}

void fixed_tokencount_check()
{
    std::istringstream ss("a = b + 5");
    std::cout << ss.str() << '\n';
    markargs::tokenizer tokenizer(ss);
    std::vector<markargs::token> tokens(5);
    for (auto& token : tokens)
    {
        tokenizer >> token;
    }

    std::vector<markargs::token> correct_answer{
            markargs::token{markargs::token::token_type::NAME, "a"},
            markargs::token{markargs::token::token_type::OP, "="},
            markargs::token{markargs::token::token_type::NAME, "b"},
            markargs::token{markargs::token::token_type::OP, "+"},
            markargs::token{markargs::token::token_type::NUMBER, "5"}
    };
    std::cout << tokens;

    if (tokens.size() != correct_answer.size() || !std::equal(tokens.begin(), tokens.end(), correct_answer.begin()))
    {
        throw std::logic_error("tokenizer doesn't work");
    }
}

void read_tilend_check()
{
    std::string expr_str("a = b + 5");
    std::istringstream ss1(expr_str);
    std::istringstream ss2(expr_str);
    std::cout << ss1.str() << '\n';
    markargs::tokenizer tokenizer(ss1);
    markargs::tokenizer tokenizer_copy(ss2);

    //exhaust tokenizer
    std::vector<markargs::token> tokenizer_result;
    markargs::token tk;
    while (tokenizer >> tk)
    {
        tokenizer_result.push_back(tk);
    }

    markargs::tokenizer_iterator first(tokenizer_copy);
    markargs::tokenizer_iterator last;
    std::vector<markargs::token> tokenizer_it_result{first, last};


    std::vector<markargs::token> correct_answer{
            markargs::token{markargs::token::token_type::NAME, "a"},
            markargs::token{markargs::token::token_type::OP, "="},
            markargs::token{markargs::token::token_type::NAME, "b"},
            markargs::token{markargs::token::token_type::OP, "+"},
            markargs::token{markargs::token::token_type::NUMBER, "5"}
    };
    std::cout << "tokenizer result:\n" << tokenizer_result << '\n';
    std::cout << "tokenizer_iterator result:\n" << tokenizer_it_result << '\n';

    if (tokenizer_result.size() != correct_answer.size() ||
            !std::equal(tokenizer_result.begin(), tokenizer_result.end(), correct_answer.begin()))
    {
        throw std::logic_error("tokenizer doesn't work");
    }

    if (tokenizer_it_result.size() != correct_answer.size() ||
        !std::equal(tokenizer_it_result.begin(), tokenizer_it_result.end(), correct_answer.begin()))
    {
        throw std::logic_error("tokenizer_iterator doesn't work");
    }
}

int main()
{
    fixed_tokencount_check();
    read_tilend_check();
}

token.hpp:

#ifndef COMPILER_TOKEN_HPP
#define COMPILER_TOKEN_HPP

#include <string>

namespace markargs
{

    struct token
    {
        enum class token_type
        {
            NAME,
            NUMBER,
            OP,
            NONE //for debug purposes
        };

        token_type tp;
        std::string payload;

        token() :
                tp(token_type::NONE)
        {}

        token(token_type tp_, const std::string& payload_) :
                tp(tp_),
                payload(payload_)
        {}

        bool operator!()
        {
            return tp == token_type::NONE;
        }
    };

    inline bool operator==(const token& lhs, const token& rhs)
    {
        return lhs.tp == rhs.tp && lhs.payload == rhs.payload;
    }

    inline bool operator!=(const token& lhs, const token& rhs)
    {
        return !(lhs == rhs);
    }
}

#endif

tokenizer.hpp:

#ifndef COMPILER_TOKENIZER_HPP
#define COMPILER_TOKENIZER_HPP

#include <iostream>
#include <iterator>

#include "token.hpp"

namespace markargs
{
    class tokenizer
    {
        std::istream* stream;
        bool state;
    public:
        class tokenizer_iterator
        {
            token tk;
            tokenizer* tknizer;
        public:
            using iterator_category = std::input_iterator_tag;
            using value_type = token;
            using reference = value_type&;
            using pointer = value_type*;
            using difference_type = void; //doesn't make much sense

            tokenizer_iterator();

            explicit tokenizer_iterator(tokenizer& tkzer);

            token& operator*();

            tokenizer_iterator& operator++();
            tokenizer_iterator operator++(int);

            friend bool operator!=(const tokenizer_iterator& lhs,
                                   const tokenizer_iterator& rhs);
        };

        explicit tokenizer(std::istream& is) noexcept;

        //simultaneous access to multiple tokenizers
        //will have *very* surprising behavior
        tokenizer(const tokenizer& other) = delete;

        tokenizer& operator=(const tokenizer& other) = delete;

        tokenizer(tokenizer&& other) noexcept;

        tokenizer& operator=(tokenizer&& other) = delete;

        operator bool();

        friend tokenizer& operator>>(tokenizer&, token& tk);

    private:
        token read_identifier();

        token read_number();

        token read_operator();

        bool is_operator(char c) const noexcept;
    };

    using tokenizer_iterator = tokenizer::tokenizer_iterator;
}

#endif

tokenizer.cpp:

#include "tokenizer.hpp"
#include <memory>
#include <cctype>

namespace markargs
{
    tokenizer::tokenizer(std::istream& is) noexcept:
            stream(std::addressof(is))
    {}

    tokenizer::tokenizer(tokenizer&& other) noexcept:
            stream(other.stream)
    {
        other.stream = nullptr;
    }

    token tokenizer::read_identifier()
    {
        std::string current_identifier;
        char next_char;
        //no need to check, since this function is called from gigantic pile of ifs which means next_char is a letter
        *stream >> next_char;
        current_identifier += next_char;

        //numbers in identifiers are allowed if they are not leading
        while (*stream >> next_char && (std::isalnum((unsigned char) next_char) || next_char == '_'))
        {
            current_identifier += next_char;
        }

        stream->unget(); //sets badbit if eof, so no check for eof

        return token{token::token_type::NAME, current_identifier};
    }

    token tokenizer::read_number()
    {
        std::string current_number;
        char next_char = 0;
        while (*stream >> next_char && std::isdigit((unsigned char) next_char))
        {
            current_number += next_char;
        }

        stream->unget(); //sets badbit if eof, so no check for eof

        return token{token::token_type::NUMBER, current_number};
    }

    token tokenizer::read_operator()
    {
        char op;
        *stream >> op;
        return token{token::token_type::OP, std::string{op}};
    }

    bool tokenizer::is_operator(char c) const noexcept
    {
        return c == '+' || c == '-' || c == '=';
    }

    tokenizer::operator bool()
    {
        return state;
    }

    tokenizer& operator>>(tokenizer& t, token& tk)
    {
        auto& stream = *t.stream;
        char next_char;

        if (!stream)
        {
            t.state = false;
            return t;
        }

        //discard spaces
        do
        {
            stream >> next_char;
        } while (std::isspace((unsigned char) next_char));

        if (!stream)
        {
            t.state = false;
            return t;
        }

        stream.unget();

        if (std::isalpha((unsigned char) next_char) || next_char == '_')
        {
            tk = t.read_identifier();
        }
        else if (std::isdigit((unsigned char) next_char))
        {
            tk = t.read_number();
        }
        else if (t.is_operator(next_char))
        {
            tk = t.read_operator();
        }
        else
        {
            throw std::invalid_argument("character outside of character set encountered");
        }

        return t;
    }

    tokenizer::tokenizer_iterator::tokenizer_iterator():
            tknizer(nullptr)
    {}

    tokenizer::tokenizer_iterator::tokenizer_iterator(tokenizer& tkzer):
            tknizer(&tkzer)
    {
        *tknizer >> tk;
    }

    tokenizer::tokenizer_iterator& tokenizer::tokenizer_iterator::operator++()
    {
        tk = token{};
        *tknizer >> tk;
        if (!tk)
        {
            tknizer = nullptr;
        }
        return *this;
    }

    tokenizer::tokenizer_iterator tokenizer::tokenizer_iterator::operator++(int)
    {
        auto copy = *this;
        ++*this;
        return copy;
    }

    token& tokenizer::tokenizer_iterator::operator*()
    {
        return tk;
    }

    bool operator!=(const tokenizer_iterator& lhs, const tokenizer_iterator& rhs)
    {
        return lhs.tknizer != rhs.tknizer; //returning false doesn't mean they're equal!
    }
}

CMakeLists.txt:

cmake_minimum_required(VERSION 3.2)
project(compiler)

set(CMAKE_CXX_STANDARD 14)

add_executable(tokenizer
        src/tokenizer/main.cpp
        src/tokenizer/tokenizer.hpp
        src/tokenizer/token.hpp
        src/tokenizer/syntax_error.hpp
        src/tokenizer/tokenizer.cpp)

---

Github repo.

Bash script to clone & build:

git clone https://github.com/simmplecoder/markargs
cd markargs
git checkout 0e294d8cfb17076fa43c5e971bbdf87997166443
mkdir build 
cd build
cmake ..
make

---

I think code got better compared to the previous post, although probably lines of code increased. The current way makes it harder to make errors compared to the other case. Also, current code does not have semantic analysis yet, so it has less functionality than in the previous post. Though I'm much more convinced that it works without bugs now.

---

Concerns:

• Architecture. Did I model things correctly?

• Use of std::istream. The iostream part of standard library is mostly unexplored for me. Did I use everything in the most efficient way possible?

• Long namespace name. Does a shorter one come to mind?

• Anything else.

---

Trivia:

The purpose of the programming language is to simplify typing and evaluating long numerical expressions, encountered in physics and other areas where expressions get really long and unreadable pretty quick. The language will allow defining new variables on the fly and define them later, recursively until all symbols are defined. Due to the nature, I called it markargs, e.g. mark the arguments and worry about them later.

Answer 1

First, thanks for posting complete code with a test harness. It makes it much easier to understand how the code is being used and the expected results. Here are some things that may help you improve your code.

Fix the bug

You will probably be surprised to hear that on my machine, the program aborts with this message:

terminate called after throwing an instance of 'std::logic_error'
  what():  tokenizer doesn't work
Aborted (core dumped)

This was ultimately caused by a subtle error in the constructor. Specifically, the state variable is not initialized. I'd recommend changing the first constructor to this:

tokenizer::tokenizer(std::istream& is) :
        stream{std::addressof(is)},
        state{true}
{}

Note here that I've used the C++ uniform initialization syntax. This reduces the probability of creating surprising errors.

Consider eliminating noexcept

Be clear about what the application of noexcept does in C++. In particular, let's look at this:

bool tokenizer::is_operator(char c) const noexcept
{
    return c == '+' || c == '-' || c == '=';
}

It's pretty trivial for the compiler to figure out that this function does not throw. It's not at all clear to me what advantage you expect to see by marking this particular function as noexcept.

For a longer discussion of this see Andrzej Krzemieński's helpful blog post on that topic. It's long and technical but well worth a read.

Simplify the interface

The tokenizer class currently includes this member function:

tokenizer::tokenizer_iterator tokenizer::tokenizer_iterator::operator++(int)
{
    auto copy = *this;
    ++*this;
    return copy;
}

Few iterators in the standard library include this operator and none of the standard algorithms (nor your program) require it. I'd advocate omitting it to both simplify the interface and encourage the use of the more efficient prefix ++ operator.

Simplify tests

The test code contains a few if statements of this form:

if (tokenizer_result.size() != correct_answer.size() ||
        !std::equal(tokenizer_result.begin(), tokenizer_result.end(), correct_answer.begin())) { /* ... */ }

However, it's not really necessary to separately compare the sizes because std::equal will return false if the sizes are different. It's not going to make any huge difference in how the code runs, but I think it makes the code easier to read and understand.

Prefer class to struct

I would advocate changing the token struct into an actual class with private data members with accessors/manipulators as needed.

Here's a quick rewrite of your token class declaration which omits the namespace and some of the error checking, but conveys the point:

class token {
public:
    enum token_type {
        NAME, NUMBER, OP, NONE 
    };
    token(token_type tp_=token_type::NONE, const std::string& payload_="");
    friend std::ostream &operator<<(std::ostream &out, const token &tk);
    friend std::istream &operator>>(std::istream &in, token &tk);

private:
    static token_type classify(char ch);

    token_type tp;
    std::string payload;
};

The implementations of the constructor and the classify function are simple:

token::token(token::token_type tp_, const std::string& payload_) :
    tp{tp_},
    payload{payload_}
{}

token::token_type token::classify(char ch) {
    if (std::isdigit(ch)) {
        return NUMBER;
    } else if (std::isalnum(ch) || ch == '_') {
        return NAME;
    } else if (ch == '+' || ch == '-' || ch == '=') {
        return OP;
    }
    return NONE;
}

The overload for the stream inserter is simple. You can modify it to suit your tastes, of course, but I chose to use something that looks like JSON data:

std::ostream &operator<<(std::ostream &out, const token &tk) {
    static const std::string optype[] { "name", "number", "operator", "!!NONE!!" };
    return out << "{" << optype[tk.tp] << " : " << tk.payload << "}";
}

Because I elected to use the simple subscript with the type as an operator, I changed from an enum class to a simple enum. Arguably, your original enum class is probably a better choice.

Implement a state machine for reading

I'd suggest instead implementing a state machine parser within the token class rather than as a separate class. In particular, I'd overload istream& operator>> for this purpose. Here's a way to do that using the rewrite shown above:

std::istream &operator>>(std::istream &in, token &tk) {
    static enum { WHITESPACE, INNAME, INNUM, DONE } state;
    token temp{};
    std::swap(tk, temp);
    using tt = token::token_type;
    for (state = WHITESPACE; in && state != DONE; ) {
        char ch = in.peek();
        switch (tk.classify(ch)) {
            case tt::NAME:
                switch (state) {
                    case WHITESPACE:
                        state = INNAME;
                        tk.tp = tt::NAME;
                        // deliberately fall through
                    case INNAME:
                        tk.payload.push_back(ch);
                        in.get();
                        break;
                    default:
                        state = DONE;
                        break;
                };
                break;

            case tt::NUMBER:
                switch (state) {
                    case WHITESPACE:
                        state = INNUM;
                        tk.tp = tt::NUMBER;
                        // deliberately fall through
                    case INNUM:
                    case INNAME:
                        tk.payload.push_back(ch);
                        in.get();
                        break;
                    default:
                        state = DONE;
                        break;
                }
                break;                            

                case tt::OP:
                    switch (state) {
                        case WHITESPACE:
                            state = DONE;
                            tk.tp = tt::OP;
                            tk.payload.push_back(ch);
                            in.get();
                            break;
                        default:
                            state = DONE;
                            break;
                    }
                    break;                            

                case tt::NONE: 
                    switch (state) {
                        case WHITESPACE:
                            in.get();
                            break;
                        default:
                            state = DONE;
                            break;
                    }
                    break;                            
        }
    }
    return in;
}

That's a bit long, but it's not really complex. Also note that we use peek() instead of unget(). We only fetch the next character using get() if it's part of the current token. Using this method, we can write code like this:

int main() {
    std::istringstream ss{"a = b + 5"};
    token tk{};
    while (ss >> tk) {
        std::cout << tk;
    }
    std::cout << '\n';
}

Output:

{name : a}{operator : =}{name : b}{operator : +}{number : 5}

Use standard iterators

Even better, because we now have an inserter and extractor, we now get an iterator "for free". Because you want to ignore whitespace anyway, you could use std::istream_iterator and write code like this:

int main() {
    std::istringstream ss{"a = b + 5"};
    std::vector<token> first{
        std::istream_iterator<token>(ss),
        std::istream_iterator<token>() 
    };

    for (const auto &t : first) {
        std::cout << t;
    }
    std::cout << '\n';
}

Output:

{name : a}{operator : =}{name : b}{operator : +}{number : 5}

Testing

I implemented a test harness to verify things were working as expected. It uses an array of an anonymous structures with the function call operator defined to make the testing extremely simple. Note that it also requires an implementation of bool operator==(const token &, const token&) which is trivial and not shown.

#include "tok2.h"
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <sstream>
#include <algorithm>

int main() {
    static const struct {
        std::string input;
        std::vector<token> tokens;
        void operator()() const { 
            std::istringstream ss{input};
            std::vector<token> gen{
                std::istream_iterator<token>(ss),
                std::istream_iterator<token>() 
            };
            std::cout << (gen == tokens ? "OK  " : "BAD ") 
                << "\"" << input << "\""
                << "\n\twanted ";
            std::copy(tokens.begin(), tokens.end(), 
                std::ostream_iterator<token>(std::cout, ""));
            std::cout 
                << "\n\tgot    ";
            std::copy(gen.begin(), gen.end(), 
                std::ostream_iterator<token>(std::cout, ""));
            std::cout << '\n';
        }
    } tests[]{
        { "foo = bar + 42", {
            {token::token_type::NAME, "foo"},
            {token::token_type::OP, "="},
            {token::token_type::NAME, "bar"},
            {token::token_type::OP, "+"},
            {token::token_type::NUMBER, "42"},
        }},

        { "foo=bar+42       ", {
            {token::token_type::NAME, "foo"},
            {token::token_type::OP, "="},
            {token::token_type::NAME, "bar"},
            {token::token_type::OP, "+"},
            {token::token_type::NUMBER, "42"},
        }},

        { "       _", {
            {token::token_type::NAME, "_"},
        }},

        { "        ", {
        }},

        { "ma = 35p42", {
            {token::token_type::NAME, "ma"},
            {token::token_type::OP, "="},
            {token::token_type::NUMBER, "35"}, 
            {token::token_type::NAME, "p42"},
        }},

        { "+-_=", {
            {token::token_type::OP, "+"},
            {token::token_type::OP, "-"},
            {token::token_type::NAME, "_"},
            {token::token_type::OP, "="},
        }},

    };

    for (const auto t : tests) {
        t();
    }
}

Conclusion

I've left out much of the error checking you had in the code and the namespace (which is fine as it is, by the way), but using a construct like the one above should considerably simplify your code and reduce its size by hundreds of lines since the tokenizer class is no longer needed.