Writing a JSON Parser from Scratch (1)

Recursive descent is arguably an intuitive and powerful parsing method.

Today, starting with JSON parsing, we will walk through how to build a JSON parser from scratch. Since the structure of JSON is relatively simple, it serves as a great exercise. Although parsing syntax might not seem closely related to front-end or everyday development, these techniques will come in handy if you ever need to design a DSL or build a custom language for specific needs.

Why Learn Recursive Descent?

With JSON.parse already available, why bother learning recursive descent? By parsing syntax on your own, beyond just parsing normal JSON data, you can implement your own custom syntax and apply this technique to other domains as well.

For example, regular JSON looks like this:

{
  "name": "kalan",
  "age": 20
}

Suppose today you want to add a new syntax—let’s call it templating—where any string enclosed in {} is automatically replaced with a variable. For example:

{
  "name": "kalan",
  "age": 20,
	"job": $job$
}

Parsed through a custom parse function:

parse(json, { job: 'engineer' });

// {
//   "name": kalan,
//   "age": 20,
//   "job": "engineer"
// }

Or maybe you want to switch to a new delimiter symbol:

{
  "name" @ "kalan"
  "age" @ 20
}

Today, we will build a recursive descent parser capable of parsing JSON, and adapt it to include the two custom features mentioned above.

What is Recursive Descent?

When discussing recursive descent, it’s easy to get lost in intimidating terminology and symbols like LL, LR, top-down, non-terminals, and so on. Let’s try to discuss it in the most intuitive way possible. First, take a look at the diagram:

Representing the structure of JSON as a diagram, we can see that JSON is primarily composed of key + : + value. The value can further be broken down into strings, booleans, numbers, null, objects, and so on.

Notice that if the value is an object, the exact same rules can be reapplied—returning to the very top of the diagram and continuing parsing with the same rules.

This continuous looping is what we call recursion, and looking up matching rules from top to bottom is called top-down. Put together, it’s known as recursive descent.

For detailed definitions of each type and syntax rule, we can refer to the JSON Specification:

Let’s start with the simplest example: only one key and value, where the value is of string type.

{
  "name": "kalan"
}

Here is the step-by-step process (refer to the diagram above):

• Encounter {, start parsing the object
• Enter key parsing, expecting a string
• Encounter ", begin string parsing
• Encounter n, a, m, e: treat name as the key
• Encounter ": end string matching, expect : to conform to the rule
• Encounter :: enter value parsing
• Encounter ": enter string parsing
• Encounter k, a, l, a, n: set value to kalan
• Encounter ": end string matching
• Encounter }: end object matching
• Encounter empty string (EOF): end parsing

Looking at this process, we can see that parsing is very much like a series of state transitions. Each time we encounter a matching value, we follow the rules in the diagram above to test whether to proceed to the next box. The acceptable values differ for each box. If we can successfully transition from the left side to the right side, it means the match succeeded.

Next, let’s try implementing it.

Implementing a Simple Parser

A simple parser can be built using just a pointer, position information, and the current character being read.

We use the parse function as the entry point, executing the corresponding function whenever a specific state is met.

First, let’s define the functions we will need:

class Parser {
  constructor(raw) {
    this.raw = raw;
    this.index = 0;
  }

  // 目前字元
  current() {
    return this.raw[this.index];
  }

  // 匹配之後的字串是否為 str
  // e.g: next('{')
  // 判斷下一個字元是否為 '{'
  // 如果是的話將 index 移過去
  // 並且回傳 true
  // 方便判斷狀態
  next(str) {
    if (this.raw.slice(this.index, this.index + str.length) === str) {
      this.index += str.length;
      return true;
    }

    return false;
  }

  // 省略空白，目前只考慮 " "
  // 不實作 tab 等功能
  skip() {
    while (this.raw[this.index] <= " ") {
      this.index += 1;
    }
  }

  parse() {
    const value = object(this); // entry point
    return value;
  }
}

The main entry point is parse. At the same time, we defined helper functions like skip and next to help us check the current state. Next, let’s look at the implementation of the object function:

function object(parser) {
  const obj = Object.create(null);
  let key = "";
	// 如果是 { 開頭，代表要用 object 函數解析
  if (parser.current() === "{") {
    parser.next("{");
    parser.skip();
    
    // 如果馬上遇到 }
    // 代表他是一個空物件 {}
    if (parser.current() === "}") {
      parser.next("}");
      return obj;
    }
    
    // 讀取當前字元，判斷要用哪一個函數解析
    while (parser.current()) {
      key = string(parser); // key 一定是字串，所以我們用字串解析

      parser.skip(); // 省略空白字元
      parser.next(":"); // 預期是 :
      obj[key] = string(parser); // 先假設值只有字串，一律用字串解析
      parser.skip();
      if (parser.current() === "}") { // 如果遇到 }，代表物件解析結束，return obj
        parser.next("}");
        return obj;
      }
      parser.next(","); // 如果有逗號，代表有下一個 key-value，繼續跑 while 解析
      parser.skip();
    }
  }
}

• If the current character is {:

  • If the next character is }, it’s an empty object; return it and exit.

• Enter the while loop, parsing the key using string (since JSON keys must be strings). We’ll explain the implementation of the string function below.

  • Skip whitespace characters (as in cases like the following):

  { "name"         : "value" }

  • Expect : to appear.
  • Parse the value using string (here we assume values are only strings for now; we’ll add handling for other types later).
  • Skip whitespace characters.
  • If } is encountered, it marks the end of the object; return obj.
  • If , is encountered, it means there is another key-value pair to parse; continue the loop.
  • Skip whitespace characters.

Implementation of string parsing:

function string(parser) {
  parser.next('"'); // 如果下一個字元為 "，代表我們要用 string 的方式解析
  if (parser.next('"')) {
    // { "": "value" } 我們將 key 為空的 JSON 當做不合法的
    throw new Error("JSON key is empty.");
  }

  let key = "";
  let curr = "";
  // 不斷讀取下一個字元直到讀到 "
  while (((curr = parser.current()), curr)) {
    if (parser.next('"')) {
      parser.index += 1;
      return key;
    }
    key += curr;
    parser.index += 1;
  }
}

• Expect the character ".
• If the next character is ", it indicates an empty string, which we treat as an invalid key and throw an error.
• Enter a while loop until the character " is encountered.

If you want to practice, you can check out the Repo.

Writing a parser by hand can be a bit tedious, and sometimes edge cases are missed. If you’re practicing, I recommend writing unit tests right from the start; it will save you a lot of time on manual testing.

Conclusion

Although we implemented a recursive descent parser, we skipped the step of transforming it into an AST (Abstract Syntax Tree) and instead converted it directly into a JavaScript object. This is because JSON’s data structure is relatively straightforward, making AST generation unnecessary here.

Additionally, when implementing a parser, it’s worth considering a few points:

1. To make error messages friendlier, we could record position information in 2D (row, column) rather than just a 1D index.
2. Provide more helpful error messages—for instance, reminding developers when a closing } is missing, or pinpointing the exact location of a syntax error.

For extra flexibility, you could also replace symbols with tokens.

In Part 2, we will continue by implementing other types such as numbers, arrays, booleans, and null to build a more complete JSON parser. At the same time, we’ll also start implementing the two custom features mentioned earlier: using @ as a separator and using {} for templating.