6 ms·

> 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) th

> 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.

jameshart 7y ago
This is true if you want to handle arbitrarily deep nested parents. But any given string you are asked to validate to see if it is a regex will be a finite length, and contain a finite number of opening paren characters. So it’s maximum possible nesting depth is known. And you can construct, fairly trivially, a regex that can validate paren nesting up to a fixed depth. So, in practice, you could use a regular expression to validate the paren nesting of any given string - if you were allowed to prepare the regex based on the string length, or on running another regex over the string first. What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not.
- daveFNbuck 7y ago
  If you allow generating a regular expression based on string length, you can validate any computable language with a regular expression. It's trivial to just run a solver on all strings of that length and or the accepted ones together. > What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not. It's fairly trivial to validate things like a-z being valid in a character class while z-a isn't. There are only finitely many legal ranges. You can just list them all, like \[(a-a|a-b|a-c|...|z-z)\].
- repsilat 7y ago
  For a fixed input length all languages are decidable by regular expressions. Trivially, the union of all valid input strings of that length, like "(abc|def|...)". It's not an interesting property.
raldi 7y ago
Sure there is. Read the linked answer, or just google it. Example: https://regular-expressions.mobi/recurse.html?wlr=1 https://regular-expressions.mobi/recurse.html?wlr=1
- josalhor 7y ago
  It depends if we're talking regex in the mathematical sense or in the programming one.
- jtanderson 7y ago
  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.
- deleted 7y ago
  [deleted]
tobinfricke 7y ago
Follow-up question: without the grouping parentheses, is the regex language regular?
- lonelappde 7y ago
  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.
- trisiak 7y ago
  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.
  - gbacon 7y ago
    Regex matching with backreferences is NP-hard. https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
  - saltcured 7y ago
    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.
mannykannot 7y ago
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-expression-limitations/ https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...
- benj111 7y ago
  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?
  - mannykannot 7y ago
    There is an importance to theoretical considerations that goes beyond their immediate practical applications. Ultimately, it comes down to how well one understands what is going on. Having said that, I think there are practical applications. Suppose you were unaware of this result, and thought a true RE could validate your input? A more knowledgeable attacker might be able to craft an input that exploits the inherent limitations of your validator. Also in practice, attempting to write a true RE to parse a language that allows restricted recursion rapidly becomes complicated. It is the wrong tool for the job.
  - jessaustin 7y ago
    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 computer can store the string, it can check whether it's regular.
    - dyarosla 7y ago
      This only works if you have a single type of parenthesis. Is that applicable to regex expressions in general that only ()’s can nest?
tgv 7y ago
It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.
- ggrrhh_ta 7y ago
  Very underrated comment. Very good point to give food for thought although I think it is clear that it was meant to be on the usual textual representation using the simplest re language (without extensions).
- morelisp 7y ago
  An analogous problem for this representation would be detecting transitions to undefined states, or ambiguous (duplicate) transitions.
  - tgv 7y ago
    I didn't verify it, but my intuition says that can't be done with a CFG; it seems at least context-sensitive.
- deleted 7y ago
  [deleted]
jimhefferon 7y ago
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 using, say, Perl's regular expressions. I know I have heard it used that way often. Since Perl regular expressions can accept anything a Turing machine can accept, the answer to the question in this case is yes.
- mannykannot 7y ago
  Sort of, but if (and only if) you know what a regular expression formally means, you can disambiguate the equivocation introduced by ambiguous usage.
- wahern 7y ago
  Very few people know that Perl's regex engine (since 5.10) supports recursion. And recursive matching cannot perform recursive captures, which is why at best it can only be used to validate a string, not parse it, making it not particularly useful in practice. For these reasons I would never assume that someone using the term "regular expression" inclusively of Perl would have in mind such capabilities. IME, such a loose definition simply implies things like zero-width assertions, backcaptures, etc. Here's a proof-of-concept Perl 5.10+ JSON validator I came up with for a presentation to Perl engineers introducing PEGs and Lua's LPeg module. Of the 20-30 people in the room, I doubt anybody in the audience knew this was even possible with Perl. my $grammar = qr{ ^(?&Value) $ (?(DEFINE) (?<Value> \s∗ (?: (?&Array) | (?&Object) | (?&Boolean) | (?&Number) | (?&String) | (?&Null) ) \s∗ ) (?<Array> \[ \s∗ (?:(?&Value) (?:\s∗,\s∗ (?&Value))∗)? \s∗ \]) (?<Object> \{ \s∗ (?:(?&KeyV) (?:\s∗,\s∗ (?&KeyV))∗)? \s∗ \}) (?<KeyV> \s∗ (?:(?&String) \s∗:\s∗ (?&Value))) \s∗ (?<Boolean> true | false) (?<Number> \d+) (?<String> "[^\"]∗") (?<Null> null) ) }xs; Note: I was trying to fit it all on a single slide, so the definition for String doesn't handle escaped characters. There may be other deficiencies. I copy+pasted this from the PDF slide deck as I can't find the original Beamer source. Any broken spacing and Unicode substitutions probably aren't original.
lioeters 7y ago
> (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!
- blibble 7y ago
  > 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
  - lioeters 7y ago
    It doesn't stop some of us from trying though! :)

jameshart 7y ago

This is true if you want to handle arbitrarily deep nested parents. But any given string you are asked to validate to see if it is a regex will be a finite length, and contain a finite number of opening paren characters. So it’s maximum possible nesting depth is known. And you can construct, fairly trivially, a regex that can validate paren nesting up to a fixed depth. So, in practice, you could use a regular expression to validate the paren nesting of any given string - if you were allowed to prepare the regex based on the string length, or on running another regex over the string first. What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not.

daveFNbuck 7y ago
If you allow generating a regular expression based on string length, you can validate any computable language with a regular expression. It's trivial to just run a solver on all strings of that length and or the accepted ones together. > What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not. It's fairly trivial to validate things like a-z being valid in a character class while z-a isn't. There are only finitely many legal ranges. You can just list them all, like \[(a-a|a-b|a-c|...|z-z)\].
repsilat 7y ago
For a fixed input length all languages are decidable by regular expressions. Trivially, the union of all valid input strings of that length, like "(abc|def|...)". It's not an interesting property.

raldi 7y ago

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

josalhor 7y ago
It depends if we're talking regex in the mathematical sense or in the programming one.
jtanderson 7y ago
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.
deleted 7y ago
[deleted]

tobinfricke 7y ago

Follow-up question: without the grouping parentheses, is the regex language regular?

lonelappde 7y ago
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.
trisiak 7y ago
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.
- gbacon 7y ago
  Regex matching with backreferences is NP-hard. https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
- saltcured 7y ago
  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.

mannykannot 7y ago

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-expression-limitations/ https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...

benj111 7y ago
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?
- mannykannot 7y ago
  There is an importance to theoretical considerations that goes beyond their immediate practical applications. Ultimately, it comes down to how well one understands what is going on. Having said that, I think there are practical applications. Suppose you were unaware of this result, and thought a true RE could validate your input? A more knowledgeable attacker might be able to craft an input that exploits the inherent limitations of your validator. Also in practice, attempting to write a true RE to parse a language that allows restricted recursion rapidly becomes complicated. It is the wrong tool for the job.
- jessaustin 7y ago
  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 computer can store the string, it can check whether it's regular.
  - dyarosla 7y ago
    This only works if you have a single type of parenthesis. Is that applicable to regex expressions in general that only ()’s can nest?

tgv 7y ago

It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.

ggrrhh_ta 7y ago
Very underrated comment. Very good point to give food for thought although I think it is clear that it was meant to be on the usual textual representation using the simplest re language (without extensions).
morelisp 7y ago
An analogous problem for this representation would be detecting transitions to undefined states, or ambiguous (duplicate) transitions.
- tgv 7y ago
  I didn't verify it, but my intuition says that can't be done with a CFG; it seems at least context-sensitive.
deleted 7y ago
[deleted]

jimhefferon 7y ago

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 using, say, Perl's regular expressions. I know I have heard it used that way often. Since Perl regular expressions can accept anything a Turing machine can accept, the answer to the question in this case is yes.

mannykannot 7y ago
Sort of, but if (and only if) you know what a regular expression formally means, you can disambiguate the equivocation introduced by ambiguous usage.
wahern 7y ago
Very few people know that Perl's regex engine (since 5.10) supports recursion. And recursive matching cannot perform recursive captures, which is why at best it can only be used to validate a string, not parse it, making it not particularly useful in practice. For these reasons I would never assume that someone using the term "regular expression" inclusively of Perl would have in mind such capabilities. IME, such a loose definition simply implies things like zero-width assertions, backcaptures, etc. Here's a proof-of-concept Perl 5.10+ JSON validator I came up with for a presentation to Perl engineers introducing PEGs and Lua's LPeg module. Of the 20-30 people in the room, I doubt anybody in the audience knew this was even possible with Perl. my $grammar = qr{ ^(?&Value) $ (?(DEFINE) (?<Value> \s∗ (?: (?&Array) | (?&Object) | (?&Boolean) | (?&Number) | (?&String) | (?&Null) ) \s∗ ) (?<Array> \[ \s∗ (?:(?&Value) (?:\s∗,\s∗ (?&Value))∗)? \s∗ \]) (?<Object> \{ \s∗ (?:(?&KeyV) (?:\s∗,\s∗ (?&KeyV))∗)? \s∗ \}) (?<KeyV> \s∗ (?:(?&String) \s∗:\s∗ (?&Value))) \s∗ (?<Boolean> true | false) (?<Number> \d+) (?<String> "[^\"]∗") (?<Null> null) ) }xs; Note: I was trying to fit it all on a single slide, so the definition for String doesn't handle escaped characters. There may be other deficiencies. I copy+pasted this from the PDF slide deck as I can't find the original Beamer source. Any broken spacing and Unicode substitutions probably aren't original.

lioeters 7y ago

> (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!

blibble 7y ago
> 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
- lioeters 7y ago
  It doesn't stop some of us from trying though! :)