CS代考计算机代写 Left recursion

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