NOTA: ESTE CÓMIC FUE ELABORADO EN PIXTON EN LÍNEA CONSULTAR EN https://www.pixton.com/mx/from/comic/a3oh50f7   

HUMILDAD, CIENCIA Y HONESTIDAD.

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.

GENERACIÓN DE CÓDIGO

GENERACIÓN DE CÓDIGO

La generación de código es una de las fases mediante el cual un compilador convierte un programa sintácticamente correcto en una serie de instrucciones a ser interpretadas por una máquina. La entrada en esta fase viene representada, típicamente, por un Árbol Sintáctico, un Árbol de Sintaxis Abstracta, o una Representación Intermedia; la máquina destino puede ser un microprocesador o una máquina abstracta tal como una máquina virtual o un lenguaje intermedio, legible por un humano.

Compiladores más sofisticados realizan múltiples traducciones en cadena (pipelining) con el fin de poder construir código para múltiples plataformas y evitar tener que construir todas las capas del compilador.

La generación de código: es usada para construir programas de una manera automática evitando que los programadores tengan que escribir el código a mano. La generación de código puede realizarse en tiempo de ejecución, Tiempo de carga, o Tiempo de compilación.

Significa la traducción de la representación intermedia a lenguaje ensamblador, después de la optimización, y después que se han asignado los registros y la memoria.

PREPARACIÓN PARA LA GENERACIÓN DE CÓDIGO

PREPARACIÓN PARA LA GENERACIÓN DE CÓDIGO

El compilador decide muchas de las cuestiones acerca de donde residirán los valores dos de las cuestiones en la preparación de la generación de código son: la asignación de memoria y la asignación de registros.

Asignación de memoria.- La asignación y el mantenimiento del espacio de memoria para conservar los valores de las variables y expresiones se conoce como asignación de memoria.

Asignación de registros.- Los registros se utilizan para conservar los valores de las variables y expresiones, y aunque rara vez hay suficientes para un programa completo, las arquitecturas más recientes basadas en RISC (Conjunto reducido de instrucciones de Cómputo) poseen más.

HUMILDAD, CIENCIA Y HONESTIDAD.

OPTIMIZACIÓN

OPTIMIZACIÓN

La optimización de código puede realizarse durante la propia generación o como paso adicional, ya sea intercalado entre el análisis semántico y la generación de código (se optimizan las cuádruplas) o situado después de ésta. 
  

En esta fase se intenta mejorar el código, en el sentido de reducir la cantidad de recursos (tiempo y memoria) necesarios.

Clasificación de optimizaciones:

1.                 Dependientes de la máquina.

·                     Asignación de registros (ver capítulo anterior).

·                     Instrucciones especiales ("idioms").

·                     Reordenación del código.

2.                 Independientes de la máquina.

·                     Ejecución en tiempo de compilación.

·                     Eliminación de redundancias.

·                     Cambio de orden.

·                     Reducción de frecuencia de ejecución (invariancias).

·                     Reducción de fuerza.

Optimización y depuración suelen ser incompatibles. Por ejemplo, si se elimina totalmente una instrucción, puede ser imposible poner una parada en ella para depuración.

La finalidad de la optimización de código es producir un código objeto lo más eficiente posible. En algunos casos también se realiza una optimización del código intermedio. Algunas optimizaciones que se pueden realizar son la evaluación de expresiones constantes, el uso de ciertas propiedades de los operadores, tales como la asociativa, conmutativa, y distributiva; así como la reducción de expresiones comunes.

El objetivo es obtener código que se ejecuta más eficientemente según los criterios:

  §  Tiempo de ejecución (optimización temporal).

  §  Espacio de memoria utilizado (optimización espacial).

FUNCIONAMIENTO

Revisa el código generado a varios niveles de abstracción y realiza las optimizaciones aplicables al nivel de abstracción.

  ü  Representaciones de código intermedio de más a menos abstractas.

·         Árbol sintáctico abstracto: optimizar subexpresiones redundantes, reducción de frecuencia, etc.

·         Tuplas o cuádruplas: optimizar en uso de los registros o de las variables temporales.

·         Ensamblador/Código máquina: convertir saltos a saltos cortos, reordenar instrucciones. Representaciones de código para extraer información: grafos.

Cambia la representación intermedia  de modo que la fase final de generación de código producirá código que se ejecutará más rápido u ocupara menos espacio o ambas cosas.

Se pueden identificar cuatro tipos de optimización:

a) Locales.- Se hacen dentro de una sentencia o grupo de sentencias. Hay dos tipos la de propagación constante y la de eliminación de sub-expresiones comunes.

b) De ciclos iterativos.- Se hacen dentro de los ciclos.

c) Globales.- Se efectúan sobre un programa o procedimiento.

d) De mirilla.- Se realizan después de que el código es seleccionado “atisbando” por una pequeña secuencia de código.

HUMILDAD, CIENCIA Y HONESTIDAD.

ANÁLISIS SEMÁNTICO

ANÁLISIS SEMÁNTICO:

Se encarga de que los tipos que intervienen en las expresiones sean compatibles o que los parámetros reales de una función sean coherentes con los parámetros formales.

  ü  Identificar cada tipo de instrucción y sus componentes

  ü  Completar la Tabla de Símbolos

  ü  Realizar distintas comprobaciones y validaciones:

§  Comprobaciones de tipos.

§  Comprobaciones del flujo de control.

§  Comprobaciones de unicidad.

§  Comprobaciones de emparejamiento.

El Analizador Semántico finaliza la fase de Análisis del compilador y comienza la fase de Síntesis, en la cual se comienza a generar el código objeto.

La especificación de la semántica puede realizarse de dos formas:

·        

       *Lenguaje natural

      *Especificación formal: Semántica Operacional, semántica denotacional, semántica Axiomática, Gramáticas con Atributos.

La fase de análisis semántico revisa el programa fuente para tratar de encontrar errores semánticos y reúne la información sobre los tipos para la fase posterior de generación de código. En ella se utiliza la estructura jerárquica determinada por la fase de análisis sintáctico para identificar los operadores y operandos de expresiones y proposiciones.

Un componente importante del análisis semántico es la verificación de tipos. Aquí, el compilador verifica si cada operador tiene operandos permitidos por la especificación del lenguaje fuente. Por ejemplo, las definiciones de muchos lenguajes de programación requieren que el compilador indique un error cada vez que se use un número real como índice de una matriz. Sin embargo, la especi- ficación del lenguaje puede imponer restricciones a los operandos, por ejemplo, cuando un operador aritmético binario se aplica a un número entero y a un número real. Revisa que los arreglos tengan definido el tamaño correcto.

La fase de análisis semántico revisa el programa fuente para tratar de encontrar errores semánticos y reúne la información sobre los tipos para la fase posterior de generación de código. En ella se utiliza la estructura jerárquica determinada por la fase de análisis sintáctico para identificar los operadores y operandos de expresiones y proposiciones.

Un componente importante del análisis semántico es la Verificación de Tipos. Aquí, el compilador verifica si cada operador tiene operandos permitidos por la especificación del lenguaje fuente.

HUMILDAD, CIENCIA Y HONESTIDAD.

ANÁLISIS SINTÁCTICO O GRAMATICAL

ANÁLISIS SINTÁCTICO O GRAMATICAL

¿Qué es el analizador sintáctico?

Un analizador sintáctico (o parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación. 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.

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.

Manejo de errores sintácticos:

Si un compilador tuviera que procesar sólo programas correctos, su diseño e implantación se simplificarían mucho. Pero los programadores a menudo escriben programas incorrectos, y un buen compilador debería ayudar al programador a identificar y localizar errores. Es más, considerar desde el principio el manejo de errores puede simplificar la estructura de un compilador y mejorar su respuesta a los errores.

Los errores en la programación pueden ser de los siguientes tipos:

• Léxicos, producidos al escribir mal un identificador, una palabra clave o un operador.

• Sintácticos, por una expresión aritmética o paréntesis no equilibrados.

• Semánticos, como un operador aplicado a un operando incompatible.

• Lógicos, puede ser una llamada infinitamente recursiva.

El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. 

Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos:

• Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localización.

• Recuperarse del error, para poder seguir examinando la entrada.

• No ralentizar significativamente la compilación.

Un buen compilador debe hacerse siempre teniendo también en mente los errores que se pueden producir; con ello se consigue:

• Simplificar la estructura del compilador.

• Mejorar la respuesta ante los errores.

La gramática que acepta el analizador sintáctico es una gramática de contexto libre:

• Gramática: G (N, T, P, S)

N = No terminales.

T = Terminales.

P = Reglas de Producción.

S = Axioma Inicial.

HUMILDAD, CIENCIA Y HONESTIDAD.