SLR(1) parsing in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Role of FOLLOW Sets in SLR(1) Parsing

In SLR(1) parsing, FOLLOW sets are crucial for deciding when to reduce. What is the primary purpose of the FOLLOW set in this context?

A To list all terminals that can start strings derived from a non-terminal, guiding shift actions.

B To determine which terminals can appear immediately after a non-terminal in some sentential form, guiding reduce actions.

C To identify all non-terminals reachable from the start symbol, guiding state construction.

D To specify the order in which productions should be applied during parsing.

💡 Hint

Think about when the parser decides to reduce a production based on the next input symbol.

The FOLLOW set contains terminals that can appear immediately after a non-terminal. In SLR(1) parsing, reduce actions are allowed only when the lookahead symbol is in the FOLLOW set of the production's left-hand side non-terminal.

📋 Factual

intermediate

SLR(1) Parsing Table Construction

Which of the following steps is not part of constructing an SLR(1) parsing table?

A Computing the LR(0) items and their closure sets.

B Calculating the FIRST sets for all grammar symbols.

C Using FOLLOW sets to decide reduce actions in the parsing table.

D Building the canonical collection of LR(1) items with lookahead symbols.

💡 Hint

SLR(1) parsing uses LR(0) items, not LR(1) items with lookaheads.

SLR(1) parsing tables are built using LR(0) items and FOLLOW sets. LR(1) items with lookahead symbols are used in more powerful parsing methods like canonical LR(1), not in SLR(1).

🔍 Analysis

advanced

Conflict Detection in SLR(1) Parsing Table

Consider the grammar:
S → Aa | b
A → b
Which type of conflict is most likely to appear in the SLR(1) parsing table for this grammar?

A No conflict; the grammar is SLR(1) compliant.

B Shift-Reduce conflict due to overlapping FOLLOW sets.

C Reduce-Reduce conflict because two productions reduce on the same lookahead.

D Shift-Shift conflict because two shifts are possible on the same input.

💡 Hint

The FOLLOW sets of S ({$}) and A ({a}) are disjoint, preventing reduce-reduce conflicts, and there are no shift-reduce situations.

This grammar has no conflicts in its SLR(1) parsing table. In the state with items S → b• and A → b•, reduce S → b uses lookahead in FOLLOW(S) = {$}, and reduce A → b uses lookahead in FOLLOW(A) = {a}. These are disjoint, and there are no shift actions in that state.

❓ Comparison

advanced

Comparing SLR(1) and LR(1) Parsing Power

Which statement correctly compares SLR(1) and canonical LR(1) parsing methods?

A Both methods use the same lookahead sets, so they have equal parsing power.

B SLR(1) parsing is more powerful because it uses LR(1) items with lookahead symbols.

C SLR(1) parsing uses FOLLOW sets for lookahead, making it less powerful than LR(1) which uses exact lookahead sets per item.

D SLR(1) parsing cannot detect any conflicts, unlike LR(1) which detects all conflicts.

💡 Hint

Consider how lookahead information is computed and used in both methods.

SLR(1) uses FOLLOW sets for all reductions, which can be imprecise and cause conflicts. LR(1) uses specific lookahead sets for each item, making it more powerful and able to parse more grammars without conflicts.

❓ Reasoning

expert

Determining the Number of States in an SLR(1) Automaton

Given the grammar:
E → E + T | T
T → T * F | F
F → ( E ) | id
How many states will the canonical collection of LR(0) items have when constructing the SLR(1) parsing automaton?

A 12 states

B 10 states

C 8 states

D 14 states

💡 Hint

Recall the classic expression grammar and the typical size of its LR(0) automaton.

This classic expression grammar generates 12 LR(0) states in its canonical collection, as it includes states for each position of the dot in all productions plus closure expansions.

Practice

1. What does the 1 in SLR(1) parsing represent?

easy

A. One grammar rule applied

B. One step shift operation

C. One reduction per state

D. One symbol lookahead during parsing

Solution

1. Step 1: Understand the meaning of lookahead in parsing

   Lookahead means the parser looks at upcoming input symbols to decide the next action.

2. Step 2: Identify what the number 1 specifies in SLR(1)

   The number 1 indicates the parser looks ahead by exactly one symbol to make decisions.

3. Final Answer:

   One symbol lookahead during parsing -> Option D

4. Quick Check:

   SLR(1) means 1 symbol lookahead [OK]

Hint: Remember: number in SLR(n) = lookahead symbols [OK]

Common Mistakes:

• Confusing lookahead with number of grammar rules
• Thinking it means one shift or reduction only
• Assuming it refers to parser states

2. Which of the following is a correct component of the SLR(1) parsing table?

easy

A. ACTION and GOTO tables

B. PREDICT and FOLLOW tables

C. SHIFT and REDUCE stacks

D. FIRST and LAST tables

Solution

1. Step 1: Recall the structure of SLR(1) parsing tables

   SLR(1) parsing uses two main tables: ACTION for parser actions and GOTO for state transitions.

2. Step 2: Identify the correct table names

   Only ACTION and GOTO tables are part of the SLR(1) parsing table, others are unrelated or parts of grammar analysis.

3. Final Answer:

   ACTION and GOTO tables -> Option A

4. Quick Check:

   SLR(1) uses ACTION and GOTO tables [OK]

Hint: ACTION table decides moves; GOTO table changes states [OK]

Common Mistakes:

• Mixing parsing tables with grammar sets like FIRST or FOLLOW
• Confusing stacks with tables
• Assuming PREDICT table exists in SLR(1)

3. Given the grammar:

S -> CC
C -> cC | d

What is the correct ACTION for state 2 on input c in SLR(1) parsing?

medium

A. Reduce by C -> d

B. Shift to state 3

C. Accept input

D. Error

Solution

1. Step 1: Identify state 2's items and possible moves

   State 2 likely has an item expecting c to continue parsing C -> cC, so it should shift on c.

2. Step 2: Determine the action for input c

   Since c can start a new C, the parser shifts to state 3 to parse C -> cC.

3. Final Answer:

   Shift to state 3 -> Option B

4. Quick Check:

   Input 'c' leads to shift in state 2 [OK]

Hint: Shift on terminals that start productions [OK]

Common Mistakes:

• Choosing reduce too early without checking lookahead
• Confusing accept with shift
• Assuming error when shift is valid

4. In an SLR(1) parser, a conflict occurs when:
state 4 has both shift and reduce actions on the same input symbol. What is the likely cause?

medium

A. Grammar is not SLR(1) compatible

B. Parser table was built incorrectly

C. Lookahead symbol is missing

D. Input string is invalid

Solution

1. Step 1: Understand shift-reduce conflicts in SLR(1)

   Shift-reduce conflicts happen when the parser cannot decide whether to shift or reduce on the same input symbol.

2. Step 2: Identify the cause of such conflicts

   This usually means the grammar is not suitable for SLR(1) parsing, i.e., it is not SLR(1) compatible.

3. Final Answer:

   Grammar is not SLR(1) compatible -> Option A

4. Quick Check:

   Shift-reduce conflict = grammar not SLR(1) [OK]

Hint: Conflicts mean grammar is not SLR(1) compatible [OK]

Common Mistakes:

• Blaming parser table construction errors
• Thinking input string causes conflicts
• Assuming missing lookahead causes conflict

5. You have the grammar:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

Why might SLR(1) parsing fail for this grammar, and what is a common solution?

hard

A. Grammar is left-factored; remove left recursion

B. Grammar lacks terminals; add more tokens

C. Grammar is ambiguous; use LALR(1) or LR(1) parsing

D. Grammar is too simple; add more productions

Solution

1. Step 1: Recognize the grammar type

   This grammar is classic expression grammar with ambiguity due to operator precedence and associativity.

2. Step 2: Understand SLR(1) limitations

   SLR(1) parsing often fails on ambiguous grammars because it cannot resolve conflicts with only one symbol lookahead.

3. Step 3: Identify common solutions

   More powerful parsers like LALR(1) or LR(1) handle such grammars by using more precise lookahead and states.

4. Final Answer:

   Grammar is ambiguous; use LALR(1) or LR(1) parsing -> Option C

5. Quick Check:

   Ambiguous grammar needs stronger parser than SLR(1) [OK]

Hint: Ambiguous grammar needs LR(1) or LALR(1) [OK]

Common Mistakes:

• Thinking adding tokens fixes ambiguity
• Confusing left recursion removal with ambiguity
• Assuming grammar simplicity causes failure