TaggedNFA

A tagged, non-deterministic finite state automata (NFA) is an abstract computing machine that recognises regular languages. In layman’s terms, they are used to decide whether a string matches a regular expression. The “tagged” part means that the NFA can do group-capture: it returns information about which parts of a string matched which subgroup of the regular expression.

The latest version (0.1.1, released January 2011) can be obtained from:

The development version is hosted in the same git repository as PredictiveMode. Note that the git repository URL is a git repository, not a web-site. You cannot view it in a web browser. To grab the latest development version, clone the repository using:

  git clone http://www.dr-qubit.org/git/predictive.git

Why re-implement regular expression matching when Emacs comes with extensive built-in support for RegularExpressions? Primarily, because some algorithms require access to the NFA states produced part way through the regular expression matching process (see Tries for an example). Secondarily, because Emacs regexps only work on strings, whereas regular expressions can equally well be used to specify other sequence types.

Note that Emacs’ regexps are not regular expressions in the original meaning of that phrase. Emacs regexps implement additional features (in particular, back-references) that allow them to match far more than just regular languages. This comes at a cost: regexp matching can potentially be very slow (NP-hard!), whereas there are efficient (polynomial-time) algorithms for matching regular expressions (in the original sense). Therefore, this package only supports a subset of the full Emacs regular expression syntax. (Read the docstrings for more information.)

This package essentially implements Laurikari’s algorithm, as described in his master's thesis, but it builds the corresponding tagged deterministic finite state automaton (DFA) on-the-fly as needed. See also RussCox?online article for more about NFAs, DFAs, and regular expression matching.

Please send bug reports and suggestions to toby-predictive@dr-qubit.org (you can post them here as well if you like, of course). I don’t check this page regularly, so anything not emailed to me is likely to languish here unnoticed for some time.

--TobyCubitt


CategoryCode CategoryExtensions