7
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Is "-5" a valid token? That is, can plus and minus be used as sign indicators? \$\endgroup\$ – JS1 Oct 3 '16 at 6:19
  • 1
    \$\begingroup\$ Why don't you wrap malloc and realloc since the only operations when they fail is to exit with failure? \$\endgroup\$ – Siyuan Ren Oct 3 '16 at 11:46
  • \$\begingroup\$ -5 is a valid token but is malformed, same with .5. Kind of weird, I know. As for why I didn't wrap malloc and realloc, I'm not sure. It should have been obvious to me. Thank you for pointing it out. \$\endgroup\$ – JRTN Oct 3 '16 at 17:02
  • \$\begingroup\$ How's about endowing your states with meaningful names, such as FLOAT_INT for the integer part of a float and FLOAT_FRAC for its fractional part? \$\endgroup\$ – Ant_222 Feb 17 '18 at 14:00
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Awesome, thanks! Allocating in chunks makes a lot more sense, and I didn't realize that realloc could shrink an array. \$\endgroup\$ – JRTN Oct 3 '16 at 17:11
  • \$\begingroup\$ Regarding your “Don't Repeat Yourself (DRY)” section, I wholeheartedly disagree. Early-outs are a powerful way to simplify logic and make it more readible— a set of checks and returns early in a function is far easier to understand than nested sets of indentation. The OP's usage of earlying-out here is a substantially justified one— it says “in the rare case that this API call doesn't work, then abort; otherwise continue on with the logic this function is designed to carry out”. \$\endgroup\$ – Slipp D. Thompson Oct 5 '16 at 11:40
  • \$\begingroup\$ Returning NULL instead of tokenizer is a smart move too— computationally they do the same thing, but the presence of “NULL” in the code makes it far more human-readable. I'll argue the intent here isn't to “return the invalid value returned from malloc() but rather to ”return NULL if asked to TKCreate and for any reason we can't” (even though it's the same computational data either way). Clearly expressing intent to other human grokkers of your code is paramount to good development. Finally, you're abusing the term “DRY”. This is not un-DRY, it's just semantically verbose. \$\endgroup\$ – Slipp D. Thompson Oct 5 '16 at 11:47

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.