Is there a regular expression to detect a valid regular expression? • Hacker News Board

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

#61

Post by dillonmckay » Sun, Sep 08, 2019, 2:20 PM UTC

ChrisSD wrote: post #37

timeattack wrote: post #32

This is perfect example of a insight which leads to a rabbit hole of intertwined complexity of our concepts when you try to understand why regexp for validating regexp is actually much simpler than regexp for validating email address.

It depends what you mean by "validating email addresses". A regex that tests if a string looks like a valid email address is simple. Forget the ancient RFCs, a real world email address is in the form of `mailbox@domainname`. Which is not so difficult to test for with a bit of care. However, testing if the email address is a valid mailbox is harder and indeed impossible using regex alone. The domain name can be valida…

Even then, there is no way to determine if there is a ‘catch-all’ address configured, or some email tarpit.

I have a domain w/ a .tech TLD, and quite a few frontend JS validators do not accept my email as a valid address (government sites, some banks).

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

#62

Post by jtanderson » Sun, Sep 08, 2019, 2:21 PM UTC

raldi wrote: post #57

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.

Sure there is. Read the linked answer, or just google it. Example: https://regular-expressions.mobi/recurse.html?wlr=1

Right but parent is thinking of the quesion "is the language of valid regular expressions itself regular?", which a very different question and of course false by an easy application of the pumping lemma. However, as shown in the SO answer, they "cheat" by using some features that don't align completely with the mathematical definitions.

edit: typo.

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

#63

Post by braythwayt » Sun, Sep 08, 2019, 2:22 PM UTC

noobiemcfoob wrote: post #26

"Evaluate it in a try..catch or whatever your language provides." "That's not very enterprisey of you" Oooh, I'm laughing so hard it hurts. It's been a particularly 'enterprisey' week at work.

That answer feels entirely wrong to me. As pointed out, it may be an XY answer: It presumes the person posing the question wants to validate regular expressions.

But with something so blatantly self-referential, it actually feels unlikely to me that what they want to do is validate regular expressions. My guess is that they are generally curious about whether Regexen (PCRE or strict regular expressions) are powerful enough to validate Regexen (again whether PCRE or strict).

XY answers are good for avoiding a lot of unnecessary yak-shaving/accidental complexity of a bad solution. But the conversation around whether we are talking about recognizing strict Regexen or PCRE Regexen, and in turn whether we are using strict Regexen or PCRE Regexen to recognize them is not accidental complexity or yak-shaving, it is intrinsic to understanding the nature of the problem and solution spaces.

I too find the answer humorous for the "enterprisey" reference, but I think it would be a very bad answer if we are judging it strictly on the basis of its value.

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

#64

Post by ukj » Sun, Sep 08, 2019, 2:26 PM UTC

mannykannot wrote: post #47

ukj wrote: post #33

Earlier quoted context omitted.

You are necessarily claiming that a compiler is incapable of false negatives. e.g incorrectly validating its own code. Beware of bugs in the above code; I have only proved it correct, not tried it --Donald Knuth

The fact that someone might make a mistake in doing something does not show it cannot be done. More generally, You seem to be mistaking validating a program's source with the question of whether it performs its intended purpose. These are different things, and attempting to conflate them will only lead to confusion.

> You seem to be mistaking validating a program's source with the question of whether it performs its intended purpose.

In general, that is a useful distinction to make, but you forgot about the edge case where the distinction is meaningless.

A self-hosting compiler's intended purpose is to validate its own source code.

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

#65

Post by tobinfricke » Sun, Sep 08, 2019, 2:27 PM UTC

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?

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

#66

Post by lonelappde » Sun, Sep 08, 2019, 2:30 PM UTC

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…

CargoCode is correct. Zalgo simply misread the question because he was so sick of similar subtly different questions.

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

#67

Post by bryanrasmussen » Sun, Sep 08, 2019, 2:31 PM UTC

unlinkr wrote: post #45

stfwn wrote: post #38

Earlier quoted context omitted.

If you were looking for the reason why a regex cannot parse HTML, it is because HTML has matching nested tags and regex parsers are finite state machines (FSM). What this means is that a regex parser is like a goldfish. It only knows about the state it is currently in (what it just read) and which possible states it may transition to (what is legally allowed to come next). The fish never remembers where it was before…

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.

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

#68

Post by lonelappde » Sun, Sep 08, 2019, 2:32 PM UTC

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 it's mostly useless, since it can't match (variable-count) repeated strings of length greater than 1. Goruping isn't only about extraction.

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

#69

Post by rocqua » Sun, Sep 08, 2019, 2:32 PM UTC

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?

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

#70

Post by lol768 » Sun, Sep 08, 2019, 2:32 PM UTC

unlinkr wrote: post #44

gamache wrote: post #2

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

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.

It doesn't work for me with regex101. "The preceding token is not quantifiable" on this part:


    
      Permalink
      View on HN
      Reply on HN
      Top