12
\$\begingroup\$

I'm building a compiler for fun, and this is my first pass at the lexer for it. It should handle all tokens for C99, with the exception of the preprocessor tokens. It's very minimal, only grabbing the token and lexeme. Specific areas where I'd like feedback:

  • I rarely get to use anything beyond C++98. Are there any more recent language features I could be taking advantage of? Anything that could be more idiomatic?

  • My error-handling seems a little ad-hoc. Is there a smarter approach?

  • I'm not sure about the best way to choose tokens. The C99 standard just breaks things down into punctuators, keywords, identifiers, and constants. But the compilers I've looked at tend to be more granular. Is there a better approach to choosing tokens? Why?

  • I think there has to be a more maintainable way of structuring this.

Things I don't care about:

  • I know there are more efficient ways to handle input. My aim here is to just do the simplest thing and worry about fancy stuff/performance tuning later.

  • You probably don't like my brace style. Sorry. :/

Lexer.h

#ifndef __JMCOMP_LEXER_H__
#define __JMCOMP_LEXER_H__

#include <iostream>
#include <string>

enum class Token
{
    PUNCTUATOR,
    KEYWORD,
    IDENTIFIER,
    INT_CONST,
    FLOAT_CONST,
    CHAR_CONST,
    ERROR
};

struct LexResult
{
    Token token = Token::ERROR;
    std::string lexeme = "";
};

class Lexer
{
public:
    explicit Lexer(std::istream& stream);
    LexResult next();
private:
    std::istream& mStream;
    char nextChar();
    char skipWhitespace();
    char peekChar();
    bool peekWord(const std::string& word);
    std::string nextIdentifier(char character, bool& isValid);
    std::string lexUniversalCharacter(char character, bool& isValid);
    std::string lexHexQuad(bool& isValid);
    LexResult lexIdentifier(char character);
    LexResult lexConstant(char character);
    std::string readIntConstant(bool predicate(char));
    std::string readIntSuffix();
    std::string readLongSuffix();
    LexResult checkInvalidToken(const LexResult& token);
    LexResult readFloatConstant(const std::string& prefix,
                                bool predicate(char));
    LexResult lexCharConst(const std::string& initial, char delimiter);
    std::string lexEscapeSequence(bool& isValid);
    void skipLineComment();
    void skipBlockComment();
};

#endif

Lexer.cpp

#include <set>
#include "Lexer.h"

namespace
{
bool startsIdentifier(char character)
{
    return std::isalpha(character) || character == '_');
}

bool isInIdentifier(char character)
{
    return startsIdentifier(character) ||
        std::isdigit(character);
}

bool isHexChar(char character)
{
    return std::isdigit(character) ||
        (character >= 'A' && character <= 'F') ||
        (character >= 'a' && character <= 'f');
}

bool isOctal(char character)
{
    return std::isdigit(character) && '8' - character > 0;
}

bool isDigit(char character)
{
    return std::isdigit(character);
}

bool isWhitespace(char character)
{
    return character == ' ' || character == '\n' || character == '\t';
}

bool isExponentChar(char character)
{
    return (character == 'e' ||
            character == 'E' ||
            character == 'p' ||
            character == 'P');
}

static std::set<std::string> keywords = {
    "auto", "break", "case", "char", "const", "continue", "default",
    "do", "double", "else", "enum", "extern", "float", "for", "goto",
    "if", "inline", "int", "long", "register", "restrict", "return",
    "short", "signed", "sizeof", "static", "struct", "switch", "typedef",
    "union", "unsigned", "void", "volatile", "while", "_Bool",
    "_Complex", "_Imaginary"
};
}

Lexer::Lexer(std::istream& stream):
    mStream(stream)
{
}

char Lexer::nextChar()
{
    char c;
    mStream.read(&c, 1);
    return c;
}

char Lexer::skipWhitespace()
{
    char c;
    do
        c = nextChar();
    while (isWhitespace(c));
    return c;
}

char Lexer::peekChar()
{
    return mStream.peek();
}

bool Lexer::peekWord(const std::string& word)
{
    std::string lexedWord;

    // We've already read the first character, so set that in advance
    lexedWord.resize(word.size());
    lexedWord[0] = word[0];

    const size_t bytesToRead = lexedWord.size() - 1;
    mStream.read(&lexedWord[1], bytesToRead);
    if (lexedWord == word) {
        return true;
    }
    else {
        mStream.seekg((-bytesToRead), std::ios::cur);
        return false;
    }
}

std::string Lexer::lexHexQuad(bool& isValid)
{
    std::string hexQuad;
    for (size_t i = 0; i < 4; ++i) {
        char character = nextChar();
        // First check if the character is okay
        if (!isHexChar(character))
            isValid = false;

        // Get a better error message (I hope?) if we keep reading
        // until a "logical" break, so no matter what keep going unless
        // there's whitespace
        if (!isWhitespace(character) && mStream)
            hexQuad += character;

        // If we hit whitespace, there's no way it's valid
        // We're at a logical boundary, so just return here
        else return hexQuad;

    }
    return hexQuad;
}

std::string Lexer::lexUniversalCharacter(char character, bool& isValid)
{
    std::string universalCharacter(1, character);

    character = nextChar();
    universalCharacter += character;
    if (character == 'u')
        universalCharacter += lexHexQuad(isValid);
    else if (character == 'U') {
        universalCharacter += lexHexQuad(isValid);
        universalCharacter += lexHexQuad(isValid);
    }
    else
        isValid = false;
    return universalCharacter;
}

std::string Lexer::nextIdentifier(char character, bool& isValid)
{
    std::string identifier;
    while (isInIdentifier(character)) {
        if (character == '\\') {
            identifier += lexUniversalCharacter(character, isValid);
            if (!isValid)
                return identifier;
        }
        else
            identifier += character;
        character = nextChar();
    }
    mStream.seekg(-1, std::ios::cur);
    return identifier;
}



LexResult Lexer::checkInvalidToken(const LexResult& token)
{
    std::string lexeme = token.lexeme;
    if (!isWhitespace(peekChar()) && peekChar() != EOF) {
        while (!isWhitespace(peekChar()) && peekChar() != EOF)
            lexeme += nextChar();
        return LexResult{Token::ERROR, lexeme};
    }
    return token;
}

LexResult Lexer::lexIdentifier(char character)
{
    bool isValid = true;
    const std::string identifier = nextIdentifier(character, isValid);
    if (!isValid)
        return LexResult{Token::ERROR, identifier};
    if (keywords.count(identifier))
        return LexResult{Token::KEYWORD, identifier};
    return LexResult{Token::IDENTIFIER, identifier};
}

std::string Lexer::readIntConstant(bool predicate(char))
{
    std::string lexeme;
    while (predicate(peekChar()))
        lexeme += nextChar();
    return lexeme;
}

std::string Lexer::readLongSuffix()
{
    std::string suffix;
    suffix += nextChar();
    if (peekChar() == 'L' || peekChar() == 'l')
        suffix += nextChar();
    return suffix;
}

std::string Lexer::readIntSuffix()
{
    std::string suffix;
    if (peekChar() == 'L' || peekChar() == 'l') {
        suffix += readLongSuffix();
        if (peekChar() == 'u' || peekChar() == 'U')
            suffix += nextChar();
    }
    else if (peekChar() == 'u' || peekChar() == 'U') {
        suffix += nextChar();
        if (peekChar() == 'l' || peekChar() == 'L')
            suffix += readLongSuffix();
    }
    return suffix;
}

LexResult Lexer::readFloatConstant(const std::string& prefix,
                                   bool predicate(char))
{
    std::string result = prefix;
    if (peekChar() == '.') {
        result += nextChar();
        result += readIntConstant(predicate);
    }
    if (isExponentChar(peekChar())) {
        result += nextChar();
        if (peekChar() == '+' || peekChar() == '-')
            result += nextChar();

        const std::string exponentSequence = readIntConstant(predicate);
        if (exponentSequence.empty())
            return checkInvalidToken(LexResult{Token::ERROR, result});

        result += exponentSequence;
    }

    const char suffix = peekChar();
    if (suffix == 'f' || suffix == 'F' ||
        suffix == 'l' || suffix == 'L')
        result += nextChar();
    return checkInvalidToken(LexResult{Token::FLOAT_CONST, result});
}

LexResult Lexer::lexConstant(char character)
{
    std::string lexeme(1, character);
    Token token = Token::INT_CONST;
    auto predicate = isDigit;

    if (peekChar() == 'x' || peekChar() == 'X') {
        predicate = isHexChar;
        lexeme += nextChar();
    }
    else if (character == '0')
        predicate = isOctal;

    lexeme += readIntConstant(predicate);

    if (peekChar() == '.' || isExponentChar(peekChar()))
        return readFloatConstant(lexeme, predicate);

    lexeme += readIntSuffix();
    return checkInvalidToken(LexResult{token, lexeme});
}

std::string Lexer::lexEscapeSequence(bool& isValid)
{
    std::string lexeme(1, nextChar());
    const char c = peekChar();

    if (c == '\'' || c == '"' || c == '?' ||
        c == '\\' || c == 'a' || c == 'b' ||
        c == 'f' || c == 'n' || c == 'r' ||
        c == 't' || c == 'v' || c == 'x' || isHexChar(c))
        return lexeme + nextChar();

    isValid = false;
    return lexeme;
}

LexResult Lexer::lexCharConst(const std::string& initial, char delimiter)
{
    bool isValid = true;
    std::string lexeme = initial + delimiter;
    while (peekChar() != delimiter && peekChar() != EOF) {
        if (peekChar() == '\n')
            isValid = false;
        if (peekChar() == '\\') {
            lexeme += lexEscapeSequence(isValid);
            continue;
        }

        lexeme += nextChar();
    }
    lexeme += nextChar();
    return LexResult{isValid ? Token::CHAR_CONST : Token::ERROR, lexeme};
}

void Lexer::skipLineComment()
{
    nextChar(); nextChar();
    while (peekChar() != '\n')
        nextChar();
}

void Lexer::skipBlockComment()
{
    nextChar(); // Skip the first *
    char c;
    do
        c = nextChar();
    while (!(c == '*' && peekChar() == '/'));
    nextChar(); // Pass the last /
}

LexResult Lexer::next()
{
    char character = skipWhitespace();
    while (character == '/' && peekChar() == '/') {
        skipLineComment();
        character = skipWhitespace();
    }
    while (character == '/' && peekChar() == '*') {
        skipBlockComment();
        character = skipWhitespace();
    }
    if (isdigit(character))
        return lexConstant(character);
    if (character == '\'' || character == '"')
        return lexCharConst("", character);
    if (character == 'L')
        if (peekChar() == '\'' || peekChar() == '"') {
            return lexCharConst("L", nextChar());
        }
    if (startsIdentifier(character))
        return lexIdentifier(character);
    switch (character) {
        case '+':
            if (peekWord("++"))
                return LexResult{Token::PUNCTUATOR, "++"};
            if (peekWord("+="))
                return LexResult{Token::PUNCTUATOR, "+="};
            return LexResult{Token::PUNCTUATOR, "+"};
        case '-':
            if (peekWord("->"))
                return LexResult{Token::PUNCTUATOR, "->"};
            if (peekWord("--"))
                return LexResult{Token::PUNCTUATOR, "--"};
            if (peekWord("-="))
                return LexResult{Token::PUNCTUATOR, "-="};
            return LexResult{Token::PUNCTUATOR, "-"};
        case '*':
            if (peekWord("*="))
                return LexResult{Token::PUNCTUATOR, "*="};
            return LexResult{Token::PUNCTUATOR, "*"};
        case '/':
            if (peekWord("/="))
                return LexResult{Token::PUNCTUATOR, "/="};
            return LexResult{Token::PUNCTUATOR, "/"};
        case '=':
            if (peekWord("=="))
                return LexResult{Token::PUNCTUATOR, "=="};
            return LexResult{Token::PUNCTUATOR, "="};
        case '[':
            return LexResult{Token::PUNCTUATOR, "["};
        case ']':
            return LexResult{Token::PUNCTUATOR, "]"};
        case '(':
            return LexResult{Token::PUNCTUATOR, "("};
        case ')':
            return LexResult{Token::PUNCTUATOR, ")"};
        case '.':
            if (peekWord("..."))
                return LexResult{Token::PUNCTUATOR, "..."};
            return LexResult{Token::PUNCTUATOR, "."};
        case '&':
            if (peekWord("&&"))
                return LexResult{Token::PUNCTUATOR, "&&"};
            if (peekWord("&="))
                return LexResult{Token::PUNCTUATOR, "&="};
            return LexResult{Token::PUNCTUATOR, "&"};
        case '~':
            return LexResult{Token::PUNCTUATOR, "~"};
        case '!':
            if (peekWord("!="))
                return LexResult{Token::PUNCTUATOR, "!="};
            return LexResult{Token::PUNCTUATOR, "!"};
        case '%':
            if (peekWord("%:%:"))
                return LexResult{Token::PUNCTUATOR, "%:%:"};
            if (peekWord("%:"))
                return LexResult{Token::PUNCTUATOR, "%:"};
            if (peekWord("%="))
                return LexResult{Token::PUNCTUATOR, "%="};
            if (peekWord("%>"))
               return LexResult{Token::PUNCTUATOR, "%>"};
            return LexResult{Token::PUNCTUATOR, "%"};
        case '<':
            if (peekWord("<<="))
                return LexResult{Token::PUNCTUATOR, "<<="};
            if (peekWord("<:"))
                return LexResult{Token::PUNCTUATOR, "<:"};
            if (peekWord("<%"))
                return LexResult{Token::PUNCTUATOR, "<%"};
            if (peekWord("<<"))
                return LexResult{Token::PUNCTUATOR, "<<"};
            if (peekWord("<="))
                return LexResult{Token::PUNCTUATOR, "<="};
            return LexResult{Token::PUNCTUATOR, "<"};
        case '>':
            if (peekWord(">>="))
                return LexResult{Token::PUNCTUATOR, ">>="};
            if (peekWord(">>"))
                return LexResult{Token::PUNCTUATOR, ">>"};
            if (peekWord(">="))
                return LexResult{Token::PUNCTUATOR, ">="};
            return LexResult{Token::PUNCTUATOR, ">"};
        case '^':
            if (peekWord("^="))
                return LexResult{Token::PUNCTUATOR, "^="};
            return LexResult{Token::PUNCTUATOR, "^"};
        case '|':
            if (peekWord("||"))
                return LexResult{Token::PUNCTUATOR, "||"};
            if (peekWord("|="))
                return LexResult{Token::PUNCTUATOR, "|="};
            return LexResult{Token::PUNCTUATOR, "|"};
        case '?':
            return LexResult{Token::PUNCTUATOR, "?"};
        case ':':
            if (peekWord(":>"))
                return LexResult{Token::PUNCTUATOR, ":>"};
            return LexResult{Token::PUNCTUATOR, ":"};
        case ';':
            return LexResult{Token::PUNCTUATOR, ";"};
        case ',':
            return LexResult{Token::PUNCTUATOR, ","};
        case '#':
            if (peekWord("##"))
                return LexResult{Token::PUNCTUATOR, "##"};
            return LexResult{Token::PUNCTUATOR, "#"};
        default:
            return LexResult{Token::ERROR, std::string(character, 1)};
    }
}
\$\endgroup\$
  • \$\begingroup\$ May want to look at flex or lex to write a lexer. \$\endgroup\$ – Martin York May 7 '18 at 17:38
  • \$\begingroup\$ I rarely get to use anything beyond C++98.. Really. Did C++98 even have exceptions in the language. I think you mean C++03. And yes there are a lot of things add in C++11 that make the language a whole bunch better. C++14/C++17 were incrementally better and more usable. \$\endgroup\$ – Martin York May 7 '18 at 21:28
  • \$\begingroup\$ @MartinYork: Yes, C++98 had exceptions. In fact, it was almost indistinguishable from C++03. Most of the changes to the standard were simply corrections to express the requirements more accurately. There were a couple of changes to the language, but only a couple--and minor ones at that. \$\endgroup\$ – Jerry Coffin May 9 '18 at 13:26
  • \$\begingroup\$ @JerryCoffin Yep Exceptions were officially included in 1990 though compiler support lagged for many years but by 1998 they were mostly supported. \$\endgroup\$ – Martin York May 9 '18 at 16:51
12
\$\begingroup\$
#ifndef __JMCOMP_LEXER_H__

That is a symbol reserved for use by the implementation. Writing your this in a way that mimics what you see in the compiler-supplied headers is exactly wrong!

For this and other reasons I suggest leaving that out completely and just use #pragma once. If you ever find a platform were this pragma is not supported, a script can add the one-time-include symbols automatically and correctly.


I rarely get to use anything beyond C++98. Are there any more recent language features I could be taking advantage of? Anything that could be more idiomatic?

Aye, scribing ye olde language doest appeareth que’r. C++11 is like a whole new language.

I think there has to be a more maintainable way of structuring this.

Have you studied parsing? LR(k), Chomsky Normal Form, pumping lemmings, … any of that sound familiar?

Lexing only, not parsing — OK, so you just want to classify tokens. BTW, have you looked at Boost.Spirit.lex? That would make quick work of it, if you just wanted a lexer. If you are doing this as an experience in itself, carry on!


I would (do) start with a comment block that gives the grammar in EBNF pseudo-code. That gives the relationship of the hierarchy of symbols and which ones are terminal or non-terminal. The names in this doc will match the names in the code.

I’m doing something not entirely dissimilar, hearing that string_view is particularly good for writing parsers, as you can whack pieces off the front end efficiently and pass them around as lightweight un-owning containers.

So I have functions like this:

std::optional<std::string> read_identifier (std::string_view&);
std::optional<Value_type> read_number (std::string_view&);

Each function will return the thing it read. In a pure lexer, you can either make that a string_view holding just the chars comprising that token, or a token structure containing information such as its kind and “value” which will be used by the parsing stage. Even if you don’t want to use it, read the tutorial for Boost.Spirit’s lex class to get ideas on that. You might want to track the original position of the token in the source, too.

In my functions shown above, if the thing was read, the string_view is updated to remove it from the beginning of the line. If not successful, the optional returns no-value and the view is not changed. This lets me write non-terminals by calling one and if that didn't work call the next possibility. For more complex cases, the string_view can be saved in a temporary and restored, cheaply — that allows for backing up to try something else.


The C99 standard just breaks things down into punctuators, keywords, identifiers, and constants. But the compilers I've looked at tend to be more granular. Is there a better approach to choosing tokens? Why?

You can get a hint from my comments above. Consider: you can chop up the source into individual “words” only, but when you feed this to the next stage the only thing it saves you is not having to skip white space and mess with comments getting in the middle of grammatical productions.

If the tokens have a rough type, like number, identifier, punctuation; it saves the parser some work. The parser grammar uses these, so starting with that dovetails nicely.

If the tokens have a type and a value, it can save the next stage from having to figure that out. But someone has to figure it out, and if you do it in the lexer you’re guessing at what the parser will find useful. If you need to figure out something to do the lexical analysis, then preserve that information and pass it along.

If you write the lexer and parser grammars together, the lexer is just the bottom end of the whole grammar and it is clear what you need, because you are choosing which terminals to handle (or partially handle) in the lexing step. Why two phases? Well, the designer or Perl 6 patterns say “why indeed?”. The tutorial and overview of Boost.Spirit goes into it, and lets you use a separate lexer or not.

One good reason is to get rid of comments. Eating whitespace after each nonterminal in a monolithic parser isn’t that bad, but consider comments and backslash continuation lines and other stuff that lives in the text, that makes it hard to deal with that mixed in with the parser grammar.

Other reasons historically are memory usage and machine capacity; that matters less today. And there is the adage that “If you put a team of three people onto a compiler-writing project, you’ll get a three-pass compiler.”


enum class Token
{
    PUNCTUATOR,
    KEYWORD,
    IDENTIFIER,
    INT_CONST,
    FLOAT_CONST,
    CHAR_CONST,
    ERROR
};

See ⧺ES.9: Avoid ALL_CAPS names.

I see you are using a new language feature of enum class, so your code might not be as out-of-date as you feared.

You might consider reserving a value of 0 for ERROR or empty or something like that.


std::string lexeme = "";

Don’t, in general, assign "" to clear out a std::string. In this case, there is no need to say anything at all because string has a constructor. So just leave the default initializer off of the member.

Token token = Token::ERROR;

Since that is what you want for the default, I would make ERROR the first thing in the enumeration list so it has the value zero. It doesn’t matter ideally, but it’s nice and might be helpful later.


return std::isalpha(character) || character == '_');

See cppreference for the Kosher way to call these ancient functions.

⋯ isalpha(static_cast<unsigned char>(character)) ⋯

Since you already wrapped these calls in your own helpers, it will only appear within those helpers, once.

bool isWhitespace(char character)

not using std::isspace? You are not covering as many characters as it does.


static std::set<std::string> keywords = {
    "auto", "break", "case", "char", "const", "continue", "default", ⋯

Two things: the set is rather slow for lookup! A sorted vector would be faster! Boost.Container has a flat_set etc.

Second, you are copying the statically-allocated lexical string literals into string objects. Do you really need string here? I would (did, actually) just use a plain (pre-sorted) array of const char*, and make the whole thing constexpr.

If std::string literals were constexpr you could at least save the redundant copy and run-time copying, but pondering why it isn’t constexpr will show you why I’m mentioning this — it needs to allocate memory, and do run-time work to set up the set.

Keeping the entire table in one contiguous lump of memory will not only save memory for all those pointers and nodes, but will be much faster.


Lexer::Lexer(std::istream& stream):
    mStream(stream)
{
}

Use uniform initialization. So now you write curly braces instead of parens:

: mStream{stream}

and this short one-liner could go inline in the header.


char Lexer::nextChar()
{
    char c;
    mStream.read(&c, 1);
    return c;
}

What if no character was read? The stream could be bad you know. Maybe you hit the end of the file, or the network glitched.


char c;
do
    c = nextChar();
while (isWhitespace(c));
return c;

You can write this in a way to prevent defining c outside the loop. More importantly, deal with errors from nextChar.

It would be cleaner if it only skipped whitespace and did not also read (and return) the next char beyond that! (Hint: see the next function in your file)

// We've already read the first character, so set that in advance
lexedWord.resize(word.size());
lexedWord[0] = word[0];

Exactly! Don’t read one ahead. Skipws should do its one job only.

It is especially confusing since peekWord does not do the skipws call. It seems that it is called when you already know that the first character of the word does match the input? This is going to lead to maintenance problems, believe me.

(later: I see a lot of the functions take the read-ahead character as another parameter and have special code to deal with that first. Get rid of all that. The function should be called with the input set to the first position of the thing it wants to read. You already know to peek and to rewind, so there is no reason to have this one-off getting in the way.)

Did you know that a stream can give you an input iterator? So rather than allocating a string and reading into it and then comparing (oh, and you didn't check to see if it read as many bytes as you asked for), you can use something like std::equal directly between word and the input stream.

If/when you do need to access the contents of a std::string as a buffer for writing into, use .data().


std::string Lexer::lexUniversalCharacter(char character, bool& isValid)

Two return values, no problem. Don’t use an “out” parameter for the second one! (⧺F.21).

However, I think you don’t have two values here, but an optional result.


return LexResult{Token::IDENTIFIER, identifier};

You don’t need to name the type, as it is automatically picked up from the function’s return type.

return {Token::IDENTIFIER, identifier};

this can be much nicer.


if (peekChar() == 'L' || peekChar() == 'l') {
    suffix += readLongSuffix();
    if (peekChar() == 'u' || peekChar() == 'U')
        suffix += nextChar();
}
else if (peekChar() == 'u' || peekChar() == 'U') {
    suffix += nextChar();
    if (peekChar() == 'l' || peekChar() == 'L')

Avoid calling peelChar twice on the same character. You can use a new feature in if statements here:

if (auto ch=peekChar(); ch=='L' || ch=='l') {

or (since you are checking a lot of cap/lower pairs) define a helper function:

if (mAtCh(peekChar(),'L') {

but later you need more general:

if (match_any_of(peekChar(), "+-") {

if (match_any_of(peekChar(), "fFlL") {

lexEscapeSequence

and to write that, use std::any_of in a one-line wrapper.


    if (peekWord("<<="))
        return LexResult{Token::PUNCTUATOR, "<<="};
    if (peekWord("<:"))
        return LexResult{Token::PUNCTUATOR, "<:"};
    if (peekWord("<%"))
        return LexResult{Token::PUNCTUATOR, "<%"};
    if (peekWord("<<"))
        return LexResult{Token::PUNCTUATOR, "<<"};
    if (peekWord("<="))
        return LexResult{Token::PUNCTUATOR, "<="};

There are a lot of these. Notice how the thing you peek always matches the parameter to the return value? What is the if even doing?

You need a function that returns the peeked word.

In fact, all of this reads one char, switches on it, then peeks on the rest of the word. Why does it need to do it in two parts like that? You are just classifying the “word” a PUNCTUATOR.

Make a list (static array, as discussed with keywords) and treat it in the same way. Just as there are keywords spelled with letters, these are a list of legal words spelled with non-letter/non-digit characters.

The trick is you have to take the longest sequence that is a valid token. But use a table, not dozens of duplicated snippets of code.

peek a character and append to the token
is that on the list?
    no: return with what you had.
    yes: advance the input and append to the token.

Good!

I see you used an anonomous namespace for the helpers in the CPP file.

Using std::stream for reading the text: most people just use a string.

\$\endgroup\$
4
\$\begingroup\$

Include what you use

You use isdigit, isalpha, etc. -- but you haven't included ctype.h or cctype to assure that they're declared.

Broken Code

bool startsIdentifier(char character)
{
    return std::isalpha(character) || character == '_');
}

I'm not sure if you accidentally messed this up while cutting and pasting to the browser, but this won't even compile as it is right now. You have mis-matched parentheses.

hex characters

Checking for hexadecimal characters.

bool isHexChar(char character) {
    return std::isdigit(character) ||
        (character >= 'A' && character <= 'F') ||
        (character >= 'a' && character <= 'f'); }

The standard library provides std::isxdigit to check for hexadecimal characters, so you could call that instead of inventing your own like this.

Conversion to unsigned char

As @JDługosz pointed out, you want to convert the argument to unsigned char before calling. Since you're writing a wrapper anyway, you can pretty easily avoid casting though--just change the argument to your function to unsigned char:

bool isHexChar(unsigned char ch) { return isxdigit(ch); }

Ignore: pure pedanticism

On a purely pedantic note, your code to check whether a character is between 'A' and 'F' inclusive isn't actually required to work. Digits are required to be contiguous, but letters aren't. That is purely pedantic though--the only character encoding I know of that has non-contiguous characters is EBCDIC, which is contiguous from A to F (its first non-contiguous section is after i)--and even if it was a problem with EBCDIC, you probably wouldn't care anyway.

Language Compliance

As it stands right now, your lexer doesn't implement a number of things the way the C and C++ standards say it should. For example, adjacent string literals:

"char literal 1" " char literal 2"

...should be spliced into a single string literal. There are phases of translation, however, so you have to do things in the right order. Splicing string literals happens at phase 6, so it's only done after conversion of universal character names (to give only one example). Removal of trigraphs from the language makes the order somewhat less important than it used to be though. For example, "??!" contains a trigraph that needs to be converted to a single character--but "?" "?!" does not contain a trigraph, and must remain as three separate characters.

Clumsy Usage

The interface to the code looks pretty clumsy and uninformative, at least to me. For example, if there's an error, you'd typically want to report its location to the user--but the LexResult doesn't contain the error location, so that's essentially impossible to do.

In fact, there doesn't even seem to be a way to distinguish between an error, and simply the end of the input. Either way, I seem to just get a LexResult with its Token set to ERROR. At least to me, it seems like when you tried to use a lexer, it would be fairly important to know whether you'd encountered an error, or successfully lexed the entire input.

\$\endgroup\$
  • 1
    \$\begingroup\$ "pedanticism"? I think you'll find the correct word is pedantry! :-p \$\endgroup\$ – Toby Speight May 9 '18 at 15:31
  • \$\begingroup\$ The "?" "?!" case is pretty important, as it's the recommended way to avoid unwanted trigraph expansion within string literals. \$\endgroup\$ – Toby Speight May 9 '18 at 15:34
  • \$\begingroup\$ @TobySpeight: If C99 still includes trigraphs at all, it's important. They did remove trigraphs (I think) but I don't remember whether it was removed in C99 or C11. \$\endgroup\$ – Jerry Coffin May 9 '18 at 15:51
  • \$\begingroup\$ I know that digraphs were introduced in C11, but I don't think trigraphs were removed (although newer GCC does default to disabling them). In the C++ world, trigraphs were removed at C++17. \$\endgroup\$ – Toby Speight May 9 '18 at 16:12
  • \$\begingroup\$ @TobySpeight: Well, either way he doesn't seem to (even attempt to) deal with trigraphs at all. I guess it's up to him to decide whether he should deal with them or not. \$\endgroup\$ – Jerry Coffin May 9 '18 at 16:34
3
\$\begingroup\$

Same Lexer writtern in Lex.

Lexer.l

startsIdentifier            [a-zA-Z_]
isInIdentifier              {startsIdentifier}|[0-9]
isHexChar                   [0-9A-Fa-f]
isOctal                     [0-7]
isDigit                     [0-9]
isWhitespace                [ \n\t]


skipWhitespace              {isWhitespace}*


isHexNumber                 0x{isHexChar}+
isOctalNumber               0{isOctal}*
isDecNumber                 [1-9]{isDigit}*
isIntegerNumber             {isHexNumber}|{isOctalNumber}|{isDecNumber}

isFloatLeadingDigit         {isDigit}+\.{isDigit}*
isFloatTrailingDigit        \.{isDigit}+
isExponentDec               [eE][+-]?{isDecNumber}
isExponentHex               [xX][+-]?{isHexNumber}
isExponent                  {isExponentHex}|{isExponentDec}
isFloatNumber               {isFloatLeadingDigit}{isExponent}?|{isFloatTrailingDigit}{isExponent}?|{isIntegerNumber}{isExponent}

escapeCharacter             ['"\?\\abfnrtvx{isHexChar}]
isCharCharacter             \\{escapeCharacter}|[^'\n\\]
isStringCharacter           \\{escapeCharacter}|[^"\n\\]
isCharLiteral               '{isCharCharacter}*'
isStringLiteral             "{isStringCharacter}*"
isLiteralChar               L?{isCharLiteral}|L?{isStringLiteral}

Identifier                  {startsIdentifier}{isInIdentifier}*

LineComment                 \/\/[^\n]*
BlockCommentStart           \/\*
BlockCommentEnd             \*\/

%x                          COMMENT_BLOCK

%%

<COMMENT_BLOCK>{BlockCommentEnd}    {BEGIN(INITIAL);}
<COMMENT_BLOCK>\*[^/]               {/* Ignore Star followed by anything except slash */}
<COMMENT_BLOCK>[^*]+                {/* Ignore blocks of text */}


{skipWhitespace}                    {/* Ignore */}
{LineComment}                       {/* Ignore */}
{BlockCommentStart}                 {BEGIN(COMMENT_BLOCK);}

{isIntegerNumber}                   {return COST_INT;}
{isFloatNumber}                     {return CONST_FLOAT;}
{isLiteralChar}                     {return CONST_CHAR;}

auto                                {return KEYWORD_AUTO;}
break                               {return KEYWORD_BREAK;}
case                                {return KEYWORD_CASE;}
char                                {return KEYWORD_CHAR;}
const                               {return KEYWORD_CONST;}
continue                            {return KEYWORD_CONTINUE;}
default                             {return KEYWORD_DEFAULT;}
do                                  {return KEYWORD_DO;}
double                              {return KEYWORD_DOUBLE;}
else                                {return KEYWORD_ELSE;}
enum                                {return KEYWORD_ENUM;}
extern                              {return KEYWORD_EXTERN;}
float                               {return KEYWORD_FLOAT;}
for                                 {return KEYWORD_FOR;}
goto                                {return KEYWORD_GOTO;}
if                                  {return KEYWORD_IF;}
inline                              {return KEYWORD_INLINE;}
int                                 {return KEYWORD_INT;}
long                                {return KEYWORD_LONG;}
register                            {return KEYWORD_REGISTER;}
restrict                            {return KEYWORD_RESTRICT;}
return                              {return KEYWORD_RETURN;}
short                               {return KEYWORD_SHORT;}
signed                              {return KEYWORD_SIGNED;}
sizeof                              {return KEYWORD_SIZEOF;}
static                              {return KEYWORD_STATIC;}
struct                              {return KEYWORD_STRUCT;}
switch                              {return KEYWORD_SWITCH;}
typedef                             {return KEYWORD_TYPEDEF;}
union                               {return KEYWORD_UNION;}
unsigned                            {return KEYWORD_UNSIGNED;}
void                                {return KEYWORD_VOID;}
volatile                            {return KEYWORD_VOLATILE;}
while                               {return KEYWORD_WHILE;}
_Bool                               {return KEYWORD_BOOL;}
_Complex                            {return KEYWORD_COMPLEX;}
_Imaginary                          {return KEYWORD_IMAGINARY;}

{Identifier}                        {return IDENTIFIER;}

\+                                  {return '+';}
\-                                  {return '-';}
\*                                  {return '*';}
\/                                  {return '/';}
\%                                  {return '%';}
\=                                  {return '=';}
\[                                  {return '[';}
\]                                  {return ']';}
\(                                  {return '(';}
\)                                  {return ')';}
\.                                  {return '.';}
\^                                  {return '^';}
\|                                  {return '|';}
\&                                  {return '&';}
\~                                  {return '~';}
\!                                  {return '!';}
\<                                  {return '<';}
\>                                  {return '>';}
\?                                  {return '&';}
\:                                  {return ':';}
\;                                  {return ';';}
\,                                  {return ',';}
\#                                  {return '#';}
\+\+                                {return PUNCT_INC;}
\-\-                                {return PUNCT_DEC;}

\-\>                                {return PUNCT_POINT;}

\<\<                                {return PUNCT_SHIFT_LEFT;}
\>\>                                {return PUNCT_SHIFT_RIGHT;}

\+\=                                {return PUNCT_ASSIGN_PLUS;}
\-\=                                {return PUNCT_ASSIGN_MINUS;}
\*\=                                {return PUNCT_ASSIGN_MUL;}
\/\=                                {return PUNCT_ASSIGN_DIV;}
\%\=                                {return PUNCT_ASSIGN_MOD;}
\|\=                                {return PUNCT_ASSIGN_OR;}
\&\=                                {return PUNCT_ASSIGN_AND;}
\^\=                                {return PUNCT_ASSIGN_NOT;}
\<\<\=                              {return PUNCT_ASSIGN_SHIFT_LEFT;}
\>\>\=                              {return PUNCT_ASSIGN_SHIFT_RIGHT;}

\<\=                                {return PUNCT_COMP_LESS_EQUAL;}
\>\=                                {return PUNCT_COMP_GREAT_EQUAL;}

\=\=                                {return PUNCT_COMP_EQUAL;}
\!\=                                {return PUNCT_COMP_NOT_EQUAL;}

\&\&                                {return PUNCT_BOOL_AND;}
\|\|                                {return PUNCT_BOOL_OR;}

\%\>                                {return PUNCT_PERCENT_GREAT;}
\%\:                                {return PUNCT_PERCENT_COLON;}
\<\:                                {return PUNCT_LESS_COLON;}
\<\%                                {return PUNCT_LESS_PERCENT;}
\:\>                                {return PUNCT_COLON_PERCENT;}
\#\#                                {return PUNCT_HASH_HASH;}
\.\.\.                              {return PUNCT_DOT_DOT_DOT;}
\%\:\%\:                            {return PUNCT_PERCENT_COLON_PERCENT_COLON;}

.                                   {/* No other rule matched. ERROR */}

%%

Built with:

> flex Lexer.l

Note: Not tested.

\$\endgroup\$
1
\$\begingroup\$

Spotted a bug:

while (character == '/' && peekChar() == '/') {
    skipLineComment();
    character = skipWhitespace();
}
while (character == '/' && peekChar() == '*') {
    skipBlockComment();
    character = skipWhitespace();
}

If you get a block comment followed by a line comment then you will hit the rest of the code with a / as the character which will look like a division rather than a comment.

To fix I would do this:

while (character == '/') {
    if (peekChar() == '/') {
        skipLineComment();
        character = skipWhitespace();
    }
    else if (peekChar() == '*') {
        skipBlockComment();
        character = skipWhitespace();
    }
    else {
        break;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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