Programming

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Compiladores ======
Para crear un compilador necesitamos un analizador léxico (o //scanner//) analiza el texto, y un analizador sintáctico (o //parser//) el que analiza la estructura del texto y realiza las acciones necesarias según esta. El analizador léxico recorre el texto y va pasando las porciones útiles (//tokens//) al parser, este actuará según la estructura en la que estén colocados los tokens.
  * Para Java el creador de analizadores léxicos se llama [[#jflex|JFlex]] y el creador de parsers [[#cup|CUP]]. Estas son herramientas a las que se les pasa código y, a partir de este, generan el analizador o el parser.
  * Los nombrados anteriormente son versiones de los primeros creadores Lex y Yacc.
  * Actualmente existen otros generadores de parsers como son [[http://www.gnu.org/software/bison/|Bison]], [[http://www.antlr.org/|ANTLR]]...

===== JFlex =====







==== Instalación y uso ====
  * [[http://jflex.de/index.html]]
  * {{otros:compilers:jflex-1.4.3.zip|JFlex}}
Es una reescritura de JLex, el generador de analizadores léxicos para Java. Para utilizarlo, tras descomprimir, podemos ejecutar script que viene en la carpeta ''bin'' denominado ''jflex'', este abre una aplicación a la que indicándole un fichero de entrada y uno de salida coge el fichero de entrada como el código para crear un analizador léxico y generará la clase Java de este donde se le indica como fichero de salida. \\ 
Para usar la clase generada, por ejemplo desde Eclipse, necesitaremos agregarla al proyecto y a la vez agregar el ''jflex.jar'' (en las propiedades del proyecto, ''Java Build Path'' y agregar un archivo jar externo).















==== Código ====
La estructura de un archivo para jflex estaría compuesta de tres bloques separados por ''<nowiki>%%</nowiki>''. En el primero se pondría el código Java que queremos que se agregue a ese archivo; en el segundo parámetros de generación para JFlex; y en el tercero las instrucciones del analizador léxico definiendo cada token. La definición de los tokens se realiza a partir de una expresión regular y del código Java que se ejecutará cuando encuentre en el texto dicha expresión regular. En las instrucciones podemos poner código Java, entre ''%{'' y ''%}'', y este se agregará a la clase generada. \\ \\ 
Por ejemplo...
<code>
import java.io.IOException;
%%
%{
public static void main(String[] args) throws IOException {
	Yylex lex = new Yylex(System.in);
	while (lex.yylex() != -1);
}
%}
%integer
%%
";" { System.out.println("Punto y coma"); }
"+" { System.out.print("SIGNO DE SUMA "); }
"*" { System.out.print("SIGNO DE MULT "); }
"-" { System.out.print("SIGNO MENOS "); }
"/" { System.out.print("SIGNO DIVIDIDO "); }
"(" { System.out.print("Parentesis izq "); }
")" { System.out.print("Parentesis der "); }
[0-9]+ { System.out.print(" numero "); }
[ \t\r\n\f] { /* Ignora espacios en blanco. */ }
. { System.err.println("Illegal character: "+yytext()); }
</code>
Genera una clase denominada ''Yylex'' (el nombre por defecto) y le agrega el método main indicado. Lo que hará el analizador léxico será indicar por consola cuando encuentra un número o un signo de puntuación, ignorará los espacios en blanco (no hay código), y cuando encuentre otro carácter que no sea ninguno de los indicados mostrará un aviso de ''carácter ilegal''. \\ \\ 
El analizador léxico funiona a partir de un objecto de la clase con nombre indicado (si no se indica ninguna se llamará ''Yylex''), el constructor de este admite un ''InputStream'' que puede ser un ''FileInputStream'', el ''System.in'' (la consola), etc. En el ejemplo anterior es la consola. El objeto irá analizando tokens mientras se llame al método ''yylex'', este retorna un objeto ''YyToken'' mientras los vaya encontrando o, como en el ejemplo, si se indica ''%integer'' devolverá un int que mientras no tenga el valor ''-1'' significará que encuentra tokens. \\ \\ 
Es importante el orden en el que se definen los posibles tokens, por ejemplo, si definimos primero número y luego fecha (esta en formato numero/numero/numero) siempre encontrará antes el token "número" separando las fechas como número, barra, número, barra y número. Es decir, es mejor definir primero la fecha.

=== Instrucciones para JFlex ===
  * ''%integer'' o ''%int'' indica que el tipo retorno del método ''yylex'' será un int.
  * ''%class Nombre'' indica el nombre de la clase generado
  * ''%public'', ''%abstract'' o ''%final'' indican como será la clase.
  * ''%cup'' activa la compativilidad con CUP.
  * ''%line'' activa una variable denominada ''yyline'' donde se cuenta el número de líneas.
  * ''%column'' activa una variable denominada ''yycolumn'' donde se cuenta el número de columnas.

En el bloque donde introducimos las instrucciones para JFlex también podemos definir expresiones para usar luego en las instrucciones:
<code>
...
blank=[\t ]+
digit = [0-9]
date = {digit}{digit}\/{digit}{digit}\/{digit}{digit}{digit}{digit}
number = {digit}+
object_id = [a-zA-Z0-9][a-zA-Z0-9][a-zA-Z0-9][a-zA-Z0-9][a-zA-Z0-9]\_{digit}{digit}{digit}\.{digit}+
%%
{date} { System.out.print("Fecha "); }
{digit} { System.out.print("numero "); }
...
</code>

=== Métodos y variables que se pueden utilizar en el código ===
  * ''yytext()'' retorna el token.
  * ''yylength()'' retorna la longitud del token.
  * ''yyclose()'' finaliza el análisis léxico.
  * ''yyline'' indica el número de línea actual.

=== Estados ===
JFlex nos permite trabajar por estados, es decir, tratar los tokens según el estado actual. Para ello debemos definir los estados existentes separados por comas en las instrucciones para JFlex utilizando la instrucción ''%state lista_de_estados''. Luego podremos definir el cuerpo de los estados en el código del código haciendo: ''<Nombre_del_Estado> { }''. Existe un estado inicial que es el llamado ''YYINITIAL'', para indicar que se ha de entrar en un estado utilizaremos el método ''yybegin(Nombre_del_estado)''. \\ \\ 
En el código de ejemplo se introducen líneas con la siguiente estructura:
<code>
04/10/09 [ACCION] 44 objid_091004
</code>
Lo primero sería la fecha de la acción, esta acción puede ser una llegada (ARRIVAL), una salida (DEPARTURE) o una eliminación del producto (REMOVAL). Luego se indica el número de elementos y el identificador del elemento en cuestión. Ha de sumar el número de errores que tenga el documento pero no realizar ninguna acción. La lectura de la fecha se realiza en primer lugar en el estado YYINITIAL, como no es necesaria no se hace nada con ella, luego se pasa al estado ACTION donde se registra el identificador de acción que se ha de realizar (más tarde se llamará a uno de los métodos que se han agregado dentro de la clase scanner generada según la acción); en el estado UNITS se recogen las unidades y en el OBJECT el identificador del objeto y es entonces donde se realiza la acción que toque.
<code>
...
%state ACTION, UNITS, OBJECT, ERROR
%%
<YYINITIAL>
{
	[\ \t\f\n|\r] {  }
	{date} 	{ yybegin(ACTION); }
	. { yybegin(ERROR); }
}
<ACTION>
{
	[\ \t\f\n|\r] {  }
	"["[A-Z]*"]" {
		String str = yytext();
		boolean berror = true;
		if (str.compareTo ("[ARRIVAL]") == 0) {
			Action = 1;
			berror = false;
		} else if (str.compareTo ("[DEPARTURE]") == 0) {
			Action = 2;
			berror = false;
		} else if (str.compareTo ("[REMOVAL]") == 0) {
			Action = 3;
			berror = false;
		}
		if (!berror) {
			yybegin(UNITS);
		} else {
			yybegin(ERROR);
		}
	}
	. { yybegin(ERROR); }
}
<UNITS>
{
	[\ \t\f\n|\r] {  }
	[0-9]* {
		Units = Integer.parseInt (yytext());
		yybegin(OBJECT);
	}
	. { yybegin(ERROR); }
}
<OBJECT>
{
	[\ \t\f\n|\r] {  }
	{object_id} {
		Obj_id = yytext();
		switch (Action) {
			case 1:
				this.arrival(Obj_id);
				break;
			case 2:
				this.departure(Obj_id);
				break;
			case 3:
				this.removal(Obj_id);
				break;
		}
		total_movements ++;
		yybegin(YYINITIAL);
	}	
	. { yybegin(ERROR); }
}
<ERROR>
{
	[\f\n|\r] {
		wrong_movements ++;
		yybegin(YYINITIAL);
	} 
	. { }	
}
</code>


===== CUP =====









==== Definición de una sintaxis ====
Imaginemos una estructura de un lenguaje en el que tendríamos:
  * Un bloque obligatorio de variables definido de la siguiente forma: ''VARS { definiciones }'' y las definiciones serían del palo ''tipo nombre;'' o ''tipo nombre, nombre...;''.
  * Un bloque opcional de funciones definido como: ''FUNCS { funciones }'' y las funciones pueden ser: ''func nombre () { código }'' o ''func nombre (parámetros) { código }''. 
  * Los parámetros de una función se definen como: ''tipo nombre, tipo nombre''.
  * Un bloque de código definido como: ''CODE { código }''.
La definición de la estructura anterior sería algo parecido (así a bote pronto) a la siguiente:
<code>
PROGRAMA  : VARBLOCK FUNCBLOCK CODEBLOCK
          : VARBLOCK CODEBLOCK
          ;
VARBLOCK  : NOMBLOCKVAR CORCH_IZQ DEC_VARS CORCH_DER
          ;
FUNCBLOCK : NOMBLOCKFUN CORCH_IZQ DEC_FUNCS CORCH_DER
          ;
CODEBLOCK : NOMBLOCKCOD CORCH_IZQ CODE_BODY CORCH_DER
          ;
DEC_VARS  : DEC_VAR PUNTOCOMA
          : DEC_VAR DEC_VARS
          ;
DEC_VAR   : TIPO GRUPO_IDS 
          ;
GRUPO_IDS : ID
          : ID COMA GRUPO_IDS
          ;
DEC_FUNCS : DEF_FUNC
          : DEF_FUNC DEC_FUNCS
          ;
DEF_FUNC  : NOMFUNC ID PAR_IZQ PAR_DER CORCH_IZQ CODE_BODY CORCH_DER
          : NOMFUNC ID PAR_IZQ DEC_PARS PAR_DER CORCH_IZQ CODE_BODY CORCH_DER
          ;
DEC_PARS  : DEC_PAR
          : DEC_PAR COMA DEC_PAR
          ;
DEC_PAR   : TIPO ID
          ;
TIPO      : NOM_INT
          : NOM_STRING
          : NOM_DOUBLE
          : NOM_BOOL
          ;
</code>
Donde los elementos que aparecen son denominados **símbolos** y sus correspondencias son...
  * PROGRAMA: El programa en sí. 
  * VARBLOCK: Al bloque de definición de variables.
  * FUNCBLOCK: Al bloque de definición de funciones.
  * CODEBLOCK: Al bloque de código principal.
  * CORCH_IZQ y CORCH_DER son los dos corchetes.
  * NOMBLOCKVAR es el nombre del grupo de variables (VARS), NOMBLOCKFUNC el de funciones (FUNCS) y NOMBLOCKCOD el del código (CODE).
  * DEC_VARS: El conjunto de declaraciones de variables.
  * DEC_VAR: Una declaración.
  * GRUPO_IDS: Nombre (ID, un string cualquiera) o nombres separados por coma de identificadores.
  * CODE_BODY: Sería la parte de código que no vamos a definir, pero que se tendría que seguir haciendo.
  * DEF_FUNC: Sería la definición de una función (declaración + cuerpo) y DEC_FUNCS el conjunto de declaraciones de funciones.
  * NOMFUNC: Correspondería a la palabra ''func''.
  * DEC_PARS: Sería el conjunto de declaraciones de parámetros (DEC_PAR).
  * TIPO: Serían todos los posibles tipos.
Elementos a tener en cuenta en la declaración serían:
  * La declaración del programa se hace dos veces, en la primera aparece el bloque de funciones, en la segunda no. Esto significa que un programa puede estar compuesto por bloque de variables seguido del bloque de código o por bloque de variables seguido del de funciones y este seguido del de código. Es decir, el bloque de funciones es opcional.
  * La declaración de varias variables también se define como dos, en la primera es únicamente la declaración de una variable y en la segunda es la declaración de una variable más la declaración de varias variables. Esto es recursivo, significa que el bloque de declaraciones puede tener una declaración o una declaración seguida de un bloque, el cual a su vez puede tener una declaración seguida de un bloque... Es decir, puedes definir tantas variables como quieras.
  * En cambio en TIPO no son seguidos, es decir sólo admite un tipo (int, string, double o bool).
  * ID se definiría como una cadena de carácteres.
  * Una declaración de variables acaba con punto y coma, aunque hayan varias. En cambio los parámetros se separan por comas.
Todos estos son identificadores terminales o no terminales, para explicar mejor cuales serían los terminales y cuales los no terminales podríamos verlo en un árbol que expresase el siguiente código:
<code>
func foo ()
{
  i = 3 + 5 * (4 + 7);
  a = 4 + i;
}
</code>
El árbol sería el siguiente: \\ \\ \\ 
{{otros:compilers:arbol.png?500|}} \\ \\ 
Siendo los **símbolos terminales** los elementos que están en las ramas del árbol (paréntesis, números, signos...) y los símbolos** no terminales** los elementos que están en el tronco (código, igualdad, operación...).







==== Instalación, uso y combinación con JFlex ====
  * [[http://www2.cs.tum.edu/projects/cup/]]
  * {{otros:compilers:java_cup_v10k.zip|CUP}}
Descomprimimos el archivo del CUP, nos aparecerá una carpeta denominada java_cup_v10k, esa es la carpeta que deberemos agregar como ''external class folder'' en eclipse (desde la misma ventana desde donde agregamos el jar del JFlex) y desde esa carpeta será desde donde ejecutemos el comando: ''java java_cup.Main nuestro_fichero.cup''. Donde nuestro fichero es el código CUP que programemos. Este comando generará dos ficheros\clases que tendremos que agregar a nuestro proyecto:
  * ''parser.java'' donde estará el código del parser.
  * ''sym.java'' donde se definirán todos los símbolos.
Para que JFlex sea compatible con CUP debemos agregar a las instrucciones de generación el parámetro ''%cup''. \\ 
Cuando combinamos los códigos generados por JFlex y CUP el que lanza el analizador léxico ahora es la misma clase parser. El siguiente código sería un ejemplo de inicio de parseo:
<code java>
parser p = null;
Yylex lex = null;
try {
	if (args.length == 0) {
		System.out.println("Llegint des de l' stream d'entrada: ");
		lex = new Yylex(System.in);
	} else {
		System.out.println("Llegint des del fitxer: " + new java.io.File(args[0]).getAbsolutePath());
	 	lex = new Yylex(new java.io.FileReader(args[0]));
	}
	p = new parser(lex);
	p.parse();
catch ...
</code>
Dentro del código JFlex tendremos que retornar objetos ''Symbol'', el constructor de estos, entre otras cosas, recibe un tipo de simbolos (de la lista de símbolos en el archivo ''sym.java'' generado), dos objetos (el left y el right) que luego podremos recoger y el valor. En el siguiente ejemplo cuando se encuentra una definción ".code" se envia que es un símbolo del tipo ''STARTCODE'', el número de línea (como objeto left), nada (como objeto right), y el texto (por si se necesita):
<code>
".code" { return new Symbol(sym.STARTCODE, yyline + 1, 0, yytext()); }
</code>
{{otros:compilers:flex_and_cup.tar.gz|Aquí}} un par de ejemplos.




==== Código ====
El código CUP se estructura de la siguiente forma:
  - Código Java de fuera de la clase (tipo imports...).
  - Código interno de la clase parser y que podrá ser accedido desde el código generado entre: ''parser code {: :}''
  - El action code, entre: ''action code {: :}''
  - El código que define la gramática.
El código que define la gramática comienza con la definición de los nombres de símbolos terminales y no terminales:
<code>
terminal WORD, COMA, NUMBER, DOSPUNTOS, CORCHIZQ, CORCHDER;
terminal STARTPROGRAM, ENDPROGRAM, STARTCODE, ENDCODE, STARTDECVAR, ENDDECVAR, STARTMACRO, ENDMACRO, STARTDECMACRO, ENDDECMACRO;
terminal COMANDO, REGISTRO, TIPO;
nonterminal programa, name, bloccodi, codi, liniacodi, blocvariables, blocmacros, decvars, valor, macro, decmacros, etiqueta;
nonterminal memaddr, operando1, operando2;
</code>
Luego la creación de la gramática se haría con la estructura explicada anteriormente, pero con la siguiente sintaxis:
<code>
PROGRAMA  ::= VARBLOCK FUNCBLOCK CODEBLOCK
          | VARBLOCK CODEBLOCK
          ;
</code>
Además podemos incluir código y leer los tokens pasados por el analizador léxico, por ejemplo podemos leer el contenido de cada token (agregando '':nombre_variable'' tras su definición) o acceder a los objetos left y right con ''nleft'' y ''nright''.
<code>
DEF_FUNC  ::= NOMFUNC ID:w PAR_IZQ PAR_DER CORCH_IZQ CODE_BODY CORCH_DER
              {:
                    System.out.println("Se ha definido una función llamada: " + w.toString() + " en linea:" + nleft);
              :}
          | ...
</code>

En el ejemplo de la documentación encontramos la definición de la gramática siguiente:
<code>
expr_list ::= expr_list expr_part 
	      | expr_part
	      ;

expr_part ::= expr:e 
	      {: System.out.println("= " + e); :} 
	      ;

expr      ::= expr:e1 PLUS expr:e2    
	      {: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
	      | expr:e1 MINUS expr:e2    
              {: RESULT = new Integer(e1.intValue() - e2.intValue()); :} 
	      | expr:e1 TIMES expr:e2 
	      {: RESULT = new Integer(e1.intValue() * e2.intValue()); :} 
	      | expr:e1 DIVIDE expr:e2 
	      {: RESULT = new Integer(e1.intValue() / e2.intValue()); :} 
	      | expr:e1 MOD expr:e2 
	      {: RESULT = new Integer(e1.intValue() % e2.intValue()); :} 
	      | NUMBER:n                 
	      {: RESULT = n; :} 
	      | MINUS expr:e             
	      {: RESULT = new Integer(0 - e.intValue()); :} 
	      | LPAREN expr:e RPAREN     
	      {: RESULT = e; :} 
	      ;
</code>





===== Notas =====
  * La herramienta de Python para generar analizadores léxicos y sintácticos es la denominada PLY (que se encuentra [[http://www.dabeaz.com/ply/index.html|aquí]]), su nombre viene de //Python Lex Yacc//.
Programming

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
