state machines
Here's a cool trick I stumbled upon for writing state machines. Works in C, and many other languages.
Each state is a function, and it returns the next state (also a function).
To run the state machine, you can use a loop similar to this: "while(!done) { state = state(); }"
Here's an example for a state machine to parse the regular expression "(ab)*c"
/* (ab)*c.c */
#include "stdio.h"
//state machine types (C won't let you do a self-referential typedef, so wraping it in a struct is necessary)
typedef struct state state;
typedef state state_fn(int c);
struct state { state_fn* fn; };
//pre-declare the states
state_fn s_init, s_a, s_c, s_ok, s_fail;
//implement the states
state s_init(int c) {
switch(c) {
case 'a': return (state){s_a};
case 'c': return (state){s_c};
default: return (state){s_fail};
}
}
state s_fail(int c) {
return (state){s_fail};
}
state s_ok(int c) {
return (state){s_fail};
}
state s_a(int c) {
switch(c) {
case 'b': return (state){s_init};
default: return (state){s_fail};
}
}
state s_c(int c) {
switch(c) {
case '\n': return (state){s_ok};
default: return (state){s_fail};
}
}
int main(int argc, char** argv) {
//initialize
state s = (state){s_init};
//run
for(int c; (c=getchar()) >= 0;) {
s = s.fn(c);
}
//check if it's in accepting state (and negate, because unix 0 is true)
return s.fn != s_ok;
}
compile:
gcc "(ab)*c.c" -o "(ab)*c"
run:
$ echo "ac" | "./(ab)*c" && echo "yes" || echo "no"
no
$ echo "abc" | "./(ab)*c" && echo "yes" || echo "no"
yes
$ echo "c" | "./(ab)*c" && echo "yes" || echo "no"
yes
$ echo "xyz" | "./(ab)*c" && echo "yes" || echo "no"
no