Predictive parsing in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the role of FIRST sets in predictive parsing

What is the primary purpose of the FIRST set in predictive parsing?

A To determine which production to use based on the next input symbol

B To find the follow-up symbols after a non-terminal

C To eliminate left recursion from the grammar

D To compute the length of the input string

💡 Hint

Think about how the parser decides which rule to apply when it sees a symbol.

The FIRST set contains terminals that can appear at the beginning of strings derived from a non-terminal. It helps the parser decide which production to use by looking at the next input symbol.

📋 Factual

intermediate

Identifying the condition for LL(1) grammar

Which condition must a grammar satisfy to be considered LL(1)?

A All productions must have exactly one terminal symbol

B The grammar must be left-recursive and ambiguous

C No two productions for the same non-terminal have intersecting FIRST sets, and if a production can derive epsilon, the FOLLOW set must be disjoint from the FIRST sets of the other productions

D The grammar must have no terminals

💡 Hint

Consider how the parser decides uniquely which production to pick with one lookahead symbol.

LL(1) grammars require that for each non-terminal, the FIRST sets of its productions do not overlap. If the non-terminal can derive epsilon, the FOLLOW set must be disjoint from the FIRST sets of the non-epsilon productions to avoid ambiguity.

🔍 Analysis

advanced

Predictive parsing table construction

Given the grammar:
S → Aa | b
A → c | ε
What entry should be placed in the parsing table cell for non-terminal A and terminal a?

A A → a

B A → c

C Error (no entry)

D A → ε

💡 Hint

Check if A can produce epsilon and if a is in FOLLOW(A).

Since A can produce epsilon and a follows A in S → Aa, the parsing table entry for A, a is A → ε.

❓ Comparison

advanced

Difference between recursive descent and predictive parsing

Which statement correctly distinguishes predictive parsing from general recursive descent parsing?

A Recursive descent parsing always uses a parsing table, predictive parsing does not

B Predictive parsing uses a parsing table and no backtracking, while recursive descent may use backtracking

C Predictive parsing requires backtracking, recursive descent never does

D Both parsing methods are identical in implementation and behavior

💡 Hint

Think about how each parser decides which production to use.

Predictive parsing is a form of recursive descent parsing that uses a parsing table to decide productions without backtracking. General recursive descent parsers may backtrack if the grammar is not LL(1).

❓ Reasoning

expert

Predictive parsing failure scenario

Consider a grammar with the productions:
E → E + T | T
T → int
Why will a predictive parser fail to parse this grammar?

A Because the grammar is left-recursive, causing infinite recursion in predictive parsing

B Because the grammar is ambiguous but not left-recursive

C Because the grammar has no terminals

D Because the grammar uses right recursion which predictive parsers cannot handle

💡 Hint

Consider what happens when the parser tries to expand E.

The grammar is left-recursive since E appears on the left side of its own production. Predictive parsers cannot handle left recursion because it leads to infinite recursion during parsing.

Practice

1. What is the main purpose of predictive parsing in compiler design?

easy

A. To optimize the runtime performance of a program

B. To analyze sentences using a stack and parsing table without backtracking

C. To generate machine code from source code

D. To translate high-level code into assembly language

Solution

1. Step 1: Understand predictive parsing function

   Predictive parsing analyzes sentences by using a stack and a parsing table to decide the next step without guessing or backtracking.

2. Step 2: Differentiate from other compiler tasks

   Generating machine code, optimizing runtime, and translating to assembly are later compiler stages, not parsing.

3. Final Answer:

   To analyze sentences using a stack and parsing table without backtracking -> Option B

4. Quick Check:

   Predictive parsing = stack + table analysis [OK]

Hint: Parsing means analyzing structure, not generating code [OK]

Common Mistakes:

• Confusing parsing with code generation
• Thinking predictive parsing guesses or backtracks
• Mixing parsing with optimization tasks

2. Which of the following is a correct component used in predictive parsing?

easy

A. Parsing table

B. Backtracking stack

C. Hash map for variables

D. Symbolic debugger

Solution

1. Step 1: Identify key components of predictive parsing

   Predictive parsing uses a parsing table and a stack to decide which grammar rule to apply next.

2. Step 2: Eliminate unrelated options

   Backtracking stack is not used because predictive parsing avoids backtracking. Hash maps and debuggers are unrelated to parsing tables.

3. Final Answer:

   Parsing table -> Option A

4. Quick Check:

   Parsing table is essential in predictive parsing [OK]

Hint: Parsing table guides decisions without guessing [OK]

Common Mistakes:

• Assuming backtracking is part of predictive parsing
• Confusing parsing table with data structures for variables
• Mixing debugging tools with parsing components

3. Given the grammar rules:
S -> a A b
A -> c | ε
and the input string acb, what will the predictive parser do at the point it reads c?

medium

A. Throw a syntax error

B. Apply rule A -> ε and skip c

C. Backtrack to try another rule

D. Apply rule A -> c and consume c

Solution

1. Step 1: Check the input and grammar at A

   The input symbol is c. The grammar allows A -> c or A -> ε.

2. Step 2: Use predictive parsing table logic

   Since the next input is c, the parser chooses A -> c to match the input symbol and consume it.

3. Final Answer:

   Apply rule A -> c and consume c -> Option D

4. Quick Check:

   Input matches rule A -> c [OK]

Hint: Match input symbol with rule start, no backtracking [OK]

Common Mistakes:

• Choosing epsilon rule when input symbol matches
• Thinking parser backtracks on mismatch
• Assuming syntax error without checking rules

4. Identify the error in this predictive parsing step:
Grammar: S -> a S b | ε
Input: a a b b
Parser applies S -> ε immediately at the start.

medium

A. Parser should backtrack after epsilon

B. Input string is invalid for the grammar

C. Incorrect application of epsilon rule too early

D. No error, parsing is correct

Solution

1. Step 1: Analyze grammar and input

   The grammar allows S -> a S b or S -> ε. The input starts with a, so epsilon should not be chosen immediately.

2. Step 2: Understand predictive parsing rules

   Predictive parsing uses lookahead to decide rules. Since input is a, it should apply S -> a S b first, not epsilon.

3. Final Answer:

   Incorrect application of epsilon rule too early -> Option C

4. Quick Check:

   Epsilon only if input doesn't match other rules [OK]

Hint: Check input symbol before choosing epsilon rule [OK]

Common Mistakes:

• Applying epsilon rule without checking input
• Assuming input is invalid without parsing
• Expecting backtracking in predictive parsing

5. You have a grammar with rules:
E -> T E'
E' -> + T E' | ε
T -> int
How would you construct the predictive parsing table entry for non-terminal E' and input symbol +?

hard

A. Use rule E' -> + T E' because input is '+'

B. Use rule E' -> ε because '+' is not in T

C. No entry needed because '+' is terminal

D. Use rule E' -> T E' to start parsing

Solution

1. Step 1: Identify first sets for E'

   The first set of E' includes '+' because of the rule E' -> + T E'.

2. Step 2: Match input symbol '+' with rule

   Since input is '+', the parser uses the rule E' -> + T E' in the parsing table for E' and '+'.

3. Final Answer:

   Use rule E' -> + T E' because input is '+' -> Option A

4. Quick Check:

   Input '+' matches E' -> + T E' [OK]

Hint: Match input with first set of non-terminal rules [OK]

Common Mistakes:

• Choosing epsilon rule when input matches '+'
• Confusing terminals with non-terminals in table
• Ignoring first sets in table construction