One-pass S-expression parser with nested lists and precise error handling

Implement a parser for a simplified S-expression language. The exercise has three parts that build on one another. The parser must read the input sequentially, in a single left-to-right pass over the characters; you may not tokenize it with `split()` or similar whole-string splitting. The interviewer's main interest is error handling: when the parser meets an invalid character, it must stop parsing at that point and report the problem. ### Constraints and Clarifications The grammar was described only as simplified S-expressions. Unless the interviewer specifies another, use this working grammar: - **Whitespace** (space, tab, carriage return, newline) separates elements and is otherwise ignored. - **Integer atom:** an optional `-` followed by one or more decimal digits, for example `42` or `-7`. - **Symbol atom:** an ASCII letter or one of `+ - * / _`, followed by any number of ASCII letters, digits or `+ - * / _`, for example `x`, `add`, `+` or `set_value`. A token that matches the integer rule is an integer, not a symbol. - **List:** `(`, then zero or more expressions separated by whitespace, then `)`. A parenthesis also ends an atom, so `(a(b))` is legal. - Any other character, for example `#`, `"` or `@`, is invalid. A token that starts with a digit but is not an integer, such as `12ab`, is invalid too. - Return integers as integers, symbols as strings and lists as lists, so `(add 1 (neg x))` parses to `["add", 1, ["neg", "x"]]`. - The input holds exactly one expression, optionally surrounded by whitespace. Anything after it is an error. - An error report must say what went wrong and at which character index. ### Clarifying Questions - Should errors be raised as exceptions or returned as values, and should anything parsed before the error be returned? - Are string literals, which may contain spaces, parentheses or escaped quotes, part of the language? - Is a character index enough to locate an error, or are line and column numbers expected? - Can the input contain more than one top-level expression? ### Part 1 — Parse an atom Write a function that parses an input consisting of a single atom, optionally surrounded by whitespace, and returns its value. For example, `" -15 "` gives `-15` and `"add"` gives `"add"`, while `"12ab"`, `"a#b"` and an empty input are errors. Structure the atom reader so that the later parts can call it in the middle of a longer input. ```hint Let the reader own the position A reader that starts at the current index and leaves the index just past what it consumed can be called from inside a list later, without slicing or re-reading the string. ``` #### What This Part Should Cover - Recognizing integers, symbols and invalid tokens in one scan - Where an atom ends, and which characters may legally follow it - Error messages that name the problem and its index - An interface the later parts can reuse ### Part 2 — Parse a parenthesized expression Extend the parser to accept a parenthesized list of atoms, with no nesting yet: `(add 1 -2 x)` gives `["add", 1, -2, "x"]` and `()` gives an empty list. Make the error handling complete. The parser must stop at the first problem and report what went wrong and where; at least these inputs must fail with a clear message: `(a # b)`, `(ab#)`, `(12ab)`, `(a b`, `)` and `(a b) c`. A nested list such as `(a (b))` may be rejected for now. ```hint Only a few things can come next Inside a list, after skipping whitespace, list what the next character is allowed to be and what each case means. Everything else is an error you can report on the spot. ``` #### What This Part Should Cover - The loop that reads a list, driven by the same cursor - One clear detection point for each error class: invalid character, malformed atom, unclosed list, unexpected `)`, trailing input - Exact error indices, and stopping without returning a half-built result - Tests for each error class ### Part 3 — Recursive parsing Now lists may contain lists to any depth: `(define (square x) (* x x))` gives `["define", ["square", "x"], ["*", "x", "x"]]`. Extend the parser, still in one pass, so that every error from Part 2 is still detected and reported correctly at any depth, for example a list deep inside the input that is never closed. ```hint Where does an inner list end? Consider what the code that reads a list should do when it meets `(`, and what it should hand back to whoever called it. ``` #### Clarifying Questions for this Part - How deep can nesting go? Is it acceptable to rely on the language's recursion limit? - When a list is never closed, which `(` should the error point to? #### What This Part Should Cover - The recursive structure: one routine for any expression and one for a list, sharing the cursor - Error reporting that stays correct inside nested lists - Very deep nesting: recursion versus an explicit stack - Running time linear in the input length ### What a Strong Answer Covers - A single-pass design with one cursor and no splitting or backtracking - Errors that stop parsing at the first problem and carry an exact index and a specific message - Atom reading separated from list structure, and reused unchanged across all three parts - Tests for valid input and for every error class, including errors inside nested lists - A working version of all three parts before polishing rare edge cases ### Follow-up Questions - An input with 100,000 nested lists crashes a recursive parser. How do you fix it without changing any result? - How would you add string literals that may contain spaces, parentheses and escaped quotes? - The input arrives in chunks from a network stream. How would you restructure the parser so it can resume where a chunk ended? - How would you report line and column numbers instead of a character index?