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

31–40 of 127 posts

Re: Calculate the difference and intersection of any two regexes

#31

Post by perihelions »

baggy_trough wrote: post #6

I love how it looks like a CS textbook.

The graphics look identical to those in Hopcroft & Ullman's "Introduction to Automata Theory, Languages, and Computation" (like the convention that they use a double-circle to denote accepting states). I imagine they're GraphViz-based: it's very easy [0] to draw these in GraphViz. I don't know what Hopcroft & Ullman used though, because that one was published in 1979, and GraphViz didn't exist before 1991. Suddenly I'm curious what the state of the art for vector diagrams was in 1979...?

[0] e.g. https://graphviz.org/Gallery/directed/fsm.html

Re: Calculate the difference and intersection of any two regexes

#32

Post by blibble »

it always bugged me as a student that had to sit through all those discrete maths lectures that standard regex libraries don't allow you to union/intersect two "compiled" regular expression objects together

(having to try them one an a time is pretty sad)

Re: Calculate the difference and intersection of any two regexes

#34

Post by tetha »

contravariant wrote: post #9
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 ?

I feel like it shouldn't be too hard to calculate from the finite automaton that encodes the regular expression, but surely in most cases it will simply be infinite?

This is hitting back a long time. But the algorithm - if I recall right - is a simple DFS on the determinstic automaton for the regular expression and it can output the full set of matching strings if you're allowed to use *s in the output.

Basically, you need an accumulator of "stuff up to here". If you move from a node to a second node, you add the character annotating that edge to the accumulator. And whenever you end up with an edge to a visited node, you add a '*' and output that, and for leaf nodes, you output the accumulator.

And then you add a silly jumble of parenthesis on entry and output to make it right. This was kinda simple to figure out with stuff like (a(ab)*b)* and such.

This is in O(states) for R and O(2^states) for NR if I recall right.

Re: Calculate the difference and intersection of any two regexes

#35

Post by dhosek »

klysm wrote: post #12

Regular expressions are a great example of bundling up some really neat and complex mathematical theory into a valuable interface. Linear algebra feels similar to me.

It always amazes me how given the appropriate field, so much math can be transformed into linear algebra. Even Möbius transformations on the complex plane w=(az+b)/(cz+d) can be turned into linear algebra.

Re: Calculate the difference and intersection of any two regexes

#36

Post by Someone »

contravariant wrote: post #18
microtonal wrote: post #14

Earlier quoted context omitted.

Say you want to compute all strings of length 5 that the automaton can generate. Conceptually the nicest way is to create an automaton that matches any five characters and then compute the intersection between that automaton and the regex automaton. Then you can generate all the strings in the intersection automaton. Of course, IRL, you wouldn't actually generate the intersection automaton (you can easily do this on…

> deterministic acyclic minimized automaton That's basically a Trie right? To be fair I have only heard of them and know they can be used to do neat tricks, I've rarely used one myself.

If you do not plan to update it often and don’t need to store extra data with each word, a dawg (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...) is more compact. You often can merge leaf nodes.

For example, if you have words

   talk
   talked
   talking
   talks
   walk
   walked
   walking
   walks
there’s no need to repeat the “”, “ed”, “ing”, “s” parts.

Re: Calculate the difference and intersection of any two regexes

#37

Post by microtonal »

contravariant wrote: post #18
microtonal wrote: post #14

Earlier quoted context omitted.

Say you want to compute all strings of length 5 that the automaton can generate. Conceptually the nicest way is to create an automaton that matches any five characters and then compute the intersection between that automaton and the regex automaton. Then you can generate all the strings in the intersection automaton. Of course, IRL, you wouldn't actually generate the intersection automaton (you can easily do this on…

> deterministic acyclic minimized automaton That's basically a Trie right? To be fair I have only heard of them and know they can be used to do neat tricks, I've rarely used one myself.

No. In a minimized automaton shared string suffixes also share states/transitions.

Re: Calculate the difference and intersection of any two regexes

#38

Post by rsstack »

I used this concept once to write the validation logic for an "IP RegEx filter" setting. The goal was to let users configure an IP filter using RegEx (no, marketing people don't get CIDRs, and they knew RegEx's from Google Analytics). How could I define a valid RegEx for this? The intersection with the RegEx of "all IPv4 addresses" is not empty, and not equal to the RegEx of "all IPv4 addresses". Prevented many complaints about the filter not doing anything, but of course didn't prevent wrong filters from being entered.

Re: Calculate the difference and intersection of any two regexes

#39

Post by o11c »

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?

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\`.

Re: Calculate the difference and intersection of any two regexes

#40

Post by oever »

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more.

For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings.

An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty string, it knows that an email address is valid.

This library can be used to check the definitions and hierarchy of such string types. The implementation of the hierarchy differs per programming language (subclassing, trait boundaries, etc).

Post reply on HN