Prompt and scope
Design a small parser for arithmetic expressions and variable declarations. Input may contain several syntax errors, yet the parser must report positions, continue with later statements, and provide a partial AST for an IDE.
This tests boundaries between lexing, parsing, recovery, and data structures. Bison recommends discarding input to a synchronization point and continuing; IDEs also need error nodes, stable ranges, and recovery beyond the first error.
What the interviewer evaluates
The candidate should define tokens and grammar before choosing recursive descent or LR, distinguish lexical from syntax errors, choose safe synchronization points, suppress cascades, preserve partial ASTs, and test nested delimiters, missing separators, and unterminated strings.
30-second answer framework
“I separate lexer, parser, and diagnostics. The parser tracks a token cursor and source ranges; after an error it records expected and actual tokens, skips to a semicolon, closing delimiter, or EOF, inserts an ErrorNode, and continues. Recovery suppresses duplicates until several tokens succeed. AST nodes retain missing ranges so callers can choose strict or tolerant mode.”
Step-by-step deep answer
Step 1: Define tokens and grammar
The lexer emits kind, text, offsets, and line and column positions for identifiers, numbers, operators, delimiters, semicolons, and invalid characters. The grammar fixes precedence and associativity so recovery is not scattered through expression functions.
Step 2: Choose parser structure
Recursive descent is readable for a small grammar; precedence climbing handles expressions. A larger grammar may use a generator with an explicit error strategy. Either way, the parser needs lookahead, bounded token recovery, and source ranges.
Step 3: Separate lexical and syntax errors
An invalid character or unterminated string is a lexical error: emit an error token and continue scanning. A missing operand, delimiter, or semicolon is a syntax error reported by the parser in context. Do not label every problem “Unexpected token.”
Step 4: Choose synchronization points
Statement-level points are semicolons, closing braces, or EOF. Inside expressions, synchronize at commas, closing parentheses, or operator boundaries. Skipping must always advance the cursor or reach EOF, or the same error loops forever.
Step 5: Build a partial AST
Keep error ranges on nodes. Represent a missing child with MissingNode and an unrecoverable span with ErrorNode containing original tokens. Formatting, highlighting, and completion must handle these nodes instead of assuming a complete tree.
Step 6: Suppress cascaded diagnostics
A recovery can expose many surface errors. Track the last synchronization point and successful-token count; wait for several successful shifts before reporting another diagnostic. Cap errors per file so logs and UI remain usable.
Step 7: Support incremental parsing
When editor text changes, reparse the affected token range and nearby grammar context while reusing unchanged subtrees. Keep node ranges and token IDs stable; invalidate caches by parent boundaries and parser state, not character offsets alone.
Step 8: Test and measure
Test valid input, one error, many errors, nested errors, long strings, and very large expressions. Assert positions, counts, error nodes, and termination. Measure linear scanning, recursion depth, memory, and worst-case recovery cost on long input.
Trade-offs and boundaries
Fail fast versus continue
Batch compilers may continue after diagnostics for better feedback; configuration validation may reject after the first error. Make this a mode while sharing lexer, tokens, and diagnostics to avoid drift.
Many versus few synchronization points
More points limit error scope but may skip recoverable tokens; fewer points preserve context but increase cascades. Define points by statements and delimiters, then test with representative corpus.
Recursive descent versus a generator
Recursive descent makes custom diagnostics easy; a generator suits a large stable grammar. Recovery should be an explicit interface rather than untested generator defaults.
Failure drills and evolution
A closing parenthesis is missing
Add the next statement and verify synchronization at its semicolon or EOF, one missing-delimiter diagnostic, and preservation of the later statement.
Invalid character and unterminated string
Verify the lexer emits an error token and reaches the line or string end without the parser getting stuck on one character.
A storm of consecutive errors
Feed input where every token is invalid. The cursor must advance, error count must be bounded, and CPU must not grow quadratically.
Common mistakes and follow-ups
Mistake 1: Returning null on the first error
Ask how an IDE continues highlighting and completion; return ranged ErrorNode or MissingNode instead.
Mistake 2: Not advancing during recovery
Ask for a termination argument that rules out looping on the same token.
Mistake 3: Reporting every error in the parser
Ask whether an unterminated string and invalid character belong to lexer or parser diagnostics.
Mistake 4: Ignoring cascaded-error suppression
Ask why one missing semicolon should not print ten repeated errors.
Mistake 5: Caching incremental parse by offset only
Ask which parent nodes and parser states become invalid after inserting one delimiter.
Extended follow-ups and reference answers
Why keep error nodes?
Formatting, completion, and highlighting still need structure and ranges. Error nodes let downstream tools handle incomplete input explicitly instead of crashing.
How do you guarantee recovery terminates?
Every recovery consumes a token or reaches EOF, with maximum error and recursion limits.
How do you validate diagnostic quality?
Use corpus containing several independent errors and assert positions, counts, later AST, and runtime rather than testing only the first error.