Is there a regular expression to detect a valid regular expression?
stackoverflow.com
stackoverflow.com
No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...
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?
One such engine is rust's https://github.com/rust-lang/regex
It can process arbitrary deep nestings? I'm not familiar with it, but I had a look and I can't see anything in there that would allow it to do it. Can you point to syntax that allows it?
In general regex's that run in linear time are based on DFA's (as opposed to NFA's - which is what most use).
A DFA is part of the Chomsky hierarchy of languages that has DFA's at the bottom (aka regex's, least powerful - can't handle recursive structures), a DFA coupled with an infinite stack for memory (aka LR parsers, can't handle context sensitive grammars, also runs in very close to linear time), and finally a DFA coupled with an infinite tape (aka Turing Machine, can do any sort of computation).
In each of these cases the DFA (regex) is essentially a computer program and all they are doing is allowing it to store stuff on various kinds of memory (none, stack, tape with arbitrary movements). An interesting corollary of this is any computer program can be expressed as a DFA.
The GP is presumably citing it as an example of a linear time regex, and not as something that can parse arbitrarily deep nestings. Note that "linear time regex engines" is a characterization that holds the size of the regex constant, such that "linear time" is with respect to the input only. The actual worst case time complexity of such regex engines is O(m * n), where m ~ len(regex) and n ~ len(input). So even with a linear time regex engine, if you bloat the size of the regex, you'll make searching slower. But, it will still be done linearly with respect to the size of the input.
> In general regex's that run in linear time are based on DFA's (as opposed to NFA's - which is what most use).
No. Please stop spreading the misuse of these terms. DFAs and NFAs have very precise meanings. It's one thing to call things regexes that aren't actually regular, but DFAs and NFAs should retain their precise theoretical meaning. A linear time regex engine such as Rust's `regex` crate uses both DFAs and NFAs in its implementation.
The Perl and PCRE folks (along with Jeffrey Friedl) have bastardized this terminology. PCRE for example claims to provide a "DFA" regex engine in its API, but it's actually an NFA. The main implementation inside PCRE (and Perl) is backtracking oriented, and carries with it much more power than an NFA. If it didn't, then the NFA could be executed in linear time, because NFAs and DFAs have equivalent power.
> An interesting corollary of this is any computer program can be expressed as a DFA.
No they can't. You're confusing terminology quite a bit here.
I'm not sure if it's possible to match regex with that time complexity, it looks like the implementation I referenced is O(AB). https://docs.rs/regex/1.3.1/regex/#untrusted-input.
(star symbol removed because hn decided to turn them into a block of italics)
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.
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.
In fact, any Turing machine using o(log log n) space recognizes a regular language (so there is an equivalent machine using O(1) space).
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 used implicitly in constructs like [a-zA-Z])
- "*" characters (same meaning as in real-world regex)
- And parentheses to allow controlling the order of operations
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.
I'm sure some sort of rather cheap algorithm falls out of the above. It wont guarantee correctness in what the balanced brackets actually contain but they will at least be balanced.
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.
> 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)\].
It's not an interesting property.
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.
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;
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!
the proof that you can't parse nested pararetheses with a regular language is a pretty standard part of first year computer science
Grouping & capturing parentheses can stay. It's only the back-referrences that you need to remove.
Example:
edit: typo.
"That's not very enterprisey of you"
Oooh, I'm laughing so hard it hurts. It's been a particularly 'enterprisey' week at work.
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.
"Well, I gave you my recommendation but hey at the end of the day you're the customer and I'm paid by the hour, so whatever you say boss"
I now consider myself very lucky to be successful enough to not have to deal with projects like that, but back when I wasn't I paid quite a few things I wanted with those sort of stupid decisions.
> Moderator's Note
> This post is locked to prevent inappropriate edits to its content. The post looks exactly as it is supposed to look - there are no problems with its content. Please do not flag it for our attention.
HTML 5 has it's own parsing rules, specified at [1]. However, I don't know of any implementation of these outside of browsers. I normally use Beatuiful Soup [2] (for Python) or HTML Agility Pack [3] (for .NET), and while I don't think these implement the exact standard, they're easier than struggling with a XML parser for HTML "in the wild".
1: https://html.spec.whatwg.org/multipage/parsing.html 2: https://www.crummy.com/software/BeautifulSoup/ 3: https://html-agility-pack.net/
> XHTML is an XML-based HTML. It serves the same function as HTML, but with the same rules as XML documents.
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 reasonably easy to process with grep and sed and awk and Perl and such"?
- I will never forget that regex can't parse XHTML
- the reason being, regex is insufficiently powerful
- when I first saw this post, I knew little about regex under the hood, this sent me down a wiki hole of FSMs, pushdown automata and turing machines
- this misconception is apparently common enough to be madness-inducing to those that know better
- use a hecking xml parser instead
It almost reminds me of a Bill Nye sketch. Teaching through a bit of non-sequitur and absurdism.
Furthermore, the asker specifically needs to distinguish between start tags and self-closing start tags. This is a token-level difference which is typically not exposed by XHTML parsers. So saying "use a parser" is less than helpful.
I have elaborated a bit in blog post: https://www.cargocultcode.com/solving-the-zalgo-regex/
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; there is no option to have the legality of a transition depend on what it read _before_ the current state. But this memory function is a requirement to recursively match opening tags to their closing tags - you need to keep a stack of opening stacks somewhere in order to then cross off their closing tags in reverse order. So regex cannot parse HTML.
Like a drunk goldfish, or a sober goldfish?
'A method to study short-term memory (STM) in the goldfish.'
'Twenty-one common goldfish (13-15.5 cm long) were randomly divided into alcohol (A) and nonalcohol (NA) groups and were trained in an alcohol solution of 400 mg/100 ml or in water, respectively. All alcohol fish were placed in an alcohol solution of 400 mg/100 ml for 3 hr before training in the same alcohol concentration. Fish were trained on a position discrimination task for 2 consecutive days. The door used for training was that opposite to each fish's spontaneous preference. Savings in relearning on Day 2 was taken as a measure of long term memory strength. Only fish which reached criterion on both days were immediately given 10 forced reversal trails in the opposite direction (i.e., a fish trained on right door was forced to choose the left door.) A and NA subjects were then tested after a 5 min (STM) delay, respectively, in a free choice situation for 10 trails (i.e., neither door was blocked). The results suggest that alcohol facilitates the STM of the forced reversal information.'
If comments in XHTML could nest you would have a problem. But this is not the case.
So you need more than a regular expression, hence your premise is incorrect.
The original question is a question about tokenization, not parsing, which is why a regular expression is sufficient.
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.
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.
[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 course much more complicated than this, but this is the basic idea.
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
The example you provide in not XHTML so not really relevant for the discussion. But in any case, a regular expression have no problem recognizing a quoted string.
Since this need doesn't appear to be an everyday one, with clearly defined targets, a simple hand-written lexer isn't hard to write, and will make less mistakes than a regex. Just use a scanning approach. As a bonus, you'll still be able to read in 12 months time.
Writing a lexer by hand is just trading ten lines of regex (a widely known declarative DSL) with hundreds of lines of custom code. I don't see how that would be more maintainable in the long run.
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
If it had been funny and right I would not have a problem with it.
tl;dr: It can indeed be solved relatively easily with a regex.
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 reason I avoid XML like the plague and keep HTML at arm's length.
| < (? \w+ )Perhaps the entire approach of "why are you trying to parse X?" Needs to be traced and re-evaluated.
So what do you think would be a more appropriate choice for writing a tokenizer?
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.
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.
And for those with a deeper understanding, they have an answer that provides the intellectual stimulation they are looking for.
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.
A lot of those people are novices when it comes to regexes, and it's useful to make it clear that there's some things that are better solved with other tools, even if you can abuse extended regexes syntaxes to solve them.
> 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.
In my experience, people sometimes ask for how to solve the more immediate detail they’re working on rather than the broader problem.
https://news.ycombinator.com/item?id=20861806
Edit: page refreshed and sure enough the sibling comment calls it out by name
Edit2: Called it the XYZ problem: https://cohan.io/the-xyz-problem/
Parsing simple regex with PCRE is cheating. If you are using PCRE, you should be parsing PCRE.
The simplest case would be DOS style globs with just * and ?, and it can parse itself: just use "*".
If you see "regex" without any special context and start thinking about what it can/can't do, then the first association should be with something like PCRE and its capabilities, not something that's bound by the pumping lemma.
I once made a recursive regex for matching a full name, complete with checking for suffixes, prefixes, an undefined amount of middle names, hyphenated last names, and Scotch-Irish names (Mc-, O'-, etc). Still simpler than this monstrosity.
My second thought: the voice of Linus Torvalds at DebConf 14 saying "Hum… No! Hum… that was quick." [1]
Though this is only speaking about a recursively defined regular expression language which is infinite, which strictly handles regular languages, as defined in computer science lessons in university.
And then, "Why not just try and see if it breaks the provided regex parser since you have one?", and it's actually one of the answers in the link… awesome. I wonder it is has security implications though (are forged regexes exploiting flawed regex parsers a thing?)
Looks like yes, depending on the engine.
PCRE for instance has a long list of security vulnerabilities including some with arbitrary code execution: https://www.cvedetails.com/vulnerability-list.php?vendor_id=...
In other words, regex can not parse regex in its entirety. It's impossible.
Perhaps you had in mind the Halting Problem: https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_i...
As a nice counter-example to what you said, you can define the Backus-Naur notation using Backus-Naur notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Furth...
[M]atching parentheses requires our recognition device to remember how many unmatched open parentheses there are. Since the only way for a DFA to remember anything is to be in one of a set of states corresponding to it, and since the unmatched open parentheses could easily outnumber the available states, we can see that the fundamental limitation of a DFA is that it can store only a finite amount of information (remember the ‘F’ in DFA?). This limitation applies to any string matching task that involves recursive structures or algebraic relationships between substrings. It is why “HTML and regex go together like love, marriage, and ritual infanticide.”
One is CS definition of regular expression matcher for regular languages. The other is extension of that into non-regular languages, typically PCRE compatible.
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 <- (name s)*
name <- [a-z][a-z]*
s <- %s*
- Looks like EBNF
- Regular expressions are a subset
- Fast parser.
https://en.wikipedia.org/wiki/Definite_clause_grammar#Exampl...
[1] https://docs.perl6.org/language/grammars
[2] https://developer.ibm.com/open/projects/rosie-pattern-langua...
Many PEG engines, especially for dynamic languages, permit grammar composition using first-class variables. That might be a small barrier to people more familiar with the terseness and conceptual simplicity of regular expressions as string'ish values. But it's fairly trivial to implement the latter using PEGs. For example, LPeg provides a small auxiliary module for doing that: http://www.inf.puc-rio.br/~roberto/lpeg/re.html
Also, Rosie seems amazing. I've not yet had the opportunity to make use of it, but I attended a presentation of Rosie by the author at a Lua workshop which left me very impressed.
sentence --> noun_phrase, verb_phrase.
noun_phrase --> det, noun.
verb_phrase --> verb, noun_phrase.
det --> [the].
det --> [a].
noun --> [cat].
noun --> [bat].
verb --> [eats].
It's directly executable as a logic program (it's Prolog syntactic sugar).
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]
s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']'].
DCGs are Turing-complete, so you can go all the way from programs to finite automata when you write a pattern to match.
They're not really a regex competitor. They were invented in the '70s as a formalism for context-free grammars to be used in representing natural language. They fit right into the logic programming language Prolog that was created soon after (and by some of the same people).
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?
One of the things that makes regex so well suited to that role is that a string is a regex that matches itself, and you can iteratively add sophistication from there. At the very least, you would want to maintain (or improve, Cthulhu knows there's plenty of room) that incremental quality in any proposed replacement, while increasing its power.
It looks like with a DCG, you have to know you're writing one up front, and have to think about what you're parsing at a much more abstract level. The average sysadmin could probably not casually toss one off for a log parsing task. If there's an alternate syntax that gets around that problem, then I'm interested. OTOH...
Re "misfeature": one of the cool things about existing parsing formalisms is all the known terminating, mostly (all?) polynomial algorithms for analyzing them. If DCGs are Turing complete, they don't have those algorithms. Turing completeness is not usually a property I want in my parser. That's what I meant by saying it's a misfeature.
Regarding Turing completeness and termination- the DCG formalism (thank you) itself is expressive enough to represent anything from finite automata to UTMs, but that doesn't mean that every grammar you write using DCG notation is Turing-complete. So, for instance, if you write a right-regular grammar as a DCG, that DCG will not be Turing-complete, it'd just be a right-regular grammar.
The DCG examples I gave above are a CFG grammar for a fragment of natural English and a single-rule grammar that matches a single string. Those are definitely not Turing-complete and parsable in polynomial time.
The difference with regexes is that you can't express CFGs or above using regexes, but you _can_ represent both regexes and CFGs using DCG notation.
>> If there's an alternate syntax that gets around that problem, then I'm interested. OTOH...
May I make a personal comment? I think your insistence on competitive language, like "i'm [not] interested", "competitor to regexes" etc, is a case of Déformation professionnelle. You sound just like a software developer hyper-focused on finding tools to maximise productivity in the office, and nothing else.
You should perhaps consider the possibilty that what we are discussing here goes a bit beyond a product that you can package and sell as an alternative to a popular tool. I mean, personally, when I realised that DCGs are executable grammars that can be run as both recognisers and generators- well let's say it shifted my understanding of what is possible to do with a computer and a programming language.
In any case I don't see the complexity you seem to see in DCGs. Like I say above, they're basically BNF. I struggle to think of a sysadmin worth her salt (so, one who knows perl, eh?) who would sweat it to write and read BNF. The kind of sysadmin I have in mind, the problem would be to drag them away from the keyboard, once they started writing a DCG to parse a log file- and realised they could write one to parse _all_ log files ever.
Regarding Turing-completeness, the entire point is about the termination of algorithms that examine parsers, not the runtime of the parsers themselves.
I also don't know how many times I need to point out that the reason I'm focusing on regexes is that that was the context for this conversation. Under any other context I'm quite interested in new parsing techniques.
Lastly, I would point out that regexes have uses far beyond a certain arbitrarily decided set of sysadmins and developers "worth their salt". Even if it's true that a meaningful subset of sysadmins are capable of writing basically sound BNF (which is not something I would count on even for CS grads, but maybe you work with smarter people than I do), there are lots of other people who could use a little more parsing power if it was offered in the right way.
With DCGs you get your recognisers for nothing and your generators for free. As I like to say.
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 validated using standard domain tools but in practice the mailbox can be anything that the server will route to a valid mailbox. The only way to validate it is to send an email.
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).
In principle, this serves as executable documentation.
A regular expression that matches valid regular expressions could be viewed as a human-readable documentation of valid regular expression syntax that has the valuable side-effect of being executable.
If, instead, we detect whether a string is a regular expression by compiling it, we may find it very difficult to read the compiler source code.
It is much more work to make an optimized regular expression engine that is also self-documenting than a regular expression.
Whereas, some form of executable DSL can serve as self-testing documentation indefinitely. DSLs can provide a separation of concerns, where the syntax is designed for readability, and the engine is designed for performance.
Modern Regexen are a dumpster fire, of course, but you asked why someone might want to, not whether this is something Everyone might want to do.
Still probably the library you are using exposes a validation function...