Implementation of tokenizer object and finite state machine in C

Question

I was given an assignment to create an implementation of a tokenizer object (by object, I mean a struct with associated functions that operate on instances of the struct). This tokenizer retrieves tokens from an input string given the following rules:

1. The input string cannot be changed

2. Tokens can only contain digits 0-9, hex digits, E and e, X and x, +, -, and periods(.).

3. Tokens are delimited by white space

4. If a character that is not a delimiter or a valid token character is encountered in the input string, a message containing its ASCII and hexadecimal representation is printed.

The program then uses the tokenizer object to retrieve tokens from an input string and classify them as zero, integer, float, octal, hexadecimal, or malformed. The classification is done using a finite state machine.

This is my first C program so I'd like pointers on where I could improve.

(And to ease any worries about cheating, this assignment was due September 29 and has already been turned in)

Code:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef enum {
    STATE_A,        STATE_B,      STATE_C,
    STATE_D,        STATE_E,      STATE_F,
    STATE_G,        STATE_H,      STATE_I,
    STATE_J,        STATE_ENTRY,
    STATE_DECIMAL,  STATE_FLOAT,  STATE_OCTAL,  STATE_HEXADECIMAL,  STATE_MALFORMED, STATE_ZERO
} state_t;

static char *classifications[] = {"Decimal", "Float", "Octal", "Hexadecimal", "Malformed", "Zero"};

static state_t A(char *);  static state_t B(char *); static state_t C(char *);
static state_t D(char *);  static state_t E(char *); static state_t F(char *);
static state_t G(char *);  static state_t H(char *); static state_t I(char *);
static state_t J(char *);  static state_t entryState(char *);

typedef state_t (state_func)(char *);
static state_func *STATE_FUNCTIONS[] = {A, B, C, D, E, F, G, H, I, J, entryState};

struct TokenizerT_ {
    char *current;
};
typedef struct TokenizerT_ TokenizerT;

int isoctal(int c) {
    return c >= '0' && c <= '7';
}

static void failedToAllocateMemory() {
    printf("\nFailed to allocate memory. Program is exiting.");
    exit(EXIT_FAILURE);
}

state_t entryState(char *token) {
    if (*token == '0') {
        return STATE_A;
    } else if (isdigit(*token)) {
        return STATE_B;
    } else {
        return STATE_MALFORMED;
    }
}

state_t A(char *token) {
    if (!*token) { //Token is 0
        return STATE_ZERO;
    } else if (isoctal(*token)) {
        return STATE_C;
    } else if (tolower(*token) == 'x') {
        return STATE_D;
    } else if (*token == '.') {
        return STATE_E;
    } else {
        return STATE_MALFORMED;
    }
}

state_t B(char *token) {
    if (!*token) {
        return STATE_DECIMAL;
    } else if (isdigit(*token)) {
        return STATE_B;
    } else if (*token == '.') {
        return STATE_E;
    } else if (tolower(*token) == 'e') {
        return STATE_H;
    } else {
        return STATE_MALFORMED;
    }
}

state_t C(char *token) {
    if (!*token) {
        return STATE_OCTAL;
    } else if (isoctal(*token)) {
        return STATE_C;
    } else {
        return STATE_MALFORMED;
    }
}

state_t D(char *token) {
    if (isxdigit(*token)) {
        return STATE_F;
    } else {
        return STATE_MALFORMED;
    }
}

state_t E(char *token) {
    if (isdigit(*token)) {
        return STATE_G;
    } else {
        return STATE_MALFORMED;
    }
}

state_t F(char *token) {
    if (!*token) {
        return STATE_HEXADECIMAL;
    } else if (isxdigit(*token)) {
        return STATE_F;
    } else {
        return STATE_MALFORMED;
    }
}

state_t G(char *token) {
    if (!*token) {
        return STATE_FLOAT;
    } else if (isdigit(*token)) {
        return STATE_G;
    } else if (tolower(*token) == 'e') {
        return STATE_H;
    } else {
        return STATE_MALFORMED;
    }
}

state_t H(char *token) {
    if (isdigit(*token)) {
        return STATE_J;
    } else if (*token == '+' || *token == '-') {
        return STATE_I;
    } else {
        return STATE_MALFORMED;
    }
}

state_t I(char *token) {
    if (isdigit(*token)) {
        return STATE_J;
    } else {
        return STATE_MALFORMED;
    }
}

state_t J(char *token) {
    if (!*token) {
        return STATE_FLOAT;
    } else if (isdigit(*token)) {
        return STATE_J;
    } else {
        return STATE_MALFORMED;
    }
}

static void notifyUnexpectedSymbol(char c) {
    printf("\nUnexpected symbol '%c' [%#02X] in input string", c, c);
}

static int isValidTokenCharacter(char c) {
    return isdigit(c) || isxdigit(c) || c == '+' || c == '-' || c == '.' || tolower(c) == 'x' || tolower(c) == 'e';
}

static char *buildToken(TokenizerT *tk) {
    size_t size = 0;
    char *token = malloc(1);
    if (!token) {
        failedToAllocateMemory();
    }
    while (*tk->current && !isspace(*tk->current)) {
        if (isValidTokenCharacter(*tk->current)) {
            size++;
            token = realloc(token, size);
            if (!token) {
                failedToAllocateMemory();
            }
            token[size - 1] = *tk->current;
        } else {
            notifyUnexpectedSymbol(*tk->current);
        }
        tk->current++;
    }
    token = realloc(token, size + 1);
    if (!token) {
        failedToAllocateMemory();
    }
    token[size] = '\0';
    return token;
}

char *TKGetNextToken(TokenizerT *tk) {
    int space_c = 0;
    int valid_c = 0;
    while (*tk->current && ( (space_c = isspace(*tk->current)) || !(valid_c = isValidTokenCharacter(*tk->current)) )) {
        if (!valid_c && !space_c) {
            notifyUnexpectedSymbol(*tk->current);
        }
        tk->current++;
    }
    if (!*tk->current) {
        return NULL;
    }
    return buildToken(tk);
}

static int isFinalState(state_t st) {
    return st >= STATE_DECIMAL;
}

void classifyTokens(TokenizerT *tk) {
    char *token;
    while ((token = TKGetNextToken(tk))) {
        char *cp = token;
        state_t currentState = STATE_ENTRY;
        while (!isFinalState(currentState)) {
            currentState = STATE_FUNCTIONS[currentState](cp++);
        }
        printf("\n%-11s %s", classifications[currentState - STATE_DECIMAL], token);
        free(token);
    }
}

TokenizerT *TKCreate(char *ts) {
    TokenizerT *tokenizer = malloc(sizeof(TokenizerT));
    if (!tokenizer) {
        return NULL;
    }
    tokenizer->current = ts;
    return tokenizer;
}

void TKDestroy(TokenizerT *tk) {
    free(tk);
}

int main(int argc, char **argv) {
    if (argc < 2) {
        printf("\nOne argument must be provided.\n");
    } else {
        TokenizerT *tok = TKCreate(argv[1]);
        if(!tok) {
            failedToAllocateMemory();
        }
        classifyTokens(tok);
        TKDestroy(tok);
    }
    return 0;
}

Answer 1

Don't Repeat Yourself (DRY)

    TokenizerT *tokenizer = malloc(sizeof(TokenizerT));
    if (!tokenizer) {
        return NULL;
    }
    tokenizer->current = ts;
    return tokenizer;

So if tokenizer is NULL, you return NULL. If not, you return tokenizer. Consider

    TokenizerT *tokenizer = malloc(sizeof *tokenizer);

    if (tokenizer) {
        tokenizer->current = ts;
    }

    return tokenizer;

This flips the logic. If tokenizer is not NULL, we can set members to values. And we return tokenizer whether it is NULL or not. This gives us the same results with fewer statements.

I changed from sizeof(TokenizerT) to sizeof *tokenizer so that even if you change the type, it will still have the right size.

Don't allocate memory constantly

    char *token = malloc(1);

Since every token string is at least one character plus a null, this will never be right.

    size_t capacity = CHUNK_SIZE;
    char *token = malloc(capacity);

This might be correct. At least we are no longer guaranteed to be wrong.

Then later you have

            size++;
            token = realloc(token, size);
            if (!token) {
                failedToAllocateMemory();
            }

Instead consider

            size++;
            if (size >= capacity) {
                capacity += CHUNK_SIZE;
                token = realloc(token, capacity);
                if (!token) {
                    failedToAllocateMemory();
                }
            }

This only attempts to allocate memory if it needs to do so.

    token = realloc(token, size + 1);

This could be

    if (size + 1 != capacity) {
        token = realloc(token, size + 1);
    }

This will shrink the array to fit if necessary.

Anything less than CHUNK_SIZE, this version does two allocations. The original always did two, so this is never worse. At CHUNK_SIZE, this actually only does one allocation, because it doesn't need to shrink the array afterwards. And of course, the original does size + 2 allocations.

Another alternative would be to scan the token string twice. The first time, you find out how long the token is. The second time, you allocate memory (once) and copy the token over.