Openai·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

Jun 2026

Summary

Got a system design question at OpenAI for a software engineer role that was basically a full compiler/parser design problem. It was one of the most technically dense questions I've ever faced in an interview, covering everything from BNF grammar parsing to AST construction to incremental parsing. Left feeling like I only got through maybe 60% of what they were looking for.

Questions Asked (1)

You are given a set of syntax rules for a hypothetical programming language in BNF/EBNF format. Design the data structures and algorithms to parse that grammar into an internal representation, detect issues like left recursion and ambiguity, apply transformations to enable efficient parsing, compute FIRST/FOLLOW sets, implement a lexer and parser that builds an AST, support error recovery with expected-token hints, handle operator precedence and associativity, analyze time/space complexity, and optionally support incremental or streaming parsing.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I stared at this for a solid 30 seconds before saying anything.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the scope and assumptions (e.g., grammar size, performance goals, incremental parsing needs), then walk through the pipeline from grammar input to AST output, highlighting key data structures and algorithms at each stage. Emphasize trade-offs and justify design decisions, especially around ambiguity handling, error recovery, and complexity.

Pro tip: Demonstrate awareness of real-world parser generators (e.g., ANTLR, Yacc) and when to use them versus hand-written parsers; mention that ambiguity detection is undecidable in general, so practical solutions use heuristics or restrict grammar classes.

1. Clarify requirements and constraints

Ask about grammar size, expected performance, need for incremental parsing, and whether the language is fixed or evolving. This shapes choices like LL vs LR, and whether to use a parser generator.

2. Design grammar representation and preprocessing

Choose data structures (e.g., AST for grammar, maps for productions) and implement algorithms to detect left recursion and ambiguity, then transform grammar (e.g., left-factoring, elimination of left recursion) to enable efficient parsing.

3. Compute FIRST/FOLLOW sets and build parsing tables

Implement algorithms to compute FIRST and FOLLOW sets, then construct LL(1) or LR(1) parsing tables. Discuss handling of operator precedence and associativity via precedence climbing or grammar stratification.

4. Implement lexer and parser with error recovery

Design a lexer (e.g., using regex or hand-written) and a parser that builds an AST. Incorporate error recovery strategies (e.g., panic mode, phrase-level recovery) and expected-token hints using FOLLOW sets.

5. Analyze complexity and discuss extensions

Analyze time/space complexity of each component (e.g., O(n) parsing for LL/LR). Discuss incremental/streaming parsing approaches (e.g., GLR, packrat parsing) and their trade-offs.

Key Points to Mention

Left recursion detection and elimination (e.g., direct vs indirect, algorithm using graph cycles)
Ambiguity detection: undecidable in general; use heuristics like checking for multiple parse trees or grammar restrictions (e.g., LL(1) conflicts)
FIRST/FOLLOW set computation algorithms and their use in predictive parsing and error recovery
Operator precedence and associativity handling: precedence climbing, Pratt parsing, or grammar stratification
Error recovery techniques: panic mode, phrase-level recovery, and using FOLLOW sets for expected tokens
Complexity analysis: O(n) for LL/LR parsing, O(n^3) for general CFG parsing; space trade-offs for tables and incremental parsing

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.