LL(1) Parsing: Working Mechanism and Parsing Table Construction for a Given Grammar

An LL(1) parser is a deterministic parser that builds a leftmost derivation using a single lookahead symbol. Its core idea is: at each step, look at the current input token (lookahead) and the top stack nonterminal, then consult the predictive parsing table to choose the unique production to apply.

At a high level, predictive parsing works like this:

1. Maintain a stack holding grammar symbols to be matched/expanded.
2. Repeatedly compare the stack top with the current input symbol.
3. If the stack top is a terminal, match it (advance input).
4. If the stack top is a nonterminal, consult the parsing table entry for (nonterminal, lookahead) to pick the production and replace the nonterminal on the stack with the production’s RHS (pushed in reverse order).

Below is the standard control flow expressed as a state-style diagram.

Key definitions you’ll use

• FIRST set: determines which terminals can start derivations.
• FOLLOW set: determines what can legally follow a nonterminal in a sentential form.
• LL(1) condition: for every nonterminal $A$ and lookahead $a$, at most one production is chosen.

These sets are used to fill the parsing table so that $M[A,a]$ is unique when the grammar is LL(1).

Constructing the LL(1) parsing table for the given grammar

Given:

$$S \rightarrow aA \mid bB$$ $$A \rightarrow a$$ $$B \rightarrow b$$

We will build $M[\text{nonterminal}, \text{lookahead}]$ using FIRST/FOLLOW-based rules.

Step 1: Compute FIRST sets

• From $A \rightarrow a$, we have FIRST(A) = { $a$ }.
• From $B \rightarrow b$, we have FIRST(B) = { $b$ }.
• From $S \rightarrow aA \mid bB$:
  • The first terminal of $aA$ is $a$
  • The first terminal of $bB$ is $b$

So FIRST(S) = { $a, b$ }.

Step 2: Compute FOLLOW sets (needed only to handle ε-productions)

None of the productions produce ε (empty string). Therefore:

• There are no ε-derived contributions to table entries via FOLLOW.
• In standard LL(1) table construction, ε-handling affects entries when a production can derive ε. Since that does not happen here, we can directly place entries using FIRST of the RHS.

We still need the end marker convention for $S$:

• $[FOLLOW(S)]$ includes $[$end-marker]$(commonly$[$]$) because$S$ is the start symbol.
• $A$ and $B$ appear at the end of RHS as $aA$ and $bB$, so their FOLLOW sets would include what can follow those positions—but again, ε is absent, so they will not produce extra table entries beyond those already determined by FIRST.

Table construction rules used (LL(1))

For each production $A \rightarrow \alpha$:

• For every terminal $t \in FIRST(\alpha)$, add $A \rightarrow \alpha$ to $M[A,t]$.
• If $ε \in FIRST(\alpha)$, then for every $t \in FOLLOW(A)$ add $A \rightarrow \alpha$ to $M[A,t]$.

Here, $ε$ is not present anywhere, so we only use the first rule.

LL(1) Parsing Table for the Grammar

Terminals appearing in lookahead are: $\{a,b\}$ (and [\]$ for acceptance).

Fill entries

1. For $S \rightarrow aA$:

   • $FIRST(aA)=\{a\}$, so $M[S,a] = S \rightarrow aA$

2. For $S \rightarrow bB$:

   • $FIRST(bB)=\{b\}$, so $M[S,b] = S \rightarrow bB$

3. For $A \rightarrow a$:

   • $FIRST(a)=\{a\}$, so $M[A,a] = A \rightarrow a$

4. For $B \rightarrow b$:

   • $FIRST(b)=\{b\}$, so $M[B,b] = B \rightarrow b$

All other $M[\cdot,\cdot]$ entries are error/empty.

For clarity, here is the parsing table in a conventional grid form:

“—” means: error (no rule for that (nonterminal, lookahead) pair).