Writing a JSON Parser from Scratch (Part 2)

In Part 1, we covered how to write a JSON parser and implemented string parsing. Next, we’ll fill in the rest of the functions. (In fact, once you understand the core principles, implementing the remaining functions is just following the recipe.)

Number

Implementing numbers isn’t difficult either. The parts that are easy to overlook are decimal points, negative signs, floating-point numbers, and exponential notation (1e6). (Speaking of which, I just realized E is also valid.)

function number(parser) {
  let str = "";
  if (parser.current() === "-") {
    str += "-";
    parser.index += 1;
  }

  let curr = "";
  while (((curr = parser.current()), curr >= "0" && curr <= "9")) {
    str += curr;
    parser.index += 1;
  }

  let isFloat = false;
  // float number
  if (parser.next(".")) {
    str += ".";
    isFloat = true;
    while (((curr = parser.current()), curr >= "0" && curr <= "9")) {
      str += curr;
      parser.index += 1;
    }
  }

  // exponential expression
  let expo = "";
  if (parser.next("e")) {
    curr = "";
    if (parser.next("-")) {
      expo += "-";
    }

    while (((curr = parser.current()), curr >= "0" && curr <= "9")) {
      expo += curr;
      parser.index += 1;
    }
  }

  if (expo) {
    return isFloat
      ? parseFloat(str, 10) * Math.pow(10, +expo)
      : parseInt(str, 10) * Math.pow(10, +expo);
  }

  return isFloat ? parseFloat(str, 10) : parseInt(str, 10);
}

• First part: Check if it’s a negative number.
• Second part: Run a while loop to collect the digit characters.
• Third part: Check if there’s a decimal point.
  • If so, traverse through the subsequent digits again.
• Fourth part: Check if there’s exponential notation (uppercase or lowercase ‘e’).
  • If so, traverse through the exponent digits as well.
• Fifth part: Convert the string to a number (using parseInt or parseFloat).

Keywords (true, false, null)

function keyword(parser) {
  if (parser.next("true")) {
    return true;
  } else if (parser.next("false")) {
    return false;
  } else if (parser.next("null")) {
    return null;
  }
}

This part is very straightforward—just check whether the value matches.

Array

function array(parser) {
  const arr = [];

  if (parser.current() === "[") {
    parser.next("[");
    parser.skip();

    if (parser.next("]")) {
      return arr;
    }
    let i = 0;
    while (parser.current()) {
      const val = value(parser);
      arr.push(val);

      parser.skip();

      if (parser.current() === "]") {
        parser.next("]");
        return arr;
      }
      parser.next(",");
      parser.skip();
    }
  }

  return arr;
}

• First part: Check if it starts with [.
  • If it immediately encounters ], that means it’s an empty array.
• Second part: Run a while loop executing the value function and push results into the array.
• Encountering ] marks the end of the array; return the array.
• Encountering a comma means there’s another element; continue execution.

With that, we’re mostly there. If you take a look at the code implementation on the Repository, you’ll notice one test called specical-character fails. This is because strings can contain escape characters. Let’s try implementing support for them.

const escape = {
  '"': '"',
  t: "\t",
  r: "\r",
  "\\": "\\",
};

while (((curr = parser.current()), curr)) {
    if (parser.next('"')) {
      return str;
    } else if (curr === "\\") {
      parser.index += 1;
      const escapeCh = parser.current();
      if (escape[escapeCh]) {
        str += escape[escapeCh];
      }
    } else {
      str += curr;
    }
    parser.index += 1;
  }

We create an escape character lookup table and replace characters with their corresponding implementations. Here, only \t and \r are implemented. With this, we pass the basic JSON tests 🍻. However, beyond what was mentioned above, we would also need to support \u representing Unicode, which is a fairly important feature.

Custom Feature: $template$

Since we wrote the parser ourselves, we can naturally add our own syntax! Suppose we want to implement a templating feature where any variable wrapped in $$ gets replaced by a passed-in object, like this:

{
  "name": $name$
}

which becomes:

new Parser(string, { name: 'kalan' }).parse();
// { name: "kalan" }

Implementation

function template(parser) {
  parser.skip();
  if (parser.next("$")) {
    parser.skip();

    if (parser.next("$")) {
      throw new Error("template can not be empty");
    }
    let curr = "";
    let key = "";
    while (((curr = parser.current()), curr)) {
      if (parser.next("$")) {
        return parser.variables[key];
      }
      key += curr;
      parser.index += 1;
    }
  }
}

• First, match $.
• Start reading characters until the next $.
• Upon hitting $, exit the while loop, replace the template variable with the corresponding value from variables, and return the result.

You can check out the full implementation on the template branch, as well as the test results (located in the test/template folder).

Conclusion

By writing our own parser, we can represent more complex implementations using more expressive syntax. We can even build an extension on top of an existing grammar (like JSON this time) to add whatever features we want. While not necessarily practical in everyday production, it serves to showcase what is possible through parsing.

Although parsing itself is vital and intriguing, parsing a language is only the very first step. Just like converting JSX purely into JavaScript code without React’s runtime is useless, or turning SQL into an Abstract Syntax Tree (AST) without a database engine to execute it is somewhat pointless. The ultimate goal of parsing a language is to facilitate downstream processing (executing queries, rendering to the DOM).

In reality, there are already many libraries that allow you to skip writing parsers from scratch altogether, such as the famous Bison or PEG.js. They let you define grammars using BNF-like syntax and automatically generate robust parsers for you, saving you parsing time so you can focus directly on language semantics.

Our JSON parser this time didn’t transform the input into an AST before generating the final result. So in our next phase, we will try parsing simple HTML, converting it into an AST, and rendering it using JavaScript’s DOM API.