In Top-Down Parsing & Recursive Descent we wrote one function per non-terminal, and each function looked at the next token to decide which production to use. That works, but the "which production?" decision is buried inside code. An LL(1) parser pulls that decision out into a table. The parser itself becomes a short, fixed loop with a stack, and all knowledge about the grammar lives in the table.
This is the parsing method GATE asks about most often on the top-down side: build the table from FIRST and FOLLOW, decide whether a grammar is LL(1), and trace a string through the stack. We will do all three, step by step.
An LL(1) parser is a non-recursive, table-driven predictive parser. It reads the input Left to right, produces a Leftmost derivation, and uses 1 token of lookahead to choose each production. A grammar is LL(1) if its predictive parsing table has at most one production in every cell.
What the Name Means
Letter | Meaning |
|---|---|
L (first) | The input is scanned from Left to right, one token at a time. |
L (second) | The parser builds a Leftmost derivation: it always expands the leftmost non-terminal first. |
1 | It looks at 1 token ahead (the lookahead) to decide what to do. LL(k) would look at k tokens. |
"Predictive" means the parser never guesses and never backtracks: with one look at the next token it predicts the only production that can possibly work.
The Model of an LL(1) Parser
Input buffer: id + id * id $
▲
│ lookahead a
┌────────┴─────────┐
Stack │ Predictive │ ──▶ Output: sequence of productions
┌────┐ │ parsing program │ (a leftmost derivation)
│ X │◀─▶│ │
│ .. │ └────────┬─────────┘
│ $ │ │ looks up M[X, a]
└────┘ ▼
Parsing table M (rows = non-terminals, columns = terminals and $)
The stack holds grammar symbols that are still expected in the input. At the start it contains $ (bottom marker) and the start symbol on top. The input ends with $. Then the parser repeats one simple rule, based on the top of stack X and the current token a:
If X = a = $: stop and accept.
If X is a terminal: if X = a, pop X and advance the input (a match); otherwise report an error.
If X is a non-terminal: look at M[X, a]. If it holds a production X → Y1Y2…Yk, pop X and push Yk, …, Y2, Y1 (so that Y1 ends up on top), and output the production. If the cell is blank, report an error.
Why push the right side in reverse? Because the stack is last-in first-out. We want Y1, the leftmost symbol, to be handled first, so it must be pushed last. For X → ε nothing is pushed: X simply disappears.
How to Build the Parsing Table
The table is filled using the FIRST and FOLLOW sets from FIRST & FOLLOW Sets. For every production A → α in the grammar:
For each terminal a in FIRST(α), put A → α in M[A, a].
If ε is in FIRST(α), then for each terminal b in FOLLOW(A), put A → α in M[A, b]. If $ is in FOLLOW(A), put A → α in M[A, $] too.
Every cell left empty is an error entry.
Why does rule 2 use FOLLOW? If A can vanish (derive ε), then when we are about to expand A, the next token might not come from A at all. It could be whatever comes after A in a sentence, which is exactly FOLLOW(A). Seeing such a token is a signal to choose the production that makes A disappear.
Worked Example 1: The Expression Grammar
The usual expression grammar is left-recursive, so it cannot be parsed top-down. After removing left recursion (see Ambiguity, Left Recursion & Left Factoring) we get:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
Step 1: FIRST and FOLLOW
Non-terminal | FIRST | FOLLOW |
|---|---|---|
E | { (, id } | { ), $ } |
E' | { +, ε } | { ), $ } |
T | { (, id } | { +, ), $ } |
T' | { *, ε } | { +, ), $ } |
F | { (, id } | { +, *, ), $ } |
Step 2: Fill the Table, Production by Production
Production | Reasoning | Cells filled |
|---|---|---|
E → T E' | FIRST(T E') = FIRST(T) = { (, id } | M[E, (], M[E, id] |
E' → + T E' | FIRST = { + } | M[E', +] |
E' → ε | FIRST(ε) = { ε }, so use FOLLOW(E') = { ), $ } | M[E', )], M[E', $] |
T → F T' | FIRST(F T') = { (, id } | M[T, (], M[T, id] |
T' → * F T' | FIRST = { * } | M[T', *] |
T' → ε | use FOLLOW(T') = { +, ), $ } | M[T', +], M[T', )], M[T', $] |
F → ( E ) | FIRST = { ( } | M[F, (] |
F → id | FIRST = { id } | M[F, id] |
Step 3: The Finished Table
+ | * | ( | ) | id | $ | |
|---|---|---|---|---|---|---|
E | E → T E' | E → T E' | ||||
E' | E' → + T E' | E' → ε | E' → ε | |||
T | T → F T' | T → F T' | ||||
T' | T' → ε | T' → * F T' | T' → ε | T' → ε | ||
F | F → ( E ) | F → id |
There are 13 filled cells and no cell has two productions, so this grammar is LL(1). The 17 blank cells are error entries.
Parsing a String Step by Step
Let us parse id + id * id. In the Stack column the top is on the right.
Step | Stack | Input | Action |
|---|---|---|---|
1 | $ E | id + id * id $ | output E → T E' |
2 | $ E' T | id + id * id $ | output T → F T' |
3 | $ E' T' F | id + id * id $ | output F → id |
4 | $ E' T' id | id + id * id $ | match id |
5 | $ E' T' | + id * id $ | output T' → ε |
6 | $ E' | + id * id $ | output E' → + T E' |
7 | $ E' T + | + id * id $ | match + |
8 | $ E' T | id * id $ | output T → F T' |
9 | $ E' T' F | id * id $ | output F → id |
10 | $ E' T' id | id * id $ | match id |
11 | $ E' T' | * id $ | output T' → * F T' |
12 | $ E' T' F * | * id $ | match * |
13 | $ E' T' F | id $ | output F → id |
14 | $ E' T' id | id $ | match id |
15 | $ E' T' | $ | output T' → ε |
16 | $ E' | $ | output E' → ε |
17 | $ | $ | accept |
A few things to notice:
The productions in the Action column, read top to bottom, form the leftmost derivation of the string: E ⇒ T E' ⇒ F T' E' ⇒ id T' E' ⇒ id E' ⇒ id + T E' ⇒ … ⇒ id + id * id.
At step 5, T' sees
+. T' cannot produce a+itself, but+is in FOLLOW(T'), so the table says T' → ε. This is rule 2 at work.The grammar's structure gives
*higher precedence than+: theid * idpart is built entirely under the second T.The number of steps is linear in the input length; each token is matched exactly once.
The parse tree that this trace builds (top-down, left to right) is:
E
/ \
T E'
/ \ / | \
F T' + T E'
| | / \ |
id ε F T' ε
| / | \
id * F T'
| |
id ε
When Is a Grammar LL(1)?
The definition is simple: build the table; if any cell has two or more productions (a conflict), the grammar is not LL(1). For exams it is faster to check the equivalent condition directly. A grammar is LL(1) if and only if, for every pair of productions A → α | β with the same left side:
FIRST(α) ∩ FIRST(β) = ∅ (ignoring ε): the two alternatives never start with the same terminal.
At most one of α and β can derive ε.
If β ⇒* ε, then FIRST(α) ∩ FOLLOW(A) = ∅: a token that could start α must not also be a token that can follow A. (And the same with α and β swapped.)
Condition 1 catches FIRST/FIRST conflicts, condition 3 catches FIRST/FOLLOW conflicts.
Quick Rejection Tests
If the grammar is … | then it is … | Why |
|---|---|---|
Left-recursive (A → Aα | β) | Not LL(1) | Every token in FIRST(β) is also in FIRST(Aα): FIRST/FIRST conflict. (If β is ε, the clash shows up as a FIRST/FOLLOW conflict instead.) |
Not left-factored (A → aα | aβ) | Not LL(1) | Both alternatives start with a. |
Ambiguous | Not LL(1) | An LL(1) table gives exactly one choice at each step, so each string has at most one leftmost derivation. Every LL(1) grammar is unambiguous. |
The reverse is not true: removing left recursion and left factoring does not guarantee LL(1), and an unambiguous grammar can still fail. You must still build the table or apply the three conditions.
Worked Example 2: An LL(1) Grammar with ε
S → A B
A → a A | ε
B → b B | c
This generates a*b*c: some a's, some b's, then one c.
Non-terminal | FIRST | FOLLOW |
|---|---|---|
S | { a, b, c } | { $ } |
A | { a, ε } | { b, c } |
B | { b, c } | { $ } |
Check A → a A | ε: FIRST(a A) = { a } and FOLLOW(A) = { b, c } do not overlap, so condition 3 holds. B → b B | c has FIRST sets { b } and { c }, disjoint. The table:
a | b | c | $ | |
|---|---|---|---|---|
S | S → A B | S → A B | S → A B | |
A | A → a A | A → ε | A → ε | |
B | B → b B | B → c |
No conflicts, so the grammar is LL(1). Trace for a b c:
Step | Stack | Input | Action |
|---|---|---|---|
1 | $ S | a b c $ | output S → A B |
2 | $ B A | a b c $ | output A → a A |
3 | $ B A a | a b c $ | match a |
4 | $ B A | b c $ | output A → ε |
5 | $ B | b c $ | output B → b B |
6 | $ B b | b c $ | match b |
7 | $ B | c $ | output B → c |
8 | $ c | c $ | match c |
9 | $ | $ | accept |
Now change one production to B → b B | a. FIRST(B) becomes { a, b }, so FOLLOW(A) = { a, b }. For A → a A | ε, the token a is in FIRST(a A) and in FOLLOW(A): M[A, a] gets both A → a A and A → ε. Not LL(1). Intuitively, on seeing an a the parser cannot tell whether it is "another a for A" or "the final a produced by B" without looking further ahead.
Worked Example 3: Grammars That Are Not LL(1)
The Dangling Else
S → i E t S S' | a
S' → e S | ε
E → b
Here i = if, t = then, e = else. This grammar is already left-factored, but it is ambiguous.
Non-terminal | FIRST | FOLLOW |
|---|---|---|
S | { i, a } | { e, $ } |
S' | { e, ε } | { e, $ } |
E | { b } | { t } |
For S' → ε we look at FOLLOW(S') = { e, $ }, so S' → ε goes into M[S', e]. But S' → e S also goes there:
i | t | a | e | b | $ | |
|---|---|---|---|---|---|---|
S | S → i E t S S' | S → a | ||||
S' | S' → e S ; S' → ε | S' → ε | ||||
E | E → b |
M[S', e] = { S' → e S, S' → ε }: a FIRST/FOLLOW conflict. Real parsers resolve it by always choosing S' → e S, which attaches each else to the nearest unmatched then. That is the rule C, C++ and Java follow.
A Grammar for Balanced a's and b's
S → a S b S | b S a S | ε
FIRST(S) = { a, b, ε } and FOLLOW(S) = { a, b, $ }. Because S → ε goes in every column of FOLLOW(S), it collides with S → aSbS in column a and with S → bSaS in column b:
a | b | $ | |
|---|---|---|---|
S | S → a S b S ; S → ε | S → b S a S ; S → ε | S → ε |
Two conflicting cells, M[S, a] and M[S, b], so it is not LL(1). (This grammar is also ambiguous; for example, abab has two parse trees.)
Error Recovery in an LL(1) Parser
An error is detected in two situations: a terminal on top of the stack does not match the input, or M[X, a] is blank. Stopping at the first error is unfriendly, so parsers use panic-mode recovery:
Mark the blank cells M[A, b] for every b in FOLLOW(A) as synch (synchronizing).
If M[A, a] is blank: skip the input token a and try again.
If M[A, a] is synch: pop A, pretending that A was fully parsed, and continue.
If a terminal on top of the stack does not match: pop it (as if it had been inserted).
Trace for the faulty input id * + id (an operand is missing after *):
Step | Stack | Input | Action |
|---|---|---|---|
1 | $ E | id * + id $ | output E → T E' |
2 | $ E' T | id * + id $ | output T → F T' |
3 | $ E' T' F | id * + id $ | output F → id |
4 | $ E' T' id | id * + id $ | match id |
5 | $ E' T' | * + id $ | output T' → * F T' |
6 | $ E' T' F * | * + id $ | match * |
7 | $ E' T' F | + id $ | error: synch, pop F |
8 | $ E' T' | + id $ | output T' → ε |
9 | $ E' | + id $ | output E' → + T E' |
10 | $ E' T + | + id $ | match + |
11 | $ E' T | id $ | output T → F T' |
12 | $ E' T' F | id $ | output F → id |
13 | $ E' T' id | id $ | match id |
14 | $ E' T' | $ | output T' → ε |
15 | $ E' | $ | output E' → ε |
16 | $ | $ | stop: input consumed, but 1 error was reported |
At step 7 the parser expects an F but sees +. Since + is in FOLLOW(F), it pops F and carries on, as if the missing operand had been there. The parser reports one error and still checks the rest of the input.
Recursive Descent vs Table-Driven LL(1)
Aspect | Recursive descent (predictive) | Table-driven LL(1) |
|---|---|---|
Where the grammar lives | In code: one procedure per non-terminal | In the table M; the driver loop is the same for every grammar |
Stack | Implicit: the call stack | Explicit stack of grammar symbols |
Changing the grammar | Rewrite functions | Regenerate the table (easy to automate) |
Adding semantic actions | Very easy; just write code in the functions | Needs action symbols on the stack |
Recursion depth problems | Possible on deeply nested input | No; uses a heap-allocated stack |
Used in practice by | Hand-written front ends (GCC and Clang C/C++ parsers, many others) | Textbook LL(1) tools; modern LL-based generators such as ANTLR 4 use a more powerful adaptive strategy called ALL(*) |
Both accept exactly the same class of grammars when no backtracking is used: the LL(1) grammars.
How Powerful Is LL(1)?
Every LL(1) grammar is unambiguous.
Every LL(1) grammar is also LR(1), and many LR(1) grammars (for example, left-recursive ones) are not LL(1). So canonical LR(1) parsing, which you will meet a few chapters later, is strictly more powerful than LL(1).
But an LL(1) grammar is not always SLR(1), a simpler bottom-up method covered a few chapters later. For example, S → A a A b | B b B a, A → ε, B → ε is LL(1) (its two alternatives start with a and b), yet an SLR parser cannot decide between reducing A → ε and B → ε because FOLLOW(A) = FOLLOW(B) = { a, b }.
LL(k) with k > 1 can handle more grammars, at the cost of much bigger tables.
Many natural grammars (left-recursive expression grammars, for example) must be rewritten into a less readable form before they are LL(1). That is the main reason bottom-up parsers are popular in parser generators.
Common Mistakes
Putting A → ε under FIRST instead of FOLLOW. An ε-production goes into the columns of FOLLOW(A), never into FIRST.
Forgetting the $ column. If $ is in FOLLOW(A) and A → α with α ⇒* ε, then M[A, $] = A → α.
Applying rule 2 only for A → ε. It applies to any α that can derive ε, e.g. A → B C where both B and C are nullable.
Pushing the right side in the wrong order. Push in reverse so the leftmost symbol is on top.
Thinking "no left recursion and left-factored" means LL(1). FIRST/FOLLOW conflicts can still exist (the dangling else).
Counting the blank cells as conflicts. Blank means error; a conflict is a cell with two or more productions.
GATE & Interview Questions
Q1. How many non-blank entries does the LL(1) table of the expression grammar E → TE', E' → +TE' | ε, T → FT', T' → *FT' | ε, F → (E) | id have?
E: 2, E': 3, T: 2, T': 4, F: 2. Total 13, with no cell holding more than one production.
Q2. Grammar: S → aABb, A → c | ε, B → d | ε. Which cells of the LL(1) table contain A → ε? Is the grammar LL(1)?
A is followed by B, and B can vanish, so FOLLOW(A) = (FIRST(B) − { ε }) ∪ { b } = { d, b }. A → ε goes into M[A, b] and M[A, d]. A → c goes into M[A, c]; B → d into M[B, d]; B → ε into M[B, b]. No cell is multiply defined, so the grammar is LL(1).
Q3. Is S → AaAb | BbBa, A → ε, B → ε LL(1)?
FIRST(AaAb) = { a } and FIRST(BbBa) = { b }, which are disjoint, and neither alternative derives ε. FOLLOW(A) = FOLLOW(B) = { a, b }, and A and B each have a single production, so no conflict. Yes, it is LL(1). (It is a classic example of an LL(1) grammar that is not SLR(1).)
Q4. For S → aSbS | bSaS | ε, which table entries are multiply defined?
FOLLOW(S) = { a, b, $ }, so S → ε appears in M[S, a], M[S, b] and M[S, $]. M[S, a] also has S → aSbS and M[S, b] also has S → bSaS. Those two cells conflict.
Q5. Can an ambiguous grammar be LL(1)? Can a left-recursive one?
No to both. An LL(1) table makes a single deterministic choice, so it yields at most one leftmost derivation per string, which means no ambiguity. A left-recursive alternative A → Aα has every token of FIRST(A) in its FIRST set, clashing with the non-left-recursive alternative.
Q6. What does the "1" in LL(1) refer to, and what would change with LL(2)?
The number of lookahead tokens used to choose a production. With LL(2) the table columns would be pairs of tokens, so it can separate alternatives that share the first token but differ in the second, at the cost of a much larger table.
Q7. In the dangling-else grammar S → iEtSS' | a, S' → eS | ε, E → b, which cell conflicts and how is it resolved?
M[S', e] holds both S' → eS (since e ∈ FIRST(eS)) and S' → ε (since e ∈ FOLLOW(S')). The parser is told to prefer S' → eS, which matches each else with the closest previous then.
Q8. What is the output of an LL(1) parser, and why is it called predictive?
The sequence of productions applied, which is the leftmost derivation of the input (equivalently, a preorder walk of the parse tree). It is predictive because it chooses each production before seeing the rest of the input, using only the next token, and never backtracks.
Summary
An LL(1) parser uses a stack, an input buffer and a table M[non-terminal, terminal]. It matches terminals and expands non-terminals by M[X, a].
Table construction: for A → α, put it in M[A, a] for every a ∈ FIRST(α); if α ⇒* ε, also put it in M[A, b] for every b ∈ FOLLOW(A), including $.
A grammar is LL(1) iff no table cell has more than one production. Equivalently, alternatives of each non-terminal have disjoint FIRST sets, at most one is nullable, and a nullable alternative's FOLLOW does not overlap the other alternatives' FIRST.
Left-recursive, non-left-factored and ambiguous grammars are never LL(1); fixing the first two does not guarantee LL(1).
The parser outputs a leftmost derivation in time linear in the input. Panic-mode recovery uses FOLLOW sets as synch tokens.
LL(1) is simple but limited. The next chapter, Bottom-Up Parsing & Shift-Reduce Parsing, starts the family of parsers that build the tree from the leaves up and handle left-recursive grammars directly.