14
\$\begingroup\$

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.
\$\endgroup\$
7
  • 8
    \$\begingroup\$ Your "partially-correct solutions allowed" note is making me dream of extracting a regex from a genetic algorithm. I must be insane. \$\endgroup\$
    – J B
    Feb 4 '11 at 14:58
  • \$\begingroup\$ @J B: That would be awesome. \$\endgroup\$
    – Joey Adams
    Feb 4 '11 at 15:43
  • \$\begingroup\$ Just curious, why is {key: "value"} consider invalid JSON ? It is valid javascript. \$\endgroup\$
    – HoLyVieR
    Feb 5 '11 at 3:12
  • \$\begingroup\$ @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. \$\endgroup\$
    – Joey Adams
    Feb 5 '11 at 4:31
  • 1
    \$\begingroup\$ I'm going to close this question as unclear. Back in the day we had a lot looser rules on clarity, but things have changed. A more modern question would have to include an actual spec and couldn't have such as "partially-correct solutions allowed". \$\endgroup\$
    – Grain Ghost
    Sep 14 at 8:10
7
\$\begingroup\$

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';
}
\$\endgroup\$
3
  • \$\begingroup\$ Wow. ` ` ` ` ` ` \$\endgroup\$ Feb 5 '11 at 0:14
  • \$\begingroup\$ You need to include the <?php IMO. \$\endgroup\$ Feb 5 '11 at 9:29
  • \$\begingroup\$ Added. 264 chars now :-) \$\endgroup\$ Feb 5 '11 at 13:02
7
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

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

Bash + jq, 29 bytes

jq -r '"Valid"'||echo Invalid

Try it online!

TIO's bash instance conveniently has jq installed for us so try it online at your leisure!

\$\endgroup\$
10
  • \$\begingroup\$ This is not a valid answer because the program is expected to print Valid or Invalid, and any other output format is not allowed (i.e. jq alone can't solve this challenge). Always watch out for I/O formats when trying very old challenges. \$\endgroup\$
    – Bubbler
    Sep 2 at 6:59
  • \$\begingroup\$ Uh oh, thanks @Bubbler. I totally missed that! I'm surprised though that our current I/O standards don't apply. Do those only apply when I/O isn't already strictly defined? \$\endgroup\$
    – AviFS
    Sep 2 at 7:01
  • \$\begingroup\$ Yes, I/O defaults only apply when the challenge doesn't specify the I/O. (Also, changing I/O rules for an existing challenge is fundamentally a breaking change, so we don't do that.) \$\endgroup\$
    – Bubbler
    Sep 2 at 7:11
  • 2
    \$\begingroup\$ (The only way to fix this answer is to delete it, since if you use something like Bash + jq, then jq surely counts as a "JSON parsing library" which is banned.) \$\endgroup\$
    – Bubbler
    Sep 2 at 7:24
  • 1
    \$\begingroup\$ Of course jq can do much more than that, but the first thing it does is to parse JSON for you (and error if the input is not a valid JSON). And I'd interpret "JSON parsing library" as "anything that can parse JSON for you without effort", since "following the spirit of the challenge" was important in the old days. \$\endgroup\$
    – Bubbler
    Sep 2 at 8:03

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