LL(1) parsing table construction in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of an LL(1) parsing table?

An LL(1) parsing table helps a parser decide which grammar rule to use based on the current input symbol and the top of the parsing stack, enabling efficient top-down parsing.

beginner

What does the '1' in LL(1) stand for?

The '1' means the parser looks ahead by one input symbol to decide which production rule to apply.

intermediate

What are the two main sets used to construct an LL(1) parsing table?

The two main sets are FIRST sets and FOLLOW sets. FIRST sets tell which terminals can appear at the start of a string derived from a symbol, and FOLLOW sets tell which terminals can appear immediately after a non-terminal.

intermediate

How do you fill the LL(1) parsing table for a production A → α when α does not derive ε (empty string)?

For each terminal 'a' in FIRST(α), place the production A → α in the table entry [A, a].

intermediate

What do you do when the production A → α can derive ε (empty string) during LL(1) table construction?

For each terminal 'b' in FOLLOW(A), place the production A → α in the table entry [A, b]. Also, if $ (end of input) is in FOLLOW(A), place the production there too.

What does the FIRST set of a non-terminal represent?

A The set of terminals that can appear immediately after the non-terminal

B The set of terminals that can appear at the start of strings derived from that non-terminal

C The set of all terminals in the grammar

D The set of non-terminals reachable from it

The FIRST set contains terminals that can appear at the beginning of strings derived from the non-terminal.

When constructing an LL(1) parsing table, if a production A → α can produce ε, where do you add this production?

A Only in the entry for the end of input symbol $

B In the table entries for terminals in FIRST(α)

C In the table entries for terminals in FOLLOW(A)

D Nowhere, ε-productions are ignored

If α can produce ε, the production is added for terminals in FOLLOW(A), including the end of input symbol if present.

What does the 'L' in LL(1) parsing stand for?

A Left-to-right scanning of the input

B Leftmost derivation

C Lookahead of one symbol

D Both A and B

LL(1) means scanning input Left-to-right and producing a Leftmost derivation with 1 symbol lookahead.

If two different productions are placed in the same LL(1) table cell, what does this indicate?

A The grammar is ambiguous or not LL(1)

B The parser will backtrack automatically

C The parser will always choose the first production

D The grammar is LL(1) compatible

Multiple productions in one cell mean the grammar is not LL(1) and cannot be parsed by a simple LL(1) parser.

Which of these is NOT a step in constructing an LL(1) parsing table?

A Generate LR(1) items

B Compute FIRST sets

C Eliminate left recursion

D Compute FOLLOW sets

Generating LR(1) items is part of LR parsing, not LL(1) parsing table construction.

Explain the process of constructing an LL(1) parsing table from a given grammar.

Think about how FIRST and FOLLOW sets guide table entries.

Why is it important that an LL(1) parsing table has at most one production per cell?

Consider how the parser uses the table during parsing.

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