LL(1) Parser Table Explained: FIRST, FOLLOW and a Complete Worked Example

FIRST and FOLLOW sets are only the setup. In the balanced-parentheses grammar below, the same nullable start symbol recurs inside and after a matched pair, so the table must guide every move through ()()$. The earlier LL(1) Parsing Table Construction: Worked GATE Example is the faster cell-filling drill with a sequence grammar. Balanced parentheses instead force the finished table to decide both recursive expansion and the epsilon moves in a complete acceptance trace.

LL(1) parser: what the two Ls and the 1 mean

The first L means scanning input from left to right, the second means constructing a leftmost derivation, and 1 means using one lookahead token.

An LL(1) parser is predictive: (nonterminal on stack, lookahead token) must select exactly one production. This is predictive top-down parsing in table-driven form. Recursive descent puts similar choices in hand-written functions instead.

Its three working parts are:

• input ending in $;

• a stack starting with S$;

• table M[A, a] for nonterminal A and lookahead a.

The stack top is written on the left throughout. A terminal match consumes input. A lookup replaces a nonterminal with its selected right-hand side. $ against $ accepts.

FIRST and FOLLOW rules that fill an LL(1) table

For A -> alpha, put the production in M[A, t] for every terminal t in FIRST(alpha). If epsilon is in FIRST(alpha), also put the production in M[A, b] for every b in FOLLOW(A). epsilon is never a table column because it is not an input token.

Use this grammar, with start symbol S and terminals {(, )}:

S -> (S)S | epsilon

The production S -> (S)S creates one matched pair. Its first recursive S generates the material inside that pair, while the second generates any balanced sequence after it. The epsilon alternative ends either role. The grammar therefore generates strings such as (), (()) and ()(), but not )( or an unmatched parenthesis.

The FIRST set is:

• FIRST((S)S) = {(} because the right-hand side begins with the terminal (.

• FIRST(epsilon) = {epsilon}. Therefore FIRST(S) = {(, epsilon}.

The FOLLOW set is:

• $ is in FOLLOW(S) because S starts the grammar.

• ) is in FOLLOW(S) because the first S in (S)S is followed by ). The trailing S inherits the left-hand side follow set but adds no new symbol. Thus FOLLOW(S) = {), $}.

For a longer fixed-point computation with several nonterminals, practise First and Follow in Compiler Design: Solved Examples.

LL(1) grammar test: find conflicts before building the parser

The non-epsilon alternative has FIRST((S)S) = {(}. The nullable alternative must use FOLLOW(S) = {), $}. Their intersection is empty, so one lookahead token always distinguishes expansion from disappearance.

Operationally, M[S,(] receives S -> (S)S, while M[S,)] and M[S,$] receive S -> epsilon. No cell receives both productions, so the grammar is LL(1).

FIRST/FIRST conflicts join two non-epsilon alternatives on one lookahead. FIRST/FOLLOW conflicts let a nullable alternative compete with another production on a following token. A collision, not an empty cell, rejects an LL(1) grammar.

For example, if X -> a | epsilon and a is in FOLLOW(X), both productions enter M[X,a]. That multiply defined cell proves the grammar is not LL(1).

LL(1) parsing table construction, cell by cell

From FIRST((S)S) = {(}, place S -> (S)S in M[S,(]. Because the other alternative is nullable, use FOLLOW(S) = {), $} to place S -> epsilon in M[S,)] and M[S,$].

Those are all possible cells because the grammar has one nonterminal and three input columns. The table is complete, and its single row makes the decision visible: expand on (; disappear before ) or $.

LL(1) parser trace for ()()$

The stack top stays on the left. A terminal match consumes input, while an epsilon production removes S without consuming anything.

At each closing parenthesis, M[S,)] selects S -> epsilon so the parser can match ). After the second pair, M[S,$] removes the final trailing S. Only then does $ meet $ and accept. The trace shows that the two FOLLOW-based entries perform different jobs even though they contain the same production.

LL(1) parser table mistakes and how to repair them

1. Creating an epsilon column. epsilon cannot appear in the input. Put S -> epsilon under FOLLOW(S), which gives the ) and $ columns here.

2. Using FIRST(S) for every alternative. Compute FIRST((S)S) and FIRST(epsilon) separately. Each production enters cells from its own right-hand side; the nullable one then uses FOLLOW(S).

3. Pushing a production in the wrong order. With the stack top on the left, replacing S by (S)S must leave ( on top. If your convention puts the top on the right, push the right-hand side in reverse order and keep that convention throughout.

4. Assuming epsilon always causes a conflict. A nullable alternative is safe when its competing FIRST symbols do not overlap the left-hand side FOLLOW set. Inspect the actual table cells rather than rejecting epsilon by itself.

Before table construction, eliminate immediate left recursion such as E -> E + T | T, and left-factor common prefixes such as E -> id | id + E.

How GATE tests LL(1) parser tables

The official GATE 2024 CS Set 2 paper, Q40, archived on the official GATE 2025 IIT Roorkee portal, gives a grammar with epsilon-productions and a partly filled LL(1) table. It asks which productions or blanks complete numbered cells.

Other questions ask you to compute FIRST and FOLLOW, test whether a grammar is LL(1), locate conflicts, complete entries, or trace acceptance. Make one table and one stack trace by hand because set-only work misses the complete procedure.

LL(1) selects productions top down with one lookahead. LR-family parsers use states and ACTION/GOTO tables. SLR vs CLR vs LALR Parsers for GATE: States and Conflicts develops that bottom-up comparison.

LL(1) parser table: the short version and next step

Use this five-step checklist:

1. Remove left recursion and left-factor the grammar if needed.

2. Compute FIRST for each right-hand side.

3. Compute FOLLOW for every nonterminal.

4. Fill the table, allowing only one production per cell.

5. Trace stack and input until $ meets $, or an error occurs.

The balanced-parentheses grammar is LL(1), its table has no collisions, and ()()$ is accepted. For the wider route, explore GATE CS Exam Preparation. For structured Compiler Design coverage within broader preparation, use GATE Guidance by Sanchit Sir.

Now rebuild the table without looking. Then trace (())$ as a self-check: expand on both opening parentheses, use M[S,)] twice before matching the outer closing parenthesis, and finish with M[S,$] before accept.