Efficient data-driven finite state machine In creating this answer to a recent question, I thought I might write a fully worked example that implements a finite state machine in C.  

The purpose is to implement the following function:


  Given a const char *, search for a string conforming to the pattern WWWDD where WWW is one of { "Mon", "Tue", "Wed, "Thu", "Fri", "Sat", "Sun" } and DD is an integer in the range \$[1, 31]\$ (inclusive).  If the pattern exists within the string, return the offset; otherwise return -1.


I implemented this state machine: using simple table structure.  This is the code, which includes a simple driver with test vectors.

#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;ctype.h&gt;

static const struct fsmNode {
    const char target;
    const struct fsmNode *next;
} fsm[] = {
    { 'T' , &amp;fsm[6] },    // 0
    { 'M' , &amp;fsm[9] },    // 1
    { 'S' , &amp;fsm[11] },   // 2
    { 'W' , &amp;fsm[12] },   // 3
    { 'F' , &amp;fsm[14] },   // 4
    { '\0' , NULL },      // 5
    // second letter
    { 'h' , &amp;fsm[18] },   // 6
    { 'u' , &amp;fsm[20] },   // 7
    { '\0' , NULL },      // 8
    { 'o' , &amp;fsm[22] },   // 9
    { '\0' , NULL },      // 10
    { 'a' , &amp;fsm[24] },   // 11
    { 'u' , &amp;fsm[22] },   // 12
    { '\0' , NULL },      // 13
    { 'e' , &amp;fsm[26] },   // 14
    { '\0' , NULL },      // 15
    { 'r' , &amp;fsm[27] },   // 16
    { '\0' , NULL },      // 17
    // third letter
    { 'u' , &amp;fsm[30] },   // 18
    { '\0' , NULL },      // 19
    { 'e' , &amp;fsm[30] },   // 20
    { '\0' , NULL },      // 21
    { 'n' , &amp;fsm[30] },   // 22
    { '\0' , NULL },      // 23
    { 't' , &amp;fsm[30] },   // 24
    { '\0' , NULL },      // 25
    { 'd' , &amp;fsm[30] },   // 26
    { '\0' , NULL },      // 27
    { 'i' , &amp;fsm[30] },   // 28
    { '\0' , NULL },      // 29
    // first digit
    { '0' , &amp;fsm[36] },   // 30
    { '1' , &amp;fsm[35] },   // 31
    { '2' , &amp;fsm[35] },   // 32
    { '3' , &amp;fsm[46] },   // 33
    { '\0' , NULL },      // 34
    // second digit
    { '0' , NULL },       // 35
    { '1' , NULL },       // 36
    { '2' , NULL },       // 37
    { '3' , NULL },       // 38
    { '4' , NULL },       // 39
    { '5' , NULL },       // 40
    { '6' , NULL },       // 41
    { '7' , NULL },       // 42
    { '8' , NULL },       // 43
    { '9' , NULL },       // 44
    { '\0' , NULL },      // 45
    { '0' , NULL },       // 46
    { '1' , NULL },       // 47
    { '\0' , NULL },      // 48
};

int findWeekdayDate(const char *str) {
    const struct fsmNode *state = fsm;
    const char *curr;
    for (curr = str ; *curr; ++curr) {
        for ( ; state-&gt;target &amp;&amp; *curr != state-&gt;target; ++state) 
        { /* do nothing */ }
        if (state-&gt;next == NULL) {
            if (state-&gt;target) {
                // found a valid string
                return curr-str-4;  
            } else {
                state = fsm;
            }
        } else {
            state = state-&gt;next;
        }
    }
    return -1;
}

// Test code follows...
static const struct test_s {
    const char *string;
    int expected;
} test[] = {
    { "abcSun24Def", 3},
    { "abcMun24Def", -1},
    { "abcSun091", 3},
    { "MON31", -1},
    { "Mon31", 0},
    { NULL, -1 }    // last item
};

#include &lt;stdio.h&gt;

#define RED    "\033[31m"
#define GREEN  "\033[32m"
#define WHITE  "\033[39m"

int main() {
    for (size_t i=0; test[i].string != NULL; ++i) {
        int val = findWeekdayDate(test[i].string);
        printf("%s: \"%s\", expected %d, got %d\n", 
            (val == test[i].expected ? GREEN " OK" WHITE: RED "BAD" WHITE),
            test[i].string, test[i].expected, val
            );
    }
}


Comments on efficiency, style, performance, data structure choice and implementation are all of interest.
Nice work.


On findWeekdayDate() return, I'd expect a value that is enumerated like fWD_SUCCESS, fWD_FAIL, fWD_SUCCESS_for_foo_reason, fWD_FAIL_for_bar_reason, etc. Rather than magic numbers -1,0,3,....  It could end up being a simple bool.
As fsm[] is const struct fsmNode, I see no value in making a field const like const char target.  char target is simpler and sufficient.  OTOH, if there is some value, then next should also be const as in const struct fsmNode * const next.
Delay/remove #includes.

#include &lt;string.h&gt;  // Needed?
#include &lt;stdlib.h&gt;  // OK, for NULL
#include &lt;ctype.h&gt;   // Needed?

Style inconsistency.  Recommend empty for body to match other indentations.  

// for ( ; state-&gt;target &amp;&amp; *curr != state-&gt;target; ++state) 
//{ /* do nothing */ }
for ( ; state-&gt;target &amp;&amp; *curr != state-&gt;target; ++state) {
  /* do nothing */
}

Use an auto formatter.  The extra space betrays manual formatting as it is inconsistent with the rest of code.  Life is too short for manual formatting.

//             v
for (curr = str ; *curr; ++curr) {



Suggest adding link to software used to create FSM.