For example, this means that there can be a start node supposedly.
Having a value of 0. It is pointing to node 1 with the value of "a"
and to node 2 with the value of "b". Trying to make something like an
NFA. Where id be changing regular expressions to NFAs.
John has already pointed out the preconception problems of
"linked list".
In the past, I've done NFA with a state machine:
(STATE_A,
STATE_B,
STATE_C,
STATE_D,
) = range(4)
transitions = {
# values are tuples of (newstate, transition_function)
STATE_A: [
(STATE_B, lambda x: x > 5),
(STATE_C, lambda x: x > 10),
(STATE_D, lambda x: x > 100),
],
STATE_B: [
(STATE_A, lambda x: x < 5),
(STATE_C, lambda x: x > 10),
],
STATE_C: [
(STATE_B, lambda x: x < 10),
(STATE_D, lambda x: x > 100),
],
STATE_D: [],
}
You may have to carry around extra information regarding your
state, and tweak accordingly. Instead of tuples of (newstate,
transition_function), you could just use transition functions
that return the new state, or None if they're not satisfied.
You then simply maintain your current state, and then test your
incoming stream of tokens/data against your transition function
to see if you can transition to the resulting state. Depending
on whether you need back-tracking, you'll want to gather all the
possible results, or otherwise may just settle for the first
available transition to a new state.
-tkc
--
http://mail.python.org/mailman/listinfo/python-list
