Left factoring in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is left factoring in compiler design?

Left factoring is a grammar transformation technique used to remove common prefixes from alternatives in a production rule to make the grammar suitable for top-down parsing.

beginner

Why is left factoring important in parsing?

Left factoring helps eliminate ambiguity caused by common prefixes in grammar rules, enabling predictive parsers to decide which production to use by looking at the next input symbol.

intermediate

Given the grammar rule: <br> A → αβ | αγ<br> How would left factoring transform this rule?

The rule is transformed to:<br> A → αA'<br> A' → β | γ<br> This removes the common prefix α from the alternatives.

intermediate

What problem does left recursion cause that left factoring helps to avoid?

Left recursion causes infinite recursion in top-down parsers. Left factoring does not remove left recursion but helps by making choices clear when alternatives share prefixes.

advanced

Can left factoring be applied multiple times on the same grammar? Why?

Yes, left factoring can be applied repeatedly until no two alternatives in a production share a common prefix, ensuring the grammar is fully factored for predictive parsing.

What is the main goal of left factoring in grammar rules?

A To add more production rules

B To remove common prefixes from alternatives

C To eliminate left recursion

D To convert grammar to Chomsky Normal Form

Left factoring removes common prefixes so parsers can decide which alternative to use by looking ahead.

Which type of parser benefits most from left factoring?

A LR parsers

B Bottom-up parsers

C Top-down predictive parsers

D Shift-reduce parsers

Top-down predictive parsers need left factoring to handle common prefixes and make parsing decisions.

Given the rule: S → if E then S else S | if E then S, what transformation does left factoring perform?

A S → if E then S S'<br>S' → else S | ε

B S → if E then S else S | if E then S

C S → if E then S else S

D No transformation needed

Left factoring extracts the common prefix 'if E then S' and creates a new rule S' for the alternatives.

Does left factoring remove left recursion from a grammar?

A Only for immediate left recursion

B Yes, always

C Only for indirect left recursion

D No, it only removes common prefixes

Left factoring does not remove left recursion; it only removes common prefixes to help predictive parsing.

What symbol is commonly introduced during left factoring to represent the factored part?

A A prime (A')

B A star (*)

C A plus (+)

D A question mark (?)

A prime (like A') is used to represent the new non-terminal holding the alternatives after factoring.

Explain what left factoring is and why it is used in compiler design.

Think about how parsers decide which rule to apply when alternatives start the same way.

Describe the steps to left factor the grammar rule: A → αβ | αγ | δ.

Focus on extracting the shared beginning part of the alternatives.