Eliminación de producciones unitarias[editar]
Dada una gramática independiente del contexto es una tupla , donde:
: Conjunto de símbolos no terminales .
: Conjunto de símbolos terminales (o alfabeto de la gramática).
: Símbolo de arranque (Start) o axioma de la gramática .
: Conjunto de reglas de producción.
.
Una producción se dice que es unitaria si tiene la forma . Las producciones unitarias hacen a la gramática innecesariamente compleja ya que simplemente renombran un símbolo no terminal. Este algoritmo elimina las producciones unitarias de una gramática G basándose en la construcción del conjunto H definido como:
H = {(A, B) V V A B}
H = ;
forall (Producción de la forma ) do
H = H {(A, B)};
end
while (H cambie) do
forall (par de parejas de la forma (A, B)(B, C)) do)
if ((A, C) H) then
H = H {(A, C)};
end
end
end
*Eliminar todas las producciones unitarias;
forall (Producción B ) do
forall (pareja (A, B) H) do
Añadir a la gramática una producción A
end
end
Veamos un ejemplo de aplicación del algoritmo. Consideremos para ello la gramática:
El primer bucle del algoritmo calcula el conjunto inicial
= {(SA), (AB), (BC), (CD)}
El bucle while calcula el conjunto de pares:
H = {(SA), (AB), (BC), (CD), (SB), (AC), (BD), (SC), (SD), (AD)}
Al eliminar las producciones unitarias, la gramática resulta:
Añadiendo las producciones:
La gramática finalmente resulta:
Referencias[editar]