Module core

source code

A simple regular expression engine in pure Python.

This takes a set of regular expressions (only the most basic functionality is supported) and generates a finite state machines that can match them against a stream of values.

Although simple (and slow compared to a C version), it has some advantages from being implemented in Python.

• It can use a variety of alphabets - it is not restricted to strings. It could, for example, match lists of integers, or sequences of tokens.
• The NFA implementation can yield intermediate matches.
• It is extensible.

The classes here form a layered series of representations for regular expressions.

The first layer contains the classes Sequence, Option, Repeat, Choice, Labelled and Regexp. These are a high level representation that will typically be constructed by an alphabet-specific parser.

The second layer encodes the regular expression as a non-deterministic finite automaton (NFA) with empty transitions. This is a "natural" representation of the transitions that can be generated by the first layer.

The third layer encodes the regular expression as a deterministic finite automaton (DFA). This is a more "machine friendly" representation that allows for more efficient matching. It is generated by transforming a representation from the second layer.