Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

stackoverflow.com

Post reply on HN
Print view View original

81–90 of 224 posts

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

#81

Post by ac42 »

ukj wrote: post #56
ac42 wrote: post #55

Earlier quoted context omitted.

Free of English errors. Not semantic errors. We don't even know it's a "liar".

Precisely, but as far as a compiler/interpreter is concerned syntax is semantics. You can't codify moral judgments.

Not sure if you are trolling, but here we go...

In the case at hand, correctness of the validator expression V clearly means "V determines well-formedness of any regular expressions" which is clearly not implied by "V is well-formed" (a much weaker statement because ".*" is well-formed but matches everything). Therefore, when applying V to itself, we only learn if a weak requirement for V's correctness holds.

Similar, perhaps, to validating whether a given number is a Gödel number of a well-formed logical statement rather than assessing the verity of the logical statement it encodes.

Also, I am not saying whether it is or is not possible to build such a regular expression. Rather, the question just doesn't tick the boxes of either, the Liar's Paradox, nor Gödel's Incompleteness result -- contrary to what was suggested. So you could still be right but for different reasons.

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

#82

Post by kortex »

gnud wrote: post #73
lolinder wrote: post #29

Earlier quoted context omitted.

My favorite part of it is the moderators' note at the end: > Moderator's Note > This post is locked to prevent inappropriate edits to its content. The post looks exactly as it is supposed to look - there are no problems with its content. Please do not flag it for our attention.

The big problem with the content is suggesting to use an XML parser to parse HTML. That might often work, and several XML parsers have some sort of HTML "mode", but in general, no, not really. HTML documents are frequently invalid XML. HTML documents lack an XML declaration, they don't close all tags, etc. They might even lack a root element. Someone mentioned this in a comment on SO, but it was (as far as I could se…

The question title implies he's parsing XHTML text.

> XHTML is an XML-based HTML. It serves the same function as HTML, but with the same rules as XML documents.

https://stackoverflow.com/q/1429065

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

#83

Post by mannykannot »

benj111 wrote: post #77
mannykannot wrote: post #74

Earlier quoted context omitted.

More precisely, it is arbitrarily deep nested clauses that cannot be parsed, on account of true REs not being able to either use recursion or keep count of how deep they are. https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...

Can regex engines actually process arbitrarily deep nestings themselves though? It seems to me it would start getting computationally expensive very quickly to search for those kinds of regexes, so is 'arbitrarily deep' a practical concern for todays hardware?

There is an importance to theoretical considerations that goes beyond their immediate practical applications. Ultimately, it comes down to how well one understands what is going on.

Having said that, I think there are practical applications. Suppose you were unaware of this result, and thought a true RE could validate your input? A more knowledgeable attacker might be able to craft an input that exploits the inherent limitations of your validator.

Also in practice, attempting to write a true RE to parse a language that allows restricted recursion rapidly becomes complicated. It is the wrong tool for the job.

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

#84

Post by andrewflnr »

rocqua wrote: post #69

So, 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?

I don't know if it's possible to do the "string describing a set strings" thing that regex does with more powerful parsing while maintaining the ease of use. CFGs make heavy use of named sub-languages (productions). A regex-style parser would at least have to have some kind of recursion-inducing metacharacter.

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

#85

Post by trisiak »

tobinfricke wrote: post #65
tobinfricke wrote: post #41

> 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.

Follow-up question: without the grouping parentheses, is the regex language regular?

Yes, but you're taking too much. Without grouping, regex is weaker than regular languages.

Grouping & capturing parentheses can stay. It's only the back-referrences that you need to remove.

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

#87

Post by mannykannot »

ukj wrote: post #78
mannykannot wrote: post #75

Earlier quoted context omitted.

Then your mistake appears to be in failing to see that your perceived edge case does not invalidate the first sentence of my reply. If the sole purpose of a parser is to syntactically validate its own source (which is not the case for a compiler's parser, by the way, not even if we expand 'its own source' to 'arbitrary input'), then if it does that correctly, that's all there is to it.

Your mistake appears to be - ignoring the alternative hypothesis. You are mistaken, not me. The consequences of Godel's incompleteness theorem are such that a mathematical system (such as a compiler) cannot prove its own correctness. It can only prove that it is free from known errors. Once you define what an "error" is.

Godel incompleteness only applies to sufficiently powerful formal systems.

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

#88

Post by ukj »

ac42 wrote: post #81
ukj wrote: post #56

Earlier quoted context omitted.

Precisely, but as far as a compiler/interpreter is concerned syntax is semantics. You can't codify moral judgments.

Not sure if you are trolling, but here we go... In the case at hand, correctness of the validator expression V clearly means "V determines well-formedness of any regular expressions" which is clearly not implied by "V is well-formed" (a much weaker statement because ".*" is well-formed but matches everything). Therefore, when applying V to itself, we only learn if a weak requirement for V's correctness holds. Similar…

You are axiomatically assuming that the proposition "V determines well-formedness of any regular expressions" to be true.

I am asking you to prove that. Constructively.

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

#90

Post by YeGoblynQueenne »

rocqua wrote: post #69

So, 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?

There are Definite Clause Grammars (which can also represent context-sensitive languages) but they are a Prolog thing:

https://en.wikipedia.org/wiki/Definite_clause_grammar#Exampl...

Post reply on HN