5 ms·
The Power of PCRE Regular Expressions (2012)
- plesner 11y agoAlternative title: the true danger of conflating regular expressions and backtracking pattern matchers. I wonder if it would be possible to reintroduce that distinction.
- igravious 11y agobacktracking, i.e. utilizes a stack, i.e. more powerful than a regular (language) pattern matcher. Alternative title: you can use regex derivatives (PCRE, Ruby ::Regexp, Boost.Regex, ...) to match non-regular syntax but you shouldn't. The advice still holds. In the case of HTML you should reach for an XML parser.
- Veedrac 11y agoI think the warning should be parsing complex domains with regex libraries, not a restriction to regular syntaxes. There are simple cases where backtracking (or some other extension) plus regex makes sense. Something like (\w+) \d+ \1 is simpler as a regex than any other common tool available.
- nmrm2 11y ago> Alternative title: you can use regex derivatives... This is particularly confusing because you mean "derivative" in the sense of "etymologically/conceptually related", but there is actually a (formal) notion of the derivative of a regular expression.
- deleted 11y ago[deleted]
- alipang 11y agoI've never understood the software engineering community's desire to call PCREs regular expressions simply because it has similar syntax to "formal" regular expressions. There is good reason to distinguish the two, since they have completely different characteristics. PCREs may use an unbounded amount of extra memory, and may use exponential time. "Formal" regular expressions take linear time and memory, and can match only the regular languages. They operate completely differently (a regular automation vs. a stack based pattern matcher). Regular expressions can NOT match HTML, PCREs CAN. Conflating the two is not helpful.
- treve 11y agoIf you are really wondering, PCRE means perl-compatible regular expressions. That may have something to do with it.
- burntsushi 11y ago> They operate completely differently (a regular automation vs. a stack based pattern matcher). It's more exciting than this actually! An implementation of formal regexes doesn't have to simulate an automaton explicitly. In fact, it can also use backtracking and keep its linear running time. Such an implementation would use an explicit stack and also keeps track of each state that has been visited for a particular position in the search text. If a state has already been visited, then it doesn't repeat itself. A backtracking implementation can be faster than a full NFA simulation if: 1) you need to track submatch boundaries, 2) you have a small regex and 3) you have small input. (2) and (3) are necessary because of the memory required to keep track of the states you've visited (proportional to len(regex) * len(search text)). (1) is necessary because you could otherwise use a DFA, which AFAIK, does not typically track submatch boundaries. Tracking submatch boundaries in a backtracking implementation is faster than simulating an NFA automaton because you only need to keep one copy of the capture locations around at any point in time. The NFA simulation has to copy them around a lot. (Of the regex implementations that guarantee linear running time, C++'s RE2, Go's `regexp` and now Rust's `regex` all implement a bounded backtracking algorithm... among others!)
- haneefmubarak 11y agoPart of it may be that "pee cee are eey" (or less commonly, "picker", "picker eey", etc.) doesn't really sound as nice as "regex". Also, PCRE does stand for "Perl Compatible Regular Expression".
- deleted 11y ago[deleted]
- nmadden 11y agoActually, "plain" regular expressions/FSAs can parse HTML up to any arbitrary finite nesting depth (i.e. all those you will ever encounter in practice). The trade-off is that they need exponentially more states to do so than an equivalent CFG/pushdown automata. For example the a^n b^n example can be recognised up to n<=3 by the RE ^(|ab|aabb|aaabbb)$.
- mpu 11y agoGood job on the 3-SAT encoding, it was very clear.
- dang 11y agoOk, we added "PCRE" to the title to satisfy the unsatisfied. Though now it's like "PIN number".
- JadeNB 11y agoI wrote about a different approach (via the SKI combinator calculus and Rule 110) on PerlMonks: http://www.perlmonks.org/?node_id=809842 http://www.perlmonks.org/?node_id=809842 .