Eliminacion Recursividad Izquierda

Tipos de recursividad

Directa. Una gram¨¢tica G es recursiva si tiene alguna Directa. Una gram¨¢tica G es recursiva si tiene alguna regla de producci¨®n que sea recursiva por la izquierda regla de producci¨®n que sea recursiva por la izquierda

A := A¦Á

 Indirecta. Si, a partir de una forma sentencial que Indirecta. Si, a partir de una forma sentencial que empieza por un no terminal se puede derivar una nueva empieza por un no terminal se puede derivar una nueva forma no sentencial donde reaparece al principio el forma no sentencial donde reaparece al principio el no Terminal.

A¦Á =>* A¦Â¦Á

Directa:

	A := A¦Á | ¦Â 		A := ¦ÂA¡¯
				A¡¯ := ¦ÁA¡¯
				A¡¯ := ¦Å

Indirecta:

Ordenar no terminales: A1, A2, ¡­ An

For i := 1 To n Do For j := 1 To i ¨C 1 Do

Sustituir cada Ai := Aj ¦Â por Ai := ¦Á1 ¦Â | ¦Á2 ¦Â | ¦Ák ¦Â

donde Aj := ¦Á1 | ¦Á2 | ¡­ | ¦Ák producciones actuales de Aj

Eliminar la recursividad directa de Ai