5 ms·
Frak takes an entirely different approach to generating regular expressions
- webjames 13y agoGreat work - I'd love it if someone would write a web front end to this.
- gleb_bahmutov 13y agoIs there analogy implemented in javascript?
- crazygringo 13y agoGitHub is currently suffering a big DDoS, here's the Google Cache version: http://webcache.googleusercontent.com/search?q=cache:PXnt0AWpMZAJ:https://github.com/noprompt/frak+&cd=1&hl=en&ct=clnk&gl=us&lr=lang_en%7Clang_pt http://webcache.googleusercontent.com/search?q=cache:PXnt0AW...
- crazygringo 13y agoI really like the idea... but so far, it seems limited to actual characters, with no "*" or "+" expansion, no collapsing whitespace into "\s", etc. So it doesn't seem like you could feed it "a", "aaa", "aaaaa" and then get "a+". But even if it did, it would seem there would be so many edge cases in what the "correct" regular expression should be, that specifying them all would be just as hard as writing the regular expression in the first place. But nevertheless, definitely a cool little toy. Would be great to have a web front end to test it out, as webjames said.
- samatman 13y agoYou're asking for implicit induction, which is not what the user would want in the general case. "a" "aaa" "aaaaa" could be expanded to "a(aa){0,2}" through deduction, and no more. since frak is using a trie, this kind of encoding should be a conceptually straightforward extension of the existing parse structure.
- noprompt 13y agoThese expansions are certainly possible and I'm planning to investigate whether they have performance benefits. One interesting discovery we made last weeks is that `(a|b|c)` actually produces a larger state table than `[abc]`. This was both the case for Java and Vim. While the performance gains are minute, nevertheless, they are gains. I haven't checked if "a{4}", for example, is faster than "aaaa" or produces fewer states. But it's something I am interested in. I just haven't had enough time this week.
- brudgers 13y agoI get the motivation for writing it. I am not sure I see wisdom in using it. The typical use case for regular expressions is to find patterns in an arbitrary unknown string. There can be multiple regular expressions which match a particular string or set of strings because of the Kleene Star - i.e. the examples: "foo" "bar" "baz" "quux" are all matched by (?:ba[rz]|foo|quux) but also by [:alpha:]* | [:lower:]* etc. Having started the port of VerbalExpressions to Racket, the fundamental issue is that the only practical way to express an automata requires the use of one of the forms which can express an automata. TANSTAAFL.
- samatman 13y agoSometimes, one of your regular expressions is "keyword" or the like. Auto-generating that one regex spares the usual concatenation of the literal options into one relatively inefficient monster.
- noprompt 13y agoThis is an excellent use case.
- cjoh 13y agoI have very limited experience around regexes, but would it be a good idea for the software to perhaps try and show multiple different regexes that would match? I'd imagine that's more difficult, if we're talking narrow scope and then broadening out... there's an interesting UI to be built around that.
- brudgers 13y agoI have limited experience as well. It's the reason I decided to try a port of VerbalExpressions. As I've learned more, I recognize that most of my puzzlement in regards to regular expressions is based on a misunderstanding of what they actually are. In ordinary language it is simple to say, "A regular expression describes a pattern to be matched." Mathematically, however, a regular expression describes a language. The typical use case is to test strings for membership within the language. What regular expressions do is provide a formal description of a language. Once we attempt to construct regular expressions based on informal descriptions of a language, we are constructing arbitrary languages, and the only way to test whether an arbitrary language is the formal language we wish to construct is to construct the formal language and compare it to the arbitrary one. There are two ways we can construct the formal description - as a regular expression or as the set of all legal strings. Frak replaces formal description with a formal enumeration of all legal strings. But what does this get us in terms of regular expressions? We don't need regular expressions for: boolean matcher? [list los string str] [foreach [token in str] [test memberof? los truth-value=or]] matcher? ["foo" "bar" "baz" "quux"] ["barber"]; In other words, how do we get (?:ba[r-z]|foo|quux) by giving examples without including ["bas" "bat" "bau" "bav" "baw" "bax" "bay"] in the input list to Frak? Then consider that some contexts are case sensitive. Which of ["bar" "Bar" "bAr"..."BaR"..."BAR"] are and aren't legal?
- samatman 13y agoFor those who are missing wildcards: Wildcards are not possible when going from a restricted input to a finite automaton. However, if you aren't using say ø, just make your input to frak "fooøbar" then add your wildcard to the generated regex. I agree the output could be more compact, and collapse certain conventional characters (\n, \t and the like). The tool itself has all the power one should need.
- Groxx 13y agoThis is pretty cool - nice work! Can't say I've seen a trie-based construction like this, but it's clever and looks like a near-perfect fit.
- noprompt 13y agoApparently the Perl community has been doing this for years. :)