ANÁLISIS SINTÁCTICO DESCENDENTE (ASD)

ANÁLISIS SINTÁCTICO DESCENDENTE (ASD)

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.

El analizador debe  realizar  la previsión de la  regla  a  aplicar  sólo  con  ver  el  primer símbolo  que  produce  para  que  el algoritmo tenga una complejidad lineal.

¿Cómo funciona el analizador sintáctico?

La primera acción de un analizador sintáctico es obtener un token de la entrada, llamando al analizador léxico (que trabaja como un subprograma).

El analizador va leyendo tokens del analizador léxico a la vez que va generando la traducción, comprobando que la sintaxis es correcta y comprobando las restricciones semánticas.          

IMPORTANTE: Las tres tareas (traducción, sintaxis, semántica) se realizan de forma simultánea, aunque a veces es necesario acumular varios tokens para realizar alguna comprobación o generar la traducción.

Se llama descendente porque parte del símbolo inicial (la raíz del árbol de derivación) y trata de llegar a la cadena de terminales (las hojas del árbol).

Para que se pueda usar en un compilador, el analizador sintáctico debe tener un coste temporal lineal, O(n).

Trata de, leyendo la cadena de entrada de izquierda a derecha (left-to-right), obtener la derivación válida por la izquierda de la cadena de entrada (leftmost derivation).

En éste analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado.

CARÁCTERISTICAS:

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.

Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:

– ELIMINAR AMBIGUEDAD: Para eliminar la ambigüedad se debe reescribir la gramática.

– ELIMINAR RECURSIVIDAD POR LA IZQUIERDA: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena .

 Es decir por simple observación podemos identificar.

Para eliminar la recursividad por la izquierda se utiliza la siguiente formula.

– Factorizar: Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta.

Ejemplo:

ANÁLISIS SINTÁCTICO DESCENDENTE RECURSIVO

·         Su funcionamiento se basa en un conjunto de funciones recursivas. Cada símbolo no terminal genera una función.

·         En esta función se selecciona la regla de producción a ejecutar en función del valor del siguiente token.  La pila se sustituye implícitamente por la pila de llamadas.

Método descendente en el que se ejecuta un conjunto de métodos recursivos para procesar la entrada. A cada no terminal de la gramática se asocia un método.

La secuencia de métodos llamados durante el procesamiento de la entrada define implícitamente un Teoría Lenguajes 8 árbol de análisis sintáctico.

Adicionalmente se tiene: » Un método de tratamiento de error » Un método de lectura de un símbolo de entrada (léxico).

Cada método de un analizador descendente recursivo realiza dos tareas:

Decide la producción a usar analizando el símbolo de entrada. Si el símbolo de entrada pertenece a First(N) entonces se usa la producción con lado derecho N.

Si hay un conflicto entre dos lados derechos entonces en esta gramática no se puede usar Teoría Lenguajes 11 el método descendente recursivo.

Usa una producción imitando el lado derecho:

»Un no terminal resulta en la llamada al método asociado

»Un terminal coincidente al símbolo de entrada hace que se lea el siguiente componente léxico.

GRAMÁTICAS

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.

Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL las cuales son:

·         ELIMINAR AMBIGUEDAD: Para eliminar la ambigüedad se debe reescribir la gramática.

·         ELIMINAR RECURSIVIDAD POR LA IZQUIERDA: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena. Es decir por simple observación podemos identificar..

Factorizar: Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta.

Funcionamiento

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: t1 t2 t3 t4 t5

·         Escoger reglas gramaticales.

·         Obtener el árbol de análisis sintáctico o error

El árbol de derivación se construye:

·         Desde la raíz

·         De izquierda a derecha

Clasificación

·         Analizador sintáctico descendente con retroceso.

·         Analizador sintáctico descendente con recursión.

·         Analizador sintáctico descendente LL.

Análisis sintáctico descendente con retroceso

El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.

·         Se usa el retroceso para resolver la incertidumbre.

·         Sencillo de implementar.

·         Muy eficiente.

Ejemplo:

Análisis sintáctico descendente con predictivo

El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el algoritmo tenga una complejidad lineal.

Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL.

A partir de gramáticas LL se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.

Conjuntos de Predicción

·         Son conjuntos de símbolos terminales

·         Ayudan a predecir qué regla se debe aplicar para el no terminal que hay que derivar.

·         Se construyen a partir de los símbolos de las partes derechas de las producciones de la gramática.

·         El analizador consulta el siguiente símbolo en la entrada.

·         Si pertenece al conjunto de predicción de una regla aplica esa regla, si no da error.

Analizador sintáctico descendente LL.

Características de la condición LL.

·         La secuencia de tokens se analiza de izquierda a derecha.

·         Siempre deriva el no terminal que aparezca más a la izquierda.

·         Sólo es necesario ver un token de la secuencia de entrada para averiguar que regla de producción seguir.

ANÁLISIS SINTÁCTICO

Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico.

En la práctica, el analizador sintáctico también hace:

• Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico).

• Chequeo de tipos ( del analizador semántico).

• Generar código intermedio.

• Generar errores cuando se producen.

En definitiva, realiza casi todas las operaciones de la compilación. Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis.

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.

El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.

GENERADORES DE ANALIZADORES SINTÁCTICO DESCENDENTES

Principales
Generadores de analizadores sintácticos (parser generators):

Yacc
Bison

Grammatica

Sid

YaYacc

Gold

Coco/R
TP Lex/Yacc
Aflex/Ayacc
AntLR
JavaCC
SableCC
AnaGram
LISA
CUP
Spirit
ParseView
Oops
Beaver

Principales generadores:

Yacc

Tipo de analizador:
Ascendente, LALR(1).
Código generado: C, C++.
Características adicionales:

Se puede integrar con Lex dejando a éste el análisis léxico.
La precedencia se puede definir al margen de la gramática, manteniendo ésta más simple.
Conjuntamente con Memphis se puede construir un árbol sintáctico como salida del analizador.

Grammatica

Tipo de analizador:
Descendente, LL(k).
Código generado: C#, Java.
Características adicionales: Soporte para depurar las gramáticas sin necesidad de generar el analizador.

Genera código legible y comentado.

Mensajes de error detallados durante el análisis.

GOLD

Tipo de analizador: Ascendente (LALR(1)).
Código generado:

Multilenguaje (Java, C#, ANSI C, Delphi, Python, VB, VB .NET, VC++, wxWidgets, todos los lenguajes .NET, todos los lenguajes ActiveX)

Características adicionales:

Incluye análisis léxico.

El código fuente está disponible también en numerosos lenguajes.

COCO/R

Tipo de analizador: Descendente, LL(k).

Código generado: C#, Java, Oberon, Pascal, Modula-2, C, C++, Delphi, Unicon.

Características adicionales:

Incluye el analizador léxico.

AntLR

Tipo de analizador: Descendente recursivo, LL(k).
Código generado:
Java, C++, C#.
Características adicionales:
Construcción de ASTs.
Hay abundante documentación en la página, incluyendo una guía en castellano.

HUMILDAD, CIENCIA Y HONESTIDAD.