Trabajo Final Compiladores

Ejemplo de un compilador -> Analizador léxico, sintáctico y semántico

Anuncios

JavaCC

El generador JavaCC (Java Compiler Compiler) es una herramienta para generar programas escritos en lenguaje Java; acepta como entrada una especificación de un determinado lenguaje y produce como salida un analizador para ese lenguaje. En la manera más simple de funcionamiento, la especificación proporcio-nada define las características sintácticas y lexicográficas de un lenguaje y se genera un analizador léxico-sintáctico del lenguaje especificado; pero también es posible completar una especificación léxico-sintáctica con la inclusión adecuada de código para que el programa generado llegue a ser un analizador completo del lenguaje.

Obtención de un analizador léxico-sintáctico

  • Pasos para la generación del analizador

1. Edición de la especificación (editor de texto plano)

vi | edit |· · · NombreFichero.jj

(el nombre del fichero puede tener cualquier extensión; suele usarse .jj)

2. Ejecución del generador

javacc NombreFichero.jj

Si el nombre elegido para la especificación es NombreDeLaEspecif (más adelante se indica la manera de dar un nombre a la especificación), como resultado de la generación se obtiene (además de otros ficheros auxiliares) el fichero

NombreDeLaEspecif.java

3.- Compilación del analizador generado

javac NombreDeLaEspecif.java

Como resultado de la compilación se obtiene (además de otras clases auxiliares) el fichero

NombreDeLaEspecif.class

  • Ejecución del analizador generado

Si el nombre del fichero donde se encuentra el texto fuente (escrito en el lenguaje para el que se ha generado el analizador) que se pretende analizar es Programa.len

java NombreDeLaEspecif < Programa.len

Si se desea que los resultados del análisis, en vez de presentarse por pantalla, queden grabados en un fichero de nombre Salida.dat

java NombreDeLaEspecif < Programa.len > Salida.dat

Ejemplo:

 </code><Expresion> ::= <Termino> { + <Termino> }
<Termino> ::= <Factor> { * <Factor> }
<Factor> ::= variable
| constante
| ( <Expresion> )
options { Ignore_Case = true; }
PARSER_BEGIN (ExprMin)
public class ExprMin {
public static void main (String[] argum) throws ParseException {
ExprMin anLexSint = new ExprMin (System.in);
anLexSint.unaExpresion();
System.out.println("Análisis terminado:");
System.out.println
("no se han hallado errores léxico-sintácticos");
}
}
PARSER_END (ExprMin)
void unaExpresion() :
{ }
{
expresion() <EOF>
}
void expresion() :
{ }
{
termino() ( "+" termino() )*
}
void termino() :
{ }
{
factor() ( "*" factor() )*
}
void factor() :
{ }
{
<constante>
| <variable>
| "(" expresion() ")"
}
TOKEN:
{
< variable : ["a"-"z"] >
}
TOKEN:
{
< constante : ( ["0"-"9"] ) + >
}
SKIP:
{ " " | "\t" | "\n" | "\r" }
<code> 

Antlr

ANTLR (ANother Tool for Language Recognitionotra herramienta para reconocimiento de lenguajes) 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).

ANTLR cae dentro de la categoría de meta-programas, por ser un programa que escribe otros programas. Partiendo de la descripción formal de la gramática de un lenguaje, ANTLR 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.

Además, ANTLR proporciona facilidades para la creación de estructuras intermedias de análisis (como ser ASTs – Abstract Sintax Tree), para recorrer dichas estructuras, y provee mecanismos para recuperarse automáticamente de errores y realizar reportes de los mismos.

ANTLR es un proyecto bajo licencia BSD, viniendo con todo el código fuente disponible, y preparado para su instalación bajo plataformas Linux, Windows y Mac OS X.

ANTLRWorks es un entorno de desarrollo con interfaz gráfica que permite el desarrollo de gramáticas para la versión 3.0 o superior de ANTLR. Consiste en una aplicación independiente Java, que se puede ejecutar directamente desde un jar. De quererse incorporar las funcionalidade de ANTLR en ambientes de desarrollo ya existentes, existen plug-ins que se pueden bajar directamente de la web del autor, habilitando el poder trabajar en IntelliJ, gUnit, Eclipse, NetBeans, etc.

Actualmente ANTLR genera código Java, C, C++, C#, Python, Perl, Delphi, Ada95, JavaScript y Objective-C. Otros lenguajes como Ruby, php, etc. son generados por medio de extensiones planteadas por la comunidad.

Ejemplo

grammar SimpleCalc;



tokens {

 PLUS     = '+' ;

 MINUS = '-' ;

}



@members {

 public static void main(String[] args) throws Exception {

 SimpleCalcLexer lex = new SimpleCalcLexer(new ANTLRFileStream(args[0]));

 CommonTokenStream tokens = new CommonTokenStream(lex);

 SimpleCalcParser parser = new SimpleCalcParser(tokens);

 try {

 parser.expr();

 } catch (RecognitionException e)  {

 e.printStackTrace();

 }

 }

}



/*------------------------------------------------------------------

 * PARSER RULES

 *------------------------------------------------------------------*/

expr      : ID '=' op {System.out.println($ID.text +"="+ $op.value);};

op          returns [int value]

 :   e=factor {$value = $e.value;}

 (   PLUS e=factor {$value += $e.value;}

 |   MINUS e=factor {$value -= $e.value;}

 )*

 ;

factor    returns [int value]

: NUMBER {$value = Integer.parseInt($NUMBER.text);};



/*------------------------------------------------------------------

 * LEXER RULES

 *------------------------------------------------------------------*/



ID  :   ('a'..'z'|'A'..'Z')+ ;

NUMBER             : (DIGIT)+ ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+   { $channel = HIDDEN; } ;

fragment DIGIT                : '0'..'9' ;

 

La primera parte es la cabecera del fichero. Aquí hemos de prestar atención de darle el mismo nombre que tiene el fichero. ¿Os recuerda a java esto, no? Pues básicamente la idea es la misma. La clase debe llamarse igual que el nombre del fichero, sino, no compilará.

El segundo bloque es la declaración de tokens. Aquí debemos añadir todos los elementos que queremos que reconozca nuestra gramática. En nuestro caso el signo + y el signo –

El tercer bloque @ members contiene el código java de nuestra aplicación. En nuestro caso hemos colocado un main. De hecho el programa funcionará igual sin este código el problema es que no podremos llegar a ver nada si el texto de entrada es aceptado. Lo que hace este código es leer un fichero de texto especificado en la línea de comandos cuando arrancamos nuestro compilador, eso es args[0]. Dentro del bloque try, llamamos a la primera regla del programa (parser.expr()), esto desencadenará el inicio del programa.

El cuarto bloque es las reglas del parser, es decir puramente la gramática. Aquí podemos ver como una expresión es un ID (identificador, o nombre de variable) el token igual ´=´ (si, ya sé que lo podríamos haber definido en el apartado de tokens, pero para que vierais que también podemos ponerlo directamente aquí) y una operación (la definimos más abajo). Lo que vemos entre { } es el código java que he escrito yo. Basicamente nos imprimirá por pantalla las expresiones que vaya reconociendo.
La siguiente regla es la operación. Tenemos un factor OPERANDO factor. El factor en nuestro caso será un entero, lo podemos ver en la tercera regla. Lo que hace es almacenar en una variable valor temporal, el resultado de sumar o restar los dos factores.
La tercera regla, almacena en una variable llamada value el resultado de parsear la lectura del fichero a un Entero.

El cuarto bloque es la declaración de los tipos en nuestro caso un ID (identificador de variable) es cualquier nombre de la a-Z que contenga al menos una letra. Esto es debido a la cláusula positiva de Klenee (+).
El mismo razonamiento para los números, para los espacios en blanco y los dígitos.

Me he dejando por comentar un par de cosas adrede, porque quería que quedaran claras. Los campos disponen de varios valores (como si fueran una struct) estos son .value y .text.

Se entiende que value es un entero y text un campo para almacenar strings, como los ID.

Definición Dirigida por la Sintaxis

Definición

Es una generalización de una gramática incontextual en la cual cada símbolo tiene asociado un conjunto de atributos.

Hay dos clases de atributos posibles:

  • Atributos Sintetizados
  • Atributos Heredados

Atributos

En general los atributos de un nodo reciben valor mediante la evaluación de las reglas semánticas asociadas a la producción usada en ese nodo propietario del atributo.
Los valores de los atributos sintetizados se calculan a partir de los valores de atributos de sus nodos hijos en el árbol de análisis sintáctico.
Los valores de los atributos heredados se calculan a partir de los valores de atributos de su nodo padre o sus nodos
hermanos.

Atributos Sintetizados

Se puede decir que un atributo es sintetizado si su valor en un nodo del árbol de análisis sintáctico se determina a partir de los valores de atributos de los hijos de ese nodo (como decir de abajo hacia arriba). Se pueden calcular mediante un solo recorrido ascendente del árbol de análisis sintáctico, lo que es muy deseable.

Atributos Heredados

Un atributo heredado es uno cuyo valor en un nodo de un árbol de análisis sintáctico está definido a partir de los atributos en el padre y los hermanos de dicho nodo. Éstos sirven para expresar la dependencia de una construcción de un lenguaje de programación en el contexto en el que aparece.

Reglas semánticas

Las reglas semanticas establecen dependencias entre los atributos de los diferentes símbolos.Esas dependencias se reflejan en un grafo con el fin deestablecer un orden de evaluación de las reglas.La evaluación de las reglas asigna valor a los atributos.Un árbol de análisis sintáctico que contiene también los atributos y su valores se llama un arbol anotado o decorado.

Ejemplo

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