4 ms·

I 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?

• brudgers 13y ago
  I 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?
  • noprompt 13y ago
    I would not use this as a replacement to test the membership of a string in a collection of strings. That's a terrible use case. I've done benchmarks comparing membership checking and regular expression testing and the former is almost always significantly faster and requires less overhead. With regard to ranges, it's another one of the areas I have yet to look in to. The question you have to answer is: will [r-z] generate fewer states? As far as case insensitivity, well, that's usually just an optional flag.
    • brudgers 13y ago
      >"I would not use this as a replacement to test the membership of a string in a collection of strings." But that's what a regular expression is used for - testing an arbitrary string for membership within the set of valid strings of the language formally described by the regular expression. The power of a regular expression is that it can enumerate all the valid strings for me. If I have to explicitly list them, what have I gained? To put it another way, the equivalent output to the example is: (?:foo|bar|baz|quux) it is one character longer than what was produced (?:ba[rz]|foo|quux) but can reasonably argued to be clearer. What I was getting at with my pseudo-code example is that if the goal is to interpret the input down to the fewest possible states from examples, then the regular expression is redundant - all we need are the examples and `if`. There's shorter syntax: > (frak/pattern [Clojure|Clojars|ClojureScript]) #"(?:Clojure|Clojars|ClojureScript)" Why not use the simplest possible syntactic sugar? As I said in my first comment, I understand the reasons for creating Frak. I find thinking about it stimulating and illuminating. It provides a great jumping off point around the of the issue of unpacking regular expressions and the terseness of their language.
      • foobarbazqux 13y ago
        I just wanted to point out that nowadays "qux" generally comes before "quux" in the standard series. http://www.catb.org/~esr/jargon/html/Q/qux.html http://www.catb.org/~esr/jargon/html/Q/qux.html
      • noprompt 13y ago
        > "But that's what a regular expression is used for - testing an arbitrary string for membership within the set of valid strings of the language formally described by the regular expression." Formally yes. And if it were always more performant to use a regular expression for this task, I would encourage the use of this tool to do so. However, depending on the data structure containing the strings, it may be more performant to simply search that. > "it is one character longer than what was produced" It's not about the length of the pattern that matters. Rather, it's the performance characteristics of the underlying state machine once the expression is compiled. > "Why not use the simplest possible syntactic sugar?" (?:Clojure|Clojars|ClojureScript) While this is certainly easier to read and understand, it will have performance drawbacks when using an NFA engine where backtracking is a real thing. It will also have a larger number of states when compared with the alternative. Cloj(?:ure(?:Script)?|ars) Suppose I am interested in testing if "ClojureScript" is a member of the set of strings described by the first expression. To be in a final state I will have to enter no fewer than 25 states and backtrack twice. With the second expression I will only need to enter 13 states before being in a final state and will not backtrack at all. For small patterns the choice to use something like frak is arguably splitting hairs; you won't gain much other than you didn't have to write an expression. But for enormous patterns, like the one I share in the README, there are real benefits from the sort of optimization frak provides.