LL(1) parsing table construction in Compiler Design - Step-by-Step Execution

Concept Flow - LL(1) parsing table construction

Start with Grammar

↓

Compute FIRST sets

↓

Compute FOLLOW sets

↓

For each production

↓

For each terminal in FIRST(production)

↓

Add production to table cell

↓

If epsilon in FIRST(production)

↓

Add production to table cells for terminals in FOLLOW(non-terminal)

↓

Repeat for all productions

↓

Parsing table complete

The flow shows starting from grammar, computing FIRST and FOLLOW sets, then filling the LL(1) parsing table by placing productions based on these sets.

Execution Sample

Compiler Design

S -> A B
A -> a | ε
B -> b

Construct LL(1) parsing table for grammar with productions S->AB, A->a or ε, B->b

Analysis Table

Step	Action	Non-terminal	Terminal	Table Entry	Reason
1	Compute FIRST(A)	A		{a, ε}	A produces 'a' or epsilon
2	Compute FIRST(B)	B		{b}	B produces 'b'
3	Compute FIRST(S)	S		{a, b}	S -> A B, FIRST(A) includes 'a' and ε, so FIRST(S) includes FIRST(A) without ε plus FIRST(B)
4	Compute FOLLOW(S)	S		{$}	S is start symbol, so $ in FOLLOW(S)
5	Compute FOLLOW(A)	A		{b}	B follows A in S->AB, so FOLLOW(A) includes FIRST(B) without ε
6	Compute FOLLOW(B)	B		{$}	B is last in production S->AB, so FOLLOW(B) includes FOLLOW(S)
7	Add A -> a to table[A, a]	A	a	A -> a	a in FIRST(A -> a)
8	Add A -> ε to table[A, b]	A	b	A -> ε	ε in FIRST(A), so add to FOLLOW(A) terminals
9	Add B -> b to table[B, b]	B	b	B -> b	b in FIRST(B -> b)
10	Add S -> A B to table[S, a]	S	a	S -> A B	a in FIRST(S)
11	Add S -> A B to table[S, b]	S	b	S -> A B	b in FIRST(S)
12	Parsing table construction complete

💡 All productions processed and table entries filled based on FIRST and FOLLOW sets

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 6	Final
FIRST(A)	{}	{a, ε}	{a, ε}	{a, ε}	{a, ε}	{a, ε}
FIRST(B)	{}	{}	{b}	{b}	{b}	{b}
FIRST(S)	{}	{}	{}	{a, b}	{a, b}	{a, b}
FOLLOW(S)	{}	{}	{}	{$}	{$}	{$}
FOLLOW(A)	{}	{}	{}	{b}	{b}	{b}
FOLLOW(B)	{}	{}	{}	{}	{$}	{$}

Key Insights - 3 Insights

Why do we add the production A -> ε to table[A, b] instead of table[A, a]?

Because ε is in FIRST(A), we add A -> ε to the table cells for terminals in FOLLOW(A). Since 'b' is in FOLLOW(A), we add A -> ε to table[A, b]. Table[A, a] gets A -> a because 'a' is in FIRST(A -> a). See execution_table rows 7 and 8.

How do we decide which terminals to use for adding productions when ε is in FIRST set?

When ε is in FIRST of a production, we add that production to the table cells for all terminals in the FOLLOW set of the non-terminal. This ensures correct parsing when the non-terminal can be empty. See execution_table row 8.

Why does FOLLOW(B) include the end symbol $?

Because B is the last symbol in the production S -> A B, FOLLOW(B) includes FOLLOW(S). Since S is the start symbol, FOLLOW(S) contains $, so FOLLOW(B) also contains $. See execution_table row 6.

Visual Quiz - 3 Questions

Look at the execution table at step 7. What is the table entry for non-terminal A and terminal 'a'?

A A -> a

B A -> ε

C No entry

D S -> A B

💡 Hint

Check execution_table row 7 under Table Entry column

At which step does the FOLLOW set for non-terminal A get computed?

A Step 4

B Step 6

C Step 5

D Step 3

💡 Hint

See execution_table row 5 where FOLLOW(A) is computed

If the production A -> ε did not exist, how would the table entry for table[A, b] change?

A It would have A -> a

B It would remain empty

C It would have S -> A B

D It would have B -> b

💡 Hint

Refer to variable_tracker and execution_table rows 7 and 8 about ε productions and FOLLOW sets

Concept Snapshot

LL(1) Parsing Table Construction:
1. Compute FIRST sets for all grammar symbols.
2. Compute FOLLOW sets for all non-terminals.
3. For each production A -> α:
   - For each terminal 'a' in FIRST(α), add A -> α to table[A, a].
   - If ε in FIRST(α), add A -> α to table[A, b] for each b in FOLLOW(A).
4. Table guides parser decisions based on current input and top of stack.

Full Transcript

This visual execution traces the construction of an LL(1) parsing table. Starting from a grammar with productions S -> A B, A -> a or epsilon, and B -> b, we first compute the FIRST sets for each non-terminal. FIRST(A) includes 'a' and epsilon, FIRST(B) includes 'b', and FIRST(S) includes 'a' and 'b' because S derives A B. Next, we compute FOLLOW sets: FOLLOW(S) includes the end symbol $, FOLLOW(A) includes 'b' because B follows A in S -> A B, and FOLLOW(B) includes $ as B is last in the production. Using these sets, we fill the parsing table. For example, since 'a' is in FIRST(A), we add A -> a to table[A, a]. Because epsilon is in FIRST(A), we add A -> ε to table[A, b] for terminals in FOLLOW(A). Similarly, B -> b is added to table[B, b], and S -> A B is added to table[S, a] and table[S, b]. This step-by-step process ensures the parser can decide which production to use based on the current input symbol and the top of the parsing stack. Key moments include understanding why epsilon productions are added to FOLLOW terminals and how FOLLOW sets propagate. The quiz questions test understanding of table entries and set computations. The snapshot summarizes the construction rules for quick reference.

Practice

1. What is the main purpose of an LL(1) parsing table in compiler design?

easy

A. To decide which production rule to apply based on the current input symbol

B. To store the entire source code for parsing

C. To generate machine code from source code

D. To optimize the grammar by removing left recursion

Solution

1. Step 1: Understand the role of LL(1) parsing table

   The LL(1) parsing table helps the parser decide which production to use by looking at the current input symbol and the top of the parsing stack.

2. Step 2: Eliminate incorrect options

   Options A, B, and C describe unrelated tasks: optimizing the grammar by removing left recursion (A), storing code (B), and generating machine code (C), which are not the parsing table's purpose.

3. Final Answer:

   To decide which production rule to apply based on the current input symbol -> Option A

4. Quick Check:

   Parsing table guides production choice = D [OK]

Hint: Parsing table picks production using current input symbol [OK]

Common Mistakes:

• Confusing parsing table with code storage
• Thinking parsing table generates machine code
• Mixing parsing table with grammar optimization

2. Which of the following is the correct way to represent an entry in an LL(1) parsing table cell?

easy

A. A set of terminals

B. A single production rule

C. A list of all grammar symbols

D. A sequence of input tokens

Solution

1. Step 1: Identify what each cell in LL(1) parsing table holds

   Each cell in the LL(1) parsing table contains exactly one production rule to apply when the parser sees a specific non-terminal and input terminal.

2. Step 2: Exclude incorrect options

   A set of terminals is incorrect because the cell does not hold a set of terminals. A list of all grammar symbols is wrong because it does not hold all grammar symbols. A sequence of input tokens is incorrect because input tokens are not stored in the table cell.

3. Final Answer:

   A single production rule -> Option B

4. Quick Check:

   Table cell = one production rule [OK]

Hint: Each cell holds one production rule only [OK]

Common Mistakes:

• Thinking cell holds multiple terminals or symbols
• Confusing input tokens with table entries
• Assuming cell stores grammar symbols list

3. Given the grammar:
S -> A a
A -> b | ε
and the FIRST and FOLLOW sets:
FIRST(A) = {b, ε}
FOLLOW(A) = {a}
What production will be placed in the parsing table cell for non-terminal A and terminal a?

medium

A. A -> b

B. No entry (empty cell)

C. A -> ε

D. A -> a

Solution

1. Step 1: Use FIRST and FOLLOW sets to fill the table

   Since a is in FOLLOW(A) and ε is in FIRST(A), the production A -> ε is placed in the cell for A and a.

2. Step 2: Confirm no other production applies

   The production A -> b applies only for input b. There is no production A -> a. So the correct entry is A -> ε.

3. Final Answer:

   A -> ε -> Option C

4. Quick Check:

   FOLLOW(A) contains 'a' and FIRST(A) has ε -> use A -> ε [OK]

Hint: Use FOLLOW set when FIRST contains ε [OK]

Common Mistakes:

• Ignoring ε in FIRST set
• Placing wrong production for terminal 'a'
• Confusing FOLLOW and FIRST sets

4. You constructed an LL(1) parsing table but found two different productions in the same cell for non-terminal B and terminal c. What is the most likely cause?

medium

A. The grammar is not LL(1) because it is ambiguous or has left recursion

B. You forgot to compute FOLLOW sets

C. You used the wrong terminals in the table rows

D. The input string is invalid

Solution

1. Step 1: Understand why multiple productions appear in one cell

   Multiple productions in one cell indicate a conflict, meaning the grammar is not LL(1). This usually happens if the grammar is ambiguous or has left recursion.

2. Step 2: Evaluate other options

   You forgot to compute FOLLOW sets is incorrect because missing FOLLOW sets would cause incomplete table, not conflicts. You used the wrong terminals in the table rows is about table construction errors but does not explain conflicts. The input string is invalid is unrelated to table construction.

3. Final Answer:

   The grammar is not LL(1) because it is ambiguous or has left recursion -> Option A

4. Quick Check:

   Multiple entries = grammar not LL(1) [OK]

Hint: Multiple entries in one cell mean grammar is not LL(1) [OK]

Common Mistakes:

• Blaming input string instead of grammar
• Ignoring grammar ambiguity or left recursion
• Assuming FOLLOW sets cause conflicts

5. Consider the grammar:
E -> T E'
E' -> + T E' | ε
T -> int | ( E )
Given FIRST and FOLLOW sets:
FIRST(E') = {+, ε}
FOLLOW(E') = {), $}
Which entries should be placed in the LL(1) parsing table for non-terminal E' and terminal )?

hard

A. E' -> T E'

B. E' -> + T E'

C. No entry (empty cell)

D. E' -> ε

Solution

1. Step 1: Check if terminal ')' is in FIRST(E')

   Since FIRST(E') = {+, ε}, ')' is not in FIRST(E'). But since ε is in FIRST(E'), we look at FOLLOW(E') which contains ')'.

2. Step 2: Use ε-production for terminals in FOLLOW(E')

   Because ')' is in FOLLOW(E') and ε is in FIRST(E'), the production E' -> ε is placed in the cell for E' and ).

3. Final Answer:

   E' -> ε -> Option D

4. Quick Check:

   FOLLOW(E') has ')' and FIRST(E') has ε -> use E' -> ε [OK]

Hint: Use ε-production when terminal is in FOLLOW set [OK]

Common Mistakes:

• Placing wrong production for terminal ')'
• Ignoring ε in FIRST set
• Confusing FOLLOW and FIRST sets