3 ms·
.. but... JSON isn't regular. And neither is HTML :(
by meritt 13y ago
.. but... JSON isn't regular. And neither is HTML :(
- gpvos 13y agoDid you look at the regex? Perl regexes are also not regular; they're basically grammars.
- yeukhon 13y agoI might be off on this one, but regular expressions are and can be defined by regular grammar. No?
- Xylakant 13y agoIf 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.
- yeukhon 13y agoWhat 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/
- algorias 13y agoYou'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.
- gpvos 13y agoYes for regular expressions, no for what is now usually called "regex" or "regexp".