Hacker News Reader

Comment by WildUtah | Hacker News Reader

All regexes run in O(N) where N is the length of the string matched.

But some regex engines accept non-regular expressions. [0] The usual notation for it is an escaped number: \1 or \2 or so on. They're used to refer back to capturing groups earlier in the expression, usually marked by parentheses.

Regular expressions don't have backreferences but various enhanced expressions add them. If you use those extensions, you are in danger of exponential execution time unless you are careful and know what you're doing. In particular you should know not to use regular expressions as your principal tool to build a parser.

[0]https://en.wikipedia.org/wiki/Chomsky_hierarchy

View on HN

It's worth pointing out that if you're using a regex engine that only uses backtracking, then you can't assume all regular expressions take linear time. For example, running `(a)c` against `aaaaaaaaaa` takes exponential time in the number of `a` characters even though it is regular.

A hybrid regular expression engine could, in theory, recognize that a particular expression is regular and therefore use a finite state machine to guarantee linear time and space execution (where the size of the regex is held constant).

But unfortunately, converting a non-deteministic finite automaton (i.e., regexp) to a deterministic finite automaton (i.e., engine that can do matches in linear time) may take exponential time and/or space.

Yet, I should add, flex does that with extraordinary success. Most grammars are not that bad, it seems.

Executing an NFA on search text takes linear time and space, so what I said is true. ;-) In practice, it is hard to make NFA execution as fast as backtracking engines. (PCRE famously implements an NFA, calls it a DFA, and uses that to declare that the DFA engine is slow, which is incredibly misleading.[1] Thank you, Mr. Friedl. sigh)

Production grade regex engines with a DFA (like GNU grep, RE2 and Rust's) do conversion lazily. By doing it lazily, at most one new DFA state is added for each byte in the input in the worst case, which maintains the linear time bound. Unfortunately, this can result in memory growth proportional to the search text, which is why all such implementations use a fixed-size cache of states that is flushed once it's full. It works well in practice, but can slow down dramatically (to about the speed of an NFA) if the cache of states needs to be flushed frequently. The most common provoker of such behavior is large counted repetitions, e.g., `\pL{100}`.

[1] - http://pcre.org/current/doc/html/pcre2matching.html#SEC4

How do you escape an asterisk on HN? Other than

  (a*)*c

which seems to work.

Reply on news.ycombinator.com