News for hackers. Stuff that matters.
Re:Calculate the difference and intersection of any two regexes by posco on Monday September 11, 2023 @01:10PM (#37470286)
The amazing page computes binary relations between pairs of regular expressions and shows a graphical representation of the DFA.

It’s a really incredible demonstration of some highly non-trivial operations on regular expressions.

Re:Calculate the difference and intersection of any two regexes by vintermann on Monday September 11, 2023 @01:35PM (#37470668)
It's very cool, but also no wonder that it doesn't support all those features of regexes which technically make them not regular expressions anymore. Though, I would have thought ^ and $ anchors shouldn't be a problem?
Re:Calculate the difference and intersection of any two regexes by teraflop on Monday September 11, 2023 @02:09PM (#37471175)
This page implements regex matching, not searching. So in effect, every pattern has an implicit ^ at the beginning and $ at the end.
Re:Calculate the difference and intersection of any two regexes by rntz on Monday September 11, 2023 @03:17PM (#37472305)
^ and $ are a problem, although one with a workaround.

The standard theory of regular expressions focuses entirely on regex matching, rather than searching. For matching, ^ and $ don't really mean anything. In particular, regexp theory is defined in terms of the "language of" a regexp: the set of strings which match it. What's the set of strings that "^" matches? Well, it's the empty string, but only if it comes at the beginning of a line (or sometimes the beginning of the document). This beginning-of-line constraint doesn't fit nicely into the "a regexp is defined by its language/set of strings" theory, much the same way lookahead/lookbehind assertions don't quite fit the theory of regular expressions.

The standard workaround is to augment your alphabet with special beginning/end-of-line characters (or beginning/end-of-document), and say that "^" matches the beginning-of-line character.

Re:Calculate the difference and intersection of any two regexes by o11c on Monday September 11, 2023 @03:56PM (#37472774)
A lack of `^` is equivalent to prepending `(.*)`, then trimming the match span to the end of that capture. And similarly for a lack of `$` (but suddenly I remember how nasty Python was before `.fullmatch` was added ...).

More interesting is word boundaries:

`\b` is just `\<|\>` though that should be bubbled up and usually only one side will actually produce a matchable regex.

`A\<B` is just `(A&\W)(\w&B)`, and similar for `\>`.

Re:Calculate the difference and intersection of any two regexes by o11c on Wednesday September 13, 2023 @06:41PM (#37502649)
Correction, `A\<B` is `(A&(\W|^))(\w&B)`, which matters if the A regex can match the empty string.
Re:Calculate the difference and intersection of any two regexes by Sharlin on Monday September 11, 2023 @04:05PM (#37472895)
As ^ and $ are implicit, you can opt out of them simply by affixing `.*`.
Re:Calculate the difference and intersection of any two regexes by zeroimpl on Monday September 11, 2023 @10:12PM (#37476283)
Only when the ^ or $ were at the start/end of your string is it simple. Eg:

    (a|b|^)(c|d|^)foo
Rewriting without ^ can require much longer regex.
Re:Calculate the difference and intersection of any two regexes by wizofaus on Tuesday September 12, 2023 @12:16AM (#37476890)
Isn't that just

    ((a|b)?(c|d)|c|d)?foo
Unless you mean it as a search expression, in which case it's more like

    ((.*a|.*b)(c|d)|c|d)?foo
Which I have to admit was a lot harder to figure out than I thought it would be (and may not even be right!)
Re:Calculate the difference and intersection of any two regexes by zeroimpl on Tuesday September 12, 2023 @07:43AM (#37479572)
Yeah the latter.

In an engine supporting ^ and $, searching for this

    (a|b|^)(c|d|^)foo
is equivalent to searching for this

    ^((.*a|.*b)(c|d)|c|d)?foo.*$
And in this context you can drop the leading/trailing ^/$ since they are implicit.
Re:Calculate the difference and intersection of any two regexes by abareplace on Tuesday September 12, 2023 @04:38AM (#37478267)
The double quote (") is also broken. If you use it in the regex, then no DFA is displayed.