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:
- It needs to be "fast," in that it should be more or less real-time while typing.
- 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).
- 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
flex
\$\endgroup\$/* ... */
) or preprocessor defines (#define ... \
). If the user alters a line, and the previous line opened a comment block, my lexer needs to know this so it knows whether to mark the line as being a comment, or containing keywords (for example). \$\endgroup\$