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

151–160 of 224 posts

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

#151

Post by mannykannot »

jimhefferon wrote: post #126
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.

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…

Sort of, but if (and only if) you know what a regular expression formally means, you can disambiguate the equivocation introduced by ambiguous usage.

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

#152

Post by ukj »

mannykannot wrote: post #141
ukj wrote: post #115

Earlier quoted context omitted.

I have already done that, what I am unsure of is how to go about convincing you. With compilers - I just fix the bug myself. With humans, I have to convince the human to self-correct. Common problem in distributed systems that - leader election.

It is a general rule that those who avoid answering a question do not have an answer, and this is no exception. Here, You completely misunderstand Chomsky’s hierarchy: By your inverted-hierarchy argument, the simplest regular language would be complex enough that incompleteness would be an issue in its validation.

Well, this looks like abuse of Cunningham's law, but I'll bite.

It is a general rule that general rules have exceptions. And you have (incorrectly) asserted that this is not an exception.

Q.E.D

Even the most powerful languages (Type 0 in the hierarchy) cannot solve the halting problem. Which is equivalent to Godel's incompleteness theorem.

https://www.scottaaronson.com/blog/?p=710

If a Type 3 grammar can recursively prove its own correctness, it's not a Type 3 grammar!

But if you desperately want to be right, I will happily lie to you (you are right, I am wrong), so I can move on with my life.

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

#153

Post by ridaj »

fortran77 wrote: post #132

We see good examples of "the problem with StackOverflow" here. The second highest-rated answer is "Evaluate it in a try..catch or whatever your language provides." and it's justified because "Surely the real question is 'how do I validate a regular expression'." This is a fascinating computer science question and I'm pretty sure the questioner wasn't asking "how do I validate a regular expression" because he would ha…

Maybe the second-ranked answer is trying to second-guess the question, but at least the highest-ranked answer is precise...

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

#154

Post by journalctl »

unlinkr wrote: post #131
journalctl wrote: post #109

Earlier quoted context omitted.

With a pushdown automaton [1] or something like a linear bounded automaton [2]. [1] https://en.m.wikipedia.org/wiki/Pushdown_automaton [2] https://en.m.wikipedia.org/wiki/Linear_bounded_automaton More specifically, a stack lets you keep track of nesting. See an opening tag, push something onto a stack. See a closing tag, pop the stack. If the stack is empty at the end, the tags match. Parsing XHTML in real life is of…

I think there are a lot of knee-jerk answer because people see "XHTML" and "regex" in the same sentence and immediately think "not possible". But the actual question is clearly not about matching start tags to end tags or building DOM or anything like that - which indeed would require a stack. The question is about recognizing start and end tags. You can do that perfectly fine with regular expressions - indeed many p…

Sorry, I misread. Indeed, actually tokenizing text is accomplished with regular expressions (although some parsers don’t need a tokenization pass, but details :).

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

#155

Post by piedar »

mholt wrote: post #150
fortran77 wrote: post #132

We see good examples of "the problem with StackOverflow" here. The second highest-rated answer is "Evaluate it in a try..catch or whatever your language provides." and it's justified because "Surely the real question is 'how do I validate a regular expression'." This is a fascinating computer science question and I'm pretty sure the questioner wasn't asking "how do I validate a regular expression" because he would ha…

I also think it's a fascinating question, but if the asker wanted a theoretical answer more than a practical one, it should have been asked on the CS or CS theory stack exchange: https://cs.stackexchange.com/ & https://cstheory.stackexchange.com/

...neither of which existed when the question was asked.

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

#156

Post by lioeters »

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.

> (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 expressions completely. Would be happy to be proven wrong, though!

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

#158

Post by detaro »

lioeters wrote: post #157
sixstringtheory wrote: post #142

Earlier quoted context omitted.

Good edge case. I’d say to immediately return an ‘unbalanced’ result once the count goes negative.

((((()

doesn't end up with zero at the end, rejected?

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

#159

Post by kmstout »

No. I wrote about this awhile back (https://reindeereffect.github.io/2018/06/24/regex/#the-limit...). From that post:

[M]atching parentheses requires our recognition device to remember how many unmatched open parentheses there are. Since the only way for a DFA to remember anything is to be in one of a set of states corresponding to it, and since the unmatched open parentheses could easily outnumber the available states, we can see that the fundamental limitation of a DFA is that it can store only a finite amount of information (remember the ‘F’ in DFA?). This limitation applies to any string matching task that involves recursive structures or algebraic relationships between substrings. It is why “HTML and regex go together like love, marriage, and ritual infanticide.”

Post reply on HN