LL(1) parsing table construction in Compiler Design - Mini Project: Build & Apply

LL(1) Parsing Table Construction

📖 Scenario: You are learning how to build an LL(1) parsing table for a simple grammar used in compilers. This table helps a parser decide which rule to use when reading input symbols.

🎯 Goal: Create the LL(1) parsing table step-by-step for a given grammar. You will first set up the grammar rules, then define the terminals and non-terminals, next build the table entries, and finally complete the table with all productions.

📋 What You'll Learn

Create a dictionary called grammar with the exact productions given

Create a list called terminals with the exact terminal symbols

Create a dictionary called parsing_table and fill it with correct entries using the grammar

Complete the parsing table by adding all necessary entries for the LL(1) parser

💡 Why This Matters

🌍 Real World

LL(1) parsing tables are used in compiler design to help parsers decide which grammar rule to apply when reading source code.

💼 Career

Understanding LL(1) parsing tables is important for compiler engineers, language designers, and software developers working on interpreters or language tools.

1

Set up the grammar rules

Create a dictionary called grammar with these exact productions:
'E': ['T E\''], 'E\'': ['+ T E\'', 'ε'], 'T': ['F T\''], 'T\'': ['* F T\'', 'ε'], 'F': ['( E )', 'id'].

Compiler Design

# Create the grammar dictionary with the given productions
# Your code here

Hint

Use a Python dictionary with keys as non-terminals and values as lists of productions.

2

Define terminals and non-terminals

Create a list called terminals with these exact terminal symbols: '+', '*', '(', ')', 'id', and '$' (end marker).

Compiler Design

grammar = {
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id']
}
# Create the terminals list with the given symbols
# Your code here

Hint

List all terminal symbols exactly as shown, including the end marker '$'.

3

Build the initial parsing table

Create an empty dictionary called parsing_table. Then add an entry for non-terminal 'E' and terminal '(' with the production 'T E\''.

Compiler Design

grammar = {
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id']
}

terminals = ['+', '*', '(', ')', 'id', '$']
# Create the parsing_table dictionary and add the entry for 'E' and '('
# Your code here

Hint

Use a dictionary with keys as tuples of (non-terminal, terminal) and values as the production string.

4

Complete the LL(1) parsing table

Add these exact entries to parsing_table:
- ('E', 'id'): 'T E\''
- ('E\'', '+'): '+ T E\''
- ('E\'', ')'): 'ε'
- ('E\'', '$'): 'ε'
- ('T', '('): 'F T\''
- ('T', 'id'): 'F T\''
- ('T\'', '+'): 'ε'
- ('T\'', '*'): '* F T\''
- ('T\'', ')'): 'ε'
- ('T\'', '$'): 'ε'
- ('F', '('): '( E )'
- ('F', 'id'): 'id'.

Compiler Design

grammar = {
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id']
}

terminals = ['+', '*', '(', ')', 'id', '$']

parsing_table = {}
parsing_table[('E', '(')] = 'T E\''
# Add all remaining parsing table entries as specified
# Your code here

Hint

Use the same dictionary syntax to add all entries exactly as listed.

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