JSON Parser

Introduction

In this comprehensive case study, we’ll design a JSON Parser from scratch using the systematic 8-step approach. This problem is excellent for learning LLD because it demonstrates fundamental computer science concepts like lexical analysis, parsing, and error handling.

Why This Problem?

JSON Parser is perfect for learning LLD because it involves:

• Lexical Analysis - Breaking strings into tokens (tokenization)
• Syntactic Analysis - Building data structures from tokens (parsing)
• Recursive Descent Parsing - Natural fit for hierarchical JSON structure
• Error Handling - Detailed error messages with position information
• Unicode Support - Handling escape sequences and Unicode characters
• Separation of Concerns - Clear separation between tokenization and parsing

---

Problem Statement

Design a JSON Parser that can:

• Convert JSON strings into corresponding data structures (objects, arrays, primitives)
• Support all JSON data types: strings, numbers (integers and floats), booleans, null, objects, arrays
• Handle nested objects and arrays of arbitrary depth
• Validate JSON syntax during parsing and throw exceptions for invalid JSON
• Provide meaningful error messages with position information (line and column)
• Correctly handle Unicode characters and escape sequences (\n, \t, \r, \", \\, \uXXXX)
• Handle whitespace (spaces, tabs, newlines) correctly between JSON elements
• Support empty objects {} and empty arrays []

---

Step 1: Clarify Requirements

Before designing, let’s ask the right questions!

Clarifying Questions

Functional Requirements:

1. JSON Data Types: What types should be supported? → Strings, numbers (integers and floats), booleans (true/false), null, objects, arrays
2. Nested Structures: How deep can nesting go? → Arbitrary depth, but should handle gracefully
3. Error Handling: How should invalid JSON be handled? → Throw exceptions with clear error messages and position information
4. Unicode Support: Should Unicode characters be supported? → Yes, including escape sequences (\n, \t, \uXXXX, etc.)
5. Whitespace: How should whitespace be handled? → Correctly handle spaces, tabs, newlines between elements
6. Comments: Should comments be supported? → No, JSON doesn’t support comments

Non-Functional Requirements:

1. Separation of Concerns: Should tokenization and parsing be separate? → Yes, clear separation
2. Parsing Approach: What parsing technique? → Recursive descent parsing
3. Error Messages: What level of detail? → Line and column numbers for debugging
4. Extensibility: Should it be easy to extend? → Yes, allow easy addition of new features

Edge Cases to Consider:

• What if JSON string is empty?
• What if string is unterminated?
• What if number format is invalid?
• What if escape sequence is invalid?
• What if structure is malformed (missing commas, colons)?
• What if nesting is too deep?

Requirements Summary

---

Step 2: Identify Actors

Actors are external entities that interact with the system.

Who Uses This System?

Primary Actors:

1. Client Application - Uses the JSON parser to parse JSON strings into data structures
2. Developer - Uses the parser in their application code

Note: The parser is a library component used by other applications. It doesn’t have external actors in the traditional sense, but it serves client applications that need to parse JSON.

Actor Interactions

Actor vs Entity

Actors are external users/systems that interact with your system. Entities are internal objects managed by the system. In this case:

• Client Application (Actor) uses JsonParser (Entity)
• JsonValue is an Entity, not an Actor (it’s data, not a user)

---

Step 3: Identify Entities

Entities are core objects in your system that have data and behavior.

The Noun Hunt

Looking at the requirements, we identify these core entities:

1. JsonParser - Main orchestrator, performs syntactic analysis
2. JsonTokenizer - Performs lexical analysis (tokenization)
3. Token - Represents a single token with type, value, and position
4. TokenType - Enum for token types (LEFT_BRACE, STRING, NUMBER, etc.)
5. JsonValue - Abstract base class for all JSON value types
6. JsonObject - Represents JSON object (key-value pairs)
7. JsonArray - Represents JSON array (ordered list)
8. JsonString - Represents JSON string value
9. JsonNumber - Represents JSON number value
10. JsonBoolean - Represents JSON boolean value
11. JsonNull - Represents JSON null value
12. JsonParseException - Custom exception with position information

Entity Relationships

---

Step 4: Assign Responsibilities

Each class should have a single, well-defined responsibility (SRP).

Responsibility Assignment

JsonParser:

• Orchestrate parsing process using recursive descent
• Maintain current token
• Coordinate between tokenizer and value construction
• Parse objects, arrays, and primitive values
• Validate JSON structure

JsonTokenizer:

• Break JSON string into tokens (lexical analysis)
• Skip whitespace while tracking position
• Parse strings with escape sequences
• Parse numbers (integers, floats, scientific notation)
• Parse keywords (true, false, null)
• Track line and column numbers for error reporting

Token:

• Store token type, value, and position information
• Provide access to token properties

JsonValue (Abstract):

• Define common interface for all JSON types
• Provide getValue() and toString() methods

JsonObject:

• Store key-value pairs as map
• Provide methods to add/get properties
• Convert to native map structure

JsonArray:

• Store elements as ordered list
• Provide methods to add/get elements
• Convert to native list structure

JsonString, JsonNumber, JsonBoolean, JsonNull:

• Represent primitive JSON values
• Store and return appropriate value types

JsonParseException:

• Extend standard exception
• Include line and column information
• Provide formatted error messages

Responsibility Visualization

[Single Responsibility Principle](/design-principles/solid-principles/00-single-responsibility-principle)

Each class should have one reason to change. For example:

• JsonTokenizer changes only when tokenization logic changes
• JsonParser changes only when parsing logic changes
• JsonValue changes only when value interface changes

---

Step 5: Design Class Diagrams

Class diagrams show structure, relationships, and design patterns.

Complete Class Diagram

classDiagram
    class TokenType {
        <<enumeration>>
        LEFT_BRACE
        RIGHT_BRACE
        LEFT_BRACKET
        RIGHT_BRACKET
        COLON
        COMMA
        STRING
        NUMBER
        BOOLEAN_TRUE
        BOOLEAN_FALSE
        NULL
        EOF
    }
    
    class JsonParseException {
        -String message
        -int line
        -int column
        +getLine() int
        +getColumn() int
        +getErrorMessage() String
    }
    
    class Token {
        -TokenType type
        -Object value
        -int line
        -int column
        +getType() TokenType
        +getValue() Object
        +getLine() int
        +getColumn() int
    }
    
    class JsonTokenizer {
        -String input
        -int position
        -int line
        -int column
        +nextToken() Token
        -skipWhitespace() void
        -parseString() Token
        -parseNumber() Token
        -parseKeyword(String, TokenType, int, int) Token
        -advance() void
        +getCurrentLine() int
        +getCurrentColumn() int
    }
    
    class JsonValue {
        <<abstract>>
        +getValue() Object
        +toString() String
    }
    
    class JsonString {
        -String value
        +getValue() String
        +toString() String
        -escapeString(String) String
    }
    
    class JsonNumber {
        -Number value
        +getValue() Number
        +toString() String
    }
    
    class JsonBoolean {
        -boolean value
        +getValue() boolean
        +toString() String
    }
    
    class JsonNull {
        +getValue() null
        +toString() String
    }
    
    class JsonObject {
        -Map~String,JsonValue~ properties
        +put(String, JsonValue) void
        +get(String) JsonValue
        +getProperties() Map
        +getValue() Map~String,Object~
        +toString() String
    }
    
    class JsonArray {
        -List~JsonValue~ elements
        +add(JsonValue) void
        +get(int) JsonValue
        +size() int
        +getElements() List
        +getValue() List~Object~
        +toString() String
    }
    
    class JsonParser {
        -JsonTokenizer tokenizer
        -Token currentToken
        +parse(String) JsonValue
        -parseValue() JsonValue
        -parseObject() JsonObject
        -parseArray() JsonArray
        -consumeToken() void
        -consumeToken(TokenType) void
    }
    
    JsonValue <|-- JsonString
    JsonValue <|-- JsonNumber
    JsonValue <|-- JsonBoolean
    JsonValue <|-- JsonNull
    JsonValue <|-- JsonObject
    JsonValue <|-- JsonArray
    
    JsonParser --> JsonTokenizer : uses
    JsonParser --> Token : uses
    JsonParser --> JsonValue : creates
    JsonTokenizer --> Token : creates
    JsonTokenizer --> JsonParseException : throws
    JsonParser --> JsonParseException : throws
    
    JsonObject --> JsonValue : contains
    JsonArray --> JsonValue : contains
    
    Token --> TokenType : uses

Design Patterns Used

1. Separation of Concerns - Tokenizer vs Parser

• Lexical analysis (tokenization) separated from syntactic analysis (parsing)
• Easier to test and maintain

2. Recursive Descent Parsing - Natural fit for JSON

• Parsing methods call themselves recursively
• Handles nested structures naturally

3. Polymorphism - JsonValue hierarchy

• All JSON types extend JsonValue
• Common interface for all value types

4. Template Method Pattern - JsonValue interface

• Defines common structure for all JSON types
• Each subclass implements specific behavior

---

Step 6: Define Contracts & APIs

Contracts define how classes interact - method signatures, interfaces, and behavior.

Core Interfaces

Python

JsonValue Abstract Class:

json_value.py

from abc import ABC, abstractmethod

class JsonValue(ABC):
    """
    Abstract base class for all JSON value types.
    Provides common interface for all JSON types.
    """
    @abstractmethod
    def get_value(self):
        """
        Get the native value representation.

        Returns:
            Object: Native value (dict, list, str, int, float, bool, None)
        """
        pass

    @abstractmethod
    def __str__(self):
        """
        Convert to JSON string representation.

        Returns:
            str: JSON string representation
        """
        pass

JsonTokenizer:

json_tokenizer.py

class JsonTokenizer:
    """
    Performs lexical analysis - breaks JSON string into tokens.
    """
    def next_token(self) -> Token:
        """
        Get the next token from input.

        Returns:
            Token: Next token in the stream

        Raises:
            JsonParseException: If invalid character or format encountered
        """
        pass

    def get_current_line(self) -> int:
        """Get current line number (1-indexed)."""
        pass

    def get_current_column(self) -> int:
        """Get current column number (1-indexed)."""
        pass

Java

JsonValue Abstract Class:

JsonValue.java

abstract class JsonValue {
    /**
     * Get the native value representation.
     * @return Native value (Map, List, String, Number, Boolean, null)
     */
    public abstract Object getValue();

    /**
     * Convert to JSON string representation.
     * @return JSON string representation
     */
    public abstract String toString();
}

JsonTokenizer:

JsonTokenizer.java

class JsonTokenizer {
    /**
     * Get the next token from input.
     * @return Next token in the stream
     * @throws JsonParseException If invalid character or format encountered
     */
    public Token nextToken() throws JsonParseException;

    /** Get current line number (1-indexed). */
    public int getCurrentLine();

    /** Get current column number (1-indexed). */
    public int getCurrentColumn();
}

Core Class Contracts

Python

JsonParser:

json_parser.py

class JsonParser:
    """
    Main parser that orchestrates JSON parsing using recursive descent.
    """
    def __init__(self, json_string: str):
        """
        Initialize parser with JSON string.

        Args:
            json_string: JSON string to parse
        """
        pass

    def parse(self) -> JsonValue:
        """
        Parse JSON string into JsonValue.

        Returns:
            JsonValue: Parsed JSON value

        Raises:
            JsonParseException: If JSON is invalid or malformed
        """
        pass

    def _parse_value(self) -> JsonValue:
        """
        Parse a JSON value (object, array, or primitive).
        Internal method used recursively.
        """
        pass

    def _parse_object(self) -> JsonObject:
        """
        Parse a JSON object (key-value pairs).
        Internal method used recursively.
        """
        pass

    def _parse_array(self) -> JsonArray:
        """
        Parse a JSON array (ordered list).
        Internal method used recursively.
        """
        pass

Java

JsonParser:

JsonParser.java

class JsonParser {
    /**
     * Initialize parser with JSON string.
     * @param jsonString JSON string to parse
     */
    public JsonParser(String jsonString);

    /**
     * Parse JSON string into JsonValue.
     * @return Parsed JSON value
     * @throws JsonParseException If JSON is invalid or malformed
     */
    public JsonValue parse() throws JsonParseException;

    /**
     * Parse a JSON value (object, array, or primitive).
     * Internal method used recursively.
     */
    private JsonValue parseValue() throws JsonParseException;

    /**
     * Parse a JSON object (key-value pairs).
     * Internal method used recursively.
     */
    private JsonObject parseObject() throws JsonParseException;

    /**
     * Parse a JSON array (ordered list).
     * Internal method used recursively.
     */
    private JsonArray parseArray() throws JsonParseException;
}

Contract Visualization

Contract [Design Principles](/design-principles/00-introduction-to-design-principles)

• Be explicit - Clear parameter types and return types
• Document exceptions - What can go wrong?
• Keep it simple - Don’t over-complicate
• Think about callers - What do they need?

---

Step 7: Handle Edge Cases

Edge cases are scenarios that might not be obvious but are important to handle.

Critical Edge Cases

1. Empty JSON String

• Return appropriate error or handle gracefully
• Validate input is not empty before parsing

2. Unterminated Strings

• String not closed with closing quote
• Track position and throw exception with line/column

3. Invalid Number Format

• Missing digits after decimal point: 12.
• Missing digits in exponent: 1.5e
• Invalid characters in number
• Throw exception with position information

4. Invalid Escape Sequences

• Invalid escape: \x (not \n, \t, etc.)
• Incomplete Unicode: \u12 (needs 4 hex digits)
• Invalid hex digits: \uXYZW
• Throw exception with position information

5. Malformed Structure

• Missing commas: {"key1": "value1" "key2": "value2"}
• Missing colons: {"key" "value"}
• Unexpected tokens: {"key": }
• Extra commas: [1, 2, 3,]
• Throw exception with position information

6. Deep Nesting

• Extremely nested structures might cause stack overflow
• Consider depth limit or iterative approach for very deep nesting

7. Invalid Keywords

• Partial keywords: tru, fals, nul
• Validate complete keyword matches

8. Whitespace Handling

• Multiple spaces, tabs, newlines between elements
• Track line/column correctly across newlines

Edge Case Handling Flow

Error Handling Examples

Python

error_handling.py

class JsonParseException(Exception):
    def __init__(self, message: str, line: int, column: int):
        self.message = message
        self.line = line
        self.column = column
        super().__init__(f"JSON Parse Error at line {line}, column {column}: {message}")

# Example error scenarios
try:
    parser = JsonParser('{"key": "unclosed')
    parser.parse()
except JsonParseException as e:
    print(f"Error: {e.message} at {e.line}:{e.column}")
    # Output: Error: Unterminated string at 1:15

try:
    parser = JsonParser('{"num": 12.}')
    parser.parse()
except JsonParseException as e:
    print(f"Error: {e.message} at {e.line}:{e.column}")
    # Output: Error: Invalid number format: expected digit after decimal point at 1:12

Java

ErrorHandling.java

class JsonParseException extends Exception {
    private int line;
    private int column;
    private String message;

    public JsonParseException(String message, int line, int column) {
        super(String.format("JSON Parse Error at line %d, column %d: %s",
                          line, column, message));
        this.message = message;
        this.line = line;
        this.column = column;
    }
}

// Example error scenarios
try {
    JsonParser parser = new JsonParser("{\"key\": \"unclosed");
    parser.parse();
} catch (JsonParseException e) {
    System.out.println("Error: " + e.getMessage());
    // Output: Error: JSON Parse Error at line 1, column 15: Unterminated string
}

Edge Case Checklist

Always think about:

• What if input is empty/null?
• What if string is unterminated?
• What if number format is invalid?
• What if structure is malformed?
• What if escape sequence is invalid?
• What if nesting is too deep?
• What if whitespace is malformed?

---

Step 8: Code Implementation

Finally, implement your design following SOLID principles and design patterns.

Complete Implementation

Python

json_parser_complete.py

# File: exceptions/json_parse_exception.py
class JsonParseException(Exception):
    def __init__(self, message: str, line: int, column: int):
        self.message = message
        self.line = line
        self.column = column
        super().__init__(f"JSON Parse Error at line {line}, column {column}: {message}")

# File: models/token_type.py
from enum import Enum

class TokenType(Enum):
    LEFT_BRACE = "LEFT_BRACE"
    RIGHT_BRACE = "RIGHT_BRACE"
    LEFT_BRACKET = "LEFT_BRACKET"
    RIGHT_BRACKET = "RIGHT_BRACKET"
    COLON = "COLON"
    COMMA = "COMMA"
    STRING = "STRING"
    NUMBER = "NUMBER"
    BOOLEAN_TRUE = "BOOLEAN_TRUE"
    BOOLEAN_FALSE = "BOOLEAN_FALSE"
    NULL = "NULL"
    EOF = "EOF"

# File: models/token.py
class Token:
    def __init__(self, token_type: TokenType, value=None, line: int = 0, column: int = 0):
        self.type = token_type
        self.value = value
        self.line = line
        self.column = column

# File: models/json_value.py
from abc import ABC, abstractmethod

class JsonValue(ABC):
    @abstractmethod
    def get_value(self):
        pass

    @abstractmethod
    def __str__(self):
        pass

# File: models/json_string.py
class JsonString(JsonValue):
    def __init__(self, value: str):
        self.value = value

    def get_value(self):
        return self.value

    def __str__(self):
        return f'"{self._escape_string(self.value)}"'

    def _escape_string(self, s: str) -> str:
        result = []
        for char in s:
            if char == '"':
                result.append('\\"')
            elif char == '\\':
                result.append('\\\\')
            elif char == '\n':
                result.append('\\n')
            elif char == '\r':
                result.append('\\r')
            elif char == '\t':
                result.append('\\t')
            else:
                result.append(char)
        return ''.join(result)

# File: models/json_number.py
class JsonNumber(JsonValue):
    def __init__(self, value):
        self.value = value

    def get_value(self):
        return self.value

    def __str__(self):
        return str(self.value)

# File: models/json_boolean.py
class JsonBoolean(JsonValue):
    def __init__(self, value: bool):
        self.value = value

    def get_value(self):
        return self.value

    def __str__(self):
        return "true" if self.value else "false"

# File: models/json_null.py
class JsonNull(JsonValue):
    def get_value(self):
        return None

    def __str__(self):
        return "null"

# File: models/json_object.py
class JsonObject(JsonValue):
    def __init__(self):
        self.properties = {}

    def put(self, key: str, value: JsonValue):
        self.properties[key] = value

    def get(self, key: str):
        return self.properties.get(key)

    def get_value(self):
        return {k: v.get_value() for k, v in self.properties.items()}

    def __str__(self):
        items = [f'"{k}": {str(v)}' for k, v in self.properties.items()]
        return "{" + ", ".join(items) + "}"

# File: models/json_array.py
class JsonArray(JsonValue):
    def __init__(self):
        self.elements = []

    def add(self, value: JsonValue):
        self.elements.append(value)

    def get_value(self):
        return [elem.get_value() for elem in self.elements]

    def __str__(self):
        items = [str(elem) for elem in self.elements]
        return "[" + ", ".join(items) + "]"

# File: tokenizer/json_tokenizer.py
class JsonTokenizer:
    def __init__(self, input_str: str):
        self.input = input_str
        self.position = 0
        self.line = 1
        self.column = 1

    def next_token(self) -> Token:
        self._skip_whitespace()

        if self.position >= len(self.input):
            return Token(TokenType.EOF, line=self.line, column=self.column)

        current = self.input[self.position]
        start_line = self.line
        start_column = self.column

        if current == '{':
            self._advance()
            return Token(TokenType.LEFT_BRACE, line=start_line, column=start_column)
        elif current == '}':
            self._advance()
            return Token(TokenType.RIGHT_BRACE, line=start_line, column=start_column)
        elif current == '[':
            self._advance()
            return Token(TokenType.LEFT_BRACKET, line=start_line, column=start_column)
        elif current == ']':
            self._advance()
            return Token(TokenType.RIGHT_BRACKET, line=start_line, column=start_column)
        elif current == ':':
            self._advance()
            return Token(TokenType.COLON, line=start_line, column=start_column)
        elif current == ',':
            self._advance()
            return Token(TokenType.COMMA, line=start_line, column=start_column)
        elif current == '"':
            return self._parse_string()
        elif current == 't':
            return self._parse_keyword("true", TokenType.BOOLEAN_TRUE, start_line, start_column)
        elif current == 'f':
            return self._parse_keyword("false", TokenType.BOOLEAN_FALSE, start_line, start_column)
        elif current == 'n':
            return self._parse_keyword("null", TokenType.NULL, start_line, start_column)
        elif current in '-0123456789':
            return self._parse_number()
        else:
            raise JsonParseException(f"Unexpected character: {current}", start_line, start_column)

    def _skip_whitespace(self):
        while self.position < len(self.input):
            c = self.input[self.position]
            if c == ' ' or c == '\t':
                self._advance()
            elif c == '\n':
                self.line += 1
                self.column = 1
                self.position += 1
            elif c == '\r':
                if self.position + 1 < len(self.input) and self.input[self.position + 1] == '\n':
                    self.position += 2
                else:
                    self.position += 1
                self.line += 1
                self.column = 1
            else:
                break

    def _advance(self):
        self.position += 1
        self.column += 1

    def _parse_string(self) -> Token:
        start_line = self.line
        start_column = self.column
        self._advance()  # skip opening quote
        result = []

        while self.position < len(self.input):
            c = self.input[self.position]
            if c == '"':
                self._advance()
                return Token(TokenType.STRING, ''.join(result), start_line, start_column)
            elif c == '\\':
                self._advance()
                if self.position >= len(self.input):
                    raise JsonParseException("Unterminated string", self.line, self.column)
                escaped = self.input[self.position]
                if escaped == '"':
                    result.append('"')
                    self._advance()
                elif escaped == '\\':
                    result.append('\\')
                    self._advance()
                elif escaped == '/':
                    result.append('/')
                    self._advance()
                elif escaped == 'b':
                    result.append('\b')
                    self._advance()
                elif escaped == 'f':
                    result.append('\f')
                    self._advance()
                elif escaped == 'n':
                    result.append('\n')
                    self._advance()
                elif escaped == 'r':
                    result.append('\r')
                    self._advance()
                elif escaped == 't':
                    result.append('\t')
                    self._advance()
                elif escaped == 'u':
                    self._advance()
                    if self.position + 4 > len(self.input):
                        raise JsonParseException("Incomplete Unicode escape sequence", self.line, self.column)
                    hex_str = self.input[self.position:self.position + 4]
                    try:
                        code_point = int(hex_str, 16)
                        result.append(chr(code_point))
                        self.position += 4
                        self.column += 4
                    except ValueError:
                        raise JsonParseException(f"Invalid Unicode escape sequence: \\u{hex_str}", self.line, self.column)
                else:
                    raise JsonParseException(f"Invalid escape sequence: \\{escaped}", self.line, self.column)
            elif c == '\n' or c == '\r':
                raise JsonParseException("Unterminated string: newline in string", self.line, self.column)
            else:
                result.append(c)
                self._advance()

        raise JsonParseException("Unterminated string", self.line, self.column)

    def _parse_keyword(self, keyword: str, token_type: TokenType, start_line: int, start_column: int) -> Token:
        if self.position + len(keyword) > len(self.input):
            raise JsonParseException("Unexpected end of input", start_line, start_column)
        actual = self.input[self.position:self.position + len(keyword)]
        if actual != keyword:
            raise JsonParseException(f"Unexpected token: {actual}", start_line, start_column)
        self.position += len(keyword)
        self.column += len(keyword)
        return Token(token_type, line=start_line, column=start_column)

    def _parse_number(self) -> Token:
        start_line = self.line
        start_column = self.column
        result = []
        has_decimal = False

        if self.input[self.position] == '-':
            result.append('-')
            self._advance()

        if self.position >= len(self.input) or not self.input[self.position].isdigit():
            raise JsonParseException("Invalid number format", start_line, start_column)

        # Parse integer part
        while self.position < len(self.input) and self.input[self.position].isdigit():
            result.append(self.input[self.position])
            self._advance()

        # Parse decimal part
        if self.position < len(self.input) and self.input[self.position] == '.':
            has_decimal = True
            result.append('.')
            self._advance()
            if self.position >= len(self.input) or not self.input[self.position].isdigit():
                raise JsonParseException("Invalid number format: expected digit after decimal point", self.line, self.column)
            while self.position < len(self.input) and self.input[self.position].isdigit():
                result.append(self.input[self.position])
                self._advance()

        # Parse exponent part
        if self.position < len(self.input) and self.input[self.position] in 'eE':
            result.append(self.input[self.position])
            self._advance()
            if self.position < len(self.input) and self.input[self.position] in '+-':
                result.append(self.input[self.position])
                self._advance()
            if self.position >= len(self.input) or not self.input[self.position].isdigit():
                raise JsonParseException("Invalid number format: expected digit in exponent", self.line, self.column)
            while self.position < len(self.input) and self.input[self.position].isdigit():
                result.append(self.input[self.position])
                self._advance()

        number_str = ''.join(result)
        try:
            if has_decimal:
                return Token(TokenType.NUMBER, float(number_str), start_line, start_column)
            else:
                return Token(TokenType.NUMBER, int(number_str), start_line, start_column)
        except ValueError:
            raise JsonParseException(f"Invalid number format: {number_str}", start_line, start_column)

    def get_current_line(self) -> int:
        return self.line

    def get_current_column(self) -> int:
        return self.column

# File: parser/json_parser.py
class JsonParser:
    def __init__(self, json_string: str):
        self.tokenizer = JsonTokenizer(json_string)
        self.current_token = None

    def parse(self) -> JsonValue:
        self.current_token = self.tokenizer.next_token()
        result = self._parse_value()
        if self.current_token.type != TokenType.EOF:
            raise JsonParseException(f"Unexpected token after JSON value: {self.current_token.type.value}",
                                    self.current_token.line, self.current_token.column)
        return result

    def _parse_value(self) -> JsonValue:
        if self.current_token.type == TokenType.LEFT_BRACE:
            return self._parse_object()
        elif self.current_token.type == TokenType.LEFT_BRACKET:
            return self._parse_array()
        elif self.current_token.type == TokenType.STRING:
            value = JsonString(self.current_token.value)
            self._consume_token()
            return value
        elif self.current_token.type == TokenType.NUMBER:
            value = JsonNumber(self.current_token.value)
            self._consume_token()
            return value
        elif self.current_token.type == TokenType.BOOLEAN_TRUE:
            self._consume_token()
            return JsonBoolean(True)
        elif self.current_token.type == TokenType.BOOLEAN_FALSE:
            self._consume_token()
            return JsonBoolean(False)
        elif self.current_token.type == TokenType.NULL:
            self._consume_token()
            return JsonNull()
        else:
            raise JsonParseException(f"Unexpected token: {self.current_token.type.value}",
                                    self.current_token.line, self.current_token.column)

    def _parse_object(self) -> JsonObject:
        self._consume_token(TokenType.LEFT_BRACE)
        obj = JsonObject()

        if self.current_token.type == TokenType.RIGHT_BRACE:
            self._consume_token()
            return obj

        while True:
            if self.current_token.type != TokenType.STRING:
                raise JsonParseException("Expected string key in object",
                                        self.current_token.line, self.current_token.column)
            key = self.current_token.value
            self._consume_token()

            self._consume_token(TokenType.COLON)

            value = self._parse_value()
            obj.put(key, value)

            if self.current_token.type == TokenType.RIGHT_BRACE:
                self._consume_token()
                break
            elif self.current_token.type == TokenType.COMMA:
                self._consume_token()
            else:
                raise JsonParseException("Expected ',' or '}' in object",
                                        self.current_token.line, self.current_token.column)

        return obj

    def _parse_array(self) -> JsonArray:
        self._consume_token(TokenType.LEFT_BRACKET)
        array = JsonArray()

        if self.current_token.type == TokenType.RIGHT_BRACKET:
            self._consume_token()
            return array

        while True:
            value = self._parse_value()
            array.add(value)

            if self.current_token.type == TokenType.RIGHT_BRACKET:
                self._consume_token()
                break
            elif self.current_token.type == TokenType.COMMA:
                self._consume_token()
            else:
                raise JsonParseException("Expected ',' or ']' in array",
                                        self.current_token.line, self.current_token.column)

        return array

    def _consume_token(self, expected_type: TokenType = None):
        if expected_type is not None:
            if self.current_token.type != expected_type:
                raise JsonParseException(f"Expected {expected_type.value} but found {self.current_token.type.value}",
                                        self.current_token.line, self.current_token.column)
        self.current_token = self.tokenizer.next_token()

# File: main.py
if __name__ == "__main__":
    # Test 1: Simple object
    json1 = '{"name": "John", "age": 30, "isActive": true}'
    parser1 = JsonParser(json1)
    result1 = parser1.parse()
    print("Test 1 - Simple Object:")
    print(f"Parsed: {result1}")
    print(f"Value: {result1.get_value()}")
    print()

    # Test 2: Nested object
    json2 = '{"person": {"name": "Alice", "age": 25}, "city": "New York"}'
    parser2 = JsonParser(json2)
    result2 = parser2.parse()
    print("Test 2 - Nested Object:")
    print(f"Parsed: {result2}")
    print()

    # Test 3: Array
    json3 = '[1, 2, 3, "hello", true, null]'
    parser3 = JsonParser(json3)
    result3 = parser3.parse()
    print("Test 3 - Array:")
    print(f"Parsed: {result3}")
    print(f"Value: {result3.get_value()}")

Java

JsonParserComplete.java

// File: exceptions/json_parse_exception.java
class JsonParseException extends Exception {
    private int line;
    private int column;
    private String message;

    public JsonParseException(String message, int line, int column) {
        super(String.format("JSON Parse Error at line %d, column %d: %s", line, column, message));
        this.message = message;
        this.line = line;
        this.column = column;
    }

    public int getLine() { return line; }
    public int getColumn() { return column; }
    public String getErrorMessage() { return message; }
}

// File: models/token_type.java
enum TokenType {
    LEFT_BRACE, RIGHT_BRACE, LEFT_BRACKET, RIGHT_BRACKET,
    COLON, COMMA, STRING, NUMBER, BOOLEAN_TRUE, BOOLEAN_FALSE, NULL, EOF
}

// File: models/token.java
class Token {
    private TokenType type;
    private Object value;
    private int line;
    private int column;

    public Token(TokenType type, Object value, int line, int column) {
        this.type = type;
        this.value = value;
        this.line = line;
        this.column = column;
    }

    public TokenType getType() { return type; }
    public Object getValue() { return value; }
    public int getLine() { return line; }
    public int getColumn() { return column; }
}

// File: models/json_value.java
abstract class JsonValue {
    public abstract Object getValue();
    public abstract String toString();
}

// File: models/json_string.java
class JsonString extends JsonValue {
    private String value;

    public JsonString(String value) {
        this.value = value;
    }

    @Override
    public Object getValue() {
        return value;
    }

    @Override
    public String toString() {
        return "\"" + escapeString(value) + "\"";
    }

    private String escapeString(String str) {
        StringBuilder sb = new StringBuilder();
        for (char c : str.toCharArray()) {
            switch (c) {
                case '"': sb.append("\\\""); break;
                case '\\': sb.append("\\\\"); break;
                case '\n': sb.append("\\n"); break;
                case '\r': sb.append("\\r"); break;
                case '\t': sb.append("\\t"); break;
                default: sb.append(c); break;
            }
        }
        return sb.toString();
    }
}

// File: models/json_number.java
class JsonNumber extends JsonValue {
    private Number value;

    public JsonNumber(Number value) {
        this.value = value;
    }

    @Override
    public Object getValue() {
        return value;
    }

    @Override
    public String toString() {
        return value.toString();
    }
}

// File: models/json_boolean.java
class JsonBoolean extends JsonValue {
    private boolean value;

    public JsonBoolean(boolean value) {
        this.value = value;
    }

    @Override
    public Object getValue() {
        return value;
    }

    @Override
    public String toString() {
        return value ? "true" : "false";
    }
}

// File: models/json_null.java
class JsonNull extends JsonValue {
    @Override
    public Object getValue() {
        return null;
    }

    @Override
    public String toString() {
        return "null";
    }
}

// File: models/json_object.java
class JsonObject extends JsonValue {
    private java.util.Map<String, JsonValue> properties;

    public JsonObject() {
        this.properties = new java.util.LinkedHashMap<>();
    }

    public void put(String key, JsonValue value) {
        properties.put(key, value);
    }

    public JsonValue get(String key) {
        return properties.get(key);
    }

    @Override
    public Object getValue() {
        java.util.Map<String, Object> result = new java.util.LinkedHashMap<>();
        for (java.util.Map.Entry<String, JsonValue> entry : properties.entrySet()) {
            result.put(entry.getKey(), entry.getValue().getValue());
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        boolean first = true;
        for (java.util.Map.Entry<String, JsonValue> entry : properties.entrySet()) {
            if (!first) sb.append(", ");
            sb.append("\"").append(entry.getKey()).append("\": ").append(entry.getValue().toString());
            first = false;
        }
        sb.append("}");
        return sb.toString();
    }
}

// File: models/json_array.java
class JsonArray extends JsonValue {
    private java.util.List<JsonValue> elements;

    public JsonArray() {
        this.elements = new java.util.ArrayList<>();
    }

    public void add(JsonValue value) {
        elements.add(value);
    }

    @Override
    public Object getValue() {
        java.util.List<Object> result = new java.util.ArrayList<>();
        for (JsonValue value : elements) {
            result.add(value.getValue());
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        boolean first = true;
        for (JsonValue value : elements) {
            if (!first) sb.append(", ");
            sb.append(value.toString());
            first = false;
        }
        sb.append("]");
        return sb.toString();
    }
}

// File: tokenizer/json_tokenizer.java
class JsonTokenizer {
    private String input;
    private int position;
    private int line;
    private int column;

    public JsonTokenizer(String input) {
        this.input = input;
        this.position = 0;
        this.line = 1;
        this.column = 1;
    }

    public Token nextToken() throws JsonParseException {
        skipWhitespace();

        if (position >= input.length()) {
            return new Token(TokenType.EOF, null, line, column);
        }

        char current = input.charAt(position);
        int startLine = line;
        int startColumn = column;

        switch (current) {
            case '{': advance(); return new Token(TokenType.LEFT_BRACE, null, startLine, startColumn);
            case '}': advance(); return new Token(TokenType.RIGHT_BRACE, null, startLine, startColumn);
            case '[': advance(); return new Token(TokenType.LEFT_BRACKET, null, startLine, startColumn);
            case ']': advance(); return new Token(TokenType.RIGHT_BRACKET, null, startLine, startColumn);
            case ':': advance(); return new Token(TokenType.COLON, null, startLine, startColumn);
            case ',': advance(); return new Token(TokenType.COMMA, null, startLine, startColumn);
            case '"': return parseString();
            case 't': return parseKeyword("true", TokenType.BOOLEAN_TRUE, startLine, startColumn);
            case 'f': return parseKeyword("false", TokenType.BOOLEAN_FALSE, startLine, startColumn);
            case 'n': return parseKeyword("null", TokenType.NULL, startLine, startColumn);
            case '-':
            case '0': case '1': case '2': case '3': case '4':
            case '5': case '6': case '7': case '8': case '9':
                return parseNumber();
            default:
                throw new JsonParseException("Unexpected character: " + current, startLine, startColumn);
        }
    }

    private void skipWhitespace() {
        while (position < input.length()) {
            char c = input.charAt(position);
            if (c == ' ' || c == '\t') {
                advance();
            } else if (c == '\n') {
                line++;
                column = 1;
                position++;
            } else if (c == '\r') {
                if (position + 1 < input.length() && input.charAt(position + 1) == '\n') {
                    position += 2;
                } else {
                    position++;
                }
                line++;
                column = 1;
            } else {
                break;
            }
        }
    }

    private void advance() {
        position++;
        column++;
    }

    private Token parseString() throws JsonParseException {
        int startLine = line;
        int startColumn = column;
        advance(); // skip opening quote
        StringBuilder sb = new StringBuilder();

        while (position < input.length()) {
            char c = input.charAt(position);
            if (c == '"') {
                advance();
                return new Token(TokenType.STRING, sb.toString(), startLine, startColumn);
            } else if (c == '\\') {
                advance();
                if (position >= input.length()) {
                    throw new JsonParseException("Unterminated string", line, column);
                }
                char escaped = input.charAt(position);
                switch (escaped) {
                    case '"': sb.append('"'); advance(); break;
                    case '\\': sb.append('\\'); advance(); break;
                    case '/': sb.append('/'); advance(); break;
                    case 'b': sb.append('\b'); advance(); break;
                    case 'f': sb.append('\f'); advance(); break;
                    case 'n': sb.append('\n'); advance(); break;
                    case 'r': sb.append('\r'); advance(); break;
                    case 't': sb.append('\t'); advance(); break;
                    case 'u':
                        advance();
                        if (position + 4 > input.length()) {
                            throw new JsonParseException("Incomplete Unicode escape sequence", line, column);
                        }
                        String hex = input.substring(position, position + 4);
                        try {
                            int codePoint = Integer.parseInt(hex, 16);
                            sb.append((char) codePoint);
                            position += 4;
                            column += 4;
                        } catch (NumberFormatException e) {
                            throw new JsonParseException("Invalid Unicode escape sequence: \\u" + hex, line, column);
                        }
                        break;
                    default:
                        throw new JsonParseException("Invalid escape sequence: \\" + escaped, line, column);
                }
            } else if (c == '\n' || c == '\r') {
                throw new JsonParseException("Unterminated string: newline in string", line, column);
            } else {
                sb.append(c);
                advance();
            }
        }

        throw new JsonParseException("Unterminated string", line, column);
    }

    private Token parseKeyword(String keyword, TokenType type, int startLine, int startColumn) throws JsonParseException {
        if (position + keyword.length() > input.length()) {
            throw new JsonParseException("Unexpected end of input", startLine, startColumn);
        }
        String actual = input.substring(position, position + keyword.length());
        if (!actual.equals(keyword)) {
            throw new JsonParseException("Unexpected token: " + actual, startLine, startColumn);
        }
        position += keyword.length();
        column += keyword.length();
        return new Token(type, null, startLine, startColumn);
    }

    private Token parseNumber() throws JsonParseException {
        int startLine = line;
        int startColumn = column;
        StringBuilder sb = new StringBuilder();
        boolean hasDecimal = false;

        if (input.charAt(position) == '-') {
            sb.append('-');
            advance();
        }

        if (position >= input.length() || !Character.isDigit(input.charAt(position))) {
            throw new JsonParseException("Invalid number format", startLine, startColumn);
        }

        // Parse integer part
        while (position < input.length() && Character.isDigit(input.charAt(position))) {
            sb.append(input.charAt(position));
            advance();
        }

        // Parse decimal part
        if (position < input.length() && input.charAt(position) == '.') {
            hasDecimal = true;
            sb.append('.');
            advance();
            if (position >= input.length() || !Character.isDigit(input.charAt(position))) {
                throw new JsonParseException("Invalid number format: expected digit after decimal point", line, column);
            }
            while (position < input.length() && Character.isDigit(input.charAt(position))) {
                sb.append(input.charAt(position));
                advance();
            }
        }

        // Parse exponent part
        if (position < input.length() && (input.charAt(position) == 'e' || input.charAt(position) == 'E')) {
            sb.append(input.charAt(position));
            advance();
            if (position < input.length() && (input.charAt(position) == '+' || input.charAt(position) == '-')) {
                sb.append(input.charAt(position));
                advance();
            }
            if (position >= input.length() || !Character.isDigit(input.charAt(position))) {
                throw new JsonParseException("Invalid number format: expected digit in exponent", line, column);
            }
            while (position < input.length() && Character.isDigit(input.charAt(position))) {
                sb.append(input.charAt(position));
                advance();
            }
        }

        String numberStr = sb.toString();
        try {
            if (hasDecimal) {
                return new Token(TokenType.NUMBER, Double.parseDouble(numberStr), startLine, startColumn);
            } else {
                long longValue = Long.parseLong(numberStr);
                if (longValue >= Integer.MIN_VALUE && longValue <= Integer.MAX_VALUE) {
                    return new Token(TokenType.NUMBER, (int) longValue, startLine, startColumn);
                } else {
                    return new Token(TokenType.NUMBER, longValue, startLine, startColumn);
                }
            }
        } catch (NumberFormatException e) {
            throw new JsonParseException("Invalid number format: " + numberStr, startLine, startColumn);
        }
    }

    public int getCurrentLine() { return line; }
    public int getCurrentColumn() { return column; }
}

// File: parser/json_parser.java
class JsonParser {
    private JsonTokenizer tokenizer;
    private Token currentToken;

    public JsonParser(String jsonString) {
        this.tokenizer = new JsonTokenizer(jsonString);
    }

    public JsonValue parse() throws JsonParseException {
        currentToken = tokenizer.nextToken();
        JsonValue result = parseValue();
        if (currentToken.getType() != TokenType.EOF) {
            throw new JsonParseException("Unexpected token after JSON value: " + currentToken.getType(),
                    currentToken.getLine(), currentToken.getColumn());
        }
        return result;
    }

    private JsonValue parseValue() throws JsonParseException {
        switch (currentToken.getType()) {
            case LEFT_BRACE:
                return parseObject();
            case LEFT_BRACKET:
                return parseArray();
            case STRING:
                JsonString str = new JsonString((String) currentToken.getValue());
                consumeToken();
                return str;
            case NUMBER:
                JsonNumber num = new JsonNumber((Number) currentToken.getValue());
                consumeToken();
                return num;
            case BOOLEAN_TRUE:
                consumeToken();
                return new JsonBoolean(true);
            case BOOLEAN_FALSE:
                consumeToken();
                return new JsonBoolean(false);
            case NULL:
                consumeToken();
                return new JsonNull();
            default:
                throw new JsonParseException("Unexpected token: " + currentToken.getType(),
                        currentToken.getLine(), currentToken.getColumn());
        }
    }

    private JsonObject parseObject() throws JsonParseException {
        consumeToken(TokenType.LEFT_BRACE);
        JsonObject obj = new JsonObject();

        if (currentToken.getType() == TokenType.RIGHT_BRACE) {
            consumeToken();
            return obj;
        }

        while (true) {
            if (currentToken.getType() != TokenType.STRING) {
                throw new JsonParseException("Expected string key in object",
                        currentToken.getLine(), currentToken.getColumn());
            }
            String key = (String) currentToken.getValue();
            consumeToken();

            consumeToken(TokenType.COLON);

            JsonValue value = parseValue();
            obj.put(key, value);

            if (currentToken.getType() == TokenType.RIGHT_BRACE) {
                consumeToken();
                break;
            } else if (currentToken.getType() == TokenType.COMMA) {
                consumeToken();
            } else {
                throw new JsonParseException("Expected ',' or '}' in object",
                        currentToken.getLine(), currentToken.getColumn());
            }
        }

        return obj;
    }

    private JsonArray parseArray() throws JsonParseException {
        consumeToken(TokenType.LEFT_BRACKET);
        JsonArray array = new JsonArray();

        if (currentToken.getType() == TokenType.RIGHT_BRACKET) {
            consumeToken();
            return array;
        }

        while (true) {
            JsonValue value = parseValue();
            array.add(value);

            if (currentToken.getType() == TokenType.RIGHT_BRACKET) {
                consumeToken();
                break;
            } else if (currentToken.getType() == TokenType.COMMA) {
                consumeToken();
            } else {
                throw new JsonParseException("Expected ',' or ']' in array",
                        currentToken.getLine(), currentToken.getColumn());
            }
        }

        return array;
    }

    private void consumeToken() throws JsonParseException {
        currentToken = tokenizer.nextToken();
    }

    private void consumeToken(TokenType expectedType) throws JsonParseException {
        if (currentToken.getType() != expectedType) {
            throw new JsonParseException("Expected " + expectedType + " but found " + currentToken.getType(),
                    currentToken.getLine(), currentToken.getColumn());
        }
        consumeToken();
    }
}

// File: main.java
public class Main {
    public static void main(String[] args) {
        try {
            String json1 = "{\"name\": \"John\", \"age\": 30, \"isActive\": true}";
            JsonParser parser1 = new JsonParser(json1);
            JsonValue result1 = parser1.parse();
            System.out.println("Test 1 - Simple Object:");
            System.out.println("Parsed: " + result1.toString());
            System.out.println("Value: " + result1.getValue());
        } catch (JsonParseException e) {
            System.err.println("Parse Error: " + e.getMessage());
        }
    }
}

Key Implementation Highlights

1. Separation of Concerns:

• JsonTokenizer handles lexical analysis (tokenization)
• JsonParser handles syntactic analysis (parsing)
• Clear separation makes code maintainable and testable

2. Recursive Descent Parsing:

• parseValue() calls parseObject() or parseArray() recursively
• Natural fit for JSON’s hierarchical structure
• Handles arbitrary nesting depth

3. Position Tracking:

• Tokenizer tracks line and column numbers
• Errors include precise position information
• Essential for debugging large JSON files

4. Unicode Support:

• Handles escape sequences (\n, \t, \r, etc.)
• Supports Unicode escapes (\uXXXX)
• Validates escape sequences properly

5. Error Handling:

• Custom exception with position information
• Clear error messages for different failure scenarios
• Helps developers debug invalid JSON quickly

---

Design Patterns Deep Dive

Why Separation of Concerns?

Problem: Parsing involves two distinct phases - breaking input into tokens and building structure from tokens.

Without Separation:

Python

no_separation.py

class JsonParser:
    def parse(self, json_string):
        # Mixing tokenization and parsing ❌
        i = 0
        while i < len(json_string):
            if json_string[i] == '{':
                # Parse object while also tokenizing
                # Hard to test, hard to maintain

Java

NoSeparation.java

class JsonParser {
    public JsonValue parse(String jsonString) {
        // Mixing tokenization and parsing ❌
        int i = 0;
        while (i < jsonString.length()) {
            if (jsonString.charAt(i) == '{') {
                // Parse object while also tokenizing
                // Hard to test, hard to maintain

With Separation:

Python

with_separation.py

class JsonTokenizer:
    def next_token(self):
        # Only responsible for tokenization ✅
        # Easy to test independently
        pass

class JsonParser:
    def __init__(self, json_string):
        self.tokenizer = JsonTokenizer(json_string)

    def parse(self):
        # Only responsible for parsing ✅
        # Uses tokens from tokenizer
        token = self.tokenizer.next_token()
        # Parse using tokens

Java

WithSeparation.java

class JsonTokenizer {
    public Token nextToken() {
        // Only responsible for tokenization ✅
        // Easy to test independently
    }
}

class JsonParser {
    private JsonTokenizer tokenizer;

    public JsonParser(String jsonString) {
        this.tokenizer = new JsonTokenizer(jsonString);
    }

    public JsonValue parse() {
        // Only responsible for parsing ✅
        // Uses tokens from tokenizer
        Token token = tokenizer.nextToken();
        // Parse using tokens
    }
}

Benefits:

• Test tokenization independently
• Test parsing independently
• Easier to maintain and debug
• Follows Single Responsibility Principle

Why Recursive Descent Parsing?

Problem: JSON has recursive structure - objects and arrays can contain other objects and arrays.

Without Recursion:

Python

no_recursion.py

class JsonParser:
    def parse(self, json_string):
        # Need explicit stack to handle nesting ❌
        stack = []
        depth = 0
        # Complex state management
        # Hard to understand and maintain

Java

NoRecursion.java

class JsonParser {
    public JsonValue parse(String jsonString) {
        // Need explicit stack to handle nesting ❌
        Stack<Object> stack = new Stack<>();
        int depth = 0;
        // Complex state management
        // Hard to understand and maintain

With Recursive Descent:

Python

with_recursion.py

class JsonParser:
    def _parse_value(self):
        # Natural recursion ✅
        if token.type == LEFT_BRACE:
            return self._parse_object()  # Calls parse_value recursively

    def _parse_object(self):
        # Calls parse_value for nested values
        value = self._parse_value()  # Recursive call

Java

WithRecursion.java

class JsonParser {
    private JsonValue parseValue() {
        // Natural recursion ✅
        if (currentToken.getType() == LEFT_BRACE) {
            return parseObject();  // Calls parseValue recursively
        }
    }

    private JsonObject parseObject() {
        // Calls parseValue for nested values
        JsonValue value = parseValue();  // Recursive call
    }
}

Benefits:

• Natural fit for hierarchical structures
• Easy to understand and implement
• Code mirrors JSON structure
• Handles arbitrary nesting depth

Why Polymorphic JsonValue Hierarchy?

Problem: Need to represent different JSON types with common interface.

Without Polymorphism:

Python

no_polymorphism.py

# Need type checking everywhere ❌
if isinstance(value, dict):
    # Handle object
elif isinstance(value, list):
    # Handle array
elif isinstance(value, str):
    # Handle string
# Type checking scattered everywhere

Java

NoPolymorphism.java

// Need type checking everywhere ❌
if (value instanceof Map) {
    // Handle object
} else if (value instanceof List) {
    // Handle array
} else if (value instanceof String) {
    // Handle string
}
// Type checking scattered everywhere

With Polymorphism:

Python

with_polymorphism.py

class JsonValue(ABC):
    @abstractmethod
    def get_value(self):
        pass

# All types implement same interface ✅
value.get_value()  # Works for all types
# No type checking needed

Java

WithPolymorphism.java

abstract class JsonValue {
    public abstract Object getValue();
}

// All types implement same interface ✅
value.getValue();  // Works for all types
// No type checking needed

Benefits:

• Type safety
• Extensible - easy to add new types
• Clean interface
• No scattered type checks

---

System Flow Diagrams

Parsing Flow

Tokenization Flow

String Parsing with Escapes

flowchart TD
    A[Start parseString] --> B[Skip opening quote]
    B --> C{Character?}
    C -->|"| D[End string, return token]
    C -->|\\| E[Escape sequence]
    C -->|Newline| F[Error: newline in string]
    C -->|Other| G[Add to result]
    
    E --> H{Escape type?}
    H -->|\\" \\\\ \\/| I[Single char]
    H -->|\\n \\t \\r| J[Control char]
    H -->|\\u| K[Unicode]
    H -->|Other| L[Error: invalid escape]
    
    K --> M[Read 4 hex digits]
    M --> N{Valid hex?}
    N -->|Yes| O[Convert to char]
    N -->|No| P[Error: invalid Unicode]
    
    I --> G
    J --> G
    O --> G
    G --> C
    
    style D fill:#10b981
    style F fill:#ef4444
    style L fill:#ef4444
    style P fill:#ef4444

---

Extensibility & Future Enhancements

Easy to Extend

1. Add JSON Schema Validation:

Python

schema_validation.py

class JsonSchemaValidator:
    def validate(self, json_value: JsonValue, schema: dict) -> bool:
        """Validate JSON value against schema."""
        if isinstance(json_value, JsonObject):
            return self._validate_object(json_value, schema)
        # ... other validations

# Use it
parser = JsonParser(json_string)
value = parser.parse()
validator = JsonSchemaValidator()
if validator.validate(value, schema):
    print("Valid!")

Java

SchemaValidation.java

class JsonSchemaValidator {
    public boolean validate(JsonValue jsonValue, Map<String, Object> schema) {
        // Validate JSON value against schema
        if (jsonValue instanceof JsonObject) {
            return validateObject((JsonObject) jsonValue, schema);
        }
        // ... other validations
    }
}

// Use it
JsonParser parser = new JsonParser(jsonString);
JsonValue value = parser.parse();
JsonSchemaValidator validator = new JsonSchemaValidator();
if (validator.validate(value, schema)) {
    System.out.println("Valid!");
}

2. Add Pretty Printing:

Python

pretty_print.py

class JsonPrettyPrinter:
    def print(self, json_value: JsonValue, indent: int = 2) -> str:
        """Format JSON with indentation."""
        if isinstance(json_value, JsonObject):
            return self._print_object(json_value, indent, 0)
        # ... other types

# Use it
parser = JsonParser(json_string)
value = parser.parse()
printer = JsonPrettyPrinter()
print(printer.print(value))

Java

PrettyPrint.java

class JsonPrettyPrinter {
    public String print(JsonValue jsonValue, int indent) {
        // Format JSON with indentation
        if (jsonValue instanceof JsonObject) {
            return printObject((JsonObject) jsonValue, indent, 0);
        }
        // ... other types
    }
}

// Use it
JsonParser parser = new JsonParser(jsonString);
JsonValue value = parser.parse();
JsonPrettyPrinter printer = new JsonPrettyPrinter();
System.out.println(printer.print(value, 2));

3. Add Streaming Parser:

Python

streaming_parser.py

class StreamingJsonParser:
    """Parse large JSON files without loading entire file."""

    def parse_stream(self, file_handle):
        """Parse JSON from file stream."""
        # Read chunks and parse incrementally
        # Useful for very large JSON files
        pass

Java

StreamingParser.java

class StreamingJsonParser {
    /**
     * Parse large JSON files without loading entire file.
     */
    public void parseStream(InputStream inputStream) {
        // Read chunks and parse incrementally
        // Useful for very large JSON files
    }
}

Future Enhancements

1. JSONPath Support:

• Query JSON using JSONPath expressions
• Example: $.users[0].name

2. JSON Transformations:

• Transform JSON structure
• Filter, map, reduce operations

3. Custom Value Types:

• Extend JsonValue hierarchy
• Add support for custom types

4. Performance Optimizations:

• Streaming parser for large files
• Lazy parsing for large structures
• Memory-efficient implementations

5. Validation Enhancements:

• JSON Schema validation
• Custom validation rules
• Type checking

---

Summary

Key Takeaways

• Follow Systematic Approach - Don’t jump to code
• Separate Concerns - Tokenization vs Parsing
• Use Recursive Descent - Natural fit for hierarchical structures
• Assign Responsibilities - Single Responsibility Principle
• Design Class Diagrams - Visualize structure and relationships
• Handle Edge Cases - Invalid JSON, errors, edge cases
• Track Position - Line and column for error reporting
• Use Polymorphism - JsonValue hierarchy

Design Patterns Used

1. Separation of Concerns - Tokenizer vs Parser
2. Recursive Descent Parsing - Natural recursion for nested structures
3. Polymorphism - JsonValue hierarchy
4. Template Method Pattern - JsonValue interface

Best Practices Demonstrated

• SOLID principles (SRP, OCP)
• Clear separation of concerns
• Comprehensive error handling
• Position tracking for debugging
• Extensible design
• Clean code structure

---

Next Steps

Now that you’ve mastered the JSON Parser:

Practice Similar Problems:

• XML Parser
• Expression Parser (calculator)
• Configuration File Parser
• Markdown Parser

Explore More Concepts:

• Lexical Analysis
• Parsing Techniques
• Compiler Design
• Formal Languages

Deepen Your Understanding:

• Study parser generators (ANTLR, Yacc)
• Learn about different parsing algorithms
• Explore AST (Abstract Syntax Tree) construction
• Study error recovery techniques

---

Practice Makes Perfect

Try implementing this parser yourself! Start with the basic version, then add:

• JSON Schema validation
• Pretty printing
• Streaming parser
• Performance optimizations

The more you practice, the better you’ll become at LLD interviews! 🚀