| 摘要 |
A method and system for direct construction of a minimal deterministic finite state machine corresponding to a regular expression are provided. The method includes providing a regular expression represented as a regular expression tree with nodes of operators and leaves of elementary character transitions and traversing the regular expression tree recursively to build minimal finite state automata (FSAs) corresponding to the branches of the tree, wherein the FSAs end in a specified tail automaton. The operators are concatenation, alternation, and Kleene closure. A concatenation operation is performed by recursive construction in reverse order wherein each automaton built becomes the tail for the preceding argument of the operation. An alternation operation is performed by recursively building automata corresponding to the arguments of the operation with the same tail and merging them. A Kleene closure operation is performed by: building an automaton terminating in a unique marker; merging the automaton with the tail automaton to form a combined automaton; and traversing the combined automaton to expand the marker into transitions and states to achieve the intended behaviour.
|
