Requirements

Let's build a JSON parser from scratch. JSON (JavaScript Object Notation) is a lightweight data-interchange format that's easy for humans to read and write, and easy for machines to parse and generate. Almost every modern application interacts with JSON in some way, making a solid understanding of its parsing mechanics invaluable. This problem focuses on designing and implementing a JSON parser that can take a string as input and represent it as an in-memory object model. We are aiming for a parser which: * Correctly parses valid JSON strings. * Handles different data types in JSON: strings, numbers, booleans, nulls, arrays, and nested objects. * Reports meaningful errors for invalid JSON strings (e.g., unexpected characters, missing quotes, etc.). * Is designed in a modular and extensible way. This exercise is not about leveraging existing JSON parsing libraries. The goal is to understand the underlying principles and trade-offs involved in creating one. # Requirements ## Functional Requirements 1. **Basic JSON Types:** * The parser must correctly parse the following JSON types: * `string`: Sequences of Unicode characters, enclosed in double quotes ("). Support escape sequences like `\n`, `\t`, `\\`, `\"`, and `\uXXXX` (where XXXX is a 4-digit hexadecimal number). * `number`: Integers and floating-point numbers. Support positive and negative signs, and exponential notation (e.g., `1.23e+4`). * `boolean`: `true` or `false` (case-sensitive). * `null`: `null` (case-sensitive). * `array`: An ordered list of zero or more JSON values, enclosed in square brackets (`[]`), separated by commas (`,`). * `object`: An unordered collection of key-value pairs, enclosed in curly braces (`{}`), where keys are strings and values are JSON values. Key-value pairs are separated by commas (`,`), and each key is separated from its value by a colon (`:`). 2. **Nested Structures:** * The parser must correctly handle nested JSON objects and arrays of arbitrary depth. For example, arrays within objects, objects within arrays, and so on. 3. **Whitespace Handling:** * The parser must ignore insignificant whitespace (spaces, tabs, newlines, carriage returns) outside of strings. Whitespace within strings must be preserved. 4. **Error Reporting:** * The parser must provide clear and informative error messages when encountering invalid JSON. This includes: * Unexpected characters. * Missing or mismatched brackets/braces. * Invalid numbers (e.g., multiple decimal points, invalid exponential notation). * Invalid escape sequences. * Missing colons or commas in objects. * Incorrectly formatted booleans or null values. 5. **Unicode Support:** * The parser needs to handle Unicode characters correctly, including those represented by escape sequences (`\uXXXX`). 6. **Graceful Handling of Invalid JSON:** The parser should not crash or throw unhandled exceptions when encountering invalid JSON. Instead, it should report an error message and, if possible, attempt to recover and continue parsing (although complete recovery is not required). ## Non-Functional Requirements 1. **Modularity:** The parser should be designed in a modular way, with well-defined responsibilities for each component. This will make it easier to maintain, extend, and test the parser. Think about separating the concerns of tokenizing, parsing, and error handling. 2. **Extensibility:** The design should be extensible to support new JSON features or variations in the future. For example, you might want to add support for comments, or for different data types (e.g., dates). Consider how new types can be added without modifying existing code. 3. **Testability:** The code should be easily testable, with a comprehensive suite of unit tests covering all aspects of the parser's functionality. Consider designing the code in a way that makes it easy to mock dependencies and isolate components for testing. 4. **Readability:** The code should be well-formatted and easy to read, with clear and concise variable names and comments. 5. **Efficiency:** While performance is not the primary focus, the parser should be reasonably efficient. Avoid unnecessary allocations and computations. Consider using efficient data structures and algorithms. Avoid premature optimization. 6. **Thread Safety (Important):** Consider the implications of using the parser in a multithreaded environment. Specifically, is the core parsing logic thread-safe? Can multiple threads concurrently parse different JSON strings using the same parser instance? If not, how could you make it thread-safe? This could involve techniques like using thread-local storage, immutable data structures, or synchronization mechanisms. Be explicit about the threading model you're adopting. ## Core Entities 1. **`JsonParser`**: The main class responsible for parsing a JSON string. It orchestrates the tokenization and parsing process. It should expose a `parse(String jsonString)` method. 2. **`JsonTokenizer` (or `Lexer`)**: Responsible for breaking down the input JSON string into a stream of tokens. Tokens represent the basic building blocks of JSON (e.g., `{`, `}`, `[`, `]`, `:`, `,`, strings, numbers, booleans, null). The tokenizer should handle whitespace and escape sequences. 3. **`JsonToken`**: Represents a single token produced by the tokenizer. It should have a type (e.g., `STRING`, `NUMBER`, `LEFT_BRACE`, `RIGHT_BRACKET`) and a value (e.g., `"hello"`, `123`, `true`). 4. **`JsonValue` (Interface)**: A common interface for all JSON values. This promotes polymorphism and allows us to treat different JSON types in a uniform way. 5. **`JsonObject` (implements `JsonValue`)**: Represents a JSON object (a collection of key-value pairs). Internally, it might use a `Map` to store the key-value pairs. 6. **`JsonArray` (implements `JsonValue`)**: Represents a JSON array (an ordered list of JSON values). Internally, it might use a `List` to store the values. 7. **`JsonString` (implements `JsonValue`)**: Represents a JSON string. 8. **`JsonNumber` (implements `JsonValue`)**: Represents a JSON number. 9. **`JsonBoolean` (implements `JsonValue`)**: Represents a JSON boolean. 10. **`JsonNull` (implements `JsonValue`)**: Represents a JSON null value. It can be a singleton. 11. **`JsonParseException`**: A custom exception class to represent errors encountered during parsing. It should provide information about the location of the error in the JSON string.

Design a Json Parser from scratch

Requirements

Interview Simulation

Functional Requirements

💡 Interview Tip

Non-Functional Requirements

Core Entity Identification

Premium Content