21
$\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?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ I removed the tag [json] because it does not seem to be worth a tag on TCS SE. $\endgroup$
    – Tsuyoshi Ito
    Dec 27, 2010 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, 2010 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, 2011 at 16:58

2 Answers 2

Reset to default
30
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Curious, what's the superscript/bracket notation used here? $\endgroup$
    – jchook
    Nov 24, 2019 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, 2019 at 23:19
32
$\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.

Improve this answer
$\endgroup$
5
  • 8
    $\begingroup$ To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers is regular. $\endgroup$
    – Charles Stewart
    Dec 27, 2010 at 23:36
  • 17
    $\begingroup$ Then keep adding "arrays of" recursively until you are happy. ;-) $\endgroup$
    – Marc Hamann
    Dec 28, 2010 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, 2011 at 13:39
  • $\begingroup$ Note that I said "at least context-free". $\endgroup$
    – Marc Hamann
    Jan 31, 2011 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, 2019 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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