20
$\begingroup$

I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself.

The reason I ask, is because I was wondering if one could use regular expressions to effectively pars JSON.

Could someone with enough rep please create the tags and for me?

$\endgroup$
3
  • 6
    $\begingroup$ I removed the tag [json] because it does not seem to be worth a tag on TCS SE. $\endgroup$ Dec 27 '10 at 20:42
  • $\begingroup$ @Tsuy, sounds good. Obviously I'm not an avid user of the site, so I'm sure you know better. $\endgroup$
    – jjnguy
    Dec 27 '10 at 20:46
  • 1
    $\begingroup$ Remember that regex implementations frequently match more than just regular languages. E.g. you can use lookaheads in most implementations, which will accept $a^nb^n$ correctly, solving the $[^nx]^n$ problem others mentioned below. $\endgroup$
    – Xodarap
    Jan 12 '11 at 16:58
29
$\begingroup$

Since $a^n b^n$ is not a regular language, neither is JSON, since $[^n 5 ]^n$ is valid input for any $n$. Likewise, your regular expression parser would have to properly reject any input $[^m 4 ]^n$ where $m \ne n$ which you cannot do with regular expressions.

Hence, JSON is not regular.

$\endgroup$
2
  • $\begingroup$ Curious, what's the superscript/bracket notation used here? $\endgroup$
    – jchook
    Nov 24 '19 at 23:08
  • 1
    $\begingroup$ @jchook The superscript notation means 'repeated.' So $a^n$ would be $a$ repeated $n$ times. Similarly, the notation $[^n$ means $[$ repeated $n$ times. The brackets have no special meaning. A regular language cannot 'count' how many brackets are on each side, so they cannot tell if both sides have the same number of brackets. $\endgroup$
    – Nick ODell
    Dec 26 '19 at 23:19
31
$\begingroup$

No, it's not regular. Since it allows arbitrary embedding of balanced delimiters, it must be at least context-free.

For example, consider an array of arrays of arrays:

[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ] 

Clearly you couldn't parse that with true regular expressions.

$\endgroup$
5
  • 8
    $\begingroup$ To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers is regular. $\endgroup$ Dec 27 '10 at 23:36
  • 17
    $\begingroup$ Then keep adding "arrays of" recursively until you are happy. ;-) $\endgroup$ Dec 28 '10 at 0:49
  • 1
    $\begingroup$ Standard JSON is context-free, but most implementations only support unique keys. I moved my unanswered question from stackoverflow to: cstheory.stackexchange.com/questions/4668/… $\endgroup$
    – Jakob
    Jan 31 '11 at 13:39
  • $\begingroup$ Note that I said "at least context-free". $\endgroup$ Jan 31 '11 at 15:18
  • $\begingroup$ Expanding on @CharlesStewart's comment, does this mean that "JSON with a strict max depth IS a regular language"? Or do other features of JSON prevent this? $\endgroup$
    – jchook
    Nov 24 '19 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.