Unix Programming - any sort of automata impl. or algorithm free of collisions?

Author

any sort of automata impl. or algorithm free of collisions?

Chinlu

2007-07-21, 7:06 pm

Hello,

I've been lately dealing with terminal's keyboard-input. For this I
implemented an nfa as per the thompson's yamada algorithm.

I then converted it to a single row one (so as to save memory and
still being able to keep track of input by means of state no.). It
ended up looking like a linked list chained to a dynamic one-
dimensional array, still it worked.

I also tried isolating curses' "trys" mechanism, which is a binary
tree, it also worked.

Then I though I could use the same construction for a file-parser I
needed so as to be able to recognize keywords, and then got into
troubles.

I found out the previous structures worked just because the first char
was always an escape char (I handle functions keys and single chars
with an nfa and an array respectively).

Even keeping function key's automata separarate from the keywords' one
produces collisions I can't handle, this occurs as soon as different
words can have same first char(s).

Trying to avoid it, I added multiple transitions to my automata, still
I get collisions.

After looking at curses code, I started looking for info on tries, but
I can't find enough of it so as to either, understand it properly and
to implement one to see whether if it could work for this situation in
particular.

So my question is if someone can give me some input on this, is there
any known algorithm out there which could suit me needs to this
regard? I know could just split things appart and make my life easier,
but I'm just curious about this, and how does people use solve it.

Kind Regads,

Chinlu

2007-07-21, 7:06 pm

> produces collisions I can't handle, this occurs as soon as different
> words can have same first char(s).

Sorry, perhaps bad explained throughtout, but there is an error there:
the problem comes when different words have same number of characters,
and hence final states overlap.

For example, this is what happens if I try to intern "hola" and
"cola", where obiously both of them should return different codes,
function/structures pointers or whatever they might be bound to.

The fact that strings are quite similar makes no difference whether a
single or multiple transition-capable machine is behind. Better read
up again on automata.

Perhaps I should have also posted this to comp.lang.c instead, my
fault again.

Regards,

Sponsored Links