Parse 2D matrix, 2 versions

Question

I'm writing a little C program that computes matrices (for learning purpose). The matrix is fed through arguments in the following form : "{{43,543.324,34},{43,432,87}}" The user doesn't give the dimensions.

I have solved this problem two times in two different ways:

1. Short series of entangled if / else / mess
2. Kind of a state machine doing one task at a time, much longer

Here they are, the first one is commented and the second one follows:

int matrix_fill(matrix * A, char * input)
{
    size_t i, j;
    float val;

/*
    size_t input_len = strlen(input);
    if (input[0] != '{' || input[input_len - 1] != '}') {
        errno = EINVAL;
        perror("matrix_fill");
        exit(-1);
    }

    input[input_len - 1] = '\0';
    input++, input_len -= 2;

    i = 0;
    while (*input != '\0') {
        printf("input: %s\n", input);
        j = 0;

        if (*input == '{') {
            input++;

            while (1) {

                val = strtof(input, &input);
                printf("(%d,%d) = %f\n", i, j, val);
                matrix_set(A, i, j, val);
                j++;

                if (*input == ',')
                    input++;

                else if (*input == '}')
                    break;

                else {

                }
            }

            i++, input++;
            A->m = i, A->n = j;
        }

        else if (*input == ',') {
            input++;
        }

        else {
            errno = EINVAL;
            perror("matrix_fill");
            exit(-1);
        }
    }
*/

    enum {
        start,
        open,
        read,
        delim,
        close,
        end
    } status = start;

    while (*input != '\0') {

        switch (status) {
        case start:
            if (*input != '{' || *(input + 1) != '{') {
                errno = EINVAL;
                goto error;
            }

            i = 0, input++;
            status = open;
            break; 

        case open:
            j = 0, input++;
            status = read;
            break;

        case read:
            val = strtof(input, &input);
            if (errno < 0) goto error;

            matrix_set(A, i, j, val);
            j++;

            if (*input == ',')
                status = delim;

            else if (*input == '}')
                status = close;

            else {
                errno = EINVAL;
                goto error;
            }

            break;

        case delim:
            input++;

            if (*input == '{')
                status = open;

            else 
                status = read;

            break;

        case close:
            input++;

            if (*input == ',')
                status = delim;

            else if (*input == '}')
                status = end;

            else {
                errno = EINVAL;
                goto error;
            }

            i++;
            break;

        case end:
            input++;
            A->m = i, A->n = j;

            break;
        }
    }

    return 0;

error:
    perror("matrix_fill");
    return -1;
}

Points I would like you to examine:

• Use of goto
• Length of the code
• Clarity
• Complexity of the solution vs complexity of the problem

I have had good results with both, but there might still be bugs. I'm more interested in your opinion about the design than the correctness.

Answer 1

Using a state machine is generally a very elegant way to parse input. This is actually how parsers generated by YACC or Bison work, and it's also how lexical analysers generated by LEX work. It allows the parsing to be more flexible.

Generally the variable names you used are quite descriptive and makes the code easier to use, the one exception is naming the matrix A.

Things That Would Have Improved This Question
It would have been much easier to review this question if the following had been provided: 1. The definition of the struct matrix. 2. The header files necessary (stdio.h, stdlib.h, strings.h and errno.h). 3. If the 2 different versions of matrix_fill() had been separated and included as matrix_fill1() and matrix_fill2(). 4. If the program had been compiled using -Wall and all warnings addressed prior to asking.

I have included the reformated code that allowed me to compile at the end of my answer to show what would have made this a better question and easier to answer.

During development of code it is a good idea to compilte the code with -Wall compiler switch so that all warnings are reported. The warning can also be treated as errors. The type size_t is not completely compatible with the printf() statements in the commented out algorithm:
Parse2DMatrix.c:142: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘size_t’
Parse2DMatrix.c:142: warning: format ‘%d’ expects type ‘int’, but argument 3 has type ‘size_t’

The matrix struct should be presented so that we could have suggested possible error handling, there are times when i or j may cause memory access problems because they are outside the scope of the matrix.

The choice of types is interesting, I would have used double instead of float, and unsigned int instead of size_t.

Error Reporting
Rather than using errno.h and perror() for this portion of the code it would have been better if there was an internal error handling mechanism providing a better description of the errors. Invalid argument is a little too general, "Missing { at start of expression" might have been more meaningful.

Exit Versus Return
Calling exit(-1) does not allow the code to clean up after itself, returning an error value allows the calling code to clean up any allocated memory and reset all items that need to be reset. If this code was part of an operating system or a daemon that calling exit() is actually not an option because you wouldn't want the system to crash.

Switch Statement Without Default Case
There should always be a default: case in a switch statement to handle unknown/undefined behavior. In this specific instance rather than having a goto in case of errors the default: case could have been used to handle the errors on the next iteration through the loop. There could be one additional enum value in the enum, error could be a status type.

Enum Coding Standards
It would be better to call attention to the enumerators in the ENUM, and follow general C Coding Standards (UCSD has published this coding standard). By making the enumerators ALL_CAPITALS the code would be clearer and show that these are defined someplace.

It is possible that the status/state might be used elsewhere so it would be better to define the enum type outside the function, and possibly in a header file.

A better way to define the enum would probably be:

typedef status { START, OPEN, READ, DELIM, CLOSE, END, ERROR} Status;

I would probably call the variable status state since that is what it is really being for.

Alternative Implementation For The State Machine
YACC, BISON and LEX generate tables (matricies) for transition from one state to another. One possible alternate implementation of the state machine is to have an array of function pointers. Another possible implementation is to use the current state as an index into an array of the next state (how YACC, BISON and LEX are implemented).

White Space
The parsing algorithm does not allow for white space. Handling white space would be easy to add and allows the user of the program to make the input more readable. There are a number of ways to implement check on white space. One possibility is to have matrix_fill() be only a parser and have it run a lexical analysing function that tokenizes the input. Note: This assumes that the buffer char *input has not been previously processed to remove white space.

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <errno.h>

typedef struct Matrix {
    size_t m;
    size_t n;
    float values[20][20];
} matrix;

int matrix_set(matrix *A, size_t i, size_t j, float val)
{
    int error = 0;

    /* Algorithm not specified */

    return error;
}

int matrix_fill2(matrix *A, char *input)
{
    size_t i, j;
    float val;


    enum {
        start,
        open,
        read,
        delim,
        close,
        end
    } status = start;

    while (*input != '\0') {

        switch (status) {
        case start:
            if (*input != '{' || *(input + 1) != '{') {
                errno = EINVAL;
                goto error;
            }

            i = 0, input++;
            status = open;
            break; 

        case open:
            j = 0, input++;
            status = read;
            break;

        case read:
            val = strtof(input, &input);
            if (errno < 0) goto error;

            matrix_set(A, i, j, val);
            j++;

            if (*input == ',')
                status = delim;

            else if (*input == '}')
                status = close;

            else {
                errno = EINVAL;
                goto error;
            }

            break;

        case delim:
            input++;

            if (*input == '{')
                status = open;

            else 
                status = read;

            break;

        case close:
            input++;

            if (*input == ',')
                status = delim;

            else if (*input == '}')
                status = end;

            else {
                errno = EINVAL;
                goto error;
            }

            i++;
            break;

        case end:
            input++;
            A->m = i, A->n = j;

            break;
        }
    }

    return 0;

error:
    perror("matrix_fill");
    return -1;
}

int matrix_fill1(matrix * A, char * input)
{
    size_t i, j;
    float val;
    int error = 0;

    size_t input_len = strlen(input);
    if (input[0] != '{' || input[input_len - 1] != '}') {
        errno = EINVAL;
        perror("matrix_fill");
        exit(-1);
    }

    input[input_len - 1] = '\0';
    input++, input_len -= 2;

    i = 0;
    while (*input != '\0') {
        printf("input: %s\n", input);
        j = 0;

        if (*input == '{') {
            input++;

            while (1) {

                val = strtof(input, &input);
                printf("(%d,%d) = %f\n", i, j, val);
                matrix_set(A, i, j, val);
                j++;

                if (*input == ',')
                    input++;

                else if (*input == '}')
                    break;

                else {

                }
            }

            i++, input++;
            A->m = i, A->n = j;
        }

        else if (*input == ',') {
            input++;
        }

        else {
            errno = EINVAL;
            perror("matrix_fill");
            exit(-1);
        }
    }
    return error;
}

Answer 2

I see a number of things that may help you improve your code.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used.

Don't abuse the comma operator

This line doesn't really need a comma operator:

i = 0, input++;

It should instead be two separate statements.

i = 0;
++input;

Follow language convention

Multidimensional arrays in C use row-major order, and the typical use would be something like mat[i][j] in code. However, this code reverses that and uses i and j in the opposite order, with j being the row index and i being the column index. This is counter-intuitive to anyone familiar with C, so you should change your code to follow the convention.

Add better error handling

Right now, the syntax doesn't really care how big the lines are, so the effect of this line of code:

matrix_fill(&one, "{{1,2,3},{4,5,6},{7}}");

Is that matrix one would have dimensions of 1x3. Since the code for matrix_set was not provided, there's no way for me to predict which values might actually be stored. Also, the value of A passed in is dereferenced without checking its value. If it's NULL, this program will crash.

Use const where practical

The current code takes a char *input as input, but it doesn't (and shouldn't) alter that passed string. This should be amended so that the declaration is:

int matrix_fill(matrix * A, const char *input)

This also means that there should be a change to the way strtof() is called. Instead of using this:

val = strtof(input, &input);

Use this:

char *stringtail;

/* ... */
val = strtof(input, &stringtail);
input = stringtail;

Take care with nan and inf

The strtof function can properly handle nan and inf numbers, so it's prudent to assure that your code can also deal with them correctly and gracefully. As an example, this is a valid line of input: "{{1,2,3},{4,5,6},{-7e-5,-INF,NAN}}"

Consider eliminating goto

It's not strictly wrong, but it's also not strictly necessary to use goto in this code. In fact, it seems to me that the code would be clearer and a little shorter if instead there were an explicit error state added to the state machine.

Write code that is clear to humans

The state machine version is much easier to understand and follow than the other version, so I'd much prefer to work on the state machine version.

Consider making the code more data-driven

There are only four different kinds of "tokens" used by this program: a number, '{', '}' and ','. This suggests that a small table could easily represent all transitions. Here's one way to do that:

int matrix_fill(matrix * A, const char *input)
{
    size_t i, j;
    float val;
    char *stringtail;


    enum { start, open, read, delim, close, end, error } state = start;

    // We're looking for the following chars "{},"
    int transition[][4] = {
        // num    '{'    '}'    ','
        { error, open,  error, error },   // start
        { error, read,  error, error },   // open
        { delim, error, close, error },   // read
        { error, error, close, read  },   // delim
        { error, error, error, open  },   // close
    };

    int thischar;
    while (*input != '\0') {
        switch (*input) {
            case '{':
                thischar = 1;
                ++input;
                break;
            case '}':
                thischar = 2;
                ++input;
                break;
            case ',':
                thischar = 3;
                ++input;
                break;
            default:
                thischar = 0;
        }
        switch (state) {
        case start:
            i = 0;
            break; 

        case open:
            j = 0; 
            break;

        case read:
            if (thischar == 0) {
                val = strtof(input, &stringtail);
                input = stringtail;
                if (errno < 0) {
                    state = error;
                } else {
                    matrix_set(A, i, j, val);
                    ++j;
                }
            } 
            break;

        case delim:
            break;

        case close:
            ++i;
            break;

        case end:
            printf("Setting dims:[%lu, %lu]\n", i,j);
            A->m = i, A->n = j;
            return 0;
            break;
        case error:
            if (errno >= 0) 
                errno = EINVAL;
            perror("matrix_fill");
            return -1;
        }
        state = transition[state][thischar];
    }
    return 0;
}

Consider using parser generator tools

If I were writing code like this, I would use flex and bison (or equivalently lex and yacc). There are many resources available for these tools. Here is one such resource.

Answer 3

A couple suggestions:

1. Why not accept the inner lists as separate parameters? This would simplify parsing. With multiple matrices, maybe have a delimiter (an operation, perhaps).
2. I think multiple functions, each handling a state in the machine would make the code much more readable. That would get rid of the gotos.

Otherwise, I think the code is fine.