Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Calculate the difference and intersection of any two regexes

phylactery.org

Post reply on HN
Print view View original

101–110 of 127 posts

Re: Calculate the difference and intersection of any two regexes

#101

Post by est »

Ha, trying to paste "regex filter numbers divisible by 3" and the page froze to death https://stackoverflow.com/q/10992279/41948

    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$

    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
I wonder if there's a shortest one.

Re: Calculate the difference and intersection of any two regexes

#102

Post by 1-more »

bradrn wrote: post #88
1-more wrote: post #58

Earlier quoted context omitted.

In languages with tagged union types you do this a lot! Some Haskell pseudocode for ya module Email (Address, fromText, toText) where -- note we do not export the constructor of Address, just the type data Address = Address Text fromString :: Text -> Maybe Address fromString = -- you'd do your validation in here and return Nothing if it's a bad address. -- Signal validity out of band, not in band with the data. toTex…

Pedantic note: ‘Address’ should really be a ‘newtype’…

Haha sorry, I get those backwards a lot. I was gonna do elm but then it’d be a conversation about why we’re writing our own email address validation on the front end instead of using the platform.

Re: Calculate the difference and intersection of any two regexes

#103

Post by wizofaus »

zeroimpl wrote: post #98
Sharlin wrote: post #44

Earlier quoted context omitted.

As ^ and $ are implicit, you can opt out of them simply by affixing `.*`.

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.

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

#104

Post by alexvitkov »

1-more wrote: post #102
bradrn wrote: post #88

Earlier quoted context omitted.

Pedantic note: ‘Address’ should really be a ‘newtype’…

Haha sorry, I get those backwards a lot. I was gonna do elm but then it’d be a conversation about why we’re writing our own email address validation on the front end instead of using the platform.

Don't worry, that's normal -- in this forum we only talk about how good obscure languages are, nobody actually uses Haskell.

Re: Calculate the difference and intersection of any two regexes

#105

Post by lubutu »

alphablended wrote: post #97
eru wrote: post #91

Earlier quoted context omitted.

Though going from NFA to explicit DFA isn't always a good idea. Btw, you might also like looking into the Brzozowski derivative https://en.wikipedia.org/wiki/Brzozowski_derivative which can be used as an alternative way to match regular expressions.

I think it is also worth mentioning that the site linked at the top uses the antimirov extension to brzozovzki work on regex deivatives.

To expand, Brzozowski introduced derivatives and Antimirov partial derivatives. Essentially the former correspond to DFAs and the latter to NFAs.

Re: Calculate the difference and intersection of any two regexes

#106

Post by mikhailfranco »

eru wrote: post #91
JoelJacobson wrote: post #27

I created a similar regex web demo that shows how a regex is parsed -> NFA -> DFA -> minimal DFA, and finally outputs LLVMIR/Javascript/WebAssembly for from the minimal DFA: http://compiler.org/reason-re-nfa/src/index.html

Though going from NFA to explicit DFA isn't always a good idea. Btw, you might also like looking into the Brzozowski derivative https://en.wikipedia.org/wiki/Brzozowski_derivative which can be used as an alternative way to match regular expressions.

You could implement the NFA directly with concurrent exploration of all paths:

https://github.com/mike-french/myrex

Re: Calculate the difference and intersection of any two regexes

#107

Post by mikhailfranco »

simlevesque wrote: post #7

Kinda related but I'm looking for something that could give me the number of possible matching strings for a simple regex. Does such a tool exist ?

Another interesting question is: how many possible successful matches are there for a given input string. For example:

How many ways can (a?){m}(a*){m} match the string a{m}

i.e. input m repetitions of the letter 'a'.

https://github.com/mike-french/myrex#ambiguous-example

The answer is a dot product of two vectors sliced from Pascal's Triangle.

For m=9, there are 864,146 successful matches.

Re: Calculate the difference and intersection of any two regexes

#109

Post by abareplace »

est wrote: post #101

Ha, trying to paste "regex filter numbers divisible by 3" and the page froze to death https://stackoverflow.com/q/10992279/41948 ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$ ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$ I wonder if t…

The web page hangs on the regular expressions that produce a DFA with a lot of states. For example, these ones:

(ab+c+)+

(abc){100}

a.*quick brown fox jumps over the lazy dog

Re: Calculate the difference and intersection of any two regexes

#110

Post by abareplace »

vintermann wrote: post #4
posco wrote: post #2

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.

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?

The double quote (") is also broken. If you use it in the regex, then no DFA is displayed.
Post reply on HN