LL(1) parsing table construction in Compiler Design - Time & Space Complexity

Time Complexity: LL(1) parsing table construction

O(N x T)

Understanding Time Complexity

We want to understand how the time to build an LL(1) parsing table changes as the grammar size grows.

Specifically, how does the work increase when we add more grammar rules or symbols?

Scenario Under Consideration

Analyze the time complexity of the following pseudocode for LL(1) parsing table construction.

for each nonterminal N:
  for each terminal t in FIRST(N):
    add production to table[N, t]
  if EPSILON in FIRST(N):
    for each terminal b in FOLLOW(N):
      add production to table[N, b]

This code builds the LL(1) parsing table by filling entries based on FIRST and FOLLOW sets.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: Iterating over all nonterminals and terminals in FIRST and FOLLOW sets.
• How many times: For each nonterminal, we loop over terminals in its FIRST set, and possibly over terminals in its FOLLOW set.

How Execution Grows With Input

The work depends on the number of nonterminals and the size of their FIRST and FOLLOW sets.

Input Size (n = number of nonterminals)	Approx. Operations
10	About 10 x (average FIRST + FOLLOW set size) operations
100	About 100 x (average FIRST + FOLLOW set size) operations
1000	About 1000 x (average FIRST + FOLLOW set size) operations

Pattern observation: The operations grow roughly in direct proportion to the number of nonterminals and the size of their FIRST and FOLLOW sets.

Final Time Complexity

Time Complexity: O(N x T)

This means the time to build the table grows linearly with the number of nonterminals (N) and the number of terminals (T) involved in FIRST and FOLLOW sets.

Common Mistake

[X] Wrong: "The parsing table construction is constant time because it just fills a table once."

[OK] Correct: The table size and the number of entries depend on grammar size, so more rules and symbols mean more work to fill the table.

Interview Connect

Understanding how parsing table construction scales helps you explain compiler design clearly and shows you can analyze algorithm costs in real systems.

Self-Check

"What if the grammar has many epsilon-productions? How would that affect the time complexity of building the LL(1) parsing table?"

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