Left factoring in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the common prefix in the grammar productions.

Compiler Design

common_prefix = [1] if production1.startswith([1]) and production2.startswith([1]) else ""

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

A"a"

B"ab"

C"b"

D"abc"

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing the entire string "ab" as the prefix without checking both productions.

Selecting a character not at the start of both productions.

The common prefix between the two productions is "a" because both start with "a".

2fill in blank

medium

Complete the code to extract the suffix after the common prefix in a production.

Compiler Design

suffix = production[len([1]):]

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

A"a"

B"ab"

C"abc"

D"b"

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong prefix length causing incorrect slicing.

Not slicing the string at all.

The suffix is extracted by removing the common prefix "ab" from the start of the production.

3fill in blank

hard

Fix the error in the code that performs left factoring on two productions.

Compiler Design

if production1.startswith(common_prefix) and production2.startswith(common_prefix):
    new_production = common_prefix + [1]

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

A"X"

B"(X)"

C"[X]"

D"{X}"

Attempts:

3 left

💡 Hint

Common Mistakes

Adding parentheses or brackets which are not part of the grammar notation here.

Leaving the blank empty.

The new production after left factoring should concatenate the common prefix with a new non-terminal symbol, here "X".

4fill in blank

hard

Fill both blanks to complete the left factoring transformation for two productions.

Compiler Design

factored_productions = {
    [2]: [common_prefix + [1]],
    [1]: [suffix1, suffix2]
}

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

A"X"

B"Y"

C"S'"

D"common_prefix"

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same symbol for both blanks.

Using the original common prefix as a key instead of a non-terminal.

The common prefix is followed by a new non-terminal "X". The original start symbol is replaced by "S'" to represent the new grammar start.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that performs left factoring on a grammar dictionary.

Compiler Design

left_factored = { [1]: [prod[len([2]):] for prod in prods] for [3], prods in grammar.items() if prods[0].startswith(common_prefix) }

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

Acommon_prefix + "X"

Bcommon_prefix

Cnon_terminal

Dprod

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable names in the comprehension.

Not slicing the productions correctly.

The new key is the common prefix plus a new non-terminal "X". The suffix is sliced by the length of the common prefix. The loop variable for keys is "non_terminal".

Practice

1. What is the main purpose of left factoring in compiler design?

easy

A. To remove common prefixes from grammar rules to simplify parsing

B. To eliminate left recursion from grammar rules

C. To optimize the speed of code execution

D. To convert grammar rules into machine code

Solution

1. Step 1: Understand left factoring concept

   Left factoring is used to remove common prefixes from grammar rules to make parsing decisions easier.

2. Step 2: Differentiate from other grammar techniques

   Unlike eliminating left recursion or code optimization, left factoring focuses on simplifying grammar by factoring out common starts.

3. Final Answer:

   To remove common prefixes from grammar rules to simplify parsing -> Option A

4. Quick Check:

   Left factoring = remove common prefixes [OK]

Hint: Left factoring removes common starts in grammar rules [OK]

Common Mistakes:

• Confusing left factoring with left recursion elimination
• Thinking it optimizes runtime code
• Assuming it generates machine code

2. Which of the following is the correct left factored form of the grammar rule:
A -> a b | a c?

easy

A. A -> b | c

B. A -> (a b) | c

C. A -> a b c

D. A -> a (b | c)

Solution

1. Step 1: Identify common prefix in rules

   Both alternatives start with 'a', so 'a' is the common prefix.

2. Step 2: Factor out the common prefix

   Rewrite as A -> a (b | c) to factor out 'a'.

3. Final Answer:

   A -> a (b | c) -> Option D

4. Quick Check:

   Common prefix 'a' factored out [OK]

Hint: Factor out the common start before alternatives [OK]

Common Mistakes:

• Not factoring out the common prefix 'a'
• Combining alternatives incorrectly
• Removing essential parts of the rule

3. Given the grammar rule:
S -> if E then S else S | if E then S
What is the left factored form?

medium

A. S -> if E then S (else S | ε)

B. S -> if E then S else S | if E then S

C. S -> if (E then S else S | E then S)

D. S -> if E then (S else S | S)

Solution

1. Step 1: Identify common prefix in alternatives

   Both alternatives start with if E then S.

2. Step 2: Factor out the common prefix

   Rewrite as S -> if E then S (else S | ε), where ε means empty (no else).

3. Final Answer:

   S -> if E then S (else S | ε) -> Option A

4. Quick Check:

   Common prefix factored with optional else [OK]

Hint: Factor out full common start, use ε for optional parts [OK]

Common Mistakes:

• Not factoring out the entire common prefix
• Misplacing parentheses
• Ignoring the optional else part

4. Identify the error in the following left factoring attempt:
Original: A -> a b | a c d
Attempted: A -> a (b | c d)

medium

A. Incorrect grouping; 'c d' should be separated

B. Correct left factoring, no error

C. Missing a new rule for 'c d'

D. Should factor out 'a b' instead of 'a'

Solution

1. Step 1: Analyze the original and attempted factoring

   Original rules share common prefix 'a'. Alternatives are 'b' and 'c d'.

2. Step 2: Verify correctness

   The attempt A -> a (b | c d) is correct: it generates a b and a c d. Sequences like 'c d' are valid in alternatives.

3. Final Answer:

   Correct left factoring, no error -> Option B

4. Quick Check:

   Same language generated [OK]

Hint: Check if grouped parts are single tokens or sequences [OK]

Common Mistakes:

• Confusing left factoring with left recursion elimination
• Thinking it optimizes runtime code
• Assuming it generates machine code

5. Given the grammar:
Expr -> Expr + Term | Expr - Term | Term
Apply left factoring to this grammar.

hard

A. Expr -> Term + Term | Term - Term

B. Expr -> (Expr + Term) | (Expr - Term) | Term

C. Expr -> Term Expr'; Expr' -> (+ | -) Term Expr' | ε

D. Expr -> Term ( + Term | - Term )

Solution

1. Step 1: Identify left recursion and common prefix

   The rule is left recursive: Expr -> Expr + Term | Expr - Term | Term.

2. Step 2: Remove left recursion and apply left factoring

   Rewrite as:
   Expr -> Term Expr'
Expr' -> (+ | -) Term Expr' | ε to factor out common prefix and remove recursion.

3. Final Answer:

   Expr -> Term Expr'; Expr' -> (+ | -) Term Expr' | ε -> Option C

4. Quick Check:

   Left recursion removed and common prefix factored [OK]

Hint: Remove left recursion first, then factor common prefixes [OK]

Common Mistakes:

• Not removing left recursion before factoring
• Incorrectly grouping alternatives
• Ignoring the ε (empty) option