Compiladores

3 Normalizacion de gramaticas

53

Cap tulo 3 Normalizacion de gramaticas
3.1 Introduccion
La de nicion de las gramaticas incontextuales, tal como se ha formulado en el cap tulo precedente,ofrece a la vez unas ventajas y unos inconvenientes que conviene considerar. La de nicion dada no impone ninguna restriccion sobre la forma que han de tener las producciones de las gramaticas. Cualquiercadena sobre el alfabeto V , donde y V son, respectivamente, los alfabetos de terminales y variables, puede gurar en el lado derecho de una produccion. La ventaja principal de esta formulacion es suadaptabilidad, pues facilita la tarea de encontrar una gramatica que genere un lenguaje dado sin otras condiciones que las impuestas por el problema considerado. Gracias a ello, es posible construir,en muchos casos, gramaticas que expresan de manera clara y directa las caracter sticas del lenguaje que generan. Pero junto a estas ventajas, la falta de restricciones en las gramaticas originanumerosos problemas en su utilizacion. As , por ejemplo, la admision de producciones unarias en las gramaticas (es decir, producciones de la forma X ! Y , donde X e Y son variables), admision que, por otraparte, es muy util a la hora de construir una gramatica, puede originar derivaciones c clicas, de la forma X ) ) X , que causan problemas con los algoritmos que han de procesar las gramaticas. Una reexion similar merecen las producciones nulas o -producciones (producciones de la forma X ! ). Decimos que una gramatica esta en una forma normalizada cuando sus variables y producciones estan sujetas anormas adicionales sin que estos requerimientos limiten la familia de los lenguajes generados. A lo largo de este cap tulo, veremos diferentes formas de normalizar las gramaticas y, en cada caso,explicaremos los objetivos que se persiguen con la normalizacion considerada. Veremos, primero, un ejemplo que ilustra lo que estamos diciendo.

plantear entre las que generan este lenguaje es S !...