Lexer for a language I'm working on

Question

I've recently started working on making my own programming language and I just wrapped up its lexer. I'm too young to take any official training in C, compiler construction, or computer science so I'm having mixed feelings in the quality of my code. It seems rather sluggish when printing but I haven't really found out the time it takes from start to finish. I'm using Visual Studio 2015 and C11 I believe (if I'm not VS is stupid).

Here is an example of the grammar:int (#nested comment # double nest?? *# *#

int meme) {
    double v_a-r = 10.2123 + 200 * 1.;
    #symbol testing; also, comment!!!
    {} [] () - + * / -= += *= /= ^ %
    return var;
}

I included the token header instead of the lexer header because the Lexerc type should be fairly obvious and I didn't want to scare anyone off with more code than there already is.

Token.h

#include "token.h"
#include "lexer.h"
#include <stdlib.h>
#include <stdio.h>

token_t* token_new(lexer_t* lexer, tk_type type) {
    token_t* token = malloc(sizeof(token_t));
    token->line = lexer->line;
    token->pos = lexer->pos;
    token->type = type;

    return token;
}

void token_print(token_t* token) {
    printf("\ntype: %i", token->line);
    printf("\tline: %i", token->line);
    printf("\tpos: %i", token->pos);

    if (token->type == _int)
        printf("\tint val: %i", token->num);
    else if (token->type == _dbl)
        printf("\tflt val: %d", token->flt);
    else
        printf("\tstr val: %s", token->str);
}

void token_free(token_t* token) {
    if (token->str != NULL)
        free(token->str);
    free(token->str);
}

Lexer.c:

#define _CRT_SECURE_NO_WARNINGS 
#define DEBUG 1

#include "error.h"
#include "token.h"
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>
#include <string.h>

static const keyword_t keywords[] = {
    // Primitive data types
    {"int", _int},  
    {"double", _dbl},
    {"enum", _enum},
    {"void", _void},
    {"char", _char},
    {"string", _str},
    {"bool", _bool},
    {"const", _const},
    {"struct", _struct},

    // keywords
    {"import", _import},
    {"while", _while},
    {"for", _for},
    {"break", _break},
    {"match", _match},
    {"case", _case},
    {"return", _return},
    {"if", _const},
    {"else", _else},
    {"false", _false},
    {"true", _true},

    {"MAC", _mac}
};

static bool can_adv(lexer_t* lexer, size_t steps) {
    return (lexer->ptr + steps <= lexer->len);
}

static keyword_t* is_keyword(char* str) {
    for (const keyword_t* word = keywords; word->word != NULL; word++)
        if (!strcmp(str, word->word))
            return word;

    return NULL;
}

static void new_line(lexer_t* lexer) {
    lexer->line++;
    lexer->pos = 0;
}

static char lexer_look(lexer_t* lexer, size_t ahead) {
    if (lexer->len < lexer->ptr + ahead) 
        return;
    return lexer->src[lexer->ptr + ahead];
}

static char lexer_adv(lexer_t* lexer, size_t steps) {
    if (!can_adv(lexer, steps)) {
        printf("Attempt to advance past src boundries.");
        getchar();
    }
    lexer->pos += steps;
    lexer->ptr += steps;
    return lexer->src[lexer->ptr];
}

static void lexer_nested(lexer_t* lexer) {
    char c = lexer_look(lexer, 0);
    size_t depth = 1;

    lexer_adv(lexer, 2);

    while (depth > 0) {
        if (!can_adv(lexer, 1))
            error_new(lexer->errors, lexer->line, lexer->pos, "Unterminated block comment.");
        else if (c == '*' && lexer_look(lexer, 1) == '#') {
            lexer_adv(lexer, 2);
            depth--;
        } else if (c == '#' && lexer_look(lexer, 1) == '*') {
            lexer_adv(lexer, 2);
            depth++;
        } else
            c = lexer_adv(lexer, 1);
    }
}

static void lexer_comment(lexer_t* lexer) {
    if (lexer_look(lexer, 1) == '*')
        lexer_nested(lexer);
    else {
        char c;
        while (((c = lexer_look(lexer, 0)) != '\n') && can_adv(lexer, 1))
            lexer_adv(lexer, 1);
        new_line(lexer);
    }
}

static token_t* lexer_str(lexer_t* lexer) {
    size_t str_len = 0;

    while (true) {
        if (!can_adv(lexer, 1)) {
            error_new(lexer->errors, lexer->len, lexer->pos, "Unterminated str.");
            return NULL;
        } else if (lexer_look(lexer, 1) == '\"') {
            lexer_adv(lexer, 2);
            break;
        } else {
            lexer_adv(lexer, 1);
            str_len++;
        }
    }

    char* str = malloc(str_len + 1);
    for (size_t idx = 0; idx < str_len; idx++)
        str[idx] = lexer->src[lexer->ptr - str_len + idx];
    str[str_len] = '\0';

    token_t* token = token_new(lexer, _str);
    token->str = str;
    return token;
}

static token_t* lexer_float(lexer_t* lexer, token_t* token, size_t v) {
    token->type = _flt_rep;

    if (!isdigit(lexer_look(lexer, 0))) {
        token->flt = (double)v;
        token->num = 0;
        return token;
    }

    double places = 10;
    double dbl = 0;

    while (can_adv(lexer, 1)) {
        char c = lexer_look(lexer, 0);

        if (isdigit(c)) {
            dbl += (c - '0') / places;
            lexer_adv(lexer, 1);
            places *= 10;
        }
        else
            break;
    }

    token->flt = v + dbl;
    return token;
}

static token_t* lexer_num(lexer_t* lexer) {
    token_t* token = token_new(lexer, _int_rep);
    unsigned int v = 0;

    while (can_adv(lexer, 1)) {
        char c = lexer_look(lexer, 0);

        if (isdigit(c)) {
            v = (v * 10) + (c - '0');
            lexer_adv(lexer, 1);
        } else if (c == '.') {
            lexer_adv(lexer, 1);
            return lexer_float(lexer, token, v);
        } else {
            break;
        }
    }

    token->num = v;
    return token;
}

static token_t* lexer_keyword(lexer_t* lexer, char* str) {
    keyword_t* word = is_keyword(str);

    if (word != NULL) {
        token_t* token = token_new(lexer, word->type);
        token->str = word->word;
    }

    return NULL;
}

static token_t* lexer_ident(lexer_t* lexer) {
    token_t* token = token_new(lexer, _ident);
    size_t id_len = 0;

    while (can_adv(lexer, 1)) {
        if (!isalpha(lexer_look(lexer, 0)))
            break;

        lexer_adv(lexer, 1);
        id_len++;
    }

    char* ident = malloc(id_len + 1);
    for (size_t idx = 0; idx < id_len; idx++)
        ident[idx] = lexer->src[lexer->ptr - id_len + idx];
    ident[id_len] = '\0';

    if (is_keyword(ident))
        return lexer_keyword(lexer, ident);

    token->str = ident;
    return token;
}

token_t* next_token(lexer_t* lexer) {
    token_t* token = NULL;

    while (token == NULL && can_adv(lexer, 1)) {
        const int c = lexer_look(lexer, 0);

        if (DEBUG)
            printf("Current character: \"%c\", Length: %d, Pointer: %d \n", lexer_look(lexer, 0), lexer->len, lexer->ptr);

        switch (c) {
        case '=':
            if (lexer_look(lexer, 1) == '=') {
                token = token_new(lexer, _eqto);
                lexer_adv(lexer, 2);
                token->str = "==";
            }
            else {
                token = token_new(lexer, _assign);
                token->str = "=";
                lexer_adv(lexer, 1);
            }

            break;
        case '+':
            if (lexer_look(lexer, 1) == '=') {
                token = token_new(lexer, _addeql);
                lexer_adv(lexer, 2);
                token->str = "+=";
            }
            else {
                token = token_new(lexer, _add);
                token->str = "+";
                lexer_adv(lexer, 1);
            }

            break;
        case '-':
            if (lexer_look(lexer, 1) == '=') {
                token = token_new(lexer, _subeql);
                lexer_adv(lexer, 2);
                token->str = "-=";
            }
            else {
                token = token_new(lexer, _sub);
                token->str = "-";
                lexer_adv(lexer, 1);
            }

            break;
        case '*':
            if (lexer_look(lexer, 1) == '=') {
                token = token_new(lexer, _muleql);
                lexer_adv(lexer, 2);
                token->str = "*=";
            }
            else {
                token = token_new(lexer, _mul);
                token->str = "*";
                lexer_adv(lexer, 1);
            }

            break;
        case '/':
            if (lexer_look(lexer, 1) == '=') {
                token = token_new(lexer, _diveql);
                lexer_adv(lexer, 2);
                token->str = "/=";
            }
            else {
                token = token_new(lexer, _div);
                token->str = "/";
                lexer_adv(lexer, 1);
            }

            break;
        case '<':
            if (lexer_look(lexer, 1) == '<') {
                token = token_new(lexer, _nteq);
                lexer_adv(lexer, 2);
                token->str = "<=";
            }
            else {
                token = token_new(lexer, _bang);
                token->str = "<";
                lexer_adv(lexer, 1);
            }

            break;
        case '>':
            if (lexer_look(lexer, 1) == '<') {
                token = token_new(lexer, _nteq);
                lexer_adv(lexer, 2);
                token->str = ">=";
            }
            else {
                token = token_new(lexer, _bang);
                token->str = ">";
                lexer_adv(lexer, 1);
            }

            break;
        case '&':
            if (lexer_look(lexer, 1) == '&') {
                token = token_new(lexer, _and);
                lexer_adv(lexer, 2);
                token->str = "&&";
            }
            else {
                token = token_new(lexer, _notype);
                lexer_adv(lexer, 1);
            }

            break;
        case '|':
            if (lexer_look(lexer, 1) == '|') {
                token = token_new(lexer, _or);
                lexer_adv(lexer, 2);
                token->str = "||";
            }
            else {
                token = token_new(lexer, _notype);
                lexer_adv(lexer, 1);
            }

            break;
        case '%':
            token = token_new(lexer, _mod);
            token->str = "%";
            lexer_adv(lexer, 1);
            break;
        case '^':
            token = token_new(lexer, _mod);
            token->str = "^";
            lexer_adv(lexer, 1);
            break;
        case '!':
            if (lexer_look(lexer, 1) == '=') {
                token = token_new(lexer, _nteq);
                lexer_adv(lexer, 2);
                token->str = "!=";
            }
            else {
                token = token_new(lexer, _bang);
                token->str = "!";
                lexer_adv(lexer, 1);
            }

            break;
        case '\"':
            token = lexer_str(lexer);
            break;
        case '#':
            lexer_comment(lexer);
            break;
        case '(':
            token = token_new(lexer, _lpara);
            token->str = "(";
            lexer_adv(lexer, 1);
            break;
        case ')':
            token = token_new(lexer, _rpara);
            token->str = ")";
            lexer_adv(lexer, 1);
            break;
        case '{':
            token = token_new(lexer, _lcurl);
            token->str = "{";
            lexer_adv(lexer, 1);
            break;
        case '}':
            token = token_new(lexer, _rcurl);
            token->str = "}";
            lexer_adv(lexer, 1);
            break;
        case '[':
            token = token_new(lexer, _lbrac);
            token->str = "[";
            lexer_adv(lexer, 1);
            break;
        case ']':
            token = token_new(lexer, _rbrac);
            token->str = "]";
            lexer_adv(lexer, 1);
            break;
        case ';':
            token = token_new(lexer, _terml);
            token->str = ";";
            lexer_adv(lexer, 1);
            break;
        default:
            if (isalpha(c) || c == '_')
                token = lexer_ident(lexer);
            else if (isdigit(c) || c == '.') {
                token = lexer_num(lexer);
            }
            else if (isspace(c)) {
                if (c == '\n')
                    new_line(lexer);

                lexer_adv(lexer, 1);
            }
            else
                token = token_new(lexer, _eof);

            break;
        }
    }

    return token;
}

void lexer_print(lexer_t* lexer) {
    size_t line = lexer->line;
    size_t pos = lexer->pos;
    size_t ptr = lexer->ptr;
    token_t* token = next_token(lexer);

    while (token != NULL && token->type != _eof) {
        token_print(token);
        token = next_token(lexer);
    }

    lexer->ptr = ptr;
    lexer->pos = pos;
}

lexer_t* lexer_open(const char* file_name) {
    FILE* file_ptr = fopen(file_name, "rb");
    lexer_t* lexer = malloc(sizeof(lexer_t));
    lexer->errors = errorlist_new();
    lexer->line = 1;
    lexer->pos = 0;
    lexer->ptr = 0;

    if (file_ptr == NULL) {
        error_new(lexer->errors, 0, 0, "Couldent open file \"%s\".\n", file_name);
        free(lexer);
        return;
    }

    if (fseek(file_ptr, 0, SEEK_END) != 0) {
        fclose(file_ptr);
        return NULL;
    }

    lexer->len = ftell(file_ptr);
    if (lexer->len == -1) {
        error_new(lexer->errors, 0, 0, "Unable to get the size of file \"%s\".\n", file_name);
        fclose(file_ptr);
        free(lexer);
    }
    fseek(file_ptr, 0, SEEK_SET);

    lexer->src = malloc(lexer->len);
    size_t r = fread(lexer->src, lexer->len, 1, file_ptr);
    fclose(file_ptr);
    return lexer;
}

void lexer_close(lexer_t* lexer) {
    if (lexer->src != NULL)
        free(lexer->src);

    free(lexer);
}

You can track this code here.

Answer 1

It is very hard to review a lexer without formal definition of the language (honestly, I have very vague understanding how the nested comments are supposed to be structured). However, even without such definition, certain things are surely bugs. For example, in

    case '%':
        token = token_new(lexer, _mod);
        token->str = "%";
        lexer_adv(lexer, 1);
        break;
    case '^':
        token = token_new(lexer, _mod);
        token->str = "^";
        lexer_adv(lexer, 1);
        break;

only the first case should create a _mod token. The

    case '>':
        if (lexer_look(lexer, 1) == '<') {

also looks extremely suspicious.

In general, instead of huge (and very error prone) case statement it is recommended to extend the keywords table with operators and punctuation (make sure that long operators come before short ones), and loop over it same way you do for keywords.

---

I presume token.h is really token.c. An actual token.h with a token_t definition is missing.

---

I don't see how token_free is called, but I expect problems. It blindly attempts to free(token->str), even though some token strings have not been allocated, but point to string literals.

At the same time you may notice that a textual representation of a keyword, operator, or punctuation adds zero information to a token (it can be trivially recovered from the token type), and for them you can safely make token->str a null pointer.

---

You should get a warning for a non-void function returning without a value:

static char lexer_look(lexer_t* lexer, size_t ahead) {
    if (lexer->len < lexer->ptr + ahead) 
        return;
    return lexer->src[lexer->ptr + ahead];
}