Re:Parsing JSON with a single regex
by gpvos on Tuesday October 22, 2013 @03:00AM
(#6590199)
Did you look at the regex? Perl regexes are also not regular; they're basically grammars.
[ Parent
| on HN ]
I might be off on this one, but regular expressions are and can be defined by regular grammar. No?
You're correct. Regular grammars are type-3 grammars in the Chomsky hierarchy, and those can be recognized by regular expressions (this is the definition of regexes in the CS sense).
In practice, however, the regex engines of most programming languages have features that makes them capable of recognizing (a subset of?) type-2 grammars, hence the confusion.
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.
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.