LL(k) vs LR(k) Grammars

Definition

LL(k) and LR(k) denote two families of grammars parseable by top-down and bottom-up parsers respectively, where k is the number of lookahead symbols.

Key Points

• LL(k): "Left-to-right scan, Leftmost derivation, k-symbol lookahead." Used by top-down/predictive parsers. Grammar must be non-left-recursive and often needs left-factoring.
• LR(k): "Left-to-right scan, Rightmost derivation in reverse, k-symbol lookahead." Used by bottom-up/shift-reduce parsers. Handles a much larger class of grammars, including left-recursive ones.
• Power comparison: every LL(k) grammar is LR(k), but not vice-versa — LR parsers are strictly more powerful/general.
• Trade-off: LL parsers are simpler to hand-write and understand; LR parsers (and variants: SLR, LALR, canonical LR) handle more real-world language grammars and are what tools like YACC/Bison generate.

Example

• LL(1): predictive recursive-descent parser for simple expression grammars (after removing left recursion)
• LR(1)/LALR(1): used internally by YACC to parse C-like languages

📌 CSS Frequency: High — direct comparison/short-note question appears very frequently.

Model Answer (short)

"LL(k) parsers scan left-to-right and build a leftmost derivation using k lookahead symbols, top-down; LR(k) parsers scan left-to-right but build a rightmost derivation in reverse, bottom-up. LR grammars are strictly more powerful than LL grammars of the same k, since every LL(k) grammar is LR(k) but not every LR(k) grammar is LL(k) — this is why most real compiler-generator tools (e.g., YACC) use LALR parsing."