Left recursion elimination in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify if a grammar rule is left recursive.

Compiler Design

if production.startswith([1]):
    print("Left recursion detected")

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

Aepsilon

Bterminal

Cnon_terminal

Ddigit

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing terminal with non-terminal symbols.

The left recursion occurs when the production starts with the same non-terminal symbol on the left side.

2fill in blank

medium

Complete the code to remove immediate left recursion from a grammar rule.

Compiler Design

A -> A [1] | beta
Rewrite as:
A -> beta A'
A' -> [2] A' | epsilon

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

Aalpha

Bbeta

Cepsilon

Dgamma

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up alpha and beta parts.

Immediate left recursion is removed by factoring out the left recursive part 'alpha'.

3fill in blank

hard

Fix the error in the code that eliminates left recursion.

Compiler Design

while productions and productions[0].startswith([1]):
    left_recursive.append(productions.pop(0))

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

Aterminal

Bnon_terminal

Cbeta

Dalpha

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for terminal or beta instead of non-terminal.

The code checks if the production starts with the non-terminal symbol to find left recursion.

4fill in blank

hard

Fill both blanks to correctly rewrite a left recursive grammar rule.

Compiler Design

A -> [1] A'
A' -> [2] A' | epsilon

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

Abeta

Balpha

Cgamma

Ddelta

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping alpha and beta parts.

The non-left-recursive part is 'beta', and the recursive part is 'alpha' used in A'.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that eliminates left recursion.

Compiler Design

new_productions = { [1]: [2] for [3] in productions if not [3].startswith(non_terminal) }

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

Aprod

Bproductions[prod]

Dnon_terminal

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent variable names or wrong filtering condition.

The comprehension iterates over productions using 'prod', maps keys to productions[prod], and filters out left recursive productions starting with the non-terminal.