LL(1) parser implementation in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the LL(1) Parsing Table Construction

Which of the following best describes the purpose of the LL(1) parsing table in the parsing process?

A It stores the grammar's production rules indexed by non-terminals and lookahead terminals to decide parsing actions.

B It holds the list of all terminals in the grammar without any relation to productions.

C It records the sequence of tokens generated by the lexer before parsing begins.

D It contains semantic actions to be executed after parsing completes.

💡 Hint

Think about how the parser decides which production to use based on the current input symbol.

The LL(1) parsing table maps each non-terminal and lookahead terminal pair to a specific production rule. This guides the parser on which rule to apply next.

📋 Factual

intermediate

First and Follow Sets in LL(1) Parsing

What is the main difference between the First set and the Follow set of a non-terminal in LL(1) parsing?

A First set is used only for terminals; Follow set is used only for non-terminals.

B First set lists all productions of a non-terminal; Follow set lists all tokens in the input.

C First set contains all terminals in the grammar; Follow set contains all non-terminals.

D First set contains terminals that begin strings derived from the non-terminal; Follow set contains terminals that can appear immediately after the non-terminal.

💡 Hint

Consider what symbols can appear at the start of a derivation versus what can appear after a non-terminal.

The First set of a non-terminal includes terminals that can appear at the beginning of strings derived from it. The Follow set includes terminals that can appear immediately to the right of that non-terminal in some sentential form.

🔍 Analysis

advanced

Parsing Table Conflict Detection

Given the following grammar productions:

S → Aa | b
A → a | ε

Which problem will occur when constructing the LL(1) parsing table for this grammar?

A No conflicts will occur; the grammar is LL(1) compatible.

B There will be a conflict in the parsing table for non-terminal A due to ε-production and overlapping First and Follow sets.

C The grammar is ambiguous and cannot be parsed by any parser.

D The parsing table will be empty because no productions apply.

💡 Hint

Check how ε-productions affect the Follow set and table entries.

The ε-production in A means that when A derives empty, the parser must look at Follow(A) to decide. If First(A) and Follow(A) overlap, the parsing table will have multiple entries for the same cell, causing a conflict.

❓ Comparison

advanced

LL(1) vs Recursive Descent Parsing

Which statement correctly compares LL(1) parsing and recursive descent parsing?

A LL(1) parsing uses a parsing table and stack; recursive descent parsing uses mutually recursive functions without backtracking if grammar is LL(1).

B LL(1) parsing always requires backtracking; recursive descent parsing never backtracks.

C Recursive descent parsing cannot handle left recursion; LL(1) parsing can handle any grammar.

D Both LL(1) and recursive descent parsing require the grammar to be ambiguous.

💡 Hint

Think about the implementation style and grammar restrictions of both parsing methods.

LL(1) parsing uses a table-driven approach with a stack, while recursive descent parsing uses functions calling each other. Both require the grammar to be LL(1) compliant to avoid backtracking.

❓ Reasoning

expert

Determining LL(1) Grammar Validity

Consider the grammar:

E → E + T | T
T → int

Why is this grammar not LL(1), and what modification can make it LL(1)?

A It is not LL(1) because 'int' is not a terminal; changing 'int' to a terminal symbol fixes it.

B It is not LL(1) because of ambiguous terminals; replacing '+' with another symbol fixes it.

C It is not LL(1) due to left recursion; removing left recursion by rewriting productions makes it LL(1).

D It is LL(1) as is; no modification needed.

💡 Hint

Check for left recursion and how it affects LL(1) parsing.

The grammar has immediate left recursion in E → E + T, which LL(1) parsers cannot handle. Removing left recursion by rewriting the grammar into right-recursive or iterative form makes it LL(1) compatible.

Practice

1. What does the 1 in LL(1) parser stand for?

easy

A. One stack is used for parsing

B. One left recursion is allowed in the grammar

C. One lookahead token is used to decide parsing steps

D. One grammar rule is applied at a time

Solution

1. Step 1: Understand LL(1) parser basics

   LL(1) parser reads input Left to right (L), produces Leftmost derivation (L), and uses 1 lookahead token.

2. Step 2: Identify what '1' means

   The '1' specifically means the parser looks ahead by one token to decide which grammar rule to apply next.

3. Final Answer:

   One lookahead token is used to decide parsing steps -> Option C

4. Quick Check:

   LL(1) = 1 lookahead token [OK]

Hint: Remember LL(1) means 1 token lookahead [OK]

Common Mistakes:

• Confusing '1' with number of grammar rules
• Thinking '1' means one stack or recursion
• Assuming '1' means one parsing step

2. Which of the following is the correct syntax to represent the parsing table entry for non-terminal A and terminal a in LL(1) parser?

easy

A. parsing_table(a, A) = production_rule

B. parsing_table.a.A = production_rule

C. parsing_table[A, a] = production_rule

D. parsing_table[A][a] = production_rule

Solution

1. Step 1: Understand parsing table structure

   Parsing table is usually a two-dimensional structure indexed by non-terminal and terminal symbols.

2. Step 2: Identify correct syntax

   Using bracket notation with parsing_table[A][a] is the standard way to access or assign entries in a 2D table or dictionary of dictionaries.

3. Final Answer:

   parsing_table[A][a] = production_rule -> Option D

4. Quick Check:

   Use parsing_table[non-terminal][terminal] [OK]

Hint: Use double brackets for 2D table access [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Swapping terminal and non-terminal order
• Using dot notation which is invalid here

3. Given the grammar rules:
S -> a A
A -> b
and the input string ab, what will be the output of an LL(1) parser?

medium

A. Parsing successful

B. Syntax error at 'b'

C. Parsing successful but with warnings

D. Syntax error at 'a'

Solution

1. Step 1: Trace parsing steps with input 'ab'

   Start with stack containing S. Input is 'a b'. Match 'a' with S -> a A, pop S, push A. Next input 'b' matches A -> b.

2. Step 2: Confirm all input consumed and stack empty

   After matching 'b', stack is empty and input is fully consumed, so parsing is successful.

3. Final Answer:

   Parsing successful -> Option A

4. Quick Check:

   Input matches grammar rules fully [OK]

Hint: Match input tokens stepwise with grammar rules [OK]

Common Mistakes:

• Assuming error on matching terminal 'b'
• Confusing input order
• Not popping stack correctly

4. Identify the error in this LL(1) parser snippet:

stack = ['$', 'S']
input = list('ab$')
while stack:
    top = stack.pop()
    current = input[0]
    if top == current:
        input.pop(0)
    else:
        rule = parsing_table[top][current]
        stack.extend(reversed(rule))

medium

A. Stack is popped before checking if top is terminal

B. Input is not consumed correctly

C. Parsing table lookup uses wrong indices

D. Stack is extended without reversing the rule

Solution

1. Step 1: Analyze stack popping logic

   The code pops the stack before checking if the top is a terminal matching the input token, which can cause loss of needed symbol if mismatch occurs.

2. Step 2: Explain correct approach

   Correct approach is to peek at the top of the stack first, then decide to pop if it matches input or replace using parsing table if non-terminal.

3. Final Answer:

   Stack is popped before checking if top is terminal -> Option A

4. Quick Check:

   Pop after checking top symbol type [OK]

Hint: Peek stack top before popping [OK]

Common Mistakes:

• Popping stack too early
• Not reversing rule before pushing
• Incorrect input token consumption

5. You want to implement an LL(1) parser for a grammar with left recursion. What is the best approach to handle this?

hard

A. Use a stack to store left recursive calls

B. Eliminate left recursion from the grammar before building the parser

C. Increase lookahead tokens to LL(2) or more

D. Ignore left recursion and parse as usual

Solution

1. Step 1: Understand LL(1) parser limitations

   LL(1) parsers cannot handle left recursion because it causes infinite recursion or parsing conflicts.

2. Step 2: Apply grammar transformation

   To use LL(1) parsing, left recursion must be removed by rewriting grammar rules into right-recursive or iterative forms.

3. Final Answer:

   Eliminate left recursion from the grammar before building the parser -> Option B

4. Quick Check:

   Remove left recursion for LL(1) compatibility [OK]

Hint: Remove left recursion before LL(1) parsing [OK]

Common Mistakes:

• Trying to parse left recursion directly
• Assuming more lookahead solves left recursion
• Ignoring grammar transformation needs