Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 40 ยท Projects and Practice

Project: A JSON Parser and Pretty Printer from Scratch

Write a complete JSON parser in OCaml with no libraries. Model JSON as a variant, parse with a position reference, report errors with offsets, print compact and indented output, and query values.

JSON is the ideal second project: the grammar is small, every value maps to one constructor of a variant type, and the result is something you will actually use. You will write a parser that reads text into a tree, a printer that writes the tree back out (compact and indented), a query helper, and error reporting with the position of the problem. Only the standard library is needed.

OCaml is not available in the site's code runners. The OCaml below targets OCaml 5 and the standard library (save as json.ml and compile with dune or ocamlfind ocamlopt). A Python program with the same structure runs here, and the outputs shown are from it; they match the OCaml code.

The data type

JSON has six kinds of value. A variant type names them directly:

OCAML
type json =
  | Null
  | Bool of bool
  | Number of float
  | String of string
  | Array of json list
  | Object of (string * json) list

exception Parse_error of int * string

Array and Object contain json values, so the type is recursive, like the tree in variant types. Objects keep their members in an association list so the source order survives printing. The exception carries the offset where parsing failed.

The parser

The parser keeps a mutable position pos and a few small helpers in one function. Local state like this is a good use of references: it does not escape parse, so the function stays pure from outside.

OCAML
let parse (s : string) : json =
  let n = String.length s in
  let pos = ref 0 in
  let fail msg = raise (Parse_error (!pos, msg)) in
  let peek () = if !pos < n then Some s.[!pos] else None in
  let advance () = incr pos in
  let rec skip_ws () =
    match peek () with
    | Some (' ' | '\t' | '\n' | '\r') -> advance (); skip_ws ()
    | _ -> ()
  in
  let expect c =
    if peek () = Some c then advance () else fail (Printf.sprintf "expected %C" c)
  in
  let literal word value =
    let l = String.length word in
    if !pos + l <= n && String.sub s !pos l = word then (pos := !pos + l; value)
    else fail ("expected " ^ word)
  in
  let parse_string () =
    expect '"';
    let b = Buffer.create 16 in
    let rec go () =
      match peek () with
      | None -> fail "unterminated string"
      | Some '"' -> advance ()
      | Some '\\' ->
          advance ();
          (match peek () with
           | Some '"' -> Buffer.add_char b '"'
           | Some '\\' -> Buffer.add_char b '\\'
           | Some '/' -> Buffer.add_char b '/'
           | Some 'n' -> Buffer.add_char b '\n'
           | Some 't' -> Buffer.add_char b '\t'
           | _ -> fail "bad escape");
          advance ();
          go ()
      | Some c -> Buffer.add_char b c; advance (); go ()
    in
    go ();
    Buffer.contents b
  in
  let parse_number () =
    let start = !pos in
    let is_num = function '0' .. '9' | '-' | '+' | '.' | 'e' | 'E' -> true | _ -> false in
    while (match peek () with Some c -> is_num c | None -> false) do advance () done;
    match float_of_string_opt (String.sub s start (!pos - start)) with
    | Some f -> Number f
    | None -> pos := start; fail "bad number"
  in
  let rec parse_value () =
    skip_ws ();
    match peek () with
    | None -> fail "unexpected end of input"
    | Some 'n' -> literal "null" Null
    | Some 't' -> literal "true" (Bool true)
    | Some 'f' -> literal "false" (Bool false)
    | Some '"' -> String (parse_string ())
    | Some '[' -> advance (); parse_array ()
    | Some '{' -> advance (); parse_object ()
    | Some _ -> parse_number ()
  and parse_array () =
    skip_ws ();
    if peek () = Some ']' then (advance (); Array [])
    else
      let rec items acc =
        let v = parse_value () in
        skip_ws ();
        match peek () with
        | Some ',' -> advance (); items (v :: acc)
        | Some ']' -> advance (); Array (List.rev (v :: acc))
        | _ -> fail "expected , or ]"
      in
      items []
  and parse_object () =
    skip_ws ();
    if peek () = Some '}' then (advance (); Object [])
    else
      let rec members acc =
        skip_ws ();
        let k = parse_string () in
        skip_ws ();
        expect ':';
        let v = parse_value () in
        skip_ws ();
        match peek () with
        | Some ',' -> advance (); members ((k, v) :: acc)
        | Some '}' -> advance (); Object (List.rev ((k, v) :: acc))
        | _ -> fail "expected , or }"
      in
      members []
  in
  let v = parse_value () in
  skip_ws ();
  if !pos < n then fail "trailing characters" else v

How it works:

  • parse_value looks at the next character to decide what comes: n, t and f start literals, " a string, [ an array, { an object, anything else a number.
  • parse_array and parse_object are mutually recursive with parse_value (joined by and), and use an accumulator that is reversed at the end.
  • fail raises Parse_error with the current offset, so a bad document tells the user where to look.
flowchart TD
    V["parse_value"] --> L["literal<br/>null / true / false"]
    V --> S["parse_string"]
    V --> N["parse_number"]
    V --> A["parse_array"]
    V --> O["parse_object"]
    A --> V
    O --> V

Figure: the parser mirrors the grammar. Arrays and objects call parse_value again.

The parser is deliberately small. It does not decode \uXXXX escapes, validate number syntax as strictly as the standard (leading zeros are accepted), or limit nesting depth. Those are good extensions.

Printing

Compact output joins parts with String.concat:

OCAML
let escape s =
  let b = Buffer.create (String.length s + 2) in
  String.iter
    (function
      | '"' -> Buffer.add_string b "\\\""
      | '\\' -> Buffer.add_string b "\\\\"
      | '\n' -> Buffer.add_string b "\\n"
      | '\t' -> Buffer.add_string b "\\t"
      | c -> Buffer.add_char b c)
    s;
  Buffer.contents b

let number_to_string f =
  if Float.is_integer f then Printf.sprintf "%.0f" f else Printf.sprintf "%g" f

let rec to_string = function
  | Null -> "null"
  | Bool b -> string_of_bool b
  | Number f -> number_to_string f
  | String s -> "\"" ^ escape s ^ "\""
  | Array xs -> "[" ^ String.concat "," (List.map to_string xs) ^ "]"
  | Object kvs ->
      let member (k, v) = "\"" ^ escape k ^ "\":" ^ to_string v in
      "{" ^ String.concat "," (List.map member kvs) ^ "}"

The indented printer passes the current indentation down:

OCAML
let rec pretty indent = function
  | Array [] -> "[]"
  | Object [] -> "{}"
  | Array xs ->
      let pad = String.make (indent + 2) ' ' in
      let items = List.map (fun x -> pad ^ pretty (indent + 2) x) xs in
      "[\n" ^ String.concat ",\n" items ^ "\n" ^ String.make indent ' ' ^ "]"
  | Object kvs ->
      let pad = String.make (indent + 2) ' ' in
      let member (k, v) = pad ^ "\"" ^ escape k ^ "\": " ^ pretty (indent + 2) v in
      "{\n" ^ String.concat ",\n" (List.map member kvs) ^ "\n" ^ String.make indent ' ' ^ "}"
  | j -> to_string j

Note that Printf "%.0f" is used for whole numbers so 3. prints as 3, since OCaml's own string_of_float 3.0 is "3.", which is not valid JSON.

Querying

Safe access returns options, in the style of option and result:

OCAML
let member key = function
  | Object kvs -> List.assoc_opt key kvs
  | _ -> None

let rec path keys j =
  match keys with
  | [] -> Some j
  | k :: rest -> (match member k j with Some v -> path rest v | None -> None)

let to_number = function Number f -> Some f | _ -> None

path ["user"; "name"] doc follows a chain of keys and stops at the first missing one.

Error handling in the caller

OCAML
let parse_result s =
  try Ok (parse s) with Parse_error (pos, msg) -> Error (Printf.sprintf "at %d: %s" pos msg)

Keeping the exception inside the library and exposing a result is a common compromise; the parser uses the cheap exception internally while callers see the type.

Runnable mirror in Python

Python Stand-in: the same parser and printer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ideas to extend

  • Decode \uXXXX escapes into UTF-8.
  • Report line and column by counting newlines up to the offset.
  • Write of_string_exn, get_string, get_list helpers like the ones in Yojson, then compare your API with the Yojson library.
  • Use Format with boxes to produce indented output that respects a line width.
  • Add a QuickCheck-style round-trip property: parse (to_string j) = j (testing).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is json a recursive variant type?

    Array holds a json list and Object holds json values, so the type refers to itself.
  2. 2. Why are parse_value, parse_array and parse_object joined with and?

    Arrays and objects call parse_value again, and parse_value calls them, so they must be defined together.
  3. 3. Why use Printf.sprintf "%.0f" for whole numbers when printing?

    OCaml prints 3.0 as "3." so the printer formats whole numbers explicitly.
  4. 4. What does the offset in Parse_error help with?

    Position information turns a generic failure into an actionable message.

Summary

  • A six-constructor variant models JSON. The parser mirrors the grammar with one function per construct.
  • A local position reference and small helpers keep the parser compact, and an exception reports the failing offset.
  • Printing is another set of pattern matches over the same type, and queries return options.
  • You can test with round trips and then compare the result with a real library.

Next: Project: A State Machine for Orders and Accounts