fsm

[luserXtrog]

Hello all,

I've hacked up a little fsm pattern matcher and hit a wall.
I'm not sure what's wrong with it (semantically), but hope
someone can spot something.

TIA

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void fatal(char *msg) {
fprintf(stderr,"%s\n",msg);
exit(EXIT_FAILURE);
}

typedef struct fsm {
int match;
int (*on_yes)(int);
struct fsm *yes;
struct fsm *no;
} fsm;

fsm *fsm_new() {
fsm *f;
if ((f=malloc(sizeof*f)) == NULL) {
fatal("malloc");
}
f->on_yes = NULL;
f->yes = NULL;
f->no = NULL;
}

fsm *fsm_string (char *s) {
fsm *fh, **ft;
fh = fsm_new();
ft = &fh;
for ( ;*s;s++) {
(*ft)->match = *s;
(*ft)->yes = fsm_new();
ft = &(*ft)->yes;
}
return fh;
}

int fsm_match(fsm *f, char *s) {
while (1)
if (f->match == *s) {
if (f->on_yes) (*f->on_yes)(*s);
if (f->yes) f = f->yes;
else return true;
} else {
if (f->no) f = f->no;
else return false;
}
}

int main() {
fsm *f;
printf("fsm_match(fsm_string(\"foo\"),\"foo\") : %d\n",
fsm_match(f = fsm_string("foo"), "foo") );
return 0;
}

 

[luserXtrog]

Hello all,

I've hacked up a little fsm pattern matcher and hit a wall.
I'm not sure what's wrong with it (semantically), but hope
someone can spot something.

I'm a dunce.

TIA

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void fatal(char *msg) {
    fprintf(stderr,"%s\n",msg);
    exit(EXIT_FAILURE);

}

typedef struct fsm {
    int match;
    int (*on_yes)(int);
    struct fsm *yes;
    struct fsm *no;

} fsm;

fsm *fsm_new() {
    fsm *f;
    if ((f=malloc(sizeof*f)) == NULL) {
        fatal("malloc");
    }
    f->on_yes = NULL;
    f->yes = NULL;
    f->no = NULL;

}

fsm *fsm_string (char *s) {
    fsm *fh, **ft;
    fh = fsm_new();
    ft = &fh;
    for ( ;*s;s++) {
        (*ft)->match = *s;
        (*ft)->yes = fsm_new();
        ft = &(*ft)->yes;
    }
    return fh;

}

int fsm_match(fsm *f, char *s) {
    while (1)
        if (f->match == *s) {
            if (f->on_yes) (*f->on_yes)(*s);
            if (f->yes) f = f->yes;
            else return true;

s++;

        } else {
            if (f->no) f = f->no;
            else return false;
        }

}

int main() {
    fsm *f;
    printf("fsm_match(fsm_string(\"foo\"),\"foo\") : %d\n",
        fsm_match(f = fsm_string("foo"), "foo") );
    return 0;

}

Apologies for any inconvenience.

 

[Barry Schwarz]

I'm a dunce.

We all are. It's only a question of frequency.

Doesn't your compiler complain that you reached the end of a non-void
function and never returned the required value.?

What does the double indirection buy you? If you changed ft to type
fsm* and

delete the & and

changed (*ft) to ft and

ditto and

replace with
ft = ft->yes;
you achieve the same result more efficiently and easier to type and
read.

It is not a problem (the types are compatible) but the function is
defined to take an int and you pass a char. Is there some reason you
want the argument converted? On the other hand, the if is never true
so it may not matter.

Style-wise, a ten line while loop without braces just sucks.

 

[luserXtrog]

We all are.  It's only a question of frequency.






Doesn't your compiler complain that you reached the end of a non-void
function and never returned the required value.?

No, it didn't (gcc, no special options). Now I truly surprised that
it appeared to work.

What does the double indirection buy you?  

Now that you mention it, I see no benefit at all.
Thanks for the missed-a-spot.

If you changed ft to type
fsm* and


delete the & and


changed (*ft) to ft and


ditto and


 replace with
    ft = ft->yes;
you achieve the same result more efficiently and easier to type and
read.

Yes, totally. I suppose I must have been thinking that the tail
was more transient than the head and needed to be more detached.
Had I noticed that, as rvalues, (*ft) was everywhere and ft nowhere
I might have realized that simplification was in order.

It is not a problem (the types are compatible) but the function is
defined to take an int and you pass a char.  Is there some reason you
want the argument converted?  On the other hand, the if is never true
so it may not matter.

It's there for future extending, and takes an int value following the
example of the standard library functions. It's conceivable that I may
want to run it against a file and match EOF competently. As int is
supposed to be the "natural" integer type, I didn't seeem likely to
be less efficient by any worthwhile measure than char.

Style-wise, a ten line while loop without braces just sucks.

Roger that. My fingers did it, not me.

Thanks again.

 

[Barry Schwarz]

No, it didn't (gcc, no special options). Now I truly surprised that
it appeared to work.

The behavior is undefined (6.9.1-12). One of the most insidious
manifestations of undefined behavior is to appear to work as expected.

 

[luserXtrog]

On Sun, 23 Aug 2009 15:14:07 -0700 (PDT), luserXtrog






The behavior is undefined (6.9.1-12).  One of the most insidious
manifestations of undefined behavior is to appear to work as expected.

Yes. My guess is that the implicit return defaults to whatever is
present in the automatic emmory area, which just happened to be
the variable I had intended to return. Not pretty.

 

[Mark]

No, it didn't (gcc, no special options). Now I truly surprised that
it appeared to work.

gcc-4.1.1 with "-W -Wall" does.

 

[Noob]

gcc-4.1.1 with "-W -Wall" does [warn].

I think -W was renamed -Wextra some time ago.

 

[luserXtrog]

gcc-4.1.1 with "-W -Wall" does.

Well I actually invoke cc with make.
I just create a foo.c file, and run 'make foo'.
So my fix is to add this line to my .bashrc:

export MAKEFLAGS='CFLAGS+=-Wall'

That should help.

--
4 8 15 16 23 42
The sequence of 'cursed' numbers from lost.
23 and 42 kinda fit.
and 4 and 8 is nice little beginning (Here comes the bride).
but I have no idea what the 15 is for.

 

[David Thompson]

It's UB if the caller uses (attempts to use) the nonexistent return
value, which is the case in the code upthread, but not always, which
is why a compiler can't just make this an outright error. As already
noted elsethread, it is an optional warning in gcc.

Yes. My guess is that the implicit return defaults to whatever is
present in the automatic emmory area, which just happened to be
the variable I had intended to return. Not pretty.

For many platforms, it is whatever is leftover in a certain register,
on >=386 namely EAX. In that routine f is the only registerable value
so you have a durn good chance it is the accidental return value,
though the standard doesn't guarantee it, nor does any impl doc I've
seen including gcc.