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

211–220 of 224 posts

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

#211

Post by [deleted] »

tzs wrote: post #124
gamache wrote: post #2

I believe Zalgo has the answer to this, via an equivalent question. https://stackoverflow.com/questions/1732348/regex-match-open...

From that answer: "You can't parse [X]HTML with regex". I've always wondered how that came about. How come very early in the development of the web no one important enough for people to pay attention to them said, "Hey...wait a second. If this thing becomes popular, people are going to really want to processes web documents with their usual text file processing tools and techniques. We really outta make this thing re…

[deleted]

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

#212

Post by unlinkr »

bryanrasmussen wrote: post #67
unlinkr wrote: post #45

Earlier quoted context omitted.

The question is about identifying end-tags in XHTML. This is indeed possible with a regex.

theoretically I believe an end tag really requires a valid start tag. anyway you can probably answer any number of simple questions about a bit of HTML using regex but as code wants to grow to handle more use cases there will come a time when the solution will break down and the code that wrote to handle all the previous uses will need to be rewritten using something other than regex.

You have to distinguish between the different levels of parsing.

Regexes are appropriate for tokenization, which is the task of recognizing lexical units like start tags, end tags, comments and so on. The SO question is about selecting such tokens, so this can be solved with a regex.

If you have more complex use cases like matching start tags to end tags, you might need a proper parser on top. But you still need tokenization as a stage in that parser! I don't see what you would gain by using something other than regexes for tokenization? I guess in some extreme cases a hand written lexer could be more performant, but in the typical case a regex engine would probably be a lot faster than the alternatives and certainly more maintainable.

I know it is possible to write a parser without a clear tokenization/parsing separation - but it is not clear to me this would be beneficial in any way.

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

#213

Post by unlinkr »

kortex wrote: post #60
unlinkr wrote: post #44

Earlier quoted context omitted.

Here is the answer to the question: https://www.cargocultcode.com/solving-the-zalgo-regex/ tl;dr: It can indeed be solved relatively easily with a regex.

This is a bit out of my wheelhouse, but this feels wrong, or at least naively capable. Like it feels like this sort of reasoning leads to the kind of bugs (depending on what you use the result of the rexex for) that allow for code injection, a la the Equifax hack. Maybe another HN poster can back me up, or explain why in fact Zalgo is mistaken and CargoCode is correct. Either way, this sort of complexity is one reaso…

This is what I really hate about the Zalgo answer. It is instilling people some vague sense that regular expressions are somehow bad, wrong and dangerous. But without any real arguments or contexts which would allow you to evaluate if the feeling is justified.

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

#214

Post by nurettin »

unlinkr wrote: post #210
nurettin wrote: post #139

Earlier quoted context omitted.

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.

That pattern would indeed match a quoted string. I don't see how it would matter if the quoted string contains something like "<input". It can contain anything except a quote character.

It just makes the starting offset of the regex input important.

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

#215

Post by yifanl »

unlinkr wrote: post #53
kyberias wrote: post #40

I hate it how the accepted answer is incorrect and does not teach the fundamental property of regular expressions.

It only works in practice, not in theory.

It doesnt work in practice, PCRE does not validate all valid PCRE expressions.

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

#216

Post by Izkata »

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 think it's a more frustrating example:

> If so please give example code below.

The phrasing, especially combined with what time of year it was asked, makes me think it's a homework question from a CS logic course where they have to provide an example showing the answer is "no", and explain why.

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

#217

Post by LoSboccacc »

unlinkr wrote: post #202
LoSboccacc wrote: post #105

Earlier quoted context omitted.

it's sad that today the stack overflow majority shares your mindset and an answer like that would drown in downvotes or killed by moderation. some people like to act super serious all the time like they're playing a sitcom version of what they think adulthood is in a quest to be the most boring person on earth like if that's the goal of human interaction

The problem is it is funny and wrong . Apparently it have given a lot of people really confused ideas about what is possible and what is not possible with regular expressions. If it had been funny and right I would not have a problem with it.

Stack overflow is not a homework help group, the "Regex are the wrong tool for the job" answer is more correct than the answer with the working Regex.

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

#218

Post by unlinkr »

nurettin wrote: post #214
unlinkr wrote: post #210

Earlier quoted context omitted.

That pattern would indeed match a quoted string. I don't see how it would matter if the quoted string contains something like "<input". It can contain anything except a quote character.

It just makes the starting offset of the regex input important.

Sure. But that would be true for any parsing technique. No parser known to man would be able to produce a valid parse if you start it in the middle of a quoted string!

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

#219

Post by andrewflnr »

YeGoblynQueenne wrote: post #199
andrewflnr wrote: post #180

Earlier quoted context omitted.

That looks great, but it's hard to position it as a regex competitor. I should be more explicit about what I mean by "regex-style": The cool thing about regex that makes them so approachable is that they kind of look like the thing they're describing/matching. Your thing here mostly does not.

"My thing here" is a grammar so it describes a class of strings. Perhaps this is why it looks to you unlike what it describes? You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history: \[13\/13,15\/12,24-24] You could write this like so in DCG notation: s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']']. And that would match the string "[13/…

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.

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

#220

Post by YeGoblynQueenne »

andrewflnr wrote: post #219
YeGoblynQueenne wrote: post #199

Earlier quoted context omitted.

"My thing here" is a grammar so it describes a class of strings. Perhaps this is why it looks to you unlike what it describes? You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history: \[13\/13,15\/12,24-24] You could write this like so in DCG notation: s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']']. And that would match the string "[13/…

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?

Edit: Apologies if I sound too terse. I'm confused by the terminology of "competitor", "alternative" etc. Are we in some kind of competition to find a technological solution that will take some prize? If so, I'd like to know the rules before I commit to any solution. What exactly are we trying to achieve here?

Post reply on HN