Oops sorry, Powerset algo is actually O(n*2^n) time complexity
On Sat, 3 Apr 2021, 13:49 Artur Vianna, wrote:
> An interesting approach would be the implementation of a regex engine that
> has optimizations just like a compiler (i think the stdlib one does that to
> an extent). Using powerset
An interesting approach would be the implementation of a regex engine that
has optimizations just like a compiler (i think the stdlib one does that to
an extent). Using powerset and hopcroft's where it can be used and leaving
backtracks where it can't.
That would be fun to implement but very
In *my* ideal world, both O(n) and backtracking implementations would be
available in the standard library.
Most popular languages have only backtracking versions in their standard
libraries (Java, Python, Ruby). It's nice that Go has an O(n)
implementation. But, some regexes that can be
*Some people, when confronted with a problem, think "I know, I'll use
regular expressions." Now they have two problems.*
I would tend to agree with this statement. Regular expressions are much
abused and over-used in situations where
simpler parsing techniques would be more appropriate. Beyond
You can try my regexp2 engine that's based on the .NET engine:
https://github.com/dlclark/regexp2
It supports atomic groups, has no dependencies, and doesn't need cgo.
Unfortunately it doesn't support Possessive Quantifier syntax, but
supposedly that may be serving as syntactic sugar for
I have nothing useful to contribute to this discussion, however, I've been
doing this long enough to remember Jamie Zawinski's quote about regular
expressions :)
Some people, when confronted with a problem, think "I know, I'll use
> regular expressions." Now they have two problems.
>
Worth mentioning Russ Cox's series of blog posts on Regular Expressions
and their implementation https://swtch.com/~rsc/regexp/
On Thursday, 1 April 2021 at 21:21:14 UTC+1 Brian Candler wrote:
> If you can live with cgo dependencies, then you might want to look at a go
> wrapper around PCRE,
If you can live with cgo dependencies, then you might want to look at a go
wrapper around PCRE, which is the "go-to" implementation for fully-featured
regexps.
e.g. https://github.com/rubrikinc/go-pcre (untested by me, and it's one of
several forks)
--
You received this message because you
