Ing. En Sistema
Páginas: 5 (1036 palabras)
Publicado: 13 de noviembre de 2012
ANALISIS SINTACTICO DESCENDENTE.
ASD consiste en ir haciendo derivaciones a la izquierda, partiendo del axioma inicial, hasta obtenerla secuencia de derivaciones que reconoce a la sentencia. En realidad, se trata de aplicar un método de búsqueda en un árbol. El método es búsqueda en profundidad.
El método de ASD intenta encontrar en el árbol universal la sentencia a reconocer en cadamomento.
Análisis con retroceso consiste en recorrer el árbol de izquierda a derecha de arriba debajo de manera que para la sentencia a analizar, la compararemos con cada nodo del árbol que vamos recorriendo y en el caso de que los terminales a la izquierda del primer no terminal no coincida, terminaremos la búsqueda por esa rama y volveremos hacia atrás para buscar otras ramas.
El problemadel análisis con retroceso, aparte de requerir gramáticas no recursivas por la izquierda, es su ineficiencia.
ANAISADORES SINTACTICOS PREDICTIVOS.
Los analizadores sintácticos con retroceso son ineficientes. Pero hay manera de aumentar la ineficiencia. Una de ellas es siendo capaces de saber que regla aplicar del conjunto de reglas aplicables en cada caso.
Los ASDP son mucho menoscostosos computacionalmente hablando que los ASD, por lo que se utilizan a la hora de implementar compiladores.
Para implementar un ASDP, se utiliza un concepto de conjunto de predicciones. Se trata de relacionar cada regla de la gramática con todos los posibles terminales a que se puede acceder aplicando dicha regla.
CONJUTO DE PREDICCION Y GRAMATICAS LL (1),
Como vimos en elepígrafe anterior. Debemos conocer el conjunto de predicción para poder implementar un ASDP. Para entender este conjunto, debemos conocer, para cada regla, los primeros símbolos que pueden generar su parte derecha.
Para obtener un conjunto de predicción, primero debemos obtener dos conjuntos, el conjunto de primeros y el conjunto siguiente.
CONJUNTO PRIMERO.
Definimos la función PRIMcomo una función que se aplica a cada cadenas se símbolos, terminales o no terminales, de una gramática y devuelve un conjunto que contiene terminales de la gramática o la cadena vacía (€).
PRIM (α) : (TUN)* (T U {€})
Donde T es el conjunto de terminales de la gramática, N es el conjunto de no terminales de la gramática y [pic] es un terminal o no terminal. U es el operador unión.PRIM (α) es el conjunto de terminales o € que pueden aparecer iniciando las cadenas que pueden derivar de α.
CONJUNTO DE SIGUIENTE.
Cada no terminal de la gramática tiene un conjunto llamado de siguiente. Este conjunto lo componen tanto los terminales como el símbolo de final de la cadena de entrada ($). Son conjunto de los elementos terminales o $ que pueden aparecer a continuacióndel no terminal en alguna forma sentencial derivada del símbolo inicial.
CONJUNTO DE PRDICCION Y GRAMATICAS LL (1).
Llamaremos PRED a la función que devuelve el conjunto de predicción de una regla. El conjunto de predicción puede contener cualquier terminal de la gramática y el símbolo de fin de cadena ($) pero nunca €.
Cuando el ASDP va a derivar un no terminal, mira el símbolo deentrada y lo busca en los conjuntos de predicción de todas las reglas de ese no terminal y solo cuando este en una solo de ellas es posible hacer una derivación por la izquierda con este método.
CONVERSION A GRAMATICAS LL (1).
La técnica anteriormente utilizada es infalible para asegurar si una gramática es LL (1) o no lo es. Hay métodos que permiten saber sin realizar cálculos singramatica no es directamente LL (1).
Para eliminar la ambigüedad. No hay ningún método establecido. Por lo que lo mejor es replantear la gramática de nuevo.
ELIMINACION DE LA FACTORIZACION POR LA IZQUIERDA.
Si dos o más producciones de un mismo símbolo comienzan igual, no se sabe cual de ella elegir se desconocen los primeros símbolos que son iguales.
ELIMIINACION DE LA...
ASD consiste en ir haciendo derivaciones a la izquierda, partiendo del axioma inicial, hasta obtenerla secuencia de derivaciones que reconoce a la sentencia. En realidad, se trata de aplicar un método de búsqueda en un árbol. El método es búsqueda en profundidad.
El método de ASD intenta encontrar en el árbol universal la sentencia a reconocer en cadamomento.
Análisis con retroceso consiste en recorrer el árbol de izquierda a derecha de arriba debajo de manera que para la sentencia a analizar, la compararemos con cada nodo del árbol que vamos recorriendo y en el caso de que los terminales a la izquierda del primer no terminal no coincida, terminaremos la búsqueda por esa rama y volveremos hacia atrás para buscar otras ramas.
El problemadel análisis con retroceso, aparte de requerir gramáticas no recursivas por la izquierda, es su ineficiencia.
ANAISADORES SINTACTICOS PREDICTIVOS.
Los analizadores sintácticos con retroceso son ineficientes. Pero hay manera de aumentar la ineficiencia. Una de ellas es siendo capaces de saber que regla aplicar del conjunto de reglas aplicables en cada caso.
Los ASDP son mucho menoscostosos computacionalmente hablando que los ASD, por lo que se utilizan a la hora de implementar compiladores.
Para implementar un ASDP, se utiliza un concepto de conjunto de predicciones. Se trata de relacionar cada regla de la gramática con todos los posibles terminales a que se puede acceder aplicando dicha regla.
CONJUTO DE PREDICCION Y GRAMATICAS LL (1),
Como vimos en elepígrafe anterior. Debemos conocer el conjunto de predicción para poder implementar un ASDP. Para entender este conjunto, debemos conocer, para cada regla, los primeros símbolos que pueden generar su parte derecha.
Para obtener un conjunto de predicción, primero debemos obtener dos conjuntos, el conjunto de primeros y el conjunto siguiente.
CONJUNTO PRIMERO.
Definimos la función PRIMcomo una función que se aplica a cada cadenas se símbolos, terminales o no terminales, de una gramática y devuelve un conjunto que contiene terminales de la gramática o la cadena vacía (€).
PRIM (α) : (TUN)* (T U {€})
Donde T es el conjunto de terminales de la gramática, N es el conjunto de no terminales de la gramática y [pic] es un terminal o no terminal. U es el operador unión.PRIM (α) es el conjunto de terminales o € que pueden aparecer iniciando las cadenas que pueden derivar de α.
CONJUNTO DE SIGUIENTE.
Cada no terminal de la gramática tiene un conjunto llamado de siguiente. Este conjunto lo componen tanto los terminales como el símbolo de final de la cadena de entrada ($). Son conjunto de los elementos terminales o $ que pueden aparecer a continuacióndel no terminal en alguna forma sentencial derivada del símbolo inicial.
CONJUNTO DE PRDICCION Y GRAMATICAS LL (1).
Llamaremos PRED a la función que devuelve el conjunto de predicción de una regla. El conjunto de predicción puede contener cualquier terminal de la gramática y el símbolo de fin de cadena ($) pero nunca €.
Cuando el ASDP va a derivar un no terminal, mira el símbolo deentrada y lo busca en los conjuntos de predicción de todas las reglas de ese no terminal y solo cuando este en una solo de ellas es posible hacer una derivación por la izquierda con este método.
CONVERSION A GRAMATICAS LL (1).
La técnica anteriormente utilizada es infalible para asegurar si una gramática es LL (1) o no lo es. Hay métodos que permiten saber sin realizar cálculos singramatica no es directamente LL (1).
Para eliminar la ambigüedad. No hay ningún método establecido. Por lo que lo mejor es replantear la gramática de nuevo.
ELIMINACION DE LA FACTORIZACION POR LA IZQUIERDA.
Si dos o más producciones de un mismo símbolo comienzan igual, no se sabe cual de ella elegir se desconocen los primeros símbolos que son iguales.
ELIMIINACION DE LA...
Leer documento completo
Regístrate para leer el documento completo.