I've been enthralled with state machines lately. It's become unhealthy. I don't remember if it started by playing around with lex and yacc, or if it was when I found Mongrel2 and read this post. But from that point on, I've been obsessed with finite state machines, parsers, regular expressions.
Recently, when after a stack overflow question pushed me into hand coding another state machine based parser, I read this blog post, which introduced a method of implementing state machines that I hadn't seen before. I'm sure it's not new. In fact it probably dates back to the era of machine code. But it was new to me, and I like it better than tables or nested conditionals. The basic idea is to break out the code for each state into its own function and then use a function pointer to track the state instead of an enum and switch.
Of course, I couldn't leave well enough alone. I thought I could do one better if I returned the new function pointer instead of storing it in a reference parameter. As it happens, C is a little funny about returning a pointer to a function with the same signature as the function doing the returning... something to do with infinitely recursive type definitions I guess. So the best I could come up with was a struct containing just the function pointer. That doesn't add too much syntactically when calling the functions, and modern compilers optimize it to just returning the function pointer in a register, but returning them becomes a little more unwieldy. You either need to define const structs somewhere (which is no better than enums), declare and define a local struct to be returned (more lines in each function), or restrict to C99 and use compound literals. If you can think of a better way to tackle this, please let me know. Here is how those three look in code.
typedef struct _state state;
struct _state
{
state (*func)(char);
};
state init(char);
state final(char);
#if CONST
const state INIT = {init};
const state FINAL = {final};
#endif
state
init(char input)
{
#if LOCAL
state next;
#endif
switch(input)
{
#if CONST
case 'a':
return FINAL;
default:
return INIT;
#elif LOCAL
case 'a':
next.func = final;
return next;
default:
next.func = init;
return next;
#elif C99
case 'a':
return (state){final};
default:
return (state){init};
#endif;
}
}Here's an example of a simple rpn calculator. I decided to go the route of using const structs, even though it pollutes the global namespace. I did this mainly because it maintains C89 compatibility while requiring less typing than locals or the original design of saving to a reference parameter.
#include <stdio.h>
#include <stack.h>
typedef struct state_ state;
struct state_
{
state (*func)(char);
};
state initial(char);
state number(char);
const state INITIAL = {initial};
const state NUMBER = {number};
const state END;
state
initial(char input)
{
int a;
if(input == 'p')
{
printf("%i\n", pop());
return INITIAL;
}
else if(input == '+')
{
a = pop();
*top() += a;
return INITIAL;
}
else if(input == '*')
{
a = pop();
*top() *= a;
return INITIAL;
}
else if(input >= '0' && input <= '9')
{
ungetc(input, stdin);
push(0);
return NUMBER;
}
else
{
return END;
}
}
state
number(char input)
{
if(input >= '0' && input <= '9')
{
*top() *= 10;
*top() += input - '0';
return NUMBER;
}
else
{
ungetc(input, stdin);
return INITIAL;
}
}
int
main(void)
{
int ch;
state s = INITIAL;
while((ch = getchar()) != EOF && s.func)
{
s = s.func(ch);
}
return 0;
}