FIRST/FOLLOW, LL(1) Parsing Table, and LL(1) Determination for a Given CFG

We are given the CFG:

• $S \rightarrow AB$
• $A \rightarrow aA \mid \epsilon$
• $B \rightarrow bB \mid \epsilon$

We will compute FIRST and FOLLOW sets for every non-terminal, then build the LL(1) parsing table and finally decide whether the grammar is LL(1).

Key conventions:

• Let $\epsilon$ denote the empty string.
• Let end-of-input be the marker \$$, and for the start symbol S$, we have$$ \in \text{FOLLOW}(S)$. (This is the standard setup for FOLLOW-based table construction.)

Footnotes

1. FOLLOW(S) includes end-of-input marker $for start symbol - https://en.wikipedia.org/wiki/LL_parser - Notes the use of$ in parsing table construction for LL(1). ↩

Step 1: Compute FIRST sets

We start from the productions:

• $A \rightarrow aA \mid \epsilon$
• $B \rightarrow bB \mid \epsilon$
• $S \rightarrow AB$

Because $A$ can either start with terminal $a$ (via $aA$) or be empty (via $\epsilon$), we get:

• $\text{FIRST}(A) = \{a, \epsilon\}$

Similarly, for $B$:

• $\text{FIRST}(B) = \{b, \epsilon\}$

Now compute $\text{FIRST}(S)$ from $S \rightarrow AB$ using the standard FIRST-of-concatenation rule:

• Start with $\text{FIRST}(A)$
• If $\epsilon \in \text{FIRST}(A)$, then also include $\text{FIRST}(B)$ (excluding $\epsilon$ unless both can derive $\epsilon$)

Since $\epsilon \in \text{FIRST}(A)$, we include $\text{FIRST}(B)$ as well:

• From $A$ producing $\epsilon$, $S$ can begin with what $B$ begins with: $\{b\}$.
• $S$ can produce $\epsilon$ only if both $A$ and $B$ derive $\epsilon$.

Thus:

• $\text{FIRST}(S) = \{a, b, \epsilon\}$

Step 2: Compute FOLLOW sets

Use the standard FOLLOW rules for CFGs:

• \ \in \text{FOLLOW}(S)$for the start symbol$S$.
• For any production $X \rightarrow \alpha Y \beta$, everything in FIRST($\beta$) except $\epsilon$ is added to FOLLOW($Y$).
• If $\epsilon \in \text{FIRST}(\beta)$ (or $\beta$ can be empty), then FOLLOW($X$) is added to FOLLOW($Y$). (This is the standard propagation rule used in FOLLOW computation.)

Now apply to each production:

From $S \rightarrow AB$

• In $AB$, the non-terminal $A$ is followed by $B$.

  • Add $\text{FIRST}(B) \setminus \{\epsilon\}$ to FOLLOW($A$).
  • $\text{FIRST}(B) = \{b,\epsilon\}$, so $\text{FIRST}(B)\setminus\{\epsilon\} = \{b\}$.
  • Since $\epsilon \in \text{FIRST}(B)$, also add FOLLOW($S$) to FOLLOW($A$).

• For $B$ in $AB$:

  • $B$ is at the end of the production, so everything in FOLLOW($S$) is added to FOLLOW($B$).

Initialize:

• FOLLOW($S$) contains $$$.

So:

• FOLLOW($A$) includes $\{b\}$ and also FOLLOW($S$) which includes \$$ → FOLLOW(A$)=${b,$}$
• FOLLOW($B$) includes FOLLOW($S$) → FOLLOW($B$)= \{\}$

We can present results:

• \text{FOLLOW}(S)=\{\}$
• \text{FOLLOW}(A)=\{b,\}$
• \text{FOLLOW}(B)=\{\}$

Footnotes

1. FOLLOW(S) includes end-of-input marker $for start symbol - https://en.wikipedia.org/wiki/LL_parser - Notes the use of$ in parsing table construction for LL(1). ↩

2. FIRST and FOLLOW sets definitions and FOLLOW propagation rules - https://en.wikipedia.org/wiki/Context-free_grammar - Includes discussion of FIRST/FOLLOW and ε interactions in parsing algorithms. ↩

Step 3: Build the LL(1) parsing table

We use the standard LL(1) table construction: For each production $X \rightarrow \gamma$:

• For each terminal $a \in \text{FIRST}(\gamma)$, add $X \rightarrow \gamma$ to table entry $M[X,a]$.
• If $\epsilon \in \text{FIRST}(\gamma)$, then for each terminal $b \in \text{FOLLOW}(X)$, add $X \rightarrow \gamma$ to $M[X,b]$.2

Non-terminals: $\{S,A,B\}$
Terminals: \{a,b,\}$(we include$$$ as lookahead for table entries)

Productions:

• $S \rightarrow AB$
• $A \rightarrow aA$
• $A \rightarrow \epsilon$
• $B \rightarrow bB$
• $B \rightarrow \epsilon$

Fill table rows

Row S: $S \rightarrow AB$

• $\text{FIRST}(AB)$ is $\text{FIRST}(S) = \{a,b,\epsilon\}$
• So:
  • Add $S \rightarrow AB$ to $M[S,a]$
  • Add $S \rightarrow AB$ to $M[S,b]$
• Because $\epsilon \in \text{FIRST}(AB)$, add $S \rightarrow AB$ to M[S,\]$for every$ $$in FOLLOW($S$).
  • FOLLOW($S$) = {\$$} so only M[S,$]$ gets it.

Row A: productions $A \rightarrow aA$ and $A \rightarrow \epsilon$

• For $A \rightarrow aA$:
  • $\text{FIRST}(aA)=\{a\}$ → $M[A,a] = A \rightarrow aA$
• For $A \rightarrow \epsilon$:
  • Since $\epsilon \in \text{FIRST}(\epsilon)$, add this production to all $M[A,b]$ where $b \in \text{FOLLOW}(A)$.
  • FOLLOW($A$) = \{b,\}$
  • So $M[A,b] = A \rightarrow \epsilon$ and M[A,\] = A \rightarrow \epsilon$

Row B: productions $B \rightarrow bB$ and $B \rightarrow \epsilon$

• For $B \rightarrow bB$:
  • $\text{FIRST}(bB)=\{b\}$ → $M[B,b] = B \rightarrow bB$
• For $B \rightarrow \epsilon$:
  • Add to M[B,\]$since FOLLOW($B) = {$$}
  • So M[B,\] = B \rightarrow \epsilon$

Footnotes

1. LL(1) parsing table construction with FIRST/FOLLOW (standard rule) - https://en.wikipedia.org/wiki/LL_parser - Describes LL parsing table population using FIRST/FOLLOW and ε handling. ↩

2. FIRST and FOLLOW sets definitions and FOLLOW propagation rules - https://en.wikipedia.org/wiki/Context-free_grammar - Includes discussion of FIRST/FOLLOW and ε interactions in parsing algorithms. ↩

To avoid encoding limitations, here is the parsing table explicitly as a grid:

(“—” means no production added; the parser would treat it as an error for that lookahead.)

Step 4: Determine whether the grammar is LL(1)

We check for conflicts in the constructed LL(1) table.

List filled cells:

• $M[S,a]$ has only $S \rightarrow AB$
• $M[S,b]$ has only $S \rightarrow AB$
• M[S,\]$has only$S \rightarrow AB$
• $M[A,a]$ has only $A \rightarrow aA$
• $M[A,b]$ has only $A \rightarrow \epsilon$
• M[A,\]$has only$A \rightarrow \epsilon$
• $M[B,b]$ has only $B \rightarrow bB$
• M[B,\]$has only$B \rightarrow \epsilon$

No cell receives two different productions. Therefore, the grammar is LL(1).