Università degli Studi di Firenze, Scuola di Ingegneria – Corso di Laurea in Ingegneria Informatica – Prof.
Stefano Berretti
Fondamenti di Informatica
PRIMA PROVA IN ITINERE – 23 novembre 2021
Esercizio 1. (5 punti) (codifica operandi 1pt ciascuno, somma 2 pt, discussione 1pt)
Date la dichiarazione int x, y; e le istruzioni x=-125; e y=-6; scrivere la codifica binaria di x e y e la loro
somma. Ipotizzare che la rappresentazione del tipo int sia su 8 bit. Discutere il risultato ottenuto.
Esercizio 2. (5 punti) (operazioni da e verso la memoria 3pt, logica 2pt)
Tradurre in codice assembler MIPS la seguente istruzione C: *(X+i) -= Y[++j]; nell’ambito delle seguenti
dichiarazioni ed istruzioni:
int X[20], Y[20], *ptr, i, j;
ptr = X;
Ipotizzare che le variabili siano allocate in memoria a partire dall'indirizzo 200.
Esercizio 3. (10 punti) (verifica legalità 5pt, produzioni 2 pt, semantica 3pt)
Data la seguente istruzione:
position = &(ptr->buffer[*position].next);
nell’ambito delle seguenti dichiarazioni e definizioni
struct list { struct record * buffer;
… };
struct record { int value;
int next; };
struct list * ptr;
int * position;
verificarne la legalità riportando anche le produzioni della grammatica C utilizzate nella riduzione. Discutere la
semantica dell’istruzione.
Esercizio 4. (10 punti) (prototipo e parametri formali 3 pt, allocazione 2pt, logica 5 pt)
Scrivere la funzione C che riceve in ingresso un array di valori interi V, la sua dimensione N, ed un intero
0<=N1<=N, ed opera nel modo seguente:
• Considera uno ad uno i valori di V con indice da N1 ad N-1 e verifica se sono presenti nei primi N1-1
elementi di V;
• Alloca un array di valori Booleani A e lo assegna in modo tale che A[i] è TRUE se V[N1+i] è presente tra
gli elementi in V con indice tra 0 e N1-1, FALSE altrimenti;
• Restituisce tra i parametri formali della funzione l’array A.
(Esempio: V = {4, 2, 2, 5, 2, 6, 1}, N = 7, N1 = 4 --> A = {TRUE, FALSE, FALSE})
Università degli Studi di Firenze, Scuola di Ingegneria – Corso di Laurea in Ingegneria Informatica – Prof. Stefano Berretti
Soluzione
Esercizio 1.
Il valore -125 è rappresentato su 8 bit in notazione 2C come segue:
+125 in forma binaria su 8 bit 01111101
Complemento ad 1 10000010+
1
Complemento a 2 10000011 rappresentazione 2C del valore -125
Il valore -6 è rappresentato su 8 bit in notazione 2C come segue:
+6 in forma binaria su 8 bit: 00000110
Complemento ad 1: 11111001 +
1
Complemento a 2 11111010 rappresentazione 2C del valore -6
La somma è eseguita tra le rappresentazioni 2C: 10000011 +
11111010 =
01111101 numero positivo in 2C avendo il MSB a 0 (il riporto
non viene considerato)
Il risultato è perciò 01111101 che in decimale risulta: +125.
Il risultato non è quello atteso dato che è stato superato il minimo valore negativo rappresentabile con 8 bit in 2C (-128).
L’aritmetica produce un risultato passando dal minimo valore negativo al massimo valore positivo.
Esercizio 2. (5 punti)
Istruzione C: *(ptr+i) -= Y[++j];
addi $1, $0, 0 // indice i
addi $2, $0, 0 // indice j
….
lw $3, 200[$1] // carica *(X+i) nel registro $3. Aritmetica dei puntatori
addi $2, $2, 1 // incremento prefisso dell’indice j
lw $4, 280[$2] // carica Y[j] nel registro $4
sub $3, $3, $4 // sottrae il valore contenuto in $4 dal valore contenuto in $3
sw $3, 200[$1] // salva il contenuto del registro $3 in memoria centrale
….
Esercizio 3. (10 punti)
Albero sintattico:
position = &(ptr->buffer[*position].next);
<id> = &(<id> -> <id>[*<id>].<id>);
<var> = &(<var> -> <id>[*<id>].<id>);
<var> = &(<expr> -> <id>[*<id>].<id>);
<var> = &(<var>[*<var>].<id>);
<var> = &(<expr>[*<expr>].<id>);
<var> = &(<expr>[<var>].<id>);
Università degli Studi di Firenze, Scuola di Ingegneria – Corso di Laurea in Ingegneria Informatica – Prof. Stefano Berretti
<var> = &(<expr>[<expr>].<id>);
<var> = &(<var>.<id>);
<var> = &(<var>);
<var> = &<var>;
<var> = <expr>;
<expr>;
<statement>
L'istruzione è legale dato che è possibile passare dai simboli terminali al simbolo iniziale <statement>.
Produzioni della grammatica usate nella derivazione dell’albero sintattico:
<var> ::= <id> | (<var>) | *<expr> | <expr>[<expr>] | <expr>-><id> | <var>.<id>
<expr> ::= <var> | &<var> | <var>=<expr> |
<statement> ::= <expr>;
La semantica di un’istruzione elementare consiste nell’eseguire l’espressione che precede il ; applicandone la semantica e
nel cedere il controllo del flusso di esecuzione all’istruzione seguente. A sua volta la semantica dell’espressione è data dal
valore restituito e dai side effect. Il valore restituito dall’espressione è il valore della variabile position nel tipo di un
puntatore a int. L’espressione produce un side effect sulla variabile position assegnandola con l’indirizzo del campo
next dell’elemento *position dell’array di dati strutturati buffer di tipo record a sua volta campo del dato
strutturato ptr di tipo list.
Esercizio 4.
#define TRUE 1
#define FALSE 0
typedef unsigned short int Boolean;
Boolean array_include_values(int * V, int N, int N1, Boolean ** A) {
int positiom, count;
Boolean found;
*A = (Boolean *) malloc(sizeof(Boolean)*(N-N1));
if ( *A == NULL )
return FALSE;
// verifica inclusione ultimi N-N1 elementi di V nei primi N1 elementi
for( position=0; position<N-N1; position++ ) {
found = FALSE;
count = 0;
while( count < N1 && found == FALSE ) {
if( V[N1+position] == V[count] )
found = TRUE
else
count++;
}
(*A)[position] = found;
}
return TRUE;
}
