Data structure in Python for NFA (regex)? -

i need push in right direction on this.

i trying create class nondeterministic finite automaton (nfa) in python using thompson's algorithm.

i'm not sure how wrap head around how arrange in terms of classes / objects. given nfa, seems clear have "start" , "end" node, , start node can point start node of separate nfa, , end node points our end node, , on.

depending on type of regex being parsed, can link start/end nodes in different ways. , edges can have different symbols!

i have no idea how arrange correctly. need 2 classes, 1 node , 1 state machine? keep start , end pieces? how tell them need "point"? how know referring right node @ given time? how label edges / how store them? python use pointers way, or have keep entirely separate "trees" in each node?

attempt:

class nfa_node():     def __init__(self):         self.type = "epsilon"         self.next = []  class nfa():     def __init__(self):         self.start = nfa_node()         self.end = none         self.start.next.append(self.end) 

(please don't take answer disagreement comments or downvotes. it's indicative of soft spot formal languages.)

suppose start nice wikipedia entry. has these nice diagrams need translate code. so, looking @ first diagrams, can tell there more 1 type. there's symbol node , union node. start off with:

class node(object):     ...  class symbolnode(node):     ...  class unionnode(node):     ... 

and forth.

now each of concrete classes needs method

    def process(self, input, i): 

which processes input @ position i, else need? symbol node needs know symbol, have

class symbolnode(node):     def __init__(self, symbol):         self._symbol = symbol 

the union node needs (let's simplify to) 2 alternatives. these alternatives be? other nodes. we'd have:

class unionnode(node):     def __init__(self, opt_a, opt_b):          self._opt_a, self._opt_b = opt_a, opt_b 

these "pointers" before.

presumably, come need other derived nodes, such composite node encapsulates sequence of nodes, , forth.

your thompson class hold node object well. that's "pointer" again.

---

there many many details fill in. luck. might want check out composite design pattern somewhere.