4 ms·
What about Python's re? How do you determine whether an implementation of "regex" is context free or regular expression as we know it? It has been a long time s
by yeukhon 13y ago
What about Python's re? How do you determine whether an implementation of "regex" is context free or regular expression as we know it? It has been a long time since I have to deal with CFG and formal CS. Thanks.
- meowface 13y agoThe vast majority of implementations of "regex engines" across all languages do not actually just match regular languages, including Python's module. They're more like general full-featured pattern matching engines for most forms of text.
- Xylakant 13y agoI don't know about python, but a lot of languages support PCRE (perl compatible regexp) or at least a large subset of it. PCRE is sometimes less than what current Perl supports but in any case a superset of "traditional" regular expressions. For example there's support for recursive subpatterns [1] which clearly places it into context free territory[2]. Other regular expression engines support similar features, so I'd say that most real world implementations are not regular expressions in the formal sense. [1] PHP manual for PCRE recursive patterns http://www.php.net/manual/en/regexp.reference.recursive.php http://www.php.net/manual/en/regexp.reference.recursive.php [2] Recursive subpatterns allow matching a language of the form (a * n)b(a * n) which is not regular.
- kamaal 13y agoActually PCRE is a wrong term to describe Perl like regular expressions in other languages. Because, when you talk of PCRE you are ideally talking of compatibility with Perl regexps circa 1995. Current day Perl regular expressions are far more powerful, and totally a very different beast.
- Xylakant 13y agoPCRE is what the library is called and it claims to offer full support for what perl5 does, both syntax and feature-wise: http://www.pcre.org/ http://www.pcre.org/