5 ms·

I like the article that this post refers to about efficient implementation (https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.htm

by jll29 4y ago

I like the article that this post refers to about efficient implementation (https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html). It mentions a debate between J. Friedl and comp. sci. purists about whether NFAs and regular expressions should really be called what they are in the face of backreferences and other notation. Friedl suggests another name should be used, because de facto "NFAs" are no longer equivalent to DFAs. Since Xerox Research Europe's invention of xfst, the term "extended regular expression" is already taken for a specific superclass of expressions that describe regular relations. So I propose two alternatives, semi-regular expressions and super-regular expressions, for strings that look like regular expressions but that use non-regular extensions like backreferences that push the complexity beyond what can be done with NDAs/DFAs.

kazinator 4y ago
I cannot agree here. The term "regular expression" relates to "regular language". So instead of inventing new words haphazardly, we should look at what kind of language we are able to express with these non-regular expressions, what the name of that language is and then use that name for the expressions. Here is a starting point: where do regular languages sit in the Chomsky hierarchy: https://en.wikipedia.org/wiki/Regular_language#Location_in_the_Chomsky_hierarchy https://en.wikipedia.org/wiki/Regular_language#Location_in_t... Here, we see that there are also less inclusive languages included in regular: finite languages and star-free languages, for which the corresponding "finite expression" and "star-free expression" make sense. In the other direction, maybe some useful language kinds can be identified between "regular" and "context-free" in relation to the capabilities of certain kinds of expressions. However, "context-free expression" isn't a bad start. ("Cfex" [si:fex]?)
Groxx 4y ago
Alternatively: declare that "regex" has graduated into its own proper term (not a contraction) for whatever this evolving somewhat-too-capable-for-easy-classification tool is. It's certainly how it's used colloquially.
- amscanne 4y ago
  The term “regex” is already used interchangeably for both classes. The Go regular expression library (which is widely used) does not support backreferences, and is guaranteed to run in linear time. It seems sillier to say “that’s not a regex” (since it definitely is a regular expression engine), than to say that the others are extended regular expressions or some other, more flexible thing (for better and worse).
anitil 4y ago
I've read that article so many times I knew what it was by seeing the link. The first few times it didn't make sense, and now it seems almost obvious - I can't remember what I was not understanding.
deleted 4y ago
[deleted]
eru 4y ago
What really irks me that there are several useful operations that can be supported by proper regular expressions in linear time, but those franken-expressions never feature them. I am mostly talking about set intersection and complement. But https://en.wikipedia.org/wiki/Regular_language#Closure_properties https://en.wikipedia.org/wiki/Regular_language#Closure_prope... has some more.
- mananaysiempre 4y ago
  Burntsushi (of regex crate / ripgrep fame) is on record saying[1] he thinks those are intractable in a standard DFA implementation on a large alphabet (Unicode), and if he can’t do it, I don’t think there’s much hope for the rest of us :) They are relatively straightforward in derivative-based implementations[2,3], but those are kind of meh performance-wise AFAIU, and just eagerly building the DFA using derivatives[4] yields huge automata. (To be fair, the regex crate can’t match canonically equivalent Unicode strings, which I also think is pretty meh, but I’ve played with Unicode normalization recently and I’m convinced it would be impossible to support canonical equivalence with the same order of magnitude in performance without going through horrible contortions.) [1] https://news.ycombinator.com/item?id=31693008 https://news.ycombinator.com/item?id=31693008 [2] https://news.ycombinator.com/item?id=17652542 https://news.ycombinator.com/item?id=17652542 [3] https://news.ycombinator.com/item?id=8199902 https://news.ycombinator.com/item?id=8199902 [4] https://news.ycombinator.com/item?id=25604829 https://news.ycombinator.com/item?id=25604829
  - burntsushi 4y ago
    > To be fair, the regex crate can’t match canonically equivalent Unicode strings, which I also think is pretty meh Yeah not "meh" at all. :-) I don't think any regex engine can do it? Does icu's regex engine even do it? Certainly no fsm regex engine does. UTS#18 doesn't even ask regex engines to do it. If you need it, it just suggests canonicalizing both the regex and the haystack first. And yes, derivatives build full DFAs. Those are a no-go in a general purpose regex engine. There's also the issue of complement and intersection being somewhat difficult to reason about. I'll also note that I have never given any serious effort to actually trying to implement complement or intersection. I just don't see any viable implememtation path to it in the first place. I don't know where I would start. Everything I cam think of involves extreme compile-time costs that would just be totally unacceptable in a general purpose regex engine. But, I am not really an "ideas" person. I see myself more as an engineer. So my inability should not really be taken for gospel. Be skeptical of expertise. That's the foundation of science. :)
flashgordon 4y ago
Hah this is a classic. I actually used this as a reference to build my own about a year ago in typescript (documentation a long way to go and still WIP) which I am using in a couple of production ready dsls: https://github.com/panyam/tlex https://github.com/panyam/tlex
082349872349872 4y ago
Of those, I'd prefer semi-regular expressions (but personally currently lean towards irregular expressions). As they lose the nice properties, there's certainly nothing "super"-regular about them.
- LudwigNagasena 4y ago
  Super-x may also mean that it has some extra properties wrt x. In fact, it was the original meaning that has drifted to its more common use today. Cf. “hyper” as in “hypersonic”. Both “super” and “hyper” even mean the same thing (“over”/“above”) in their original languages (Latin and Greek respectively).
- catlifeonmars 4y ago
  What about pseudo-regular expressions?

by jll29 4y ago

kazinator 4y ago

I cannot agree here. The term "regular expression" relates to "regular language". So instead of inventing new words haphazardly, we should look at what kind of language we are able to express with these non-regular expressions, what the name of that language is and then use that name for the expressions. Here is a starting point: where do regular languages sit in the Chomsky hierarchy: https://en.wikipedia.org/wiki/Regular_language#Location_in_the_Chomsky_hierarchy https://en.wikipedia.org/wiki/Regular_language#Location_in_t... Here, we see that there are also less inclusive languages included in regular: finite languages and star-free languages, for which the corresponding "finite expression" and "star-free expression" make sense. In the other direction, maybe some useful language kinds can be identified between "regular" and "context-free" in relation to the capabilities of certain kinds of expressions. However, "context-free expression" isn't a bad start. ("Cfex" [si:fex]?)

Groxx 4y ago

Alternatively: declare that "regex" has graduated into its own proper term (not a contraction) for whatever this evolving somewhat-too-capable-for-easy-classification tool is. It's certainly how it's used colloquially.

amscanne 4y ago
The term “regex” is already used interchangeably for both classes. The Go regular expression library (which is widely used) does not support backreferences, and is guaranteed to run in linear time. It seems sillier to say “that’s not a regex” (since it definitely is a regular expression engine), than to say that the others are extended regular expressions or some other, more flexible thing (for better and worse).

anitil 4y ago

I've read that article so many times I knew what it was by seeing the link. The first few times it didn't make sense, and now it seems almost obvious - I can't remember what I was not understanding.

deleted 4y ago

[deleted]

eru 4y ago

What really irks me that there are several useful operations that can be supported by proper regular expressions in linear time, but those franken-expressions never feature them. I am mostly talking about set intersection and complement. But https://en.wikipedia.org/wiki/Regular_language#Closure_properties https://en.wikipedia.org/wiki/Regular_language#Closure_prope... has some more.

mananaysiempre 4y ago
Burntsushi (of regex crate / ripgrep fame) is on record saying[1] he thinks those are intractable in a standard DFA implementation on a large alphabet (Unicode), and if he can’t do it, I don’t think there’s much hope for the rest of us :) They are relatively straightforward in derivative-based implementations[2,3], but those are kind of meh performance-wise AFAIU, and just eagerly building the DFA using derivatives[4] yields huge automata. (To be fair, the regex crate can’t match canonically equivalent Unicode strings, which I also think is pretty meh, but I’ve played with Unicode normalization recently and I’m convinced it would be impossible to support canonical equivalence with the same order of magnitude in performance without going through horrible contortions.) [1] https://news.ycombinator.com/item?id=31693008 https://news.ycombinator.com/item?id=31693008 [2] https://news.ycombinator.com/item?id=17652542 https://news.ycombinator.com/item?id=17652542 [3] https://news.ycombinator.com/item?id=8199902 https://news.ycombinator.com/item?id=8199902 [4] https://news.ycombinator.com/item?id=25604829 https://news.ycombinator.com/item?id=25604829
- burntsushi 4y ago
  > To be fair, the regex crate can’t match canonically equivalent Unicode strings, which I also think is pretty meh Yeah not "meh" at all. :-) I don't think any regex engine can do it? Does icu's regex engine even do it? Certainly no fsm regex engine does. UTS#18 doesn't even ask regex engines to do it. If you need it, it just suggests canonicalizing both the regex and the haystack first. And yes, derivatives build full DFAs. Those are a no-go in a general purpose regex engine. There's also the issue of complement and intersection being somewhat difficult to reason about. I'll also note that I have never given any serious effort to actually trying to implement complement or intersection. I just don't see any viable implememtation path to it in the first place. I don't know where I would start. Everything I cam think of involves extreme compile-time costs that would just be totally unacceptable in a general purpose regex engine. But, I am not really an "ideas" person. I see myself more as an engineer. So my inability should not really be taken for gospel. Be skeptical of expertise. That's the foundation of science. :)

flashgordon 4y ago

Hah this is a classic. I actually used this as a reference to build my own about a year ago in typescript (documentation a long way to go and still WIP) which I am using in a couple of production ready dsls: https://github.com/panyam/tlex https://github.com/panyam/tlex

082349872349872 4y ago

Of those, I'd prefer semi-regular expressions (but personally currently lean towards irregular expressions). As they lose the nice properties, there's certainly nothing "super"-regular about them.

LudwigNagasena 4y ago
Super-x may also mean that it has some extra properties wrt x. In fact, it was the original meaning that has drifted to its more common use today. Cf. “hyper” as in “hypersonic”. Both “super” and “hyper” even mean the same thing (“over”/“above”) in their original languages (Latin and Greek respectively).
catlifeonmars 4y ago
What about pseudo-regular expressions?