Parsing JSON with a single regex | Hacker News Reader

Parsing JSON with a single regex

blogs.perl.org

37 pointskamaal30 comments

To whomever is thinking "but JSON is not regular!", note that that regex is not a regular expression (Perl has a very liberal definition of regexes).

Perl regexes can be recursive: the operator $^R means "match here the whole regex itself", making the matching algorithm a full recursive descent parser. I suspect that parsing speed wouldn't be too bad because JSON is LL(1), so the parser shouldn't backtrack.

I don't think that the author is suggesting to use this in any useful code, he's just showing a cool hack. It kind of resonates well with the Perl aesthetics of short, "clever" code with as little as possible dependencies (and a fascination for regexes).

The original Randal Schwartz post (http://www.perlmonks.org/?node_id=995856) says it was infact code for a customer app.

Running code in the regex with (?{ ... code ... }) is cheating, because you can just put a whole Perl program in there. It's also one of the many badly implemented features of Perl that could be more useful if the implementation was any good. Using it will cause subtle bugs when you use regexps in the code called from there (even if you just call a sub/function), because the context (of regexp processing) isn't saved.

>>Running code in the regex with (?{ ... code ... }) is cheating, because you can just put a whole Perl program in there.

Would you like to call eval, recursion, macros, closures and many such things cheating?

Sorry but doing things without understanding or knowing the true consequences of what you are actually writing, always causes bugs. And that's true with any programming language.

Perl has many features which are designed to make the language powerful enough, to express solutions to very complex problems that other wise demands piles and piles of code in other languages. That's the whole point of the Perl language as a whole, you should take a really hard problem on a Friday night which you would find very difficult to code up in a weekend and then go to a finished script by Sunday evening.

> Would you like to call eval, recursion, macros, closures and many such things cheating?

Yes, in the context of "I did this with just a regexp".

> Sorry but doing things without understanding or knowing the true consequences of what you are actually writing, always causes bugs. And that's true with any programming language.

That's a cheap excuse for implementing this in a way that is just plain wrong, or too limited to be useful, when it could have been implemented correctly (at least if enough capable programmers still understood Perl's source code to work on it).

> Perl has many features which are designed to make the language powerful enough

I never disputed that. I used Perl almost exclusively in the past 14 years or so, so I know what I'm talking about. These broken language features are the biggest PITA about the language. They are useful for some very specific tasks, but useless for others where they could be used if they had been implemented correctly. Adding a feature with more gotchas than useful use cases is not the way to making a language more useful and enjoyale.

> Sorry but doing things without understanding or knowing the true consequences of what you are actually writing, always causes bugs. And that's true with any programming language.

I agree with this in general, but not in this situation. Let's say you use a function you verify doesn't contain regex matching. Then someone else changes that function to contain regex - s/he shouldn't need to (and may not be able to) verify every single place where this function is used - introducing a hard to find bug. Who caused a bug here? In my opinion that's the regex engine/language creator who didn't decide to either handle this case correctly in all cases, or explicitly fail in this edge case.

A great example of why you shouldn't, in fact, ever try doing this for JSON parsing within something important.

or this: http://stackoverflow.com/questions/827557/how-do-you-validat...

Or for that matter this: http://stackoverflow.com/questions/1732348/regex-match-open-...

(which is what I was expecting yeukhon's link to go to; it comes up in every discussion of abusing regular expressions to parse very non-regular languages, for good reason).

What did I just read lol. I don't want to spoil my own fun... those fonts...

Here is the original thread on which this talk is based upon : http://www.perlmonks.org/?node_id=995856

Here's the video for this presentation: http://perltv.org/v/parsing-json-with-a-regex

save disabled by author @ http://www.slideshare.net/brian_d_foy/json-regex

.. but... JSON isn't regular. And neither is HTML :(

Did you look at the regex? Perl regexes are also not regular; they're basically grammars.

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.

Yes for regular expressions, no for what is now usually called "regex" or "regexp".

Somebody show this guy a parser combinator library.

notice you can _match_ json with systems based on oniguruma/onigmo (ruby, sublime text, textmate, julia etc), and the syntax is quite readable.

Sadly, I couldn't find a way to access the nested matches, so it's quite pointless :)

Right, now parse HTML :D

Oh that has already been done too, using perl :) http://stackoverflow.com/questions/4231382/regular-expressio... (Check the answer from tchrist)

..because you can!!

very ugly presentation....

Reply on news.ycombinator.com