Algoritmo para eliminar 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αjδj/βk jδ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. Para ello, se toma cada grupo de reglas del no terminal A que sea recursiva por izquierda y que se escriban de la forma: AAα1/ Aα2/…/Aαp/….β1/….βq; donde las primeras p alternativas son recursivas y las q restantes no lo son. Se añade a la gramática un nuevo no terminal A’, y todas las reglas A anteriores se sustituyen por las siguientes: Aβj

A βjA’,

1≤ i ≤ q

A’αj

A’αjA’,

1≤ j ≤ p

Algoritmo para vacuidad de lenguaje: Begin VI=φ; N={A/ (At) de P y se cumple que t ∈ VT*}// A deriva en un terminal while N < > VI Do begin VI=N; // copiar N en VI N=VI ∪ {B/ (Bα)de P y α ∈ (VT ∪VI)}// Buscar los lados derechos que derivan en terminales más los símbolos de VI, incluir en N los lados izquierdos de las reglas que cumplan la restricción. end; if S ∈ N then VACIO = “NO”, else VACIO = “SI” end

Algoritmo para supresión de símbolos inútiles:

Parte A – Determinar si X es terminable Begin VI=φ; N={A/ (At) de P y se cumple que t ∈ VT*}// A deriva en un terminal while N < > VI Do begin VI=N; // copiar N en VI N=VI ∪ {B/ (Bα)de P y α ∈ (VT ∪VI)}// Buscar los lados derechos que derivan en terminales más los símbolos de VI, incluir en N los lados izquierdos de las reglas que cumplan la restricción. end; V’N=N; End Parte B – Determinar si X es accesible Begin VI= {S} N= VI ∪ {X/ (SαXβ) de P} // todo en lo que deriva S, pero que esté en el conjunto restringido. while N < > VI Do begin VI=N; // copiar N en VI N=VI ∪ { Y/ (SαYβ) de P y A está en VI}// Buscar los lados derechos que derivan en terminales más los símbolos de VI, incluir en N los lados izquierdos de las reglas que cumplan la restricción. end;

Eliminar reglas unitarias:

Eliminación de reglas borradoras: Begin

VI= φ; N={A/ (Aλ) de P}// A es anulable while N < > VI Do begin VI=N; // copiar N en VI N=VI ∪ {B/ Bα y todos los símbolos de α son anulables} end; V’N=N;

End Se forma un conjunto de reglas P’, de la siguiente manera: Si A X1X2…Xn es una producción de P, entonces agregar la producción A α0 α1…αn a P’, donde: a) Si Xi no es anulable, entonces αi = Xi b) Si Xi es anulable, entonces αi = Xi ó αi = λ c) No añadir la regla Aλ, que ocurriría si todos los αi son λ. Para eliminar las reglas unitarias, primero se deben eliminar las reglas borradoras y los símbolos inútiles, y luego aplicar el siguiente algoritmo: Begin

VI= φ; N=A while N < > VI Do begin VI=N; N=VI ∪ {C/ (BC) en P y B está en VI} end; NA=N;

End Se determinan los conjuntos NA para cada A∈VN tal que AB. El conjunto P’ se construye como sigue:Si AB y Bα (y no es regla unitaria), poner Aα en P’.