advancedParsing
When would you choose an LL parser over an LR parser, or the other way round?
Whether the candidate weighs parsing techniques by engineering consequences — diagnostics, maintainability, grammar flexibility — rather than by expressive power alone. Nearly everyone knows LR is more powerful; the discriminator is whether they know why hand-written recursive descent won in practice.
What a strong answer covers
- LR accepts strictly more grammars. It decides bottom-up with the whole right-hand side in hand, so it handles left recursion directly and copes with grammars where the correct production is not determined until the end of the construct. LL must decide top-down before consuming the construct, which means left recursion has to be eliminated and the grammar has to be factored.
- And yet almost every production compiler people admire — GCC, Clang, Rust, Go, V8, Roslyn, TypeScript — uses hand-written recursive descent, usually with a Pratt expression parser bolted in where precedence lives. The reasons are all about everything except accepting grammars: error messages, because a recursive-descent parser knows exactly which construct it was in and can say "expected
)to close the argument list opened on line 12"; error recovery, because you can synchronize on a construct boundary you named yourself; context sensitivity, because a hand-written parser can consult the symbol table or a mode flag; and debuggability, because the parser is code you can step through instead of a generated table. - LR earns its place when the grammar is the specification and must be checked mechanically, when someone else owns the grammar, when the language has genuinely awkward constructs, or when the grammar changes often enough that regenerating beats rewriting. Generator conflicts are also a real feature: a shift/reduce conflict is the tool telling you your language is ambiguous, and a hand-written parser silently picks a branch instead.
- The honest summary is that grammar power stopped being the binding constraint once machines were fast enough to backtrack a little, and diagnostics became the binding constraint instead. That is a statement about what compilers are for, not about parsing theory.
✓ Green flags
- Leads with diagnostics and recovery rather than with expressive power.
- Knows the industrial answer is hand-written recursive descent plus Pratt, and can name examples.
- Explains left recursion concretely as the LL problem and why it is not the LR problem.
- Values conflict reports as a correctness check on the language design.
- Mentions that neither is what a formatter or IDE wants — those want a lossless concrete syntax tree.
✗ Red flags
- "LR is strictly better because it handles more grammars." Power is the axis that stopped mattering; the shipping compilers chose the weaker technique deliberately.
- "Recursive descent cannot handle operator precedence." It handles it in two well-known ways — stratified functions or Pratt binding powers — and the latter is what most real parsers do.
- "Parser generators produce faster parsers." Parsing is rarely the bottleneck, and a table-driven parser with poor cache behaviour is not automatically faster than a call chain.
- "You just eliminate left recursion and it is fine." Eliminating it mangles the grammar into a form that no longer resembles the language reference, which is a documentation cost people forget.
Follow-up
Your language needs a < b > c to be either two comparisons or a generic instantiation depending on whether a names a type. How does each approach handle that?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Write the recursive-descent functions for expression, term and factor, then rewrite the expression part as a Pratt loop with a binding-power table. Which one do you extend when a new operator is added?