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

161–170 of 224 posts

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

#161

Post by unlinkr »

kortex wrote: post #76
lol768 wrote: post #70

Earlier quoted context omitted.

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

See, this is kinda what I mean. Maybe you can detect tags with regex, but maybe you shouldn't, given the widespread but subtle differences in regex engines. Perhaps the entire approach of "why are you trying to parse X?" Needs to be traced and re-evaluated.

> Maybe you can detect tags with regex, but maybe you shouldn't...

So what do you think would be a more appropriate choice for writing a tokenizer?

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

#162

Post by majewsky »

lol768 wrote: post #70
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.

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

You want (?:, not (?

Without the colon, the parser appears to be interpreting (? as "one or more instances of (", but ( is no a full expression by itself and therefore cannot be modified with a quantifier.

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

#163

Post by gbacon »

trisiak wrote: post #85
tobinfricke wrote: post #65

Earlier quoted context omitted.

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.

Regex matching with backreferences is NP-hard.

https://perl.plover.com/NPC/

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

#164

Post by heinrichhartman »

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 have been a happy user of PEG grammars for a while:

https://en.wikipedia.org/wiki/Parsing_expression_grammar

In particular this lua implementation:

http://www.inf.puc-rio.br/~roberto/lpeg/re.html

It let's you write stuff like this:

      list
Features:

- Looks like EBNF

- Regular expressions are a subset

- Fast parser.

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

#165

Post by mannykannot »

ukj wrote: post #152
mannykannot wrote: post #141

Earlier quoted context omitted.

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…

Your second paragraph is just a direct begging-of-the-question.

More significantly, verifying that sentences are well-formed in some language is not the same as proving the language’s correctness.

As a response to you argument, consider this regular language:

A

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

#166

Post by jogjayr »

sosborn wrote: post #137
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.

> I think most people read through all of the answers

You're vastly overestimating what most SO users come to the site for. They (and I include myself) just want something that'll work and isn't horrible. Even "not horrible" is something I care about but I know that many devs don't.

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

#167

Post by saltcured »

trisiak wrote: post #85
tobinfricke wrote: post #65

Earlier quoted context omitted.

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.

Grouping is very useful, but I think you can get pretty far in practical patterns with a limit of k-nesting for k=0..3 or so. That pattern language would still be regular.

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

#168

Post by blibble »

lioeters wrote: post #156
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…

> In short, I agree with you that regex cannot parse regular expressions completely. Would be happy to be proven wrong, though!

the proof that you can't parse nested pararetheses with a regular language is a pretty standard part of first year computer science

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

#169

Post by malisper »

ukj wrote: post #88
ac42 wrote: post #81

Earlier quoted context omitted.

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.

It's not possible to do this for regular expressions, but it is possible to do it for context free grammars. You can write a context-free grammar in Backus-Naur form that recognizes all context-free grammars in Backus-Naur form:

            ::=  |  
              ::=  " ">"  "::="   
    ::= " "  | ""
        ::=  |   "|"  
          ::=   |  
              ::=  |   
              ::=  | " ">"
           ::= '"'  '"' | "'"  "'"
             ::= "" |  
             ::= '' |  
         ::=  |  | 
            ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
             ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
            ::=  "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "     ::=  | "'"
        ::=  | '"'
         ::=  |  
         ::=  |  | "-"
I got this from Wikipedia: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Furth...

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

#170

Post by [deleted] »

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

[deleted]
Post reply on HN