7 ms·

I'm not sure if any regex library exposes this, but since regular languages are closed over compliment and intersection you could theoretically do something lik

I'm not sure if any regex library exposes this, but since regular languages are closed over compliment and intersection you could theoretically do something like match("....string..", regex("Tarzan") - regex("\"Tarzan\"")), where the - operation is shorthand for intersection with the compliment. Does anyone know if any regex libraries expose these sorts of operations on the regular expression/underlying DFA?

sixo 5y ago
Not exactly that but take a look at https://github.com/mtrencseni/rxe https://github.com/mtrencseni/rxe ("literate regex"). I found this on HN and recall the comment thread being good but I can't find it now.
- sodality2 5y ago
  This perhaps? second result on hn.algolia.com. https://news.ycombinator.com/item?id=20646174 https://news.ycombinator.com/item?id=20646174
amenghra 5y ago
Greenery (python3) let’s you manipulate regular expressions and do things like compute intersections: https://github.com/qntm/greenery https://github.com/qntm/greenery
- miloignis 5y ago
  This is exactly the type of thing I was thinking of, and seems quite fully featured - thank you!
codeflo 5y ago
Unfortunately (or perhaps fortunately), “regexes” as commonly implemented in programming languages are only loosely related to regular expressions from automata theory. With all their extensions, they can recognize much, much more than just regular languages, and I don’t think they’re closed under complement (though I’m not sure). However, most regex engines have a feature called negative lookahead assertions, (?!do not match), which would almost work in the way you suggest. You have to be careful about inputs like this though: “Inside a string”Tarzan”Again inside a string”
- User23 5y ago
  Yeah, a DFA that recognizes a regular language can easily be implemented with O(n) worst case behavior. My attitude is generally that one should use regexes for matching regular languages and if one needs a stack or even Turing completeness then handle that in code around the regex.
contravariant 5y ago
Wouldn't that end up just being the same as 'regex(Tarzan)'? Those regexes can't match the same thing, they can only overlap. What you want is something like all matches of regex("Tarzan") not contained in a match for regex("\"Tarzan\""), which is a bit trickier. That would require something like: regex("Tarzan") - all-substrings(regex("\"Tarzan\"")) and I'm not sure regular languages are closed over the "all-substrings" operation. Actually I'm pretty sure they aren't.
layer8 5y ago
> compliment I’ll take that as a complement.
- taneq 5y ago
  "It's a complement... NOT" - Borat.
kazinator 5y ago
Intersection with the complement will not work here. Because the idea is to match Tarzan, but only if it is not preceded and followed by a quote. Regex intersection and complement do not perform look-behind or trailing context. Live demo: This is the TXR Lisp interactive listener of TXR 265. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. TXR may be used in areas that are not necessarily well ventilated. 1> [#/Tarzan&~"Tarzan"/ "Jane shouted, \"Tarzan\""] "Tarzan" 2> [#/Tarzan&~"Tarzan"/ "Jane shouted, \"Tarzan!\""] "Tarzan" The &~"Tarzan" makes absolutely no difference. The reason is that Tarzan matches exactly one string. The complement ~"Tarzan" matches a whole countable infinity of strings, and one of those is Tarzan. The intersection of that infinity and Tarzan is therefore Tarzan. Intersection with complement is useful like this: Search for a three-character substring that is not cat: 3> [#/...&~cat/ "hat"] "hat" 4> [#/...&~cat/ "dog"] "dog" 5> [#/...&~cat/ "doggy" "dog" 6> [#/...&~cat/ "cat"] nil 7> [#/...&~cat/ "scatter"] "sca" 8> [#/...&~cat/ "catalan"] ;; "cat" is skipped, then "ata" works. "ata"

sixo 5y ago

Not exactly that but take a look at https://github.com/mtrencseni/rxe https://github.com/mtrencseni/rxe ("literate regex"). I found this on HN and recall the comment thread being good but I can't find it now.

sodality2 5y ago
This perhaps? second result on hn.algolia.com. https://news.ycombinator.com/item?id=20646174 https://news.ycombinator.com/item?id=20646174

amenghra 5y ago

Greenery (python3) let’s you manipulate regular expressions and do things like compute intersections: https://github.com/qntm/greenery https://github.com/qntm/greenery

miloignis 5y ago
This is exactly the type of thing I was thinking of, and seems quite fully featured - thank you!

codeflo 5y ago

Unfortunately (or perhaps fortunately), “regexes” as commonly implemented in programming languages are only loosely related to regular expressions from automata theory. With all their extensions, they can recognize much, much more than just regular languages, and I don’t think they’re closed under complement (though I’m not sure). However, most regex engines have a feature called negative lookahead assertions, (?!do not match), which would almost work in the way you suggest. You have to be careful about inputs like this though: “Inside a string”Tarzan”Again inside a string”

User23 5y ago
Yeah, a DFA that recognizes a regular language can easily be implemented with O(n) worst case behavior. My attitude is generally that one should use regexes for matching regular languages and if one needs a stack or even Turing completeness then handle that in code around the regex.

contravariant 5y ago

Wouldn't that end up just being the same as 'regex(Tarzan)'? Those regexes can't match the same thing, they can only overlap. What you want is something like all matches of regex("Tarzan") not contained in a match for regex("\"Tarzan\""), which is a bit trickier. That would require something like: regex("Tarzan") - all-substrings(regex("\"Tarzan\"")) and I'm not sure regular languages are closed over the "all-substrings" operation. Actually I'm pretty sure they aren't.

layer8 5y ago

> compliment I’ll take that as a complement.

taneq 5y ago
"It's a complement... NOT" - Borat.

kazinator 5y ago

Intersection with the complement will not work here. Because the idea is to match Tarzan, but only if it is not preceded and followed by a quote. Regex intersection and complement do not perform look-behind or trailing context. Live demo: This is the TXR Lisp interactive listener of TXR 265. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. TXR may be used in areas that are not necessarily well ventilated. 1> [#/Tarzan&~"Tarzan"/ "Jane shouted, \"Tarzan\""] "Tarzan" 2> [#/Tarzan&~"Tarzan"/ "Jane shouted, \"Tarzan!\""] "Tarzan" The &~"Tarzan" makes absolutely no difference. The reason is that Tarzan matches exactly one string. The complement ~"Tarzan" matches a whole countable infinity of strings, and one of those is Tarzan. The intersection of that infinity and Tarzan is therefore Tarzan. Intersection with complement is useful like this: Search for a three-character substring that is not cat: 3> [#/...&~cat/ "hat"] "hat" 4> [#/...&~cat/ "dog"] "dog" 5> [#/...&~cat/ "doggy" "dog" 6> [#/...&~cat/ "cat"] nil 7> [#/...&~cat/ "scatter"] "sca" 8> [#/...&~cat/ "catalan"] ;; "cat" is skipped, then "ata" works. "ata"