3 ms·
To sum it all up: most "regular expression" implementations are actually powerful enough to describe context-free grammars, which are essentially regular expres
by baddox 17y ago
To sum it all up: most "regular expression" implementations are actually powerful enough to describe context-free grammars, which are essentially regular expressions mixed with balanced parentheses. The fact that the author manages to never use the term "context-free grammar" leads me to believe he's unduly surprised at his discovery.
- pkrumins 17y agoWell said. I will include this in the article. Couldn't figure out how to say it well before because they are still not equivalent to context-free languages, they are just sometimes powerful enough to describe some of the context-free languages. Therefore I didn't include it. I think only the regex implementations with recursion are context-free. Others are not, therefore I wouldn't say "most" of them are. You're right that I was surprised because I hadn't heard of recursive regular expressions in Perl before. Update: I just remembered that extended regular expressions can even recognize recursive languages. Here is a regex that decides if the number is a prime: perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ is prime"' This goes beyond context-free, therefore I couldn't just say "context-free" carelessly in the article.
- baddox 17y agoTechnically, a CFG is the intersection of an n-balanced parentheses language and a regular language. Therefore, any regular language can be described by a CFG (but obviously not vice-versa). I am completely unfamiliar with Perl and its regular expressions, but from your article and this comment I get the impression that they are Turing-complete, which would mean they're capable of describing any formal language as well as doing any "doable" computation. Is that correct?
- pkrumins 17y agoJust found this comment. I am not exactly sure if they are Turing-complete. The code in (??{code}) can be anything, so I guess, they are.
- haberman 17y agoThis is incorrect. What is being described is closer to PEGs. A parser for context-free grammars will correctly handle ambiguity between alternatives, whereas a PEG (and modern regex engines) will just try all of the alternatives and choose the first one that matches.