Re:Parsing JSON with a single regex
by Xylakant on Tuesday October 22, 2013 @03:08AM
(#6590221)
If you use the strict term, yes. If you're looking at what Perl calls Regexp, then no. Perls regular expressions are a superset that can parse (at least some) context free languages.
[ Parent
| on HN ]
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.
I 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
[2] Recursive subpatterns allow matching a language of the form (a * n)b(a * n) which is not regular.
Actually 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.
PCRE 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/
The 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.