Write a program that determines whether its input is valid JSON.

  • Input: ASCII text: [\x00-\x7F]*

    Note: if ASCII is problematic, feel free to use another encoding, but indicate it in your post.

  • Output: Valid or Invalid. Trailing newline may be omitted.

  • Example:

    $ echo '{"key": "value"}' | ./json-validate
    Valid
    $ echo '{key: "value"}' | ./json-validate
    Invalid
    
  • Rules:

    • Do not use a JSON parsing library.
    • Partially-correct solutions are allowed, but frowned upon.
    • Post your test suite score (see below).

The shortest correct solution wins.

Please run json-validate-test-suite.sh on your program, and post your score. Example:

$ ./json-validate-test-suite.sh ./buggy-prog
fail: should be invalid:  [ 0.1e ] 
fail: should be invalid:  [ 0.1e+-1 ] 
fail: should be invalid:  [ 0.1e-+1 ] 
score: 297/300

Resources:

  • json.org - Concise definition of the JSON grammar with easy-to-follow pictures.
  • RFC 4627 - JSON specification
  • json-validate.c - A 200-line implementation that passes the testsuite.

The JSON grammar is as follows:

json: object | array

object: '{' members? '}'
    members: pair (',' pair)*
    pair:    string ':' value

array: '[' elements? ']'
    elements: value (',' value)*

value: string
     | number
     | object
     | array
     | 'true'
     | 'false'
     | 'null'

string: '"' char* '"'
    char: [^"\\\x00-\x1F]
        | '\' escape
    escape: ["\\/bfnrt]
          | u [0-9A-Fa-f]{4}

number: '-'? (0 | [1-9][0-9]*) ('.' [0-9]+)? ([Ee] [+-]? [0-9]+)?

Also, whitespace can appear before or after any of the six structural characters {}[]:,

ws = [\t\n\r ]*

Bear in mind the following:

  • Be careful with functions like isspace(). Whitespace in JSON is [\t\n\r ], but isspace() also treats \v (vertical tab) and \f (form feed) as space. Although word has it that isdigit() can accept more than just [0-9], should be okay to use here, as we assume input is in ASCII.
  • \x7F is technically a control character, but the JSON RFC doesn't mention it (it only mentions [\x00-\x1F]), and most JSON parsers tend to accept \x7F characters in strings. Because of this ambiguity, solutions may choose to either accept them or not.
  • 7
    Your "partially-correct solutions allowed" note is making me dream of extracting a regex from a genetic algorithm. I must be insane. – J B Feb 4 '11 at 14:58
  • @J B: That would be awesome. – Joey Adams Feb 4 '11 at 15:43
  • Just curious, why is {key: "value"} consider invalid JSON ? It is valid javascript. – HoLyVieR Feb 5 '11 at 3:12
  • @HoLyVieR: I imagine it's so JSON will be easier to parse and less ambiguous to implementors. I'm not sure I like this restriction either. – Joey Adams Feb 5 '11 at 4:31
  • Anyone got a copy of the validator script? – Armand Sep 27 '12 at 18:04
up vote 7 down vote accepted

PHP : 297 285 264 253 characters

<?=preg_match(<<<'R'
~([\h
]*)({(?1)((("([^"\\\0- ]| |\\(["\\/bfnrt]|u[\dA-Fa-f]{4}))*")(?1):(?1)((?5)|-?(0|[1-9]\d*)(\.\d+)?([Ee][+-]?\d+)?|(?2)|true|false|null))(((?1),(?1))(?4))*)?}|\[(?1)((?8)((?13)(?8))*)?(?1)])(?1)\z~A
R
,`cat`)?'Valid':'Invalid';

score: 300/300

This is a full, recursive implementation of the JSON grammar.

It works only on PHP ≥ 5.3 due to nowdoc syntax (heredoc would have required to double all \).

Readable version:

(this is the same regex, with named capture groups and extended syntax):

#!/usr/bin/env php
<?php

$re = <<< 'RE'
~\A (?P<ws>[\t\n\r ])* (
    (?P<object>\{ (?P>ws)*
        (?P<members>
            (?P<pair>
                (?P<string>
                    "(?P<char>
                        [^"\\\x00-\x1F]
                        |\\(?P<escape>
                            ["\\/bfnrt]
                            |u [0-9A-Fa-f]{4}
                        )
                    )*"
                ) (?P>ws)* : (?P>ws)* (?P<value>
                    (?P>string)
                    | (?P<number>-? (0 | [1-9][0-9]*) (\. [0-9]+)? ([Ee] [+-]? [0-9]+)? )
                    | (?P>object)
                    | (?P>array)
                    | true
                    | false
                    | null
                )
            ) ( (?P>ws)* , (?P>ws)* (?P>pair) )*
        )?
    \})
    |(?P<array>\[ (?P>ws)*
        (?P<elements>
            (?P>value) ( (?P>ws)* , (?P>ws)* (?P>value) )*
        )?
    (?P>ws)* \])
) (?P>ws)* \z~x
RE;

if (preg_match($re, stream_get_contents(STDIN))) {
    echo 'Valid';
} else {
    echo 'Invalid';
}
  • Wow. ` ` ` ` ` ` – Nathan Osman Feb 5 '11 at 0:14
  • You need to include the <?php IMO. – anonymous coward Feb 5 '11 at 9:29
  • Added. 264 chars now :-) – user300 Feb 5 '11 at 13:02

Python - 340 314 299 292 chars

import re,os
r=x=re.sub
z=r('0\.0+','0',r('e[+-]?0+|[\t\n\r]',' ',r(r'"(\\["nrtb\\/]|[^\\"\0-\37])*"','1',r(r'true|false|null|\\u\w{4}|[1-9]\d*','0',os.read(0,99)))))
while z!=x:z,x=r('\{(1:\d)?(,\\1)*\}|\[(-?\d(,-?\d)*)?\]','0',r(' *([][{}:,]) *','\\1',z)),z
print['Inv','V'][z=='0']+'alid'

score

$ ./json-validate-test-suite.sh ./codegolf-474.py
score: 300/300

Scala - 390 chars

import scala.util.parsing.combinator.JavaTokenParsers
object J extends JavaTokenParsers{def j=o|a
def o:Parser[Any]="{"~repsep(p,",")~"}"
def p=s~":"~v
def a:Parser[Any]="["~repsep(v,",")~"]"
def v=s|o|a|"true"|"false"|"null"
def s=stringLiteral
def n=floatingPointNumber}
object Main{def main(a:Array[String]){print(if(J.parseAll(J.j,readLine()).successful)"Valid"else"Invalid")}}

This is no-brainer soluton, using parser combinators. Written in 1 or 2 minutes, literally. Cannot get validator script, browser said that server not found.

  • looks like an interesting solution; validator link has been fixed. – Armand Sep 28 '12 at 9:12
  • Is there a simple way to do it on Windows? (without cygwin or similar heresy) – Sarge Borsch Oct 6 '12 at 19:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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