Subtopic 2 of 4
4.2Left recursion and left factoring
Left recursion (A → A α | β) makes a top-down parser loop forever; rewrite as A → β A′, A′ → α A′ | ε. Left factoring (A → αβ | αγ) delays the choice: A → α A′, A′ → β | γ.
Load example
Original
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
After removing left recursion
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id
Load example
Original
S -> i E t S | i E t S e S | a
E -> b
After left factoring
S -> i E t S S' | a
S' -> ε | e S
E -> b
Previous year questions: Top-down Parsing (LL(1)) (5)
PYQs are grouped by topic, so this is the full set for Top-down Parsing (LL(1)); try the ones that match this subtopic. Open all 5 on the topic page.