Course contentsShow
← Computer Science
Lesson 1958 of 2,87244. Lexical Analysis and ParsingFree lesson

LL(1) Grammars

Defining LL(1) grammars: grammars parseable top-down with one token lookahead using predictive parsing.

LL(1) Grammars

What you'll learn: You'll understand what makes a grammar LL(1) and why it's the "sweet spot" for efficient top-down parsing.

The Core Idea

An LL(1) grammar is a context-free grammar that can be parsed from Left-to-right, building a Leftmost derivation, with just 1 token of lookahead. In practical terms, at every point during parsing, the parser can decide which production rule to use by examining only the current input token—no backtracking needed.

Think of it like choosing which hallway to walk down in a building: if each door is clearly labeled and you can tell from the sign which way to go without having to try each path and come back, you're in an "LL(1) building."

What Makes a Grammar LL(1)?

A grammar is LL(1) if its predictive parsing table has no conflicts. This happens when:

  1. FIRST sets don't overlap: For any two productions of the same non-terminal (like A → α and A → β), the FIRST sets of α and β must be disjoint. You shouldn't have two rules that could both start with the same token.

  2. FOLLOW handled correctly: If a production can derive the empty string (ε), its FIRST set must not overlap with the FOLLOW set of its left-hand non-terminal.

These conditions ensure that when you look at the next input token, there's exactly one choice for which rule to apply.

Why LL(1) Matters

LL(1) grammars enable predictive parsing—fast, deterministic, single-pass parsing without backtracking. This is why tools like recursive descent parsers work so well for LL(1) grammars: each parsing function knows exactly which production to use just by peeking at the next token.

Key Takeaway: LL(1) grammars are those parseable top-down with one token of lookahead and no ambiguity—they guarantee deterministic, efficient predictive parsing.