Análisis Sintáctico Descendente

UNIVERSIDAD DE PANAMÁ[pic 1]

FACULTAD DE INFORMÁTICA, ELECTRÓNICA Y COMUNICACIÓN

ESCUELA DE INFORMÁTICA

Lic. En Ingeniería Informática

Tema:

Análisis Sintáctico Descendente

Integrantes:

Leonardo Ortega 8-928-1522

Andrés Morales 8-899-1618

Víctor Alfonso 8-891-1794

Ricardo Vargas 8-917-1592

Felipe de León 8-897-2382

Alexander Echeverría 8-904-264

Profesor:

Ayax Mendoza

Fecha:

5 de julio de 2018

1. Análisis Sintáctico Descendente (top-down-Parser)

Se conoce como análisis sintáctico descendente a los análisis que parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia, efectuando dichas derivaciones de forma descendente.

Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas.

Según su clasificación pueden ser:

• Con retroceso.
• Con funciones recursivas.
• De gramáticas LL.

Características:

• El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.
• Parte del axioma de la gramática.
• Procesa la entrada de izquierda a derecha.
• Escoge reglas gramaticales.

La forma en que funciona un analizador sintáctico descendente es:

• Los terminales se examinan en el orden en que aparecen en la cadena de tokens.
• Escoge las reglas gramaticales.
• Obtener y desarrollar un árbol de análisis sintáctico o un esquema de sintaxis.

El árbol de derivación se construye desde el nodo raíz hacia los nodos hojas y se leen de izquierda a derecha.

Analizador Sintáctico descendente con Retroceso

Este tipo de analizador consiste en recorrer principalmente un árbol de izquierda a derecha y de arriba abajo. De manera que la sentencia que estamos analizando la comparamos con nodo del árbol que vamos recorriendo.

En el caso de que los terminales que están colocados a la izquierda del primer no terminal no coincidan, entonces terminaremos la búsqueda que se está realizando en ese nodo, o en esa rama del árbol y volvemos hacia atrás para buscar otra rama. En tal caso siempre se va a dirigir al nodo que se encuentra siempre más a la izquierda.

En tal caso, que todos los terminales que se encuentran siempre más a la izquierda de los nodos que estamos visitando, entonces seguiremos bajando el árbol, hasta llegar a la última rama de búsqueda. Si logramos llegar al momento en que todas las sentencias son terminales y no quedan ningún no terminal en un nodo, sabremos que la gramática dada, reconoce la sentencia que se está examinando.

Este método de analizador es básicamente de cómo sería el comportamiento de la maquina al momento de examinar las diferentes sentencias de entrada. Pues tiene como punto de desventajas que necesita demasiada gramática y una cantidad de pasos innecesarios para poder llegar a la gramática final y obtener el resultado de la sentencia, este método es muy ineficiente.

[pic 2][pic 3]

Árbol de reglas gramaticales

Ejemplo de Búsqueda:  Si tenemos la sentencia x-65+z

Utilizamos la serie de reglas que están predeterminada en el ejemplo, pero mayormente utilizamos el árbol de búsqueda. Iniciamos con la regla E y como se trata de una descendente va a comenzar siempre por la izquierda.

...