Skip to content
Tutorials Center
My learning

Topics

Lesson 127 of 134 ยท Projects

Project: A JSON Parser

Write a JSON parser in Ruby from scratch: recursive descent with StringScanner, a Data-based tree, helpful error messages, a pretty printer and path queries.

Ruby ships with a JSON library, so why write a parser? Because a parser is one of the best programming exercises there is. It combines recursion, string processing, data modelling, error handling and testing in about 150 lines. Once you can build a JSON parser, you can build a parser for configuration files, query languages or a calculator, and you will understand what library code is doing for you.

We will use recursive descent, the most readable parsing technique: each rule of the grammar becomes one method, and rules that contain other rules call the corresponding methods, so the structure of the code mirrors the structure of the data. The result is a tree of immutable Data objects. We then add a pretty printer, a conversion to ordinary Ruby values and a small path query language (users[1].name). You may find it useful to have seen the expression calculator first, which uses the same technique for arithmetic, and Regular Expressions.

The grammar

JSON is small enough to describe in a few lines. A value is one of:

TEXT
value   = object | array | string | number | "true" | "false" | "null"
object  = "{" [ pair { "," pair } ] "}"
pair    = string ":" value
array   = "[" [ value { "," value } ] "]"

Spaces, tabs and newlines may appear between any two tokens. Strings use double quotes and the escapes \", \\, \/, \b, \f, \n, \r, \t and \uXXXX. Numbers look like -12, 3.5 or 1e9, with no leading zeros and no + sign.

Notice that value appears inside object and array, which in turn are values. The grammar is recursive, so the parser will be too: parse_value calls parse_array, which calls parse_value for every element.

Step 1: scanning scalars with StringScanner

Our parser walks over the text from left to right. Ruby's standard library has the right tool: StringScanner (from strscan) keeps a position in a string, and scan(regex) tries to match at exactly that position, moves forward on success and returns nil on failure. It is faster and cleaner than slicing strings by hand.

Ruby Step 1: StringScanner in action

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 gets), it gets the next line from this box.

scan returns the matched text or nil; matched remembers the last match; peek(n) looks ahead without moving; eos? ("end of string") tells whether everything has been consumed. The fourth line shows that scan fails when the text at the current position does not match (42 was already consumed, so \d+ finds ,). Failing does not move the position, which is what makes it easy to try one alternative after another.

Now the scalar part of the parser: null, booleans, numbers and strings. The tree nodes are Data classes. Strings need the most work because of escapes: the loop appends runs of plain characters and translates each escape sequence.

Ruby Step 2: parsing scalar values

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 gets), it gets the next line from this box.

Each alternative in parse_value is tried in order, and the first that matches wins. The \b after null and true is a word boundary: without it, nullable would be read as null followed by garbage. The number regex follows the JSON grammar exactly: an optional minus, either a single 0 or a non-zero digit followed by digits, then an optional fraction and exponent. Whether the result is an Integer or a Float depends on whether the text contains ., e or E.

Because the nodes are Data, equality is structural: two Num.new(1) are equal, which will make testing the parser pleasant. The last line shows a subtle point: Num.new(1) == Num.new(1.0) is also true, because Data#== compares members with ==, and 1 == 1.0. If you need the stricter comparison that tells integers from floats, use eql?, which is false for that pair. Unicode escapes are converted with [code].pack("U"); this simple version does not combine surrogate pairs such as ๐Ÿ˜€ into one character.

Step 3: arrays, objects and good error messages

Now the recursion. An array is [, then values separated by commas, then ]. An object is the same with key: value pairs. Both call parse_value for their elements, which may be arrays or objects again.

A parser is only as friendly as its errors. "Syntax error" is useless; "expected ',' or ']' at line 3, column 14" tells you where to look. So every failure goes through one helper, fail_at, which turns the scanner's character position into a line and column. We also limit the nesting depth, because a document of 100,000 opening brackets would otherwise overflow Ruby's stack (see Recursion).

Ruby Step 3: the complete parser, with errors

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 gets), it gets the next line from this box.

A walk through the important parts. parse_value is the dispatcher: it looks at the next character and picks a rule. nested wraps the two recursive rules, counting the depth and always decreasing it again with ensure, even when an error unwinds the stack. parse_array and parse_object use the same loop shape: parse an element, skip spaces, then either a comma (continue) or the closing bracket (stop) or an error. A trailing comma like [1, 2,] makes the loop call parse_value at ], which reports unexpected "]", just what the user needs to know.

The error table above shows what each broken input reports. Compare the line/column numbers with the inputs: for the multi-line example the position points at x on the third line. Every error is a Json::ParseError, a subclass of StandardError, so a caller can write rescue Json::ParseError and nothing else. The very last input (200 opening brackets) trips the depth limit before it can blow the stack.

The final lines compare with the standard library: JSON.parse gives hashes and arrays of plain values, while our parser gives a tree of nodes. Next we write the code that converts between the two and a query language on top.

Step 4: walking the tree with pattern matching

Having Data nodes makes pattern matching a natural way to write functions on the tree. Obj(members:) matches an object and binds its hash, Arr(items:) an array. Each function handles every node type once, and the compiler-like structure makes it easy to check that nothing is forgotten.

We build a tiny tree by hand here so the example stays short; the final program connects it to the parser.

Ruby Step 4: to_ruby and a pretty 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 gets), it gets the next line from this box.

The line in Bool | Num combines two class patterns with | and then reads node.value. We cannot write in Bool(value:) | Num(value:) here: Ruby does not allow an alternative pattern to bind variables (it reports variable capture in alternative pattern), so you match the classes and read the member from the node itself. The order matters again: Arr(items: []) (the empty array) must come before the general Arr(items:), and the guard if members.empty? handles {}. The printer writes a comma between elements by joining, so there is never a trailing comma.

Step 5: path queries

A path like users[1].tags[0] is a list of steps: a key (users), an index (1), a key (tags), an index (0). Parsing the path is another job for StringScanner; applying it is a reduce over the steps, with a pattern-matching case that says what each step means on each kind of node. A step that makes no sense raises a QueryError with a message, so the user hears why the query failed.

Step 6: the complete program

The finished program contains the whole parser from step 3, the printer and converter from step 4, and the query module. It parses a built-in document, then executes scripted commands: pretty, ruby, get PATH and parse TEXT (to check small snippets of JSON, including broken ones).

Ruby The complete JSON toolkit

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 gets), it gets the next line from this box.

The first output line is the most reassuring one: converting our tree back to plain Ruby values gives exactly what JSON.parse produces for the same document. That is a cheap and strong test, and a good habit: whenever a library offers a reference implementation, compare against it.

Then follow the queries. get users[1].name walks object, array, object; get users[5] fails with an index message that includes the size; get users.name fails because an array cannot be indexed by a key, and the message names the node type. Notice how both exception classes are rescued in one place and printed in the same shape, and how a get of a whole sub-tree prints it through the pretty printer. The parse command prints errors with line and column, e.g. for the unclosed array [1, 2.

The helper functions live in module_function, so they can be called as Json.pretty(...) without creating an object. This is a neat way to group stateless functions.

Where to go from here

  • Handle surrogate pairs in \u escapes, and reject lone surrogates.
  • Add Json.generate(tree) for compact output, and compare it with JSON.generate.
  • Make the parser streaming: yield events instead of building a tree, so huge files need no memory for the tree.
  • Add wildcards to the path language (users[*].name) using flat_map.
  • Write Minitest tests: a table of valid documents compared against JSON.parse, and a table of invalid documents with expected error messages.
  • Read the JSON lesson for what the real library offers (symbolize_names, pretty_generate, custom to_json).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main idea of recursive descent parsing?

    The structure of the code mirrors the grammar. A value can contain arrays and objects, which contain values, so parse_value, parse_array and parse_object call each other.
  2. 2. What does StringScanner#scan(/\d+/) do when the text at the current position is not a digit?

    scan only matches at the current position. On failure it returns nil without moving, so the parser can try the next alternative.
  3. 3. Why does nested decrease @depth in an ensure clause?

    ensure always runs. The depth counter must be consistent however the block ends.
  4. 4. Why are the tree nodes defined with Data.define instead of plain hashes?

    Typed immutable nodes make the printer and query code easy to write with case/in and make test comparisons trivial.
  5. 5. What should the parser do with the input [1, 2,]?

    After the comma the parser expects another value and finds ], so it reports an unexpected character with its line and column.

Summary

  • A grammar maps directly to code: one method per rule, recursion where the grammar is recursive.
  • StringScanner walks through text; scan matches at the current position and returns nil without moving when it fails.
  • Data nodes give a typed, immutable tree with structural equality and pattern matching.
  • Route all failures through one helper that reports a message with line and column, raise one error class, and limit the nesting depth.
  • Test against the library's reference implementation (JSON.parse) to catch mistakes cheaply.
  • A path query is a list of steps applied with reduce and a case/in over node and step type.

Next: Project: A Tiny Web Framework