SLR(1) parsing in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the type of parser SLR(1) is.

Compiler Design

SLR(1) parsing is a type of [1] parser used in compiler design.

Drag options to blanks, or click blank then click option'

Atop-down

Bpredictive

Crecursive descent

Dbottom-up

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing SLR(1) with top-down parsers like LL(1).

Thinking SLR(1) is predictive parsing.

SLR(1) parsing is a bottom-up parsing technique that uses shift-reduce parsing.

2fill in blank

medium

Complete the code to specify the lookahead symbol count in SLR(1) parsing.

Compiler Design

SLR(1) parsing uses [1] lookahead symbol(s) to make parsing decisions.

Drag options to blanks, or click blank then click option'

A0

B2

C1

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming SLR(1) uses multiple lookahead symbols.

Confusing the number with the grammar's length.

The '1' in SLR(1) means it uses one lookahead symbol to decide parsing actions.

3fill in blank

hard

Fix the error in the statement about SLR(1) parsing's use of FOLLOW sets.

Compiler Design

In SLR(1) parsing, the FOLLOW set of a non-terminal is used to decide when to [1] during parsing.

Drag options to blanks, or click blank then click option'

Ashift

Breduce

Caccept

Derror

Attempts:

3 left

💡 Hint

Common Mistakes

Thinking FOLLOW sets decide when to shift.

Confusing FOLLOW sets with FIRST sets.

SLR(1) uses FOLLOW sets to decide when to reduce a production during parsing.

4fill in blank

hard

Fill both blanks to complete the description of the SLR(1) parsing table construction.

Compiler Design

The SLR(1) parsing table has [1] and [2] parts, representing actions and goto transitions respectively.

Drag options to blanks, or click blank then click option'

Aaction

Bshift

Cgoto

Dreduce

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up 'shift' and 'action' as table parts.

Confusing 'reduce' with 'goto'.

The parsing table consists of an action part for terminals and a goto part for non-terminals.

5fill in blank

hard

Fill all three blanks to complete the SLR(1) parsing table entry rule.

Compiler Design

If the parser is in state [1] and the lookahead symbol is [2], then the action is to [3] or reduce based on the table.

Drag options to blanks, or click blank then click option'

Astate number

Bterminal symbol

Cshift

Dnon-terminal symbol

Attempts:

3 left

💡 Hint

Common Mistakes

Using non-terminal symbols as lookahead in the action table.

Confusing shift with reduce in the action.

The parsing table uses the current state and terminal lookahead to decide whether to shift or reduce.

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