LL(1) Parsing Table Construction for GATE

An LL(1) table can look like a large grid of arbitrary choices. It is not. Once FIRST and FOLLOW are correct, filling the table is a mechanical exercise, and the final conflict check tells you whether the grammar is LL(1).

The safest exam method is to separate those jobs. Compute the sets, apply the two filling rules, and only then inspect the cells.

Why LL(1) questions can become free marks

LL(1) means that the parser scans the input from left to right, constructs a leftmost derivation, and uses one lookahead symbol. At every step, the non-terminal on top of the stack and the next input symbol select one production from the parsing table.

There is no guessing if each relevant cell contains at most one production. Most wrong answers come from an incorrect FOLLOW set, forgetting the epsilon rule, or deciding that a grammar is LL(1) before building the complete table.

FIRST and FOLLOW prerequisites in 90 seconds

FIRST(X) contains the terminals that can begin a string derived from X. If X can derive the empty string, epsilon also belongs to FIRST(X). FOLLOW(A) contains the terminals that can appear immediately after non-terminal A in some sentential form. The end marker $ belongs to FOLLOW of the start symbol.

That is enough to use the construction here. If the set computation itself is the weak point, revise FIRST and FOLLOW in Compiler Design before attempting the table. The two details that matter most are:

• FIRST of a sequence may need to move past nullable symbols.

• FOLLOW is used for a production only when its right-hand side can derive epsilon.

The LL(1) table-filling rule

For every production A -> alpha, apply these rules:

1. For every terminal a in FIRST(alpha), excluding epsilon, put A -> alpha in M[A, a].

2. If epsilon is in FIRST(alpha), put A -> alpha in M[A, b] for every b in FOLLOW(A). If $ is in FOLLOW(A), this includes M[A, $].

All remaining cells are errors. Do not write epsilon into every empty cell. An epsilon production goes only under the FOLLOW symbols of its left-hand side.

This same rule sits inside the wider distinction between predictive and shift-reduce methods covered in top-down and bottom-up parsing.

Worked LL(1) table with an epsilon production

Use this grammar, with S as the start symbol:

S -> A B
A -> a A | epsilon
B -> b B | c

First compute FIRST:

• FIRST(A) = {a, epsilon} because A can begin with a or disappear.

• FIRST(B) = {b, c}.

• FIRST(S) = FIRST(AB) = {a, b, c}. We include FIRST(B) because A is nullable.

Now compute FOLLOW:

• FOLLOW(S) = {$} because S is the start symbol.

• In S -> AB, B follows A, so FIRST(B) = {b, c} goes into FOLLOW(A). Thus FOLLOW(A) = {b, c}.

• B is at the end of S -> AB, so FOLLOW(S) goes into FOLLOW(B). Thus FOLLOW(B) = {$}.

Fill the cells one production at a time.

1. S -> AB has FIRST(AB) = {a, b, c}, so place it in M[S, a], M[S, b], and M[S, c].

2. A -> aA has FIRST(aA) = {a}, so place it in M[A, a].

3. A -> epsilon is nullable. FOLLOW(A) = {b, c}, so place it in M[A, b] and M[A, c].

4. B -> bB goes in M[B, b].

5. B -> c goes in M[B, c].

The complete table is:

No cell contains two productions, so this grammar is LL(1). As a quick input check, for aac$, the parser repeatedly chooses A -> aA under lookahead a, then chooses A -> epsilon under c, followed by B -> c.

Is this grammar LL(1)? Use the collision test

Consider another grammar:

S -> a A | a B
A -> c
B -> d

FIRST(aA) = {a} and FIRST(aB) = {a}. Both S productions must therefore be placed in M[S, a]. That cell becomes multiply defined:

M[S, a] = {S -> aA, S -> aB}

The parser cannot select a unique production from one lookahead symbol, so the grammar is not LL(1). The exact answer is not merely that the FIRST sets overlap. The decisive evidence is the collision in M[S, a].

An epsilon production can create the other common collision. If epsilon is in FIRST(alpha), FIRST of another alternative for A must not overlap FOLLOW(A), or both alternatives can land in the same table cell.

Two classic grammar fixes

Remove left recursion when a grammar contains a form such as E -> E + T | T. A predictive parser would keep expanding E without consuming input. The standard transformation introduces a helper non-terminal, for example E -> TE' and E' -> +TE' | epsilon.

Apply left factoring when alternatives share a prefix. The failed grammar above can be written as S -> aX, X -> A | B. Factoring postpones the decision until the parser has consumed the common a. It does not guarantee that every grammar becomes LL(1), so rebuild the sets and table after the transformation.

How GATE tests LL(1) construction

Typical questions ask for a particular cell, the number of filled entries, whether a grammar is LL(1), or which transformation makes predictive parsing possible. Watch for indirect left recursion, nullable chains, and a FOLLOW symbol that causes a hidden collision.

When a question refers to the current syllabus or paper instructions, confirm them on the official GATE portal of the organising IIT. For topic placement and preparation routes, use the GATE CS preparation category.

The short version

Compute FIRST and FOLLOW, process every production with the two filling rules, and inspect every cell. One multiply defined cell is enough to reject the grammar. Empty cells are errors, not automatic epsilon entries.

After the method is stable, practise table construction and conflict questions in the GATE Test Series. Build the complete grid on paper each time until the epsilon and FOLLOW step becomes automatic.