LL(1) parsing table construction in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding FIRST sets in LL(1) parsing

Given the grammar rule A → aB | ε, what is the FIRST(A) set?

A {ε}

B {a}

C {B, a}

D {a, ε}

💡 Hint

Recall that FIRST set includes terminals that begin strings derived from the non-terminal, including ε if it can produce empty.

The rule A → aB | ε means A can start with terminal 'a' or be empty. So FIRST(A) = {a, ε}.

📋 Factual

intermediate

FOLLOW set determination for LL(1) parsing

For the grammar with start symbol S and rule S → AB, if FOLLOW(S) = { $ }, and FIRST(B) = {b, ε}, what is FOLLOW(A)?

A {b, $}

B {b}

C {$}

D {a, b}

💡 Hint

FOLLOW(A) includes FIRST(B) except ε, and if B can be ε, then FOLLOW(S) is also included.

Since B can be ε, FOLLOW(A) includes FIRST(B) without ε plus FOLLOW(S). So FOLLOW(A) = {b, $}.

🔍 Analysis

advanced

LL(1) parsing table ε-production placement

Consider the grammar rules:
E → TE'
E' → +TE' | ε
T → int
Assuming FOLLOW(E') = {$}, which input symbol has the ε-production in the LL(1) parsing table for E'?

A +

B int

C $

D *

💡 Hint

The ε-production is placed in the table for symbols in the FOLLOW set of the non-terminal.

FIRST(E' → +TE') = {+}, so table[E', +] = E' → +TE'.
FIRST(E' → ε) includes ε, so table[E', $] = E' → ε (since $ ∈ FOLLOW(E')).
No conflict because {+} ∩ {$} = ∅.

❓ Comparison

advanced

Comparing LL(1) and non-LL(1) grammars

Which of the following grammars is NOT LL(1) due to ambiguity in the parsing table?

1. S → aSb | ε
2. S → Aa | Ab
3. S → aA | bA
4. S → aS | a

A Grammar 2

B Grammar 1

C Grammar 3

D Grammar 4

💡 Hint

Look for productions with common prefixes causing FIRST set overlaps.

Grammar 2 has productions S → Aa and S → Ab starting with the same non-terminal 'A', causing FIRST sets overlap and ambiguity in the parsing table, so it is not LL(1).

❓ Reasoning

expert

Constructing LL(1) parsing table entries

Given the grammar:
S → AB
A → a | ε
B → b
and FIRST and FOLLOW sets:
FIRST(A) = {a, ε}
FIRST(B) = {b}
FOLLOW(A) = {b}
FOLLOW(S) = {$}

Which entries should be added to the LL(1) parsing table for non-terminal A?

A A, b → A → a; A, a → A → ε

B A, a → A → a; A, b → A → ε

C A, a → A → ε; A, b → A → a

D A, a → A → a; A, $ → A → ε

💡 Hint

Use the rule: For each production A → α, add to table[A, t] for each t in FIRST(α). If ε in FIRST(α), add to table[A, t] for each t in FOLLOW(A).

For A → a, FIRST(a) = {a}, so table[A, a] = A → a.
For A → ε, ε in FIRST(A), so add table[A, t] for t in FOLLOW(A) = {b}, so table[A, b] = A → ε.

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