Earlier quoted context omitted.
((((()
doesn't end up with zero at the end, rejected?
I was just trying to suggest a possible edge case, a failing test.
Is there a regular expression to detect a valid regular expression?
181–190 of 224 posts
Re: Is there a regular expression to detect a valid regular expression?
#182Earlier quoted context omitted.
> (famously) there is no regex to detect balanced parentheses God, I remember running into this wall with an in-company domain-specific language that used regex as its tokenizer/parser. Adding support for nested structures required us to untangle the whole thing and rewrite the regex into explicit algorithms. Fortunately the regex was only a few pages long.. In short, I agree with you that regex cannot parse regular…
> In short, I agree with you that regex cannot parse regular expressions completely. Would be happy to be proven wrong, though! the proof that you can't parse nested pararetheses with a regular language is a pretty standard part of first year computer science
It doesn't stop some of us from trying though! :)
Re: Is there a regular expression to detect a valid regular expression?
#183> Is there a regular expression to detect a valid regular expression? No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
The problem is that "regular expression" is equivocal. Sometimes you hear "regular expression" used to mean the language of things accepted by some Finite State machine. Lots of folks on HN took a Theory of Computation class and learned about these in that class. In that meaning, yes, you are right. But sometimes in professional conversations you hear "regular expression" used to mean the strings that can be matched…
Very few people know that Perl's regex engine (since 5.10) supports recursion. And recursive matching cannot perform recursive captures, which is why at best it can only be used to validate a string, not parse it, making it not particularly useful in practice. For these reasons I would never assume that someone using the term "regular expression" inclusively of Perl would have in mind such capabilities. IME, such a loose definition simply implies things like zero-width assertions, backcaptures, etc.
Here's a proof-of-concept Perl 5.10+ JSON validator I came up with for a presentation to Perl engineers introducing PEGs and Lua's LPeg module. Of the 20-30 people in the room, I doubt anybody in the audience knew this was even possible with Perl.
my $grammar = qr{
^(?&Value) $
(?(DEFINE)
(? \s∗ (?:
(?&Array)
| (?&Object)
| (?&Boolean)
| (?&Number)
| (?&String)
| (?&Null)
) \s∗ )
(? \[ \s∗ (?:(?&Value) (?:\s∗,\s∗ (?&Value))∗)? \s∗ \])
(? \{ \s∗ (?:(?&KeyV) (?:\s∗,\s∗ (?&KeyV))∗)? \s∗ \})
(? \s∗ (?:(?&String) \s∗:\s∗ (?&Value))) \s∗
(? true | false)
(? \d+)
(? "[^\"]∗")
(? null)
)
}xs;
Re: Is there a regular expression to detect a valid regular expression?
#184A regular language for writing regular language recognizers is an interesting thought exercise.
Re: Is there a regular expression to detect a valid regular expression?
#185So, given the much discussed limitations of reg-exps and the desire to parse context-free grammars. My question is, why are we still using regular expressions. Or rather, why isn't there something as easy to use as regular expressions that can processes context-free grammars?
Something like Perl6 grammars[1], or maybe Rosie Pattern Language[2]? Of course Perl6 regexes also go well beyond regular expressions, and I suspect they could be used to match context-free grammars if pressed hard enough. Both P6 grammars and RPL are based on parsing expression grammars, and there are also tools/libraries for many other languages based on PEGs. But now you are entering in the scary realm of parsers…
PEGs are amazing precisely because they're as easy to use as, if not easier than, common regular expression syntax. PEGs are literally the same as regular expressions except 1) alternations are ordered, 2) zero-width assertions are formalized, and 3) quantifiers match greedily. This is effectively the same behavior as the Perl-compatible regular expressions with which most people are familiar.
Many PEG engines, especially for dynamic languages, permit grammar composition using first-class variables. That might be a small barrier to people more familiar with the terseness and conceptual simplicity of regular expressions as string'ish values. But it's fairly trivial to implement the latter using PEGs. For example, LPeg provides a small auxiliary module for doing that: http://www.inf.puc-rio.br/~roberto/lpeg/re.html
Also, Rosie seems amazing. I've not yet had the opportunity to make use of it, but I attended a presentation of Rosie by the author at a Lua workshop which left me very impressed.
Re: Is there a regular expression to detect a valid regular expression?
#186Earlier quoted context omitted.
Personally, I think this is a strength of StackOverflow. I think most people read through all of the answers, and this particular one keeps people who know nothing about regex from trying to evaluate regex with regex. And for those with a deeper understanding, they have an answer that provides the intellectual stimulation they are looking for.
> I think most people read through all of the answers You're vastly overestimating what most SO users come to the site for. They (and I include myself) just want something that'll work and isn't horrible. Even "not horrible" is something I care about but I know that many devs don't.
If somebody doesn't know the answer to their question in advance, which by definition they don't, it's by no means guaranteed they will know a horrible answer when they see it.
Re: Is there a regular expression to detect a valid regular expression?
#187Maybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...) state that a language can not define itself? You need a meta language to be able to define and specify a language in its entirety.
In other words, regex can not parse regex in its entirety. It's impossible.
Re: Is there a regular expression to detect a valid regular expression?
#188Maybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems ( https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... ) state that a language can not define itself? You need a meta language to be able to define and specify a language in its entirety. In other words, regex can not parse regex in its entirety. It's impossible.
No, not really. This is probably closer to Chomsky's area than Gödel's. Gödel's theorem is about semantics, not syntax.
As a nice counter-example to what you said, you can define the Backus-Naur notation using Backus-Naur notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Furth...
Re: Is there a regular expression to detect a valid regular expression?
#189Maybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems ( https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... ) state that a language can not define itself? You need a meta language to be able to define and specify a language in its entirety. In other words, regex can not parse regex in its entirety. It's impossible.
Can a C program parse C source code? A Java program parse Java source code? Yes, they can, so such a general limitation couldn't be the reason regular expressions can't parse themselves.
Perhaps you had in mind the Halting Problem: https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_i...
Re: Is there a regular expression to detect a valid regular expression?
#190Earlier quoted context omitted.
It’s a famous post on StackOverflow, but I don’t find it particularly helpful.
I don't think that answer was written with the intent of being particularly helpful, I think it was written with a different goal in mind.
The author said at one point that it was written in a bit of a huff of frustration, and if I remember correctly, also after a pint or two. It's not the best answer answer by any means, but it is one of those small gems of the web, I think.