Prácticas de Procesadores de Lenguaje

Curso 2007/2008

Enunciado de la convocatoria de septiembre

Objetivo de la Práctica

• Esta práctica tiene como objetivo el desarrollo de un compilador cuyo núcleo principal coincide con el que se ha desarrollado durante el curso. Las diferencias con él se detallan a continuación.

Nuevas características del lenguaje de programación ALFA

Tipo puntero

• En la nueva versión del lenguaje no se utilizará este tipo de dato.

Cambios en las estructuras de control de flujo de programa

• En la nueva versión del lenguaje no están contempladas las siguientes estructuras:
  • Sentencia DESDE-HASTA.
  • Sentencia de SELECCIÓN.

Funciones

• Se recuerda que el compilador desarrollado durante el curso excluyó la implementación de funciones. Dicha exclusión se mantiene para la convocatoria de septiembre.

Vectores

• En la nueva versión del lenguaje se añaden vectores de tres dimensiones según la notación reflejada en la gramática que acompaña a este enunciado.
• Se añaden también las siguientes operaciones sobre vectores:
  • Suma de vectores de cualquier dimensión.
  • Producto (elemento a elemento) de vectores de cualquier dimensión.
  • Copia de un vector en otro.
• La sintaxis de estas operaciones se describe en la gramática que acompaña este enunciado.
• La semántica de estas operaciones se describe con más detalle posteriormente.

Nuevo tipo de dato "conjunto"

• Un conjunto es una colección de elementos que tiene las siguientes propiedades:

1. Todos los elementos son de tipo entero.
2. Los elementos no mantienen una relación de orden.
3. No hay elementos repetidos.
4. Inicialmente un conjunto está vacío (tiene 0 elementos)
5. El tamaño máximo de un conjunto es de 64 elementos.

• La declaración de conjuntos se describe en la gramática que acompaña este enunciado.
• Se añaden también las siguientes operaciones sobre conjuntos:
  • Unión.
  • Intersección.
  • Inserción.
  • Vaciado.
  • Tamaño.
  • Pertenencia.
• La sintaxis de estas operaciones se describe en la gramática que acompaña este enunciado.
• La semántica de estas operaciones se describe con más detalle posteriormente.

Nuevas sentencias de entrada / salida

• En la nueva versión del lenguaje se permite la escritura de vectores y conjuntos según la sintaxis descrita en la gramática adjunta.
• La semántica de estas nuevas sentencias se describe con más detalle posteriormente.

Restricciones semánticas

Comprobaciones semánticas relacionadas con los tipos básicos de datos

• En la nueva versión del lenguaje está permitido que en las expresiones y comparaciones se mezclen subexpresiones de diferente tipo básico si se siguen las siguientes indicaciones:
  • El valor lógico de una expresión entera se calcula de la siguiente manera:
    • Si el valor entero es 0, le corresponde el valor lógico falso.
    • En otro caso, le corresponde el valor lógico verdadero. 
  • Asimismo el valor entero de un expresión lógica se calcula de la siguiente manear:
    • El valor entero de una expresión lógica falsa es 0.
    • El valor entero de una expresión lógica verdadera es 1.

Vectores

• Para los vectores de tres dimensiones hay que realizar el mismo tipo de comprobaciones semánticas que para los vectores de 1 y 2 dimensiones. 

• Al indexar un vector de 3 dimensiones debe suponer que cada posición de índice tiene el siguiente significado:
  • La primera posición está asociada con la "tercera dimensión" (es decir, cada valor concreto del primer índice identifica un vector de 2 dimensiones)
  • La segunda corresponde a las filas (dentro del vector de 2 dimensiones determinado por el primer índice)
  • La tercera corresponde a las columnas.
• La suma y producto de vectores están sujetos a las siguientes restricciones:
  • Como puede observarse en la gramática, estas operaciones especifican una lista de tres identificadores, el primero almacenará el resultado de la operación, Los otros dos son, respectivamente, el primer y el segundo operandos.
  • Los tres identificadores tienen que haber sido declarados como vectores de tipo entero con la misma dimensión y con el mismo tamaño por cada dimensión.
  • La suma o el producto se realizan elemento a elemento.
• La copia de vectores está sujeta a las siguientes restricciones:
  • Como puede observarse en la gramática, la copia especifica una lista de dos identificadores, tras la operación, el primero almacenará una copia del segundo.
  • Los dos identificadores tienen que haber sido declarados como vectores con la misma dimensión y con el mismo tamaño por cada dimensión.

Conjuntos

• La unión y la intersección de conjuntos están sujetos a las siguientes restricciones:
  • Como puede observarse en la gramática, estas operaciones especifican una lista de tres identificadores, el primero almacenará el resultado de la operación, Los otros dos son, respectivamente, el primer y el segundo operandos.
  • Los tres identificadores tienen que haber sido declarados como conjuntos. Respecto a sus capacidades máximas deben comprobarse las siguientes restricciones semánticas:
    • Para la unión, el primero de los conjuntos (el que almacenará el resultado) debe tener una capacidad máxima mayor o igual que la suma de las capacidades máximas de los operandos.
    • Para la intersección, el conjunto resultado debe tener una capacidad máxima mayor o igual que el mínimo de las capacidades máximas de los operandos.
  •  El resto de la semántica de las operaciones es la de la unión e intersección de conjuntos habitual en matemáticas.
• La inserción de una expresión en un conjunto está sujeta a las siguientes restricciones:
  • La expresión tiene que ser de tipo entero.
  • El conjunto tiene que estar declarado.
  • Si el conjunto no tiene espacio suficiente (está lleno antes de la inserción) para hacer la inserción debe detectarse en tiempo de ejecución y salir del programa de manera controlada.
  • Se insertará el valor de la expresión teniendo en cuenta la semántica de la operación de conjuntos habitual en matemáticas: si la expresión ya está en el conjunto, tras la inserción el conjunto realmente no cambia.
• Vaciar un conjunto significa asignar 0 como el número de elementos que contiene.
• El tamaño de un conjunto se refiere al número de elementos que contenga (y no a la capacidad máxima especificada en su declaración) y, por tanto, es de tipo entero.. 
• La condición de pertenencia de una expresión a un conjunto está sujeta a las siguientes restricciones:
  • La expresión tiene que ser de tipo entero.
  • El conjunto tiene que estar declarado.
  • La condición de pertenencia de una expresión a un conjunto es de tipo lógico.
  • El resto de la semántica de esta operación es la habitual en matemáticas.

Nuevas sentencias de entrada / salida

• En la página web del laboratorio el alumno puede encontrar una nueva versión de la librería io.o en la que se ha añadido una nueva función que permite imprimir por la salida estándar un espacio en blanco. El nombre de esta función es "imprime_blanco" y se invoca de manera similar a la función "imprime_fin_linea".
• Es necesario utilizar esta función para conseguir los formatos de salida que se describen a continuación:
• Escritura de un conjunto
  • Se escribirán todos lo elementos en la misma línea separados por un espacio en blanco.
• Escritura de un vector
  • Los vectores de una dimensión se escribirán en una línea separando los elementos por un espacio en blanco.
  • Los vectores de dos dimensiones se escribirán en forma de tabla, con cada fila en una línea diferente con los elementos separados por un espacio en blanco.
  • Loas vectores de tres dimensiones se escribirán como una secuencia de tablas separadas (cada una de las tablas) por dos saltos de línea.

Evaluación de la práctica

La normativa de evaluación que se aplicará está publicada en la página web del laboratorio de Procesadores de Lenguaje.

Entrega de la práctica

Las normas de entrega de la práctica también se describirán en la página web del laboratorio de Procesadores de Lenguaje.

Sugerencias

Se sugiere al alumno que escriba un fichero compatible con la herramienta make y con el nombre makefile que para el objetivo all genere el ejecutable de nombre alfa.

 

IMPORTANTE: Se sugiere al alumno que implemente un método que garantice que la interrupción de cualquier programa debido a un error "controlado" en tiempo de ejecución gestione de manera correcta la pila eliminando de la misma cualquier residuo antes de terminar la ejecución. Una posible implementación sería declarar una variable en ensamblador ( __esp resd 1) en la cual se almacene el puntero de pila al inicio del programa (mov dword [__esp] ,esp )  y en la etiqueta "final" utilizada como destino de salto de todos los errores controlados en tiempo de ejecución restaurar el puntero de pila que se guardó al inicio del programa (mod dword esp, [__esp]). La variable __esp tiene dos guiones bajos como primeros caracteres (en lugar de uno solo) para evitar el error que se produciría si en un programa ALFA hubiera declarada una variable de nombre "esp".

 

Gramática del Lenguaje de Programación ALFA

1:	<programa>	::=	INICIO <declaraciones> <sentencias> FIN
2:	<declaraciones>	::=	<declaracion>
3:		|	<declaracion> <declaraciones>
4:	<declaracion>	::=	<clase> <identificadores> ;
5:	<clase>	::=	<clase_escalar>
7:		|	<clase_vector>
8:		|	<clase_conjunto>
9:	<tipo>	::=	ENTERO
10:		|	LOGICO
11:	<clase_escalar>	::=	<tipo>
12:	<clase_conjunto>	::=	CONJUNTO DE <constante_entera>
13:	<clase_vector>	::=	VECTOR <tipo> DE <constante_entera>
14:		|	VECTOR <tipo> DE <constante_entera> POR <constante_entera>
15:		|	VECTOR <tipo> DE <constante_entera> POR <constante_entera> POR <constante_entera>
16:	<identificadores>	::=	<identificador>
17:		|	<identificador> , <identificadores>
18:	<sentencias>	::=	<sentencia>
19:		|	<sentencia> ; <sentencias>
20:	<sentencia>	::=	<asignacion>
21:		|	<condicional>
22:		|	<bucle>
23:		|	<lectura_escritura>
24:		|	<operacion_vector>
25:		|	<operacion_conjunto>
26:	<asignacion>	::=	<identificador> = <exp>
27:		|	<elemento_vector> = <exp>
28:	<elemento_vector>	::=	<identificador> [ <exp> ]
29:		|	<identificador> [ <exp> , <exp> ]
30:		|	<identificador> [ <exp> , <exp> , <exp> ]
31:	<condicional>	::=	SI <exp> ENTONCES <sentencias> FIN
32:		|	SI <exp> ENTONCES <sentencias> SINO <sentencias> FIN
33:	<bucle>	::=	MIENTRAS <exp> HACER <sentencias> FIN
34:	<lectura_escritura>	::=	LEER <identificador>
35:		|	LEER <elemento_vector>
36:		|	ESCRIBIR <exp>
37:		|	ESCRIBIRN <identificador>
38:	<operacion_vector>	::=	SUMA(<identificador>, <identificador>, <identificador>)
39:		|	POR(<identificador>, <identificador>, <identificador>)
40:		|	COPIA( <identificador>, <identificador>)
41:	<operacion_conjunto>	::=	UNION(<identificador>, <identificador>, <identificador>)
42:		|	INTERSECCION(<identificador>, <identificador>, <identificador>)
43:		|	INSERCION( <exp>, <identificador>)
44:		|	VACIAR( <identificador>)
45:	<exp>	::=	<exp> + <exp>
46:		|	<exp> - <exp>
47:		|	<exp> / <exp>
48:		|	<exp> * <exp>
49:		|	- <exp>
50:		|	<exp> Y <exp>
51:		|	<exp> O <exp>
52:		|	NO <exp>
53:		|	<identificador>
54:		|	<constante>
55:		|	( <exp> )
56:		|	( <comparacion> )
57:		|	<elemento_vector>
58:		|	TAMANIO(<identificador>)
59:		|	PERTENECE(<exp>, <identificador>)
60:	<comparacion>	::=	<exp> == <exp>
61:		|	<exp> != <exp>
62:		|	<exp> <= <exp>
63:		|	<exp> >= <exp>
64:		|	<exp> < <exp>
65:		|	<exp> > <exp>
66:	<constante>	::=	<constante_logica>
67:		|	<constante_entera>
68:	<constante_logica>	::=	VERDADERO
69:		|	FALSO
70:	<constante_entera>	::=	<numero>
71:	<numero>	::=	<digito>
72:		|	<numero> <digito>
73:	<identificador>	::=	<letra>
74:		|	<letra> <cola_identificador>
75:	<cola_identificador>	::=	<alfanumerico>
76:		|	<alfanumerico> <cola_identificador>
77:	<alfanumerico>	::=	<letra>
78:		|	<digito>
79:	<letra>	::=	a | b | ... | z | A | B |...| Z
90:	<digito>	::=	0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9