Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 39 ยท Parsing, Security and Tooling

Writing a Tokenizer and Parser

Learn how data-format parsers work by building a JSON tokenizer and recursive-descent parser in Node, with line and column errors, depth limits and tests against the built-in JSON.parse.

Every file format you have met in this course, from JSON to YAML to Markdown, is read by the same two-stage machine: a tokenizer (lexer) turns characters into tokens, and a parser turns tokens into data. Understanding this machine makes you better at debugging parse errors, at choosing safe limits, and at writing small parsers for your own formats. In this lesson you build a complete JSON parser from scratch, about 100 lines, and test it against the engine's built-in JSON.parse.

Two stages

flowchart LR
  A["text: an object with a list"] --> B["tokenizer"]
  B --> C["tokens: brace, string, colon, bracket, number, true..."]
  C --> D["parser"]
  D --> E["data: an object with array"]

The tokenizer ignores structure; the parser ignores whitespace and spelling.

  • The tokenizer reads characters and groups them: "abc" becomes a STRING token, -12.5e3 a NUMBER token, { a punctuation token. It skips whitespace and remembers the position (line and column) of each token for error messages.
  • The parser consumes tokens following a grammar. JSON's grammar is tiny: a value is an object, array, string, number, true, false or null; an object is { then comma-separated string : value pairs then }; an array is [ then comma-separated values then ].

Grammars like this are naturally handled by recursive descent: one function per grammar rule, calling each other. parseValue looks at the next token and calls parseObject or parseArray, which call parseValue again for their children.

Step 1: the tokenizer

Node.js A JSON tokenizer with positions

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 node:readline or process.stdin), it gets the next line from this box.

The tokenizer enforces the lexical rules of JSON: numbers cannot have leading zeros (the regex accepts 0 and then stops, leaving 1 as a surprise token that the parser rejects), strings cannot contain raw control characters, and only seven escapes plus \u are valid. The error messages carry a position, which is the single most useful thing a parser can report.

Step 2: the parser

Node.js A recursive-descent JSON parser with a depth limit

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 node:readline or process.stdin), it gets the next line from this box.

The parser agrees with JSON.parse on every case, including the duplicate key (the last value wins in both), and its errors tell the user what it expected and where. Two design details deserve attention:

  • Object.defineProperty for keys. A key named __proto__ in a naive obj[key] = value would change the object's prototype in some designs; defining an own property avoids it (JSON.parse does the same). See Data Format Security.
  • A depth limit. Each nested array or object recurses, so a hostile input of ten thousand brackets could exhaust the call stack. Limiting depth turns that attack into a clean error.

From JSON to other formats

The same structure applies to every format:

Format Tokenizer concerns Parser concerns
JSON strings, numbers, punctuation tiny context-free grammar
CSV quotes, delimiters, newlines state machine, no nesting
YAML indentation as tokens (INDENT/DEDENT), many scalar forms context-dependent, anchors, multi-document
XML tags, attributes, entities, CDATA well-formedness, namespaces, DTD
Markdown line-based blocks, then inline spans two-phase, ambiguity rules

YAML's difficulty is why a full YAML parser is thousands of lines while a JSON parser fits on a screen. A cheap "format" with a simple grammar is a real advantage, and it is one reason JSON dominates APIs.

Parser design checklist

  1. Report position (line, column) and what was expected.
  2. Limit input size, nesting depth, string length and number of entries.
  3. Be strict by default; accept extensions (comments, trailing commas) only via an explicit option.
  4. Never eval data; do not mix parsing with execution.
  5. Fuzz and test with the known suites (for JSON: the JSONTestSuite of valid, invalid and ambiguous documents).
  6. Prefer a maintained library unless your grammar is small and yours.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a tokenizer produce?

    The tokenizer groups characters into tokens; the parser later gives them structure.
  2. 2. What is recursive descent?

    For JSON, parseValue calls the object and array routines, which call parseValue for their children.
  3. 3. Why does a parser need a maximum nesting depth?

    Without a limit, a malicious input with thousands of nested brackets can cause a stack overflow.
  4. 4. Which makes YAML harder to parse than JSON?

    Indentation, flow and block styles, anchors and implicit typing make the YAML grammar far larger.

Summary

  • Parsing is tokenizing (characters to tokens) then parsing (tokens to data).
  • JSON's small grammar fits a recursive-descent parser of about 100 lines.
  • Good parsers report line and column, enforce limits, and are strict by default.
  • Defining properties instead of assigning avoids __proto__ problems; depth limits stop stack exhaustion.
  • Test against a trusted implementation and prefer libraries for big formats.

Next: Data Format Security