Compare top-down and bottom-up parsing.
Assesses fundamental understanding of Compilers & Languages conventions, runtime behavior, and memory/performance considerations.
Hiring managers look for precision, avoidance of ambiguous jargon, and ability to explain trade-offs under real production conditions.
Parsing turns tokens into a parse tree. Two broad families exist.
Top-down parsers start at the root and predict productions. Recursive descent, and its table-driven form LL(1), is easy to write by hand and gives good errors. Left recursion must be eliminated, and the grammar must be factored to avoid backtracking. Many production compilers use hand-written recursive descent.
Bottom-up parsers start at the leaves and reduce to the start symbol. LR variants, SLR, LALR and canonical LR, are driven by tables and handle a larger class of grammars, including left recursion, without backtracking. LALR is what tools like yacc and Bison generate.
LL: root -> leaves, predictive
LR: leaves -> root, shift/reduce
LL is simpler to understand and debug; LR is more powerful and efficient for complex grammars but its errors are harder to explain. Parser generators trade control for speed of development.
Candidate Response Strategy & Interview Tips
- Start with a concise one-sentence summary: Deliver a direct, confident answer first before expanding into nuances.
- Demonstrate real-world trade-offs: Discuss where this approach excels and when you would avoid it in production systems.
- Discuss complexity & edge cases: Proactively explain time/space complexity or boundary conditions (null values, scale limits).
- Prepare for interviewer follow-ups: Technical hiring panels frequently probe deeper into concurrency, backward compatibility, or alternative libraries.