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

131–140 of 224 posts

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

#131

Post by unlinkr »

journalctl wrote: post #109
unlinkr wrote: post #71

Earlier quoted context omitted.

How do you think an XHTML parser is written? In particular, how does an XHTML parser identify tokens like start and end tags?

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 parsers uses regular expressions to tokenize the input before parsing.

Furthermore, the question specifically needs to recognize the difference between start-tags and self-closing tags. A differece which is not exposed by most XHTML parsers a far as I am aware

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

#132

Post by fortran77 »

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 have asked that.

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

#133

Post by [deleted] »

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?

[deleted]

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

#134

Post by Piskvorrr »

gpm wrote: post #122
dyarosla wrote: post #113

Earlier quoted context omitted.

This only works if you have a single type of parenthesis. Is that applicable to regex expressions in general that only ()’s can nest?

As typically defined academically, yes. In the real world things might be more complex, but I think it would hold true for many implementations. Academically a regex is a string of of: - character literals - "epsilon" characters (meaning empty string) - "+" characters (which means either what we see before the + or what we see after the +, in real-world regex these are usually represented as | instead of + as well as…

In other words, "if we build a state machine which is different from a regex, it will perform differently than a regex would." That's trivially true, but is it interesting beyond restating "there is no Silver Bullet"?

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

#135

Post by notyourday »

Don't use a regex to do it. Most of languages have a way to catch runtime errors. Stick regex to a variable, create a dummy input and run that block with a catcher around it. If catcher throws a runtime error, you have a bad regex. If it does not, you have a valid regex.

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

#136

Post by gpm »

Piskvorrr wrote: post #134
gpm wrote: post #122

Earlier quoted context omitted.

As typically defined academically, yes. In the real world things might be more complex, but I think it would hold true for many implementations. Academically a regex is a string of of: - character literals - "epsilon" characters (meaning empty string) - "+" characters (which means either what we see before the + or what we see after the +, in real-world regex these are usually represented as | instead of + as well as…

In other words, "if we build a state machine which is different from a regex, it will perform differently than a regex would." That's trivially true, but is it interesting beyond restating "there is no Silver Bullet"?

Technically we aren't discussing the regex itself here but the syntax for defining a regex.

You could use a different syntax for defining the same regex, and that syntax could have different properties. For instance you could use parantheses like racket where "(...)" and "[...]" have the same meaning, but "(...]" is not well formed syntax (if I remember my racket correctly). Using such a syntax to define regex a counter would no longer suffice to decide if a string is a regex.

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

#137

Post by sosborn »

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…

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.

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

#138

Post by thereare5lights »

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'm pretty sure the questioner wasn't asking "how do I validate a regular expression" because he would have asked that.

In my experience, people sometimes ask for how to solve the more immediate detail they’re working on rather than the broader problem.

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

#139

Post by nurettin »

unlinkr wrote: post #127
nurettin wrote: post #116

Earlier quoted context omitted.

"/>

That is a valid XHTML tag (if I remember correctly) and can be matched perfectly fine by a regex.

Perhaps something like "([^"]*)" could skip what is inside the string literal. Unless there is "<input" in the string literal, then where you start parsing becomes very important.

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

#140

Post by nightfly »

jessaustin wrote: post #95
benj111 wrote: post #77

Earlier quoted context omitted.

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?

Just considering the language of balanced parentheses, the only memory needed is a single integer to track depth. If we see a "(", increment. If we see a ")", decrement. If we never go negative and end up with zero, that's a balanced parentheses expression. (To be clear, the parser I've described is not a regex parser.) Adding the rest of the regex machinery makes this a bit more complex, but in general, if the compu…

)))((()(()
Post reply on HN