top down and predictive parsing notes

Chapter Roadmap: Top-Down and Predictive Parsing

What are FIRST and FOLLOW, and why do they exist?

.def-grid { display: grid; grid-template-columns: 1fr; gap: 16px; margin: 16px 0; } @media (min-width: 500px) { .def-grid { grid-template-columns: 1fr 1fr; } } .def-box { padding: 16px; border-radius: 12px; border: 1px solid var(--color-border); background: color-mix(in srgb, var(--color-muted) 8%, transparent); } .def-box h3 { margin: 0 0 8px 0; font-size: 1rem; font-weight: 600; color: var(--color-primary); } .def-box p { margin: 0; font-size: 0.9rem; line-height: 1.5; } .parser-q { margin: 20px 0; padding: 16px; border-left: 3px solid var(--color-primary); background: color-mix(in srgb, var(--color-primary) 6%, transparent); border-radius: 0 8px 8px 0; font-style: italic; font-size: 0.95rem; line-height: 1.5; } A top-down parser expands non-terminals one at a time. At each step it must pick a production. To pick correctly while reading the input only once, it needs two pieces of information about every non-terminal A : FIRST of A The set of terminals that can appear at the very beginning of a string derived from A . FOLLOW of A The set of terminals that can appear immediately to the right of A in some sentential form. Together they answer the parser's only real question: "Given that I am about to expand A, and the next input token is a, which production of A should I use?" If the grammar is well-behaved (LL(1)), the answer is unique. Computing FIRST and FOLLOW is the first step toward checking that, and toward building the parsing table.

FIRST set — formal definition

.math-block { text-align: center; margin: 20px 0; font-size: 1.1rem; } .corollary { margin-top: 24px; padding: 16px; border-radius: 10px; background: color-mix(in srgb, var(--color-muted) 10%, transparent); border: 1px solid var(--color-border); } .corollary h4 { margin: 0 0 10px 0; font-size: 0.85rem; text-transform: uppercase; letter-spacing: 0.05em; opacity: 0.7; } .corollary ul { margin: 0; padding-left: 20px; } .corollary li { font-size: 0.95rem; line-height: 1.6; margin-bottom: 6px; } For any string of grammar symbols α (terminals and non-terminals mixed), FIRST (α) = {a \in T ∣ α \Rightarrow^{*} a β} where T is the set of terminals and β is any string of grammar symbols. Special case. If α \Rightarrow^{*} ε, then ε \in FIRST (α) . Immediate Corollaries For a single terminal a : FIRST (a) = {a} . For a single non-terminal X : FIRST (X) = X \to γ ⋃ FIRST (γ) . The whole computation is just repeated application of these two facts, plus one rule for strings of length greater than one.

34 more cards in this chapter

Top-Down and Predictive Parsing Notes for GATE CS

Top-Down and Predictive Parsing notes for GATE CS: 37 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Top-Down and Predictive Parsing

Chapter · Top-Down and Predictive Parsing

Three topics, one engine

From "what can start a string" to "which table cell to fill".

FIRST and FOLLOW Set Computation

This topic · moderate weight · 2 PYQs in this course

Build the two foundational sets that make predictive parsing possible. By the end you will compute FIRST and FOLLOW for any CFG by hand.

LL(1) Grammar Conditions and Predictive Parsing

Moderate weight · 2 PYQs in this course

Use FIRST and FOLLOW to decide whether a grammar is LL(1). Master the disjointness condition that removes ambiguity in top-down choices.

LL(1) Parsing Table Construction

Moderate weight · 2 PYQs in this course

Turn the disjointness condition into a concrete table. Fill entries, detect conflicts, and read off parse steps.

By the end of this chapter you will

Compute FIRST and FOLLOW sets for any CFG in under two minutes.
Decide in one glance whether a grammar is LL(1) or not.
Build the full LL(1) parsing table and trace a derivation.

What are FIRST and FOLLOW, and why do they exist?

A top-down parser expands non-terminals one at a time. At each step it must pick a production. To pick correctly while reading the input only once, it needs two pieces of information about every non-terminal $A$ :

FIRST of $A$

The set of terminals that can appear at the very beginning of a string derived from $A$ .

FOLLOW of $A$

The set of terminals that can appear immediately to the right of $A$ in some sentential form.

Together they answer the parser's only real question:

"Given that I am about to expand

A

, and the next input token is

a

, which production of

A

should I use?"

If the grammar is well-behaved (LL(1)), the answer is unique. Computing FIRST and FOLLOW is the first step toward checking that, and toward building the parsing table.

FIRST set — formal definition

For any string of grammar symbols $α$ (terminals and non-terminals mixed),

FIRST (α) = {a \in T ∣ α \Rightarrow^{*} a β}

where $T$ is the set of terminals and $β$ is any string of grammar symbols.

Special case. If $α \Rightarrow^{*} ε$ , then $ε \in FIRST (α)$ .

Immediate Corollaries

For a single terminal $a$ : $FIRST (a) = {a}$ .
For a single non-terminal $X$ : $FIRST (X) = X \to γ ⋃ FIRST (γ)$ .

The whole computation is just repeated application of these two facts, plus one rule for strings of length greater than one.

Computing FIRST of a string — the four rules

To compute $FIRST (X_{1} X_{2} \dots X_{k})$ for a string of grammar symbols, walk left to right:

Step	Action
1	Start with $S \leftarrow FIRST (X_{1})$ .
2	If $ε \in / S$ , stop. Result is $S$ .
3	Else replace $S \leftarrow (S ∖ {ε}) \cup FIRST (X_{2})$ .
4	If $ε \in / FIRST (X_{2})$ , stop. Else continue with $X_{3}$ , and so on.
5	If every $X_{i}$ can derive $ε$ , then $ε$ is in the final set.

In one line. Add

FIRST (X_{1})

. If it contains

ε

, also add

FIRST (X_{2}) ∖ {ε}

; if that also contains

ε

, add

FIRST (X_{3}) ∖ {ε}

; stop at the first non-nullable symbol.

For a non-terminal $X$ with productions $X \to γ_{1} ∣ γ_{2} ∣ \dots ∣ γ_{m}$ :

FIRST (X) = FIRST (γ_{1}) \cup FIRST (γ_{2}) \cup \dots \cup FIRST (γ_{m})