Package lepl :: Package regexp :: Module core :: Class NfaToDfa
[hide private]
[frames] | no frames]

Class NfaToDfa

source code


Convert a NFA graph to a DFA graph (uses the usual superset approach but does combination of states in a way that seems to fit better with the idea of character ranges).
Instance Methods [hide private]
 
__init__(self, nfa, alphabet)
x.__init__(...) initializes x; see help(type(x)) for signature
source code
 
__build_graph(self)
This is the driver for the "usual" superset algorithm - we find all states that correspond to a DFA state, then look at transitions to other states.
source code
 
__fragment_transitions(self, nfa_nodes)
From the given nodes we can accumulate the destination nodes and terminals associated with each transition (edge/character).
source code
 
__add_groups(self, src, groups, stack)
The target nfa nodes identified above are now used to create dfa nodes.
source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Static Methods [hide private]
 
__group_fragments(fragments)
For each fragment, we for the complete set of possible destinations and associated terminals.
source code
Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, nfa, alphabet)
(Constructor)

source code 
x.__init__(...) initializes x; see help(type(x)) for signature
Overrides: object.__init__
(inherited documentation)

__build_graph(self)

source code 
This is the driver for the "usual" superset algorithm - we find all states that correspond to a DFA state, then look at transitions to other states. This repeats until we have covered all the different combinations of NFA states that could occur.

__fragment_transitions(self, nfa_nodes)

source code 
From the given nodes we can accumulate the destination nodes and terminals associated with each transition (edge/character). At the same time we separate the character matches into non-overlapping fragments.

__group_fragments(fragments)
Static Method

source code 
For each fragment, we for the complete set of possible destinations and associated terminals. Since it is possible that more than one fragment will lead to the same set of target nodes we group all related fragments together.