ALGORITMOS PARA PARCIAL Recursividad a izquierda directa Es recursiva a izquierda si las reglas de producción son de la forma: A  A Algoritmo de supresión de la recursividad a izquierda: 1. Se toman las reglas del no terminal A que sea recursiva por izquierda de la forma: A  A 1 / A 2 / .... / A p / 1 / 2 /.../  q donde las primeras p alternativas son recursivas y las q restantes no lo son. 2. Se añade a la gramática un nuevo no terminal A' y todas las reglas A anteriores se sustituyen por las siguientes: A  i A   iA' 1iq A'  j A'  j A' 1jp Recursividad a izquierda indirecta Es recursiva a izquierda indirectamente si las reglas de producción son de la forma: A  B 1 / ... B  A 2 / … Algoritmo para suprimir la recursividad izquierda indirecta: • Se toma cada grupo de reglas de la forma: A  B 1 / B 2 / .../ B n /1 /.../ p B  A 1 / A 2 /.../A q / 1 / ... /  r •

Se reemplaza A por la parte derecha de sus reglas quedando: B  B i j /  k j / 1 / ... / r para cada i, j = 1, ... ,q con i = 1, ... ,n, y para cada k, j=1, ... ,q con k = 1, ... ,p • Luego se elimina la recursividad a izquierda directa. Factorización a izquierda Si A 1/2 son dos producciones de A y la entrada comienza con una cadena no vacía , no se sabe si expandir A a 1 ó a 2. Sin embargo, se puede retrasar la decisión expandiendo A a A'. Entonces, después de ver la entrada derivada de , se puede expandir A' a 1 ó a 2. Es decir, factorizadas por izquierda las producciones originales se convierten en: A  A' A'  1 / 2