LL(1) parsing table construction in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the first step in LL(1) parsing table construction: computing the FIRST set of a grammar symbol.

Compiler Design

def compute_first(symbol):
    if symbol is terminal:
        return {symbol}
    first_set = set()
    for production in productions[symbol]:
        first_set |= compute_first(production[0])
    return first_set

# The key operation to combine sets is [1]

Drag options to blanks, or click blank then click option'

A&=

B-=

C+=

D|=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+=' which is not valid for sets.

Using '&=' which performs intersection, not union.

Using '-=' which removes elements instead of adding.

The operator |= is used to add elements from one set to another in Python, which is essential when combining FIRST sets.

2fill in blank

medium

Complete the code to check if a production can derive epsilon (empty string) during FIRST set computation.

Compiler Design

def can_derive_epsilon(production):
    for symbol in production:
        if epsilon not in compute_first(symbol):
            return [1]
    return True

Drag options to blanks, or click blank then click option'

AFalse

Bepsilon

CNone

DTrue

Attempts:

3 left

💡 Hint

Common Mistakes

Returning True too early.

Returning None which is not a boolean.

Returning epsilon which is a symbol, not a boolean.

If any symbol in the production cannot derive epsilon, the whole production cannot derive epsilon, so the function returns False.

3fill in blank

hard

Fix the error in the code that adds entries to the LL(1) parsing table for a production based on its FIRST set.

Compiler Design

for terminal in first_set:
    if terminal != epsilon:
        parsing_table[non_terminal][[1]] = production

Drag options to blanks, or click blank then click option'

Aterminal

Bnon_terminal

Cproduction

Depsilon

Attempts:

3 left

💡 Hint

Common Mistakes

Using non_terminal as the key which is incorrect.

Using production as the key which is a value, not a key.

Using epsilon which should be excluded.

The key in the parsing table is the terminal symbol from the FIRST set, so terminal must be used as the index.

4fill in blank

hard

Fill both blanks to correctly add entries for epsilon productions in the LL(1) parsing table using FOLLOW sets.

Compiler Design

if epsilon in first_set:
    for terminal in [1][non_terminal]:
        parsing_table[non_terminal][[2]] = production

Drag options to blanks, or click blank then click option'

Afollow_set

Bfirst_set

Cterminal

Dnon_terminal

Attempts:

3 left

💡 Hint

Common Mistakes

Using FIRST set instead of FOLLOW set for epsilon entries.

Using non_terminal as the key instead of terminal.

Confusing the loop variable with the parsing table key.

When a production can derive epsilon, entries are added for all terminals in the FOLLOW set of the non-terminal. The key in the parsing table is the terminal symbol.

5fill in blank

hard

Fill all three blanks to complete the LL(1) parsing table construction code snippet that handles all productions.

Compiler Design

for non_terminal in grammar:
    for production in grammar[non_terminal]:
        first_set = compute_first(production)
        for terminal in first_set:
            if terminal != [1]:
                parsing_table[non_terminal][terminal] = [2]
        if [3] in first_set:
            for terminal in follow_set[non_terminal]:
                parsing_table[non_terminal][terminal] = production

Drag options to blanks, or click blank then click option'

Aepsilon

Bproduction

Dfirst_set

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong symbols for epsilon.

Assigning wrong values in the parsing table.

Not checking for epsilon correctly.

The code skips epsilon when adding entries from the FIRST set, adds the production as the value, and checks for epsilon presence to add entries from the FOLLOW set.

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