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 y el creador de parsers 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.

• http://jflex.de/index.html
• 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).

La estructura de un archivo para jflex estaría compuesta de tres bloques separados por %%. 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…

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()); }

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.

• %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:

...
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 "); }
...

• 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.

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:

04/10/09 [ACCION] 44 objid_091004

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.

...
%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);
	} 
	. { }	
}

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:

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
          ;

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:

func foo ()
{
  i = 3 + 5 * (4 + 7);
  a = 4 + i;
}

El árbol sería el siguiente:




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…).

• http://www2.cs.tum.edu/projects/cup/
• 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:

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 ...

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" { return new Symbol(sym.STARTCODE, yyline + 1, 0, yytext()); }

Aquí un par de ejemplos.

El código CUP se estructura de la siguiente forma:

1. Código Java de fuera de la clase (tipo imports…).
2. Código interno de la clase parser y que podrá ser accedido desde el código generado entre: parser code {: :}
3. El action code, entre: action code {: :}
4. 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:

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;

Luego la creación de la gramática se haría con la estructura explicada anteriormente, pero con la siguiente sintaxis:

PROGRAMA  ::= VARBLOCK FUNCBLOCK CODEBLOCK
          | VARBLOCK CODEBLOCK
          ;

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.

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);
              :}
          | ...

En el ejemplo de la documentación encontramos la definición de la gramática siguiente:

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; :} 
	      ;

La herramienta de Python para generar analizadores léxicos y sintácticos es la denominada PLY (que se encuentra aquí), su nombre viene de Python Lex Yacc.