Left recursion
• A grammar is left-recursive if there exists a nonterminal ! such that there is a derivation ! ⇒# ! $ for some string $
%→%+(|( (→(∗+|+ +→% |,-
We cannot compute FIRST sets for left-recursive grammars.
Left recursion
• A left-recursive grammar can be transformed to eliminate left recursion
!→!+#|# #→#∗(|( (→! |*+
!→ #!$
!$ → +# !$ | ‘ # → (#$
#$→ ∗(#$|’ (→! |*+
Eliminating immediate left recursion
!→!&|# !→ #!′ !% → &!% | (
Eliminating immediate left recursion
!→!+#|# #→#∗(|( (→! |*+
!→ #!$
!$ → +# !$ | ‘ # → (#$
#$→ ∗(#$|’ (→! |*+
Eliminating immediate left recursion
In general…
Indirect left recursion
Eliminating left recursion
Eliminating left recursion