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.

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.

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.

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