Is there a regular expression to detect a valid regular expression? • Hacker News Board

Re: Is there a regular expression to detect a valid regular expression?

#221

Post by andrewflnr » Tue, Sep 10, 2019, 2:21 AM UTC

YeGoblynQueenne wrote: post #220

andrewflnr wrote: post #219

Earlier quoted context omitted.

Well, we started this subthread looking for alternatives to regex, so if DCGs aren't in the running I'm not sure what your point is. Also, I happen to believe Turing-completeness is a misfeature for this job.

The OP asked for "something as easy to use as regular expressions that can processes context-free grammars". You requested ease-of-use. I proposed DCGs. They are not an alternative to regexes in the sense that regexes can't represent anything beyond regular grammars, including CFGs. They can be as simple or as complicated as you want them and they are easy to use. I'm not sure what is a "misfeature". What do you mean…

My interpretation of "as easy to use as regular expressions" is that the desired... formalism be usable in the same contexts and with the same casual ease as regex. Think Unix command lines, hairy ad-hoc Python parsing scripts, etc.

One of the things that makes regex so well suited to that role is that a string is a regex that matches itself, and you can iteratively add sophistication from there. At the very least, you would want to maintain (or improve, Cthulhu knows there's plenty of room) that incremental quality in any proposed replacement, while increasing its power.

It looks like with a DCG, you have to know you're writing one up front, and have to think about what you're parsing at a much more abstract level. The average sysadmin could probably not casually toss one off for a log parsing task. If there's an alternate syntax that gets around that problem, then I'm interested. OTOH...

Re "misfeature": one of the cool things about existing parsing formalisms is all the known terminating, mostly (all?) polynomial algorithms for analyzing them. If DCGs are Turing complete, they don't have those algorithms. Turing completeness is not usually a property I want in my parser. That's what I meant by saying it's a misfeature.

Re: Is there a regular expression to detect a valid regular expression?

#222

Post by YeGoblynQueenne » Tue, Sep 10, 2019, 1:12 PM UTC

andrewflnr wrote: post #221

YeGoblynQueenne wrote: post #220

Earlier quoted context omitted.

The OP asked for "something as easy to use as regular expressions that can processes context-free grammars". You requested ease-of-use. I proposed DCGs. They are not an alternative to regexes in the sense that regexes can't represent anything beyond regular grammars, including CFGs. They can be as simple or as complicated as you want them and they are easy to use. I'm not sure what is a "misfeature". What do you mean…

My interpretation of "as easy to use as regular expressions" is that the desired... formalism be usable in the same contexts and with the same casual ease as regex. Think Unix command lines, hairy ad-hoc Python parsing scripts, etc. One of the things that makes regex so well suited to that role is that a string is a regex that matches itself, and you can iteratively add sophistication from there. At the very least, y…

I don't quite understand what you mean by "a regex that matches itself". Could you explain? What you describe sound smore like a quine.

Regarding Turing completeness and termination- the DCG formalism (thank you) itself is expressive enough to represent anything from finite automata to UTMs, but that doesn't mean that every grammar you write using DCG notation is Turing-complete. So, for instance, if you write a right-regular grammar as a DCG, that DCG will not be Turing-complete, it'd just be a right-regular grammar.

The DCG examples I gave above are a CFG grammar for a fragment of natural English and a single-rule grammar that matches a single string. Those are definitely not Turing-complete and parsable in polynomial time.

The difference with regexes is that you can't express CFGs or above using regexes, but you _can_ represent both regexes and CFGs using DCG notation.

>> If there's an alternate syntax that gets around that problem, then I'm interested. OTOH...

May I make a personal comment? I think your insistence on competitive language, like "i'm [not] interested", "competitor to regexes" etc, is a case of Déformation professionnelle. You sound just like a software developer hyper-focused on finding tools to maximise productivity in the office, and nothing else.

You should perhaps consider the possibilty that what we are discussing here goes a bit beyond a product that you can package and sell as an alternative to a popular tool. I mean, personally, when I realised that DCGs are executable grammars that can be run as both recognisers and generators- well let's say it shifted my understanding of what is possible to do with a computer and a programming language.

In any case I don't see the complexity you seem to see in DCGs. Like I say above, they're basically BNF. I struggle to think of a sysadmin worth her salt (so, one who knows perl, eh?) who would sweat it to write and read BNF. The kind of sysadmin I have in mind, the problem would be to drag them away from the keyboard, once they started writing a DCG to parse a log file- and realised they could write one to parse _all_ log files ever.

Re: Is there a regular expression to detect a valid regular expression?

#223

Post by burntsushi » Thu, Sep 12, 2019, 11:03 AM UTC

rstuart4133 wrote: post #193

gpm wrote: post #107

Earlier quoted context omitted.

Yes, regex engines that are designed to do so run in linear time on the size of the regex (as well as linear time with respect to the length of the input). One such engine is rust's https://github.com/rust-lang/regex

> One such engine is rust's https://github.com/rust-lang/regex It can process arbitrary deep nestings? I'm not familiar with it, but I had a look and I can't see anything in there that would allow it to do it. Can you point to syntax that allows it? In general regex's that run in linear time are based on DFA's (as opposed to NFA's - which is what most use). A DFA is part of the Chomsky hierarchy of languages that has…

> It can process arbitrary deep nestings?

The GP is presumably citing it as an example of a linear time regex, and not as something that can parse arbitrarily deep nestings. Note that "linear time regex engines" is a characterization that holds the size of the regex constant, such that "linear time" is with respect to the input only. The actual worst case time complexity of such regex engines is O(m * n), where m ~ len(regex) and n ~ len(input). So even with a linear time regex engine, if you bloat the size of the regex, you'll make searching slower. But, it will still be done linearly with respect to the size of the input.

> In general regex's that run in linear time are based on DFA's (as opposed to NFA's - which is what most use).

No. Please stop spreading the misuse of these terms. DFAs and NFAs have very precise meanings. It's one thing to call things regexes that aren't actually regular, but DFAs and NFAs should retain their precise theoretical meaning. A linear time regex engine such as Rust's `regex` crate uses both DFAs and NFAs in its implementation.

The Perl and PCRE folks (along with Jeffrey Friedl) have bastardized this terminology. PCRE for example claims to provide a "DFA" regex engine in its API, but it's actually an NFA. The main implementation inside PCRE (and Perl) is backtracking oriented, and carries with it much more power than an NFA. If it didn't, then the NFA could be executed in linear time, because NFAs and DFAs have equivalent power.

> An interesting corollary of this is any computer program can be expressed as a DFA.

No they can't. You're confusing terminology quite a bit here.

Re: Is there a regular expression to detect a valid regular expression?

#224

Post by andrewflnr » Thu, Sep 12, 2019, 7:47 PM UTC

YeGoblynQueenne wrote: post #222

andrewflnr wrote: post #221

Earlier quoted context omitted.

My interpretation of "as easy to use as regular expressions" is that the desired... formalism be usable in the same contexts and with the same casual ease as regex. Think Unix command lines, hairy ad-hoc Python parsing scripts, etc. One of the things that makes regex so well suited to that role is that a string is a regex that matches itself, and you can iteratively add sophistication from there. At the very least, y…

I don't quite understand what you mean by "a regex that matches itself". Could you explain? What you describe sound smore like a quine. Regarding Turing completeness and termination- the DCG formalism (thank you) itself is expressive enough to represent anything from finite automata to UTMs, but that doesn't mean that every grammar you write using DCG notation is Turing-complete. So, for instance, if you write a righ…

"foo" is a string. It's also a regex that matches exactly the string "foo".

Regarding Turing-completeness, the entire point is about the termination of algorithms that examine parsers, not the runtime of the parsers themselves.

I also don't know how many times I need to point out that the reason I'm focusing on regexes is that that was the context for this conversation. Under any other context I'm quite interested in new parsing techniques.

Lastly, I would point out that regexes have uses far beyond a certain arbitrarily decided set of sysadmins and developers "worth their salt". Even if it's true that a meaningful subset of sysadmins are capable of writing basically sound BNF (which is not something I would count on even for CS grads, but maybe you work with smarter people than I do), there are lots of other people who could use a little more parsing power if it was offered in the right way.