Category: COMPILADORES


Análisis Sintáctico Descendente

Parte de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial.

Es decir en el Análisis ascendente se construye el árbol de análisis sintáctico de la cadena de entrada partiendo desde las hojas hasta la raíz. En las hojas tenemos la cadena a analizar (los símbolos terminales) que se intentan reducir al axioma, que se encontrará en la raíz, si la cadena es correcta sintácticamente.
¿Como construir el árbol?
Se trata de desplazarse en la entrada hasta encontrar una subcadena de símbolos que represente la parte derecha de una producción, en ese momento
sustituimos esa subcadena por el no-terminal de la parte izquierda correspondiente de la producción, la reducimos.
Ejemplo: Supongamos la siguiente gramática que permite generar expresiones aritméticas donde aparece el operador suma y potencia y combinar números e identificadores.
Pueden ser:
 *Con retroceso.
 *LR(1)

Descendentes : Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta
obtener la secuencia de derivaciones que reconoce a la sentencia.
Pueden ser:
 Con retroceso.
 Con recursión.
 LL(1)
Análisis descendente con retroceso.
• Objetivo : El método parte del axioma inicial y aplica todas las posibles reglas al
no terminal más a la izquierda.
• Ejemplo: Utilizaremos la siguiente gramática (No recursiva por la izquierda)
± E Ú T + E
² E Ú T
³ T Ú F * T
´ T Ú F
µ F Ú a
¶ F Ú b
· F Ú (E)
para reconocer la cadena de entrada: (a + b) * a + b
• Ascendentes: Parten de la sentencia de entrada, y van aplicando reglas de producción
hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial.
Pueden ser:
 Con retroceso.
 LR(1)

JAVACC

EL Java Compiler Compiler (JAVACC) es un generador de analizadores sintácticos de código abierto para el lenguaje de programación Java.

JavaCC es similar a Yacc en que genera un parser para una gramática presentada en notación BNF, con la diferencia de que la salida es en código Java.

A diferencia de Yacc, JavaCC genera analizadores descendentes (top-down), lo que lo limita a la clase de gramáticas LL(K) (en particular, la recursión desde izquierda no se puede usar).

El constructor de árboles que lo acompaña, JJTree, construye árboles de abajo hacia arriba (bottom-up). En 1996Sun Microsystems lanzó un generador del programa de análisis llamado Gato.

Los reveladores responsables de Gato creó a su propia compañía llamada Metamata y cambió Gato nombre a JavaCC. Metamata se convirtió en eventual parte de WebGain. Después de que WebGain cerrara sus operaciones, JavaCC fue movido a su hogar actual.     

  CARACTERÍSTICAS PRINCIPALES

JavaCC integra las funciones de análisis léxico y análisis sintáctico en una sola herramienta, obteniendo a la salida código java

–a diferencia de lex/yacc cuya salida es código C

-. Antes que nada veamos un ejemplo sobre el cual se va a ir haciendo un seguimiento de cada uno de los distintos puntos que vayamos comentando.

En él se muestra una gramática reconocedora de una calculadora.

 

 

 

 

La principal diferencia con lex/yacc es que los analizadores sintácticosgenerados por JavaCC son analizadores sintácticos descendentes de tipo LL(k),mientras que los analizadores sintácticos generados por yacc son de tipo ascendenteLALR.

Otra diferencia bastante importante es que las especificaciones léxicas puedenestar incluidas dentro de la especificación de la gramática.

Por ejemplo, podemosescribir algo como esto:

sentenciaIf : {} { “if” “(” expresion() “)” sentencia() }

y automáticamente se ocupa de generar tokens para “if” y para “(“.También es necesario reseñar que el análisis léxico en JavaCC generacombinaciones de autómatas finitos deterministas (AFD) y autómatas finitos nodeterministas(AFND); por contra, lex siempre genera autómatas finitos deterministas.

En definitiva diremos que Java Compiler Compiler (JavaCC) es un potentegenerador de parsers descendentes escritos en lenguaje Java puro.

Es, quizá, uno de losgeneradores de parsers más populares dada su multiplataformidad.

Es por esto que serecomienda su uso para usuarios más afines a los lenguajes de programación orientadosa objetos.Dentro de las características de este metacompilador hay algunas que son aportadas por lex/yacc y otras que no.

Principalmente destacamos:

• Análisis descendente, permitiendo el uso de gramáticas mas generales y la posibilidad de poder utilizar atributos en el árbol sintáctico durante el parsing.

Especificaciones léxicas y gramaticales en un solo archivo. De esta manera la gramática puede ser leída y mantenida más fácilmente gracias al uso de lasexpresiones regulares dentro de la gramática.

• Permite extender especificaciones BNF mediante la utilización de expresionesregulares, tales como (A)*, (A)+.sentenciaIf : {} { “if” “(” expresion() “)” sentencia() }

• Ofrece estados léxicos y la capacidad de agregar acciones léxicas incluyendo unbloque de código java tras el identificador de un token. Además de los conceptosde token, more, skip, cambio de estados, etc. Ello permite trabajar conespecificaciones más claras, a la vez que permite un mejor manejo de mensajesde error y advertencias de JavaCC.

• Genera por defecto un parser LL(1). sin embargo, puede haber porciones de lagramática que no son LL(1).

JavaCC ofrece la posibilidad de resolver lasambigüedades shift-shift localmente al punto del conflicto.

En otras palabras,permite que el parser se vuelva LL(k) sólo en tales puntos; pero se conservaLL(1) en el resto de las producciones para obtener una mejor actuación.

• Permite el uso de Tokens Especiales que son ignorados por el parser; pero estándisponibles para poder ser procesados por el desarrollador.

• Las especificaciones léxicas pueden definir tokens de manera tal que a nivelglobal no se diferencien las mayúsculas de las minúsculas en la especificaciónléxica completa o en una especificación léxica individual

• El análisis del parsing y los pasos de procesamiento de tokens pueden realizarseen profundidad por medio de la utilización de las opciones DEBUG_PARSER,DEBUG_LOOKAHEAD, y DEBUG_TOKEN_MANAGER,.

JavaCC incluye JJTree, un preprocesador para el desarrollo de árboles, concaracterísticas muy poderosas.

De entre los generadores de parsers, JavaCC se halla entre los que tienen mejormanejo de errores.

Los parsers generados por JavaCC son capaces de localizarexactamente la ubicación de los errores, proporcionando informacióndiagnóstica completa.

JavaCC incluye una herramienta llamada JJDoc que convierte los archivos de lagramática en archivos de documentación.

El analizador léxico de JavaCC puede manejar entradas Unicode, y lasespecificaciones léxicas también pueden incluir cualquier caracter Unicode. Estofacilita la descripción de los elementos del lenguaje, tales como losidentificadores Java que permiten ciertos caracteres Unicode que no son ASCII,pero no otros.

• JavaCC es quizá el generador de parsers usado con aplicaciones Java máspopular.

• JavaCC ofrece muchas opciones diferentes para personalizar su comportamientoy el comportamiento de los parsers generados.

Para ampliar la información pulsa aqy

Tutorial util pulsa aqy

Es una herramienta creada principalmente por Terence Parr, que opera sobre lenguajes, proporcionando un marco para construir reconocedores (parsers), intérpretes, compiladores y traductores de lenguajes a partir de las descripciones gramaticales de los mismos (conteniendo acciones semánticas a realizarse en varios lenguajes de programación).

Es un programa está escrito en java, por lo que se necesita alguna máquina virtual de java para poder ejecutarlo.

ANTLR es un generador de analizadores. Es capaz de generar un analizador léxico, sintáctico o semántico en varios lenguajes(java, C++ y C# en su versión 2.7.2) a partir de unos ficheros escritos en un lenguaje propio.Dicho lenguaje es básicamente una serie de reglas EBNF y un conjunto de construcciones auxiliares.

Genera un programa que determina si una sentencia o palabra pertenece a dicho lenguaje (reconocedor), utilizando algoritmos LL(*) de parsing. Si a dicha gramática, se le añaden acciones escritas en un lenguaje de programación, el reconocedor se transforma en un traductor o intérprete.

ANTLR es un generador de lenguajes, a partir de laespecificación de un lenguaje a partir de una gramática podemos:

  • Reconocer si un programa (o palabra) cumple una especificación.
  • Traducir el programa (o palabra) a otro lenguaje.

Es software libre, lo que quiere decir que al descargarlo de la página oficial  (pulsa aqy para descargarlo)obtendremos tanto los ficheros compilados *.class como elcódigo fuente en forma de ficheros *.java.ANTLR

Para entender mas sobre el tema pulsa  aqy

Ejemplo utilizando ANTLR

 

Traducción Dirigida por la Sintáxis El significado de una sentencia de entrada está relacionado con su estructura sintáctica.  Encierran aquellos formalismos utilizados para especificar las traducciones para las construcciones de los lenguajes de programación guiadas por una GLC. ◦ Se Asocian Atributos a los símbolos de la gramática. ◦ Se computan los valores de atributos por reglas semánticas asociadas a las producciones de la gramática.  La evaluación de las reglas semánticas puede: ◦ Generar Código. ◦ Insertar información en la Tabla de Símbolos. ◦ Realizar el Chequeo Semántico. ◦ Dar mensajes de error ◦ Etc. Existen dos notaciones para asociar información a las reglas semánticas:

Definiciones Dirigidas por la Sintáxis: es una especificación de alto nivel que oculta detalles de implementación. Es una generalización de una gramática independiente de contexto en la que cada símbolo gramatical tiene asociado un conjunto de atributosEspecifica la traducción de una construcción en función de los atributos asociados con sus componentes sintácticos. Para traducir una construcción de un lenguaje de programación, un compilador puede necesitar tener en cuenta muchas características, además del código generado para la construcción. Una definición dirigida por sintaxis es un formalismo para especificar las traducciones para las construcciones en funciónde atributos asociados con sus componentes sintácticos.

Utiliza una gramática independiente de contexto para especificar la estructura sintáctica de la entrada, la idea es asociar con cada símbolo de la gramática un conjunto de atributos quepueden ser sintetizados o heredados y además a cada producción un conjunto de reglas semánticas para calcular los valores de los atributos asociados con los símbolos que aparecen en esa producción.

Ladefinición dirigida por sintaxis consiste en sí entonces de la gramática y el conjunto de reglas semánticas. En una definición dirigida por sintaxis, para cada producción gramatical A=>α se asocia un conjunto de reglas semánticas de la forma b:=f(c1,c2,…,ck) donde f es una función y b es un atributo sintetizado de A o un atributo heredado de uno de los símbolos gramaticales de la parte derecha de laproducción y c1,c2,…,ck son atributos que pertenecen a los símbolos gramaticales de la producción. Se dice que b depende de c1,c2,…,ck. •

Utilizan una gramática independiente de contexto para especificar la estructura sintáctica de la entrada

• A cada símbolo de la gramática se le asocia un conjunto de atributos

• A cada regla de la gramática se le asocia un conjunto de reglas semánticas para calcular los valores de los atributos asociados con los símbolos de esa regla

• La gramática y el conjunto de reglas semánticas constituyen la definición dirigida por la sintaxis

ATRIBUTOS • El conjunto de atributos asociado a cada símbolo gramatical se divide en dos subconjuntos

Atributos sintetizados. Se pueden calcular durante un solo recorrido ascendente del árbol de análisis sintáctico –

Atributos heredados. Sirven para expresar la dependencia de una construcción en de un lenguaje en el contexto en el que aparece • Si se considera un nodo de un símbolo gramatical de un árbol sintáctico como un registro para guardar información entonces un atributo se corresponde con el nombre de un campo •

. Un atributo puede representar cualquier cosa (una cadena, un número, un tipo, una posición de memoria…)

• El proceso de calcular los valores de los atributos en los nodos se denomina anotar o decorar el árbol de análisis sintáctico

• El valor de un atributo se define mediante la regla semántica asociada a la regla de producción utilizada en ese nodo

• El valor de un atributo sintetizado se calcula a partir de los valores de los atributos de los hijos de ese nodo en el árbol de análisis sintáctico

• El valor de un atributo heredado se calcula a partir de los valores de los atributos de los hermanos y el padre de ese nodo

• En una definición dirigida por la sintaxis, se asume que los terminales sólo tienen atributos sintetizados (la definición no proporciona ninguna regla semántica para los terminales)

• Los valores para los atributos de los terminales son proporcionados generalmente por el analizador léxico

REGLAS SEMÁNTICAS • Las reglas semánticas establecen las dependencias entre los atributos que serán representadas mediante un grafo

• El grafo de dependencias proporciona el orden de evaluación de las reglas semánticas

• La evaluación de las reglas semánticas define los valores de los atributos de los nodos del árbol

• Una regla semántica puede tener también efectos colaterales (imprimir un valor, actualizar una variable global…)

• Una gramática con atributos es una definición dirigida por la sintaxis en la que las funciones de las reglas semánticas no pueden tener efectos colaterales

EJEMPLO Definición Dirigida por la Sintaxis de una calculadora de escritorio sencilla

Para ampliar el tema pulsa aqy o aqy

ANÁLISIS DESCENDENTE Parte de las hojas del correspondiente árbol de derivación derecho (cadena de entrada)
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.
• Ejemplo:
– analizar la cadena de entrada “cad” dada la gramática siguiente:

Gramática
S = c A d
A = a b
A = a

S
/ | \
c A d
|
a
Análisis ascendente: se construye el árbol de análisis sintáctico de la cadena de entrada desde las hojas hasta la raíz. En las hojas tenemos la cadena a analizar (los símbolos terminales) que se intentan reducir al axioma, que se encontrará en la raíz, si la cadena es correcta sintácticamente.
¿Como construir el árbol?
Se trata de desplazarse en la entrada hasta encontrar una subcadena de
símbolos que represente la parte derecha de una producción, en ese momento sustituimos esa subcadena por el no-terminal de la parte izquierda
correspondiente de la producción, la reducimos.
Ejemplo: Supongamos la siguiente gramática que permite generar expresiones aritméticas donde aparece el operador suma y potencia y combinar números e identificadores.
E = E + E
E =E ^E
E =id
E =num
Para la entrada id + id + id

E
/ | \
E | E
/ | \ | |
E | E| |
| | | | |
id + id + id

Los métodos ascendentes se caracterizan porque analizan la cadena d componentes léxicos de izquierda a derecha, obtienen la derivación más a la derecha y el árbol de derivación se construye desde la raíz hasta las hojas.

Para ampliar este tema puede visitar los siguientes LINKS:

http://www2.uah.es/jcaceres/uploaded/teoria/LenguajesProgramacion/tema4.pdf

http://informatica.uv.es/docencia/iiguia/asignatu/2000/PL/2007/tema4.pdf

http://ants.dif.um.es/staff/juanbot/traductores/files/20022003/tema4.pdf

Mini compilador