C-style language lexer for a syntax highlighter

Question

I'm working on implementing a syntax highlighter for a simple text editor I've been working on. To do this, I need a simple lexer for various languages (I don't need a full one - I'm only interested in highlighting things like comments, strings, numbers and keywords). The way my editor component works is it highlights the entire document, and then re-highlights lines of the file as they are changed. So I have some requirements for this lexer:

1. It needs to be "fast," in that it should be more or less real-time while typing.
2. I need to be able to re-lex a given line of text, given the state from the previous blocks (this should be trivial for a lexer implemented as a state machine).
3. It should be written in C or C++ (I am using C++ for my project), and it should be fairly easily maintainable (I realize lexers are usually somewhat "messy", but I still want it as "clean" as possible).

I am aware of and have used in the past various tools for creating lexers like (f)lex, Antlr, Quex, boost::spirit/qi, etc, but as far as I have been able to find none of them satisfy requirement (2) (if you have an example of how to achieve (2) using one of these tools, I would love to see it!).

As such, I have implemented a very simple lexer for C-style languages by hand. Note that it is very obviously incomplete as far as language elements, and some more work needs to be done to turn lexer states into actual tokens. Here is my source code so far:

CLexer.h

#ifndef INCLUDE_C_LEXER_H
#define INCLUDE_C_LEXER_H

#include <map>
#include <vector>
#include <string>

class CLexer;
typedef int (CLexer::*C_LEXER_TRANSITION)(char);

struct CLexerToken;
typedef struct CLexerToken CLexerToken;

class CLexer
{
    public:
        static const int INITIAL_STATE;

        CLexer();
        virtual ~CLexer();

        std::vector<CLexerToken> lexBlock(int &s, const std::string &t, int p);

    private:
        static const std::map<int, C_LEXER_TRANSITION> transitions;

        int rootTransition(char c);
        int stringTransition(char c);
        int stringEndTransition(char c);
        int escapeTransition(char c);
};

struct CLexerToken
{
    int start;
    int count;
    int state;
};

#endif

CLexer.cpp

#include "CLexer.h"

#include <cassert>

#define ST_ROOT     1
#define ST_STRING   2
#define ST_STRING_END   3
#define ST_ESCAPE   4

// This is a list of functions which are used to transition between states.
const std::map<int, C_LEXER_TRANSITION> CLexer::transitions = {
    {ST_ROOT, &CLexer::rootTransition},
    {ST_STRING, &CLexer::stringTransition},
    {ST_STRING_END, &CLexer::stringEndTransition},
    {ST_ESCAPE, &CLexer::escapeTransition}
};

const int CLexer::INITIAL_STATE = ST_ROOT;

CLexer::CLexer()
{
}

CLexer::~CLexer()
{
}

/*
 * \param s This will receive the state at the end of this block.
 * \param t The text this block contains.
 * \param p The state at the end of the previous block.
 */
std::vector<CLexerToken> CLexer::lexBlock(int &s, const std::string &t, int p)
{
    std::vector<CLexerToken> tokens;
    int start = 0;
    int state = p;

    for(size_t idx = 0; idx < t.length(); ++idx)
    {
        std::map<int, C_LEXER_TRANSITION>::const_iterator transit =
            CLexer::transitions.find(state);

        assert(transit != CLexer::transitions.cend());

        int newstate = (this->*(transit->second))(t.at(idx));

        if(newstate != state)
        {
            CLexerToken tok;

            tok.start = start;
            tok.count = idx - start;
            tok.state = state;

            if(tok.count > 0)
            {
                tokens.push_back(tok);
            }

            start = idx;
        }

        state = newstate;
    }

    CLexerToken tok;

    tok.start = start;
    tok.count = t.length() - start;
    tok.state = state;

    if(tok.count > 0)
    {
        tokens.push_back(tok);
    }

    s = state;
    return tokens;
}

int CLexer::rootTransition(char c)
{
    switch(c)
    {
        case '"': return ST_STRING;
        default: return ST_ROOT;
    }
}

int CLexer::stringTransition(char c)
{
    switch(c)
    {
        case '\\': return ST_ESCAPE;
        case '"': return ST_STRING_END;
        default: return ST_STRING;
    }
}

int CLexer::stringEndTransition(char c __attribute__((unused)))
{
    return ST_ROOT;
}

int CLexer::escapeTransition(char c __attribute__((unused)))
{
    return ST_STRING;
}

main.cpp

#include <iostream>
#include <vector>
#include <string>

#include "CLexer.h"

int main(void)
{
    // A REALLY simple test program to lex.
    std::vector<std::string> lines {
        "#include <iostream>",
        "",
        "int main(void)",
        "{",
        "\tstd::cout << \"Hello, world!\\n\";",
        "",
        "\treturn 0;",
        "}",
        ""
    };

    CLexer lexer;
    int state = CLexer::INITIAL_STATE;

    for(size_t idx = 0; idx < lines.size(); ++idx)
    {
        std::vector<CLexerToken> tokens = lexer.lexBlock(state, lines.at(idx), state);

        for(std::vector<CLexerToken>::iterator it = tokens.begin(); it != tokens.end(); ++it)
        {
            std::cout << "Lexeme on line " << (idx + 1) << " from " << (*it).start <<
                " for " << (*it).count << ", type " << (*it).state << "\n";
        }
    }

    return 0;
}

I'm hoping for feedback on my design - can I simplify this code to make it more maintainable? Is there a way I can use an existing tool to achieve the same thing?

Note: I have been working on this code using gcc 4.7.3, with the flags -Wall -Wextra -ansi -pedantic -Wshadow -Wpointer-arith -Wcast-qual -pipe -fomit-frame-pointer -Wall -W -O2 -std=c++0x

Answer 1

There are still some things to add to complete Jamal's answer:

• You are using the GCC extension __attribute__((unused)). That's useful for C code, but since you are using C++, you can simply drop the parameter name, that's allowed an encouraged:

  int CLexer::stringEndTransition(char)
  {
      return ST_ROOT;
  }
  

• You are using the syntax (*it).foo all over the place. You can simply replace that with the shorthand syntax it->foo.

• Concerning your #defines, I would go even further than Jamal and use an enum class (we are using C++11 after all):

  enum class state_t
  {
      ROOT,
      STRING,
      STRING_END,
      ESCAPE
  };
  

  Then, wherever you use int to represent the state, you should replace it by state_t. Also, you will have to change ST_ROOT by state_t::ROOT and so on... However, in order to do so, you will have to refactor some amount of code. But it is worth it, strong typing is a good pratice.

• C++11 guidelines again: replace static const variables by static constexpr variables whenever possible (I don't think it is possible for std::map though). Also, you can initialize variables (including static ones) directly at their point of declaration:

  static constexpr state_t INITIAL_STATE = state_t::ROOT;
  

• And C++11 once again: you should consider replacing the meaningful typedefs (see Jamal's answer for the useless ones) by using declarations. It may be a mere matter of taste, but I find them easier to read:

  using C_LEXER_TRANSITION = state_t (CLexer::*)(char);
  

• You should use meaningful names for your functions parameters, especially the ones that are meant to be used by everone (aka the public ones). For example, in this definition:

  lexBlock(state_t &s, const std::string &t, state_t p);
  

  I don't really know what s, t and p mean. And it was even worse before I replaced int parameters by state_t ones.

Answer 2

• You're using single-character variables in various places. With the exception of typical loop counters (such as i), variables should be descriptive and not need comments to help explain their meaning. This will also help you remember what they're for at a later point in the program.

• There are some remnants of C code that are not required in C++:

  • You have a typedef struct, but C++ does the same thing with just struct.
  • Functions with no parameters don't need void.
  • return 0 is already applied by the compiler at the end of main().

• You can now use C++11's default constructor and destructor instead of providing your own.

  Instead of having these in the .cpp file:

  CLexer::CLexer()
  {
  }
  
  CLexer::~CLexer()
  {
  }
  

  you'll just have these in the .h file:

  CLexer() = default;
  ~CLexer() = default;
  

  In pre-C++11, you would just leave them out and let the compiler make them for you.

• #defines aren't too common in C++ as opposed to C:

  #define ST_ROOT     1
  #define ST_STRING   2
  #define ST_STRING_END   3
  #define ST_ESCAPE   4
  

  This should instead be an enum:

  enum State { ROOT=1, STRING, STRING_END, ESCAPE };
  

  The 1 is needed for the initial value (it normally starts at 0), while all the following values will be one higher than the previous. This is generally how enums work.

• For this loop statement:

  for(size_t idx = 0; idx < t.length(); ++idx)
  

  Since t is of type std::string, use std::string::size_type as the loop counter type. This is the specific return value of t.size(). In general, size() returns an std::size_type.

• This function:

  int CLexer::rootTransition(char c)
  {
      switch(c)
      {
          case '"': return ST_STRING;
          default: return ST_ROOT;
      }
  }
  

  doesn't need a switch statement as there are only two possible outcomes. It can be done much simpler with a single-line ternary statement.

  Using the aforementioned enum, this function should now return a State:

  State CLexer::rootTransition(char c)
  {
      return (c == '"') ? STRING : ROOT;
  }
  

  This will return either the value on the left (if true) or on the right (if false).