Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

The question itself is already in the title, so here I will just provide additional details.

I call a regular expression "deterministic", if, after converting the regular expression into a nondeterministic finite automaton in the obvious way, the result is already a deterministic finite automaton, without performing an explicit nondeterminism removal procedure.

For example:

  • Deterministic: ab(cb)*
  • Nondeterministic: a(bc)*b

I never use nondeterministic regular expressions. In particular, this means that matching my regular expressions never requires backtracking.

I want a regular expression implementation that is explicitly designed to handle deterministic regular expressions, and takes advantage of them in order to match character streams that must be read sequentially, such as C++'s std::istreams. My preferred languages are Haskell, Standard ML, Rust and C++11, although I am open to suggestions for any statically typed languages.

share|improve this question

closed as off-topic by gnat, Bart van Ingen Schenau, GlenH7, World Engineer Apr 12 '14 at 17:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – gnat, Bart van Ingen Schenau, GlenH7, World Engineer
If this question can be reworded to fit the rules in the help center, please edit the question.

Regular expressions, strictly understood, are always deterministic: for each input, either they match or else they don't. Engines to compute that answer can be DFA or NFA or various intermediate solutions. DFAs are rare because they offer no good way of doing many of the additional things programmers want from regexes, e.g. subgroup extraction. Where this isn't needed, DFAs are in fact common, e.g. with grep. –  Kilian Foth Dec 16 '13 at 13:32
@KilianFoth: I edited my question to clarify what I mean by "determinstic regular expression". Also, I want an implementation that I can conveniently use in a conventional statically typed programming language, which grep is clearly not. –  Eduardo León Dec 16 '13 at 13:39
Hmmm, interesting. I don't think there is a well-established short term for "regex that does not require backtracking to evaluate", but "deterministic" will probably give many readers the wrong idea if they read only the question title, because they'll think it's about the engine type. –  Kilian Foth Dec 16 '13 at 13:43
@KilianFoth: If you come up with a better title, feel free to edit my question. :-) –  Eduardo León Dec 16 '13 at 13:49
@delnan: OTOH, the NFA to DFA transformation is a lot harder, and this is why I write regular expressions whose NFAs are guaranteed to be DFAs without performing any transformation. –  Eduardo León Dec 16 '13 at 18:31

1 Answer 1

This doesn't directly answer your question, but Russ Cox calls these "one-pass regular expressions." Given such a regexp, it's possible to implement an optimization where an NFA simulation only takes "one pass" (i.e., never backs up), which means you don't have to do as much work tracking capture groups. Here's what he has to say:

Let's define a “one-pass regular expression” to be a regular expression with the property that at each input byte during an anchored match, there is only one alternative that makes sense for a given input byte. For example, x*yx* is one-pass: you read x's until a y, then you read the y, then you keep reading x's. At no point do you have to guess what to do or back up and try a different guess. On the other hand, x*x is not one-pass: when you're looking at an input x, it's not clear whether you should use it to extend the x* or as the final x. More examples: ([^x])x(.) is one-pass; (.)x(.) is not. (\d+)-(\d+) is one-pass; (\d+).(\d+) is not.

As far as I know, this optimization is implemented in both RE2/C++ and RE2/Go.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.