JSON Recursive Descent Parser

A fully-featured JSON parser built from scratch using recursive descent parsing. This project demonstrates compiler fundamentals including lexical analysis (tokenization) and syntactic analysis (parsing) — core concepts used in production parsers at companies like Google and Meta.

No external parsing libraries. Just pure TypeScript implementing the RFC 8259 JSON specification.

Why This Project?

Recursive descent parsing is a fundamental technique used in:

• Compilers (GCC, Clang, V8 JavaScript engine)
• Interpreters (Python, Ruby)
• Configuration parsers (JSON, YAML, TOML)
• Query languages (SQL, GraphQL)

This implementation showcases:

• Clean separation between lexer and parser
• Comprehensive error handling with line/column information
• Full JSON spec compliance including Unicode escapes
• 100+ test cases verifying correctness

Demo Output

╔══════════════════════════════════════════════════════════════╗
║     JSON Recursive Descent Parser - Demo                     ║
╚══════════════════════════════════════════════════════════════╝

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Demo 1: Basic JSON Parsing
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Input JSON:
{
  "name": "Mo Shirmohammadi",
  "university": "USC",
  "skills": ["Python", "TypeScript", "React", "Node.js"],
  "seeking_internship": true
}

Parsed Result:
  Name: Mo Shirmohammadi
  Skills: Python, TypeScript, React, Node.js

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Demo 2: Tokenization (Lexical Analysis)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Input: {"count": 42, "active": true}

Tokens:
  1. LEFT_BRACE      | value: "{"
  2. STRING          | value: "count"
  3. COLON           | value: ":"
  4. NUMBER          | value: 42
  5. COMMA           | value: ","
  6. STRING          | value: "active"
  7. COLON           | value: ":"
  8. TRUE            | value: true
  9. RIGHT_BRACE     | value: "}"
  10. EOF            | value: null

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Demo 6: Error Handling
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  Missing value:
    Input: {"key": }
    Error: Unexpected token '}' at line 1, column 9

  Trailing comma:
    Input: {"key": "value",}
    Error: Trailing comma not allowed in JSON at line 1, column 17

  Unquoted key:
    Input: {key: "value"}
    Error: Unexpected identifier 'key' at line 1, column 1

Installation

git clone https://github.com/mohosy/json-recursive-descent-parser.git
cd json-recursive-descent-parser
npm install
npm run build

Usage

Basic Parsing

import { parse } from './dist/index.js';

const data = parse('{"name": "Mo", "age": 21, "skills": ["TypeScript", "Python"]}');
console.log(data.name);   // "Mo"
console.log(data.skills); // ["TypeScript", "Python"]

Tokenization

import { tokenize } from './dist/index.js';

const tokens = tokenize('{"key": 42}');
// Returns array of tokens with type, value, line, and column info

Validation

import { isValid, parseWithError } from './dist/index.js';

console.log(isValid('{"valid": true}'));  // true
console.log(isValid('{invalid}'));        // false

// Get detailed error info
const result = parseWithError('{invalid}');
if (!result.success) {
  console.log(result.error);
  // { message: "...", line: 1, column: 2 }
}

Run Demo

npm run demo

Run Tests

npm test

Architecture

┌─────────────────────────────────────────────────────────────────┐
│                         Input String                            │
│                    '{"name": "Mo", "age": 21}'                  │
└─────────────────────────────┬───────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────┐
│                       LEXER (Tokenizer)                         │
│                                                                 │
│  Converts characters into tokens:                               │
│  • Structural: { } [ ] : ,                                      │
│  • Strings: "..." with escape handling                          │
│  • Numbers: integers, decimals, exponents                       │
│  • Keywords: true, false, null                                  │
│                                                                 │
│  Time: O(n)  |  Space: O(n)                                     │
└─────────────────────────────┬───────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────┐
│                         Token Stream                            │
│  [LEFT_BRACE, STRING("name"), COLON, STRING("Mo"), ...]        │
└─────────────────────────────┬───────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────┐
│                 PARSER (Recursive Descent)                      │
│                                                                 │
│  Grammar rules map to methods:                                  │
│  • parseValue()  → Dispatches to type-specific parsers          │
│  • parseObject() → Handles { key: value, ... }                  │
│  • parseArray()  → Handles [ value, value, ... ]                │
│                                                                 │
│  Time: O(n)  |  Space: O(d) where d = nesting depth             │
└─────────────────────────────┬───────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────┐
│                      JavaScript Value                           │
│             { name: "Mo", age: 21 }                             │
└─────────────────────────────────────────────────────────────────┘

File Structure

json-recursive-descent-parser/
├── src/
│   ├── types.ts       # Token types, JSON types, error classes
│   ├── lexer.ts       # Tokenizer - converts string to tokens
│   ├── parser.ts      # Recursive descent parser
│   ├── index.ts       # Public API (parse, tokenize, isValid)
│   ├── demo.ts        # Interactive demonstration
│   └── tests/
│       └── parser.test.ts  # Comprehensive test suite
├── package.json
├── tsconfig.json
└── README.md

JSON Grammar

The parser implements this grammar (simplified BNF):

json    → value
value   → object | array | STRING | NUMBER | "true" | "false" | "null"
object  → "{" (pair ("," pair)*)? "}"
pair    → STRING ":" value
array   → "[" (value ("," value)*)? "]"

Each grammar rule maps directly to a method in the parser:

• parseValue() → Handles the value rule
• parseObject() → Handles the object rule
• parseArray() → Handles the array rule

This 1:1 mapping between grammar and code is what makes recursive descent parsing so elegant and maintainable.

Features

Full JSON Specification Support

• ✅ Objects with string keys
• ✅ Arrays with mixed types
• ✅ Strings with all escape sequences (\n, \t, \\, \", \/, \b, \f, \r)
• ✅ Unicode escapes (\uXXXX)
• ✅ Numbers (integers, decimals, scientific notation)
• ✅ Booleans (true, false)
• ✅ Null values

Error Handling

• ✅ Precise line and column numbers
• ✅ Descriptive error messages
• ✅ Trailing comma detection
• ✅ Invalid escape sequence detection
• ✅ Unterminated string detection
• ✅ Invalid number format detection

Developer Experience

• ✅ TypeScript with full type definitions
• ✅ Zero runtime dependencies
• ✅ Separate lexer/parser for debugging
• ✅ Validation utilities

Complexity Analysis

Operation	Time	Space
Tokenize	O(n)	O(n)
Parse	O(n)	O(d)
Overall	O(n)	O(n)

Where:

• n = input string length
• d = maximum nesting depth

Why Recursive Descent?

Pros:

• Simple and intuitive — grammar rules map directly to code
• Easy to debug — call stack shows parse state
• Excellent error messages — you know exactly where you are
• No external tools needed — just code

Cons:

• Not suitable for left-recursive grammars (not an issue for JSON)
• Stack depth limited by nesting (handles 1000+ levels easily)

Alternatives:

• LL(k) parser generators (ANTLR) — more powerful but require external tools
• LR parsers (Bison, Yacc) — handle more grammars but harder to understand
• PEG parsers — similar to recursive descent with memoization

For JSON's simple grammar, recursive descent is the perfect choice.

Running the Project

# Install dependencies
npm install

# Build TypeScript
npm run build

# Run interactive demo
npm run demo

# Run test suite
npm test

Author

Mo Shirmohammadi

• GitHub: @mohosy
• University: University of Southern California (USC)
• Major: Computer Science

License

MIT License - feel free to use this code for learning, interviews, or building your own parsers!

---

Built from scratch to demonstrate compiler fundamentals. No parsing libraries were harmed in the making of this project.