What Is the Difference Between LL and LR Parsing?

Top-down LL parsing and bottom-up LR shift-reduce parsing are two fundamental techniques used in classical computing to analyze the syntactic structure of source code and formal languages. While both methods read input tokens from left to right, they construct the parse tree in opposite directions and differ in the types of grammars they can handle, their implementation complexity, and their error-detection behavior.

Top-Down LL Parsing

LL parsing stands for Left-to-right scan of the input, producing a Leftmost derivation. An \(LL(k)\) parser starts from the start symbol of a context-free grammar and attempts to expand non-terminals down to the terminal tokens of the input string, using \(k\) tokens of lookahead to decide which production rule to apply.

Because it predicts which rule to use before seeing the entire right-hand side of a production, LL parsing is often called predictive parsing. It is commonly implemented using recursive descent, where each non-terminal in the grammar corresponds to a function in code, or using an explicit stack with a parsing table.

A major limitation of LL parsers is that they cannot handle left-recursive grammars. For example, a rule of the form \(A \to A\alpha \mid \beta\) causes infinite recursion in a top-down parser unless the grammar is first rewritten to eliminate left recursion.

Bottom-Up LR Shift-Reduce Parsing

LR parsing stands for Left-to-right scan of the input, producing a Rightmost derivation in reverse. An \(LR(k)\) parser starts from the terminal tokens of the input and works upward toward the start symbol by recognizing complete right-hand sides of production rules.

LR parsers operate using a stack and two primary actions:

• Shift: Push the next input token onto the stack.
• Reduce: When the top of the stack matches the right-hand side of a production rule \(A \to \alpha\), pop \(\alpha\) from the stack and push the non-terminal \(A\).

Because an LR parser delays its decision until it has seen all tokens belonging to a production's right-hand side, it can recognize a strictly larger class of deterministic context-free grammars than LL parsers. Notably, LR parsers naturally handle left-recursive rules without requiring grammar transformations.

Key Differences

Direction of Tree Construction

LL parsers build the parse tree from the root down to the leaves, whereas LR parsers build the parse tree from the leaves up to the root.

Grammar Expressiveness

Every \(LL(k)\) grammar is also an \(LR(k)\) grammar, but the reverse is not true. LR parsers—including practical variants like \(SLR(1)\) and \(LALR(1)\)—can parse more complex language constructs without requiring grammar refactoring.

Implementation and Tooling

LL parsers are straightforward to write by hand as recursive descent parsers, making them popular for hand-crafted compilers and interpreters. LR parsers rely on complex state machines and large parsing tables, so they are almost always generated automatically using parser generators such as Yacc or Bison.

Error Detection

Both \(LL(1)\) and \(LR(1)\) parsers detect syntax errors as soon as an invalid token is encountered, without reading further into the input. However, hand-written LL parsers often make it easier to produce clear, context-specific error messages because the parser's call stack directly reflects the expected grammar rules.