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.
No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.