Práctica Obligatoria

El objetivo de esta práctica es desarrollar un compilador sencillo, implementando todos sus componentes: analizador léxico, analizador sintáctico, analizador semántico y generación de código. El compilador que tiene que desarrollar debe de traducir programas escritos en el lenguaje fuente que se describe más adelante a Java. El compilador recibirá como entrada un fichero de texto con el programa fuente a traducir y producirá como resultado una o varias clases Java (siempre y cuando el programa fuente no contenga errores). Si el programa fuente contiene errores se levantará una excepción.

Tutoriales

Antes de empezar a realizar la práctica se recomienda a los alumnos realizar está práctica para familiarizarse con el entorno de trabajo, así como consultar los manuales de CUP y JLex disponibles a través de Aula Global o bien estos pequeños resúmenes de CUP y JLex

Empecemos con un pequeño programa de ejemplo:

PF2011 Ejemplo(argumento)

vars

int x, y;

{
x:=Str2Int(argumento);
y:=0;

while(x>0) {
 y:=y+x;
 x:=x-1;
}

print("Resultado= " + Int2Str(y));
}

Un programa en el lenguaje de programación fuente consta de las siguientes partes:

1. Cabecera del programa. En el ejemplo anterior la cabecera es la línea:

   PF2011 Ejemplo(argumento)

   Consta de: palabra clave PF2011, seguida del nombre del programa (en el ejemplo Ejemplo), seguida opcionalmente de uno o varios identificadores separados por comas entre paréntesis. Estos identificadores son variables de tipo string que se utilizan para que el programa pueda recibir argumentos al ser ejecutado. Cuando se invoca el programa, lo que se escriba a continuación del nombre del programa se le pasará al programa en estas variables.

2. Opcionalmente, pueden declararse variables que serán utilizadas dentro del programa. Las declaraciones de variables están formadas por un tipo de datos seguido de una lista de identificadores (nombres de variables). Los tipos de datos existentes en este lenguaje de programación son int, bool y string.

   Cuando se declara una variable se supondrá que inicialmente tomará el valor false si la variable es de tipo bool, 0 si la variable es de tipo int y "" si la variable es de tipo string.

3. Cuerpo del programa, formado por una secuencia de sentencias que describen las operaciones que realiza el programa.

Las sentencias de un programa pueden ser de los siguientes tipos:

• Sentencia de asignación: almacena en la variable indicada a la izquierda del := el valor que se obtiene como resultado de evaluar la expresión a la derecha del :=.

• Sentencia condicional if <Exp> then <Sent> [else <Sent>] endif.

• Bucle while <Exp> <Sent> .

• Sentencia break n (siendo n un constante entera positiva). Esta sentencia solamente se puede encontrar dentro de un bucle while, y hace que se termine abruptamente la ejecución de los n bucles más interiores desde la posición en la que está la sentencia break (tenga en cuenta que puede haber bucles anidados).

• Sentencia print ( <Exp> ). Esta sentencia recibe como argumento un dato de tipo string que imprime en pantalla, seguido de un salto de línea.

El analizador léxico JLex a desarrollar debe reconocer los siguientes tokens:

• Palabras clave. Generan los siguientes tokens: IF, THEN, ELSE, ENDIF, WHILE, PRINT, INT2STR, STR2INT, BREAK, NOT, AND, OR, PROG, VARS, TIPO. Todas estos tokens representan la palabra clave con el mismo nombre pero en minúsculas, excepto el token TIPO que agrupa a las 3 palabras clave que identifican tipos de datos: int, bool, string y el token PROG que representa a la palabra clave PF2011.

• Signos de puntuación y operadores: PC (";"), ASOP (":="), MAS ("+"), MENOS ("-"), POR ("*"), DIV ("/"), MAYORQUE (">"), MENORQUE ("<"), IGUALQUE ("="), ABRELLAVE ("{"), CIERRALLAVE ("}"), COMA (","), PAREN ("("), TESIS (")").

• Identificadores: IDENT. Comienzan por una letra (mayúscula o minúscula), seguida opcionalmente de cualquier cadena de letras y dígitos

• Constantes, que pueden ser de tres tipos:

  • Números enteros no negativos, es decir, cualquier cadena de dígitos: CENT.

  • Las constantes lógicas (true y false): CLOG.

  • Constantes de tipo string (cadenas de caracteres): CST. Necesariamente tienen que comenzar y terminar con el carácter comilla (") y entre las dos comillas puede haber cualquier cadena de caracteres que no contenga el símbolo comilla.

El lenguaje distingue mayúsculas y minúsculas; por lo tanto mientras print es una palabra clave, Print es un identificador y PRINT es otro identificador distinto del anterior.

Recuerde que también tiene que especificar en el fichero JLex que se deben reconocer y consumir (sin generar token) los espacios en blanco, tabuladores, saltos de línea y retornos de carro.

Para desarrollar el analizador léxico pedido lo único que hay que hacer es completar este esqueleto de fichero JLex en el que lo único que falta es definir para cada token a reconocer, la expresión regular asociada y la acción asociada. A modo de ejemplo, se proporciona ya definido el token para la palabra clave and.

Como puede observarse en la definición de la regla para la palabra clave and, lo que hay que hacer es:

1. Para cada token definir la expresión regular asociada, según el formato requerido por JLex (véase la documentación que se proporciona).
2. A continuación de la expresión regular definir la acción que se toma cuando se reconoce dicho token. Para los tokens que no tienen ningún dato asociado, escribiremos {return tok(sym.X, null); }, donde X es el nombre que se le ha dado al token en cuestión en el fichero CUP.

   Para los tokens que tienen un dato asociado, escribiremos {return tok(sym.X, obj); }, donde X es el nombre que se le ha dado al token en cuestión en el fichero CUP y obj es el objeto Java asociado al token. Para construir el objeto Java asociado a un token puede utilizar el método yytext(), tal y como se explica en la documentación de JLex.

   Como se explica en el manual de CUP y se ve en clase, un fichero CUP declara una lista de tokens, donde cada token es representado por un idendificador (por ejemplo, AND). Cuando se genera el analizador sintáctico a partir del fichero CUP, se producen como resultado 2 ficheros Java. Uno de ellos, que lleva por nombre sym.java contiene una clase llamada sym en la que simplemente se asocia un número entero a cada uno de los tokens que se han declarado en el fichero CUP. Por lo tanto, sym.X es el entero que utiliza la clase sym para identificar al token X.

3. En el caso de los espacios en blanco, saltos de línea, etc., escribiremos como acción { }, cuyo efecto es no devolver nada y seguir consumiendo caracteres de entrada para producir el siguiente token.

El analizador léxico deberá lanzar una excepción de tipo LexerException, que se proporciona, cuando se detecte un error léxico.

Definición de la sintaxis del lenguaje de programación fuente

A continuación vamos a dar la definición de la sintaxis del lenguaje fuente por medio de una gramática independiente del contexto. Como excepción, la sintaxis de las expresiones la daremos a continuación en leguaje natural.

Los tokens generados por el analizador léxico se corresponden con los símbolos terminales de la gramática que define el analizador sintáctico.

La gramática que define la sintaxis del lenguaje de programación fuente es la siguiente:

G=<ET, EN, S, P>
ET= {PC, ASOP, IF, THEN, ELSE, ENDIF, WHILE, PRINT, INT2STR, STR2INT,
BREAK, NOT, MENORQUE, MAS, MENOS, UMENOS, POR, DIV, AND, OR,
IGUALQUE, MAYORQUE, PAREN, TESIS, PROG, ABRELLAVE, 
CIERRALLAVE, COMA, VARS, TIPO, CENT, CLOG, CST, IDENT}

EN= {S, <LVar>, <Sent>, <Body>, <SentSimp>, <Asign>, <Cond>, 
    <Repet>, <Print>, <Exp>, <VDef>, <Decl>}

S= S

P= {
S -> PROG IDENT PAREN <LVar> TESIS <Body> 
       | PROG IDENT <Body>
       | PROG IDENT VARS <VDef> <Body>
       | PROG IDENT PAREN <LVar> TESIS VARS <VDef> <Body>

<VDef> -> <Decl> PC 
       | <Decl> PC <VDef>

<Decl> -> TIPO <LVar>

<LVar> -> IDENT
     |   IDENT COMA <LVar>

<Body> -> <Sent>

<SentSimp> -> Asign PC
	|   Cond
	|   Repet
        |   Print PC 
	|   BREAK CENT PC

Print-> PRINT PAREN <Exp> TESIS

Asign-> IDENT ASOP <Exp>

Cond-> IF <Exp> THEN <Sent> ENDIF 
    |   IF <Exp> THEN <Sent> ELSE <Sent> ENDIF 

Repet-> WHILE <Exp> <Sent>
}

NOTA: no se proporcionan, intencionadamente, reglas de producción que tengan a <Sent> como antecedente. Deberá definirlas usted (puede ser necesario añadir algún símbolo no terminal auxiliar). <Sent> representa una sentencia o bien una lista de una o más sentencias entre llaves.

Expresiones en el lenguaje de programación fuente

Las expresiones del lenguaje de programación fuente (identificadas en la gramática con el símbolo no terminal <Exp>) deben ajustarse a lo siguiente:

Expresiones sin tipo definido:

• Un identificador que sea el nombre de una variable. Será del tipo de la variable.

• Una expresión entre paréntesis. Será del tipo de la expresión contenida dentro de los paréntesis.

Expresiones de tipo int:

• Una constante expresada en decimal.

• Una suma, resta, multiplicación o división de expresiones de tipo int utilizando los operadores habituales "+", "-", "*", "/".

• El opuesto de una expresión de tipo int, utilizando el símbolo habitual "-" antes de la expresión.

• Una expresión que pertenezca al lenguaje definido por la expresión lingüística Str2Int "(" <Exp> ")", donde la subexpresión entre paréntesis ha de ser de tipo string. El resultado de evaluar esta expresión será el número entero que se obtendría en Java al invocar el método Integer.parseInt sobre el dato que se obtendría al evaluar la subexpresión de tipo string.

Expresiones de tipo string:

• Una constante que se representa como cualquier cadena de símbolos entre comillas ("), donde la cadena de símbolos no debe de contener la comilla.

• Concatenaciones de expresiones de tipo string utilizando el operador "+".

• Una expresión que pertenezca al lenguaje definido por la expresión lingüística Int2Str "(" <Exp> ")" , donde la subexpresión entre paréntesis ha de ser de tipo int. El resultado de evaluar esta expresión será una cadena de caracteres que represente el número entero que se obtendría al evaluar la subexpresión de tipo int en base decimal.

Expresiones de tipo bool:

• Las constantes true y false.

• La conjunción o disyunción de expresiones lógicas, utilizando los operadores and y or respectivamente.

• Una expresión lógica negada, utilizando el operador not antes de la expresión lógica.

• La igualdad entre 2 expresiones utilizando el operador "=". Las dos expresiones comparadas deberán de ser del mismo tipo.

• La comparación entre 2 expresiones de tipo int utilizando los operadores "<" (menor que) o ">" (mayor que).

Reglas de precedencia

La precedencia de los operadores es, de menor a mayor:

1. or
2. and
3. not
4. =
5. < y >
6. + y -
7. * y /
8. - (opuesto)

Todos los operadores asocian por la derecha.

Tal y como se realiza en un compilador habitualmente, en la fase de análisis semántico se debe comprobar que el programa fuente se ajusta a todas las especificaciones del lenguaje de programación fuente que no hayan podido ser comprobadas en la fase de análisis sintáctico. A estos efectos, se debe entender que la descripción del lenguaje fuente realizada anteriormente forma parte de dichas especificaciones, y por lo tanto, el analizador semántico deberá comprobar que el programa fuente se ajusta a todo lo indicado y que no se haya verificado en la fase de análisis sintáctico.

Esto aplica particularmente a las comprobaciones de tipos de las expresiones. Las expresiones que combinan una o 2 subexpresiones se deberán ajustar a lo indicado anteriormente. Por ejemplo, de acuerdo con lo indicado anteriormente, una expresión que combine una subexpresión de tipo int con otra subexpresión de tipo string por medio del operador '+' debería producir un error de tipo, detectado en la fase de análisis semántico.

• No se deben declarar en el programa fuente 2 variables con el mismo nombre (incluida la o las variables que se declaran en la cabecera del programa y que se utilizan para que el programa pueda recibir argumentos al ser ejecutado).

• Todas las variables utilizadas en un programa deberán haber sido declaradas.

• En una sentencia condicional (if), la expresión debe ser de tipo bool, mientras que las sentencias que forman parte de la sección then y de la sección else no deben tener errores de tipo.

• En una sentencia bucle (while), la expresión debe ser de tipo bool, mientras que las sentencias que forman el cuerpo del bucle no deben tener error de tipo.

• En una sentencia de asignación, el tipo de la variable en la parte izquierda de la asignación y el tipo de la expresión en la parte derecha debe ser el mismo.

• La sentencia break (permite salir abruptamente de un bucle), no debe aparecer fuera de una sentencia while (esto deberá comprobarse si no se hizo en la fase de análisis sintáctico).

• En una sentencia break, su argumento debe ser mayor que 0 y menor o igual al número de bucles while anidados que la contienen.

• La expresión que se le pasa como argumento a una sentencia print debe ser de tipo string.

El analizador semántico debe lanzar una excepción, que no debe ser capturada, cuando se detecte un error semántico. La clase o clases utilizadas para las excepciones correspondientes a errores semánticos se pueden definir libremente, pero deben extender la clase CompilerExc, incluida en el fichero Errors.zip. Se valorará que los mensajes que se generen identiifiquen claramente el error producido.

Comportamiento esperado de la ejecución de un programa fuente

La ejecución de un programa fuente consiste en la ejecución de la secuencia de instrucciones que lo forman. El comportamiento de las instrucciones de asignación, condicional (if...then) y bucle (while...) es análogo al de sus equivalentes en lenguaje Java. El comportamiento de la sentencia break se explicó anteriormente. El comportamiento de la sentencia print es equivalente al del método System.out.println de Java. El comportamiento de las expresiones se explicó anteriormente.

Se supone que las variables al declararse (incluyendo, si los hubiera, los argumentos del programa) se inicializan por defecto a los siguientes valores:

• Variables tipo int: 0.

• Variables tipo string: "".

• Variables tipo bool: false.

El código Java generado por el compilador deberá cumplir lo siguiente:

• El resultado de traducir un programa fuente consistirá en una o varias clases Java, que se dejarán en el directorio desde el que se ejecuta el compilador.

• De entre las clases Java generadas, existirá una que se utilizará para ejecutar el código Java generado, cuyo nombre se le pasará al compilador en un argumento al invocarlo, según se explica más adelante. Por lo tanto, dicha clase Java deberá contener un método main

• El programa obtenido con el compilador se ejecutará de la siguiente forma:

  java <nombre_clase_generada> [<argumento1> <argumento2> ...]

  Los argumentos son opcionales. Los argumentos se utilizan para pasárselos al programa a ejecutar en las variables que se definen en la cabecera del programa. Los argumentos se guardan en las variables según el orden en que éstas se declaran. Por ejemplo, supongamos que tenemos un programa en lenguaje PF2011, cuya cabecera es:

  PF2011 Ejemplo(arg1, arg2, arg3)

  Supongamos que al traducir este programa a Java la clase que se utiliza para ejecutar el código generado se llama EjemMain. Supongamos que ejecuto dicha clase Java, pasándole 2 argumentos, de la siguiente forma:

  java EjemMain Hola Mundo

  El efecto de esta ejecución es que las variables en la cabecera del programa se inicializan de la siguiente forma: arg1="Hola", arg2="Mundo" y arg3="". Nótese que por lo tanto no es un error que se pasen menos argumentos que variables se declaran en la cabecera, sino que las variables a las que no se les asigna un argumento se inicializan a "". Tampoco es un error pasar más argumentos que variables hay en la cabecera; los argumentos que sobren simplemente se ignoran.

Para esta práctica se deberá desarrollar una clase Main. La ejecución de dicha clase se realizará de acuerdo con lo siguiente:

java Main <nombre_fichero> <nombre_clase_generada>

Donde <nombre_fichero> es el nombre del fichero (con el path si es necesario) del programa fuente a traducir y <nombre_clase_generada> es el nombre de la clase Java generada al ejecutar el compilador que contiene su propio método main.

El programa deberá de levantar una excepción que no deberá ser capturada en el caso de que el programa fuente tenga algún error léxico, sintáctico o semántico. Si el programa fuente no contiene errores, el compilador debe depositar en el directorio actual uno o varios ficheros que contendrán la o las clases Java generadas para el programa fuente.

Obligatoriamente las clases generadas por CUP deberán pertenecer a un paquete llamado Parser y la clase generada por JLex deberá pertenecer a un paquete llamado Lexer.

Las clases Java que desarrolle en esta práctica obligatoriamente deberán estar organizadas en los siguientes paquetes:

• Paquete Errors, que debe contener todas las excepciones utilizadas (incluidas las clases proporcionadas en la práctica 1). Si las excepciones utilizasen alguna clase auxiliar, dicha clase deberá pertenecer asimismo a ese paquete.

• Paquete AST, contendrá todas las clases necesarias para representar árboles de sintaxis abstracta correspondientes a programas del lenguaje de programación fuente.

• Paquete Compiler, contendrá cualquier otra clase que necesite el compilador, incluyendo las de la tabla de símbolos.

• Opcionalmente, paquete GeneratedCodeLib, que contendrá las clases Java que usted desarrolle para que sean utilizadas por el código generado (si es que éstas existen).

La clase Main no pertenecerá a ningún paquete.

Orden de compilación

Antes de entregar la práctica deberá cerciorarse de que su práctica puede compilarse correctamente con javac siguiendo el siguiente orden:

1. Clases del paquete Errors.

2. Clases del paquete GeneratedCodeLib (si es que éstas existen).

3. Clases del paquete Compiler.

4. Clases del paquete AST.

5. Clases parser y sym generadas por CUP.

6. Clase Yylex generada por JLex.

7. Clase Main.

Aquellas prácticas que no se puedan compilar en este orden serán calificadas con 0.

Se proporciona un juego de tests con el que probar la práctica. De entre ellos solamente deberían de producir un error los tests en carpetas cuyo nombre comienza por ErrSem, ErrSint y ErrLex. Puede ocurrir que alguno de los ejemplos ErrLex de error de sintaxis (y no léxico). Los tests de las carpetas cuyo nombre comienza por ErrSem deberían producir un error semántico.

Las carpetas que contienen programas fuente que no tienen errores (es decir, carpetas cuyo nombre empieza por Ejem) contienen además un fichero de nombre ejecucion.txt que contiene el resultado esperado de una o varias ejecuciones (con diferentes argumentos) de la o las clases Java generadas para el programa fuente contenido en la carpeta.

Se advierte que se realizarán tests adicionales a los proporcionados a las prácticas recibidas, por lo que se recomienda a los alumnos que planifiquen tests complementarios a su práctica.

Se deberán entregar exclusivamente los siguientes ficheros:

• fichero Yylex en formato JLex para el analizador léxico

• fichero parser en formato CUP para el analizador sintáctico

• fichero java.zip, que al descomprimirlo genere una carpeta de nombre java cuyo contenido debe ser exactamente el siguiente:

  • fichero Main.java que contenga la clase Main.

  • Carpeta Errors que contenga las clases Java del paquete Errors (proporcionar ficheros Java, no ficheros .class).

  • Carpeta Compiler que contenga las clases Java del paquete Compiler (proporcionar ficheros Java, no ficheros .class).

  • Carpeta AST que contenga las clases Java del paquete AST (proporcionar ficheros Java, no ficheros .class).

  • Opcionalmente, carpeta GeneratedCodeLib que contenga las clases Java del paquete GeneratedCodeLib (proporcionar ficheros Java, no ficheros .class).