8 ms·
Calculate the difference and intersection of any two regexes
- posco 3y agoThe 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.
- vintermann 3y agoIt'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?
- teraflop 3y agoThis page implements regex matching, not searching. So in effect, every pattern has an implicit ^ at the beginning and $ at the end.
- rntz 3y ago^ 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.
- o11c 3y agoA 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 `\>`.
- o11c 3y agoCorrection, `A\<B` is `(A&(\W|^))(\w&B)`, which matters if the A regex can match the empty string.
- Sharlin 3y agoAs ^ and $ are implicit, you can opt out of them simply by affixing `.*`.
- zeroimpl 3y agoOnly 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.
- wizofaus 3y agoIsn'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!)
- zeroimpl 3y agoYeah 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.
- deleted 3y ago[deleted]
- abareplace 3y agoThe double quote (") is also broken. If you use it in the regex, then no DFA is displayed.
- deleted 3y ago[deleted]
- snoble 3y agoOh neat, this is scala via scalajs.
- deleted 3y ago[deleted]
- baggy_trough 3y agoI love how it looks like a CS textbook.
- cobbal 3y agoIt has the look of graphviz about it, which is an excellent tool. Often helpful in debugging anything related to graphs. https://graphviz.org/ https://graphviz.org/
- perihelions 3y agoThe 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 https://graphviz.org/Gallery/directed/fsm.html
- therealcamino 3y agoMaybe something related to 'pic'? This doc on it is a revised version of a 1984 edition, so maybe it's a little too late, but there are references to other systems back to 1977 or so. https://pikchr.org/home/uv/pic.pdf https://pikchr.org/home/uv/pic.pdf
- simlevesque 3y agoKinda 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 ?
- contravariant 3y agoI 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?
- kadoban 3y agoMaybe the number of possible matchings for a given length (or range of lengths) might be interesting?
- microtonal 3y agoSay 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 the fly), but you get the idea. Automata are really a lost art in modern natural language processing. We used to do things like store a large vocabulary in an deterministic acyclic minimized automaton (nice and compact, so-called dictionary automaton). And then to find, say all words within Levenshtein distance 2 of hacker, create a Levenshtein automaton for hacker and then compute (on the fly) the intersection between the Levenshtein automaton and the dictionary automaton. The language of the automaton is then all words within the intersection automaton. I wrote a Java package a decade ago that implements some of this stuff: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
- contravariant 3y ago> 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.
- klysm 3y agoRegular 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.
- abecedarius 3y agoiirc connections with linear algebra come up in Conway's https://store.doverpublications.com/0486485838.html https://store.doverpublications.com/0486485838.html (which I only skimmed).
- Jaxan 3y agoThere is a whole field of “weighted automata” which combine linear algebra and automata theory.
- deleted 3y ago[deleted]
- pishpash 3y agoThat usually means the representation is getting close to the truth. Good interfaces have intrinsic value, which many result-focused people do not appreciate.
- dhosek 3y agoIt 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.
- deleted 3y ago[deleted]
- pishpash 3y agoLinear transformations preserve the structure of the space so you can keep applying them. It's not surprising that you can always find some "space-preserving" part of a problem and fold the rest (the "non-linear" structure) into transformations or the definition of the space itself.
- hoten 3y agoOn mobile: are the rectangle glyphs as suffixes on the states on purpose or am I missing a font?
- progbits 3y agoThe states are numbered, $\alpha_0, ..., \alpha_N$ and $\beta_0, ...$. You might be missing the font for the digits.
- JoelJacobson 3y agoI 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 http://compiler.org/reason-re-nfa/src/index.html
- eru 3y agoThough 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 https://en.wikipedia.org/wiki/Brzozowski_derivative which can be used as an alternative way to match regular expressions.
- alphablended 3y agoI think it is also worth mentioning that the site linked at the top uses the antimirov extension to brzozovzki work on regex deivatives.
- lubutu 3y agoTo expand, Brzozowski introduced derivatives and Antimirov partial derivatives. Essentially the former correspond to DFAs and the latter to NFAs.
- mikhailfranco 3y agoYou could implement the NFA directly with concurrent exploration of all paths: https://github.com/mike-french/myrex https://github.com/mike-french/myrex
- blibble 3y agoit 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)
- rsstack 3y agoI 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.
- Etheryte 3y agoWouldn't a simpler solution work here? Instead of trying to validate the filter regex, show some sample IP addresses or let the user insert a set of addresses, and then show which ones the filter matches and which ones it doesn't. Also helps address the problem of incorrect filters.
- rsstack 3y agoThe odds of the sample addresses matching is essentially zero, and adding work to the user is counterproductive.
- Etheryte 3y agoI'm not sure I agree — most common regex editing tools available online include a section for adding test strings to verify what you actually wrote is correct. Clearly there is a benefit to it. In similar vein, allowing the user to test before they commit and then test actually reduces their work load, they don't have to drop and then reload the whole regex in their mind.
- rsstack 3y agoSure, I use that when authoring and editing a RegEx. That's not the same as entry validation.
- oever 3y agoThis 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).
- 1-more 3y agoIn 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. toText :: Address -> Text toText (Address addr) = addr -- for when you need to output it somewhere
- alexeldeib 3y ago> Signal validity out of band, not in band with the data. Could you expand on this?
- 1-more 3y agoSure! Sorry that was a little too obtuse. So in this case we can imagine an app where we don't use any tagged unions and just use primitive types (your strings, booleans, integers, things of that nature). And we want to signal the validity of some data. Say a user ID and an email address. We store the User ID as an integer to keep space down and store the email address as a string. We use semaphore values: if the user ID is invalid we store -1 (it's JS and there are no unsigned numbers) and if the email address is invalid we store the empty string. Whenever we consume these values, we need to make sure that userId > 0 and email != "" I mean email !== "". We are testing for special values of the data. Data and "this is for sure not meaningful data" are the same shape! So your functions need to handle those cases. But with tagged unions you can check these things at the edge of the program and thereafter accept that the contents of the tagged data are valid (because you wrote good tests for your decoders). So your data is a different shape when it's valid vs when it's invalid, and you can write functions that only accept data that's the valid shape. If you got Json that was hit by cosmic rays when trying to build your User model, you can fail right then and not build a model and find a way to handle that. It's out of band because you don't guard for special values of your morphologically identical data. If you want examples of any specific part of this let me know. IDK your level of familiarity and don't want to overburden you with things you already get.
- layer8 3y agoI wanted to see the intersection between syntactically valid URLs and email addresses, but just entering the URL regex (cf. below) already takes too long to process for the page. [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*) (source: https://stackoverflow.com/a/3809435/623763 https://stackoverflow.com/a/3809435/623763)
- d66 3y agoexpressions like (...){1,256} are very heavyweight and the scala JS code ends up timing out or crashing the browser. if you replace that with (...)+ then it seems to work (at least for me). smaller expressions like (...){1,6} should be fine.
- noduerme 3y agoJust wondering, what is it about testing repetition [a-z]{1,256} with an upper bound that's so heavy? Intuitively it feels like greedy testing [a-z]+ should actually be worse since it has to work back from the end of the input.
- d66 3y agothe library uses a fairly simple data representation where x{m,n} is compiled using conjunction and disjunction. so x{1,4} ends up being represented as x|xx|xxx|xxxx. this simplifies the code for testing equality and inclusion, since logically x{n} is just xx... (n times) and x{m,n} is just x{m}|x{m+1}|...|x{n}. but when you have x{m,n} and n-m is large you can imagine what kind of problems that causes.
- less_less 3y agoInteresting. I think this problem is actually EXPSPACE-complete in general? But still has a straightforward algorithm. https://en.wikipedia.org/wiki/EXPSPACE https://en.wikipedia.org/wiki/EXPSPACE
- DannyBee 3y agoIt depends on your operators. For these, no. Equivalence of DFA or NFA is PSPACE complete by savitch's theorem, regardless of time bound. As such, most types of regex equivalence is pspace-complete. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.3636 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.... Has a detailed breakdown of operators vs complexity. In particular, the paper cited in the expspace page is talking about allowing a squaring operator. It is EXPSPACE complete if you allow squaring, but not if you use repetition. IE it is expspace complete if you allow e^2, but not if you only allow ee.
- DannyBee 3y agoSince this may be confusing at first (why does squaring buy you anything here) - the reason squaring makes it expspace complete is, basically, squaring allows you to express an exponentially large regex in less than exponential input size. This in turn means polynomial space in the size of the input is no longer enough to deal with the regex. If you only allow repetition, than an exponentially large regex requires exponential input size, and thus polynomial space in the size of the input still suffices to do equivalence. This is generally true - operators that allow you to reduce the size of the input necessary to express a regex by a complexity class will usually increase the size complexity class necessary to determine equivalence by a corresponding amount.
- less_less 3y agoBut the site does allow squaring, and in fact also general exponentiation? Like you can write "fo{2}" to match "foo", where the {2} is squaring.
- 3y ago
- haltist 3y agoCan LLMs do this?
- pimlottc 3y agoSuggestion: turn off auto suggest in the regex input fields to make it more usable on mobile. https://stackoverflow.com/questions/35513968/disable-autocorrect-in-safari-text-input https://stackoverflow.com/questions/35513968/disable-autocor...
- _a_a_a_ 3y agoAny def for 'difference and intersection of regexes' might actually mean? I guess for regexes r1 and r2 this means the diff and intersect of their extensional sets, expressed intensionally as a regex. I guess. But nothing seems defined, including what ^ is, or > or whatever. It's not helpful
- d66 3y agonegation (~α): strings not matched by α difference (α - β): strings matched by α but not β intersection (α & β): strings matched by α and β exclusive-or (α ^ β): strings matched by α or β but not both inclusion (α > β): does α matches all strings β matches? equality (α = β): do α and β match exactly the same strings?
- themusicgod1 3y agough STOP USING GITHUB
- emmanueloga_ 3y agoOne possible application: If an input to a function parameter must match a certain regex, and the output of a function produces results matching another regex, we can know if the functions are compatible: if the intersection of regular expressions is empty, then you cannot connect one function to the other. Combined with the fact the regular expressions can be used not only on strings but more generally (e.g. for JSON schema validation [1]), this could be a possible implementation of static checks, similar to "design by contract". -- 1: https://www.balisage.net/Proceedings/vol23/html/Holstege01/BalisageVol23-Holstege01.html https://www.balisage.net/Proceedings/vol23/html/Holstege01/B...
- bjt12345 3y ago[flagged]
- x-complexity 3y agoI used 2 similar divide-by-3 regexes to test the page (after removing the ^ and $ to their ends), and it froze up: Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))* Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))* Everything up until the last '*' is parsable. The moment I put in the *, the entire page freezes up. Without the *, it produced a valid verifier for parsing chunks of digits whose sum mod 3 = 0.
- jepler 3y agoThis is neat! I was surprised then not surprised that the union & intersection REs it comes up with are not particularly concise. For example the two expressions "y.+" and ".+z" have a very simple intersection: "y.*z" (equality verified by the page, assuming I haven't typo'd anything). But the tool gives yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* instead. I think there are reasons it gives the answer it does, and giving a minimal (by RE length in characters or whatever) regular expression is probably a lot harder.
- ufo 3y agoI think one of the reasons is the ".+z" gets bigger and uglier after you convert it to a deterministic automaton.
- daveFNbuck 3y agoThey show the DFA for it on the site, it's 3 states. There's a starting state for the first . and then two states that transition back and forth between whether z was the last character or not. I think what's actually happening here is that they're doing the intersection on the DFAs and then producing a regex from the resulting DFA. The construction of a regex from a DFA is where things get ugly and weird.
- est 3y agoHa, trying to paste "regex filter numbers divisible by 3" and the page froze to death https://stackoverflow.com/q/10992279/41948 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.
- abareplace 3y agoThe 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
- zamadatix 3y agoThe page says it doesn't support anchors anyway.
- deleted 3y ago[deleted]