Domande teoriche compiti precedenti Fondamenti di informatica

La Visibilità di una variabile rappresenta la sezione di codice in cui il nome introdotto per quella variabile

può essere utilizzato per referenziarla.

Si illustrino, anche attraverso degli esempi, le tecniche di legame dei parametri per valore e per riferimento.

Il legame tra i parametri può avvenire per valore e per riferimento.

Nel caso del legame per valore il parametro attuale è un’espressione, al momento della chiamata viene

creata una variabile temporanea che viene inizializzata con il valore restituito dal corrispondente

parametro attuale. La funzione chiamata non ha accesso alla variabile della funzione chiamante perché non

vengono prodotti side effects sulle variabili, quindi si può passare come parametro attuale il valore

dell’indirizzo di una variabile. La funzione chiamata utilizza quindi quell’indirizzo attraverso l’operatore di

de-referenziazione * per modificare la variabile.

Nel caso, invece, del legame per riferimento il parametro attuale è un riferimento a variabile. Ogni

riferimento ad un parametro formale fatto dalla funzione chiamata colpisce direttamente la relativa

variabile identificata dal parametro attuale quindi la funzione chiamante e la funzione chiamata

condividono le variabili specificate come parametri attuali.

Si descriva cosa è una grammatica e si discutano le regole attraverso le quali essa definisce un linguaggio.

La grammatica definisce la sintassi e permette anche di definire in maniera non ambigua la semantica. In

particolare ogni linguaggio è definito da una grammatica solitamente rappresentata da una quadrupla: G =

V, N, S, P dove è il vocabolario, è un insieme i cui elementi sono detti categorie sintattiche, è un

elemento di e è l’insieme delle produzioni. Le regole attraverso cui la grammatica definisce un

: “un

linguaggio sono la derivazione diretta e indiretta e la definizione stessa di linguaggio linguaggio LG

⟨, , , ⟩ ∗

definito dalla grammatica = sul vocabolario è l’insieme degli elementi di che derivano

”.

dal simbolo iniziale attraverso le categorie sintattiche e le produzioni

Si descriva e si discuta il formato di rappresentazione dei numeri interi, con e senza segno, del linguaggio c.

I numeri interi vengono rappresentati mediante un numero di byte dipendenti dall’architettura del

processore, in particolare: unsigned int rappresenta gli interi senza segno e viene rappresentato su N bit di

memoria che variano a seconda dell’architettura del processore (tipicamente, 32 o 64 bit). Per = 32 bit si

−32

2 − 1

possono rappresentare gli interi compresi tra 0 e ; Int rappresenta gli interi con segno e viene

rappresentata su V bit tramite la rappresentazione «Complemento a 2» , in cui però il Most Significant Bit

ha peso negativo.

Si illustri cosa è una lista, si discutano le operazioni che possono essere eseguite su di essa, e se ne descriva

la rappresentazione in forma collegata con puntatori. Non è richiesta l'implementazione delle funzioni

elementari

Una lista è una successione finita di valori di un tipo. L’informazione che questo codifica consiste di due

componenti: il multi-insieme dei valori e la relazione di ordine tra i valori stessi. Una lista è qualificata dalle

operazioni che vi si possono eseguire all’interno: l’inserimento che aggiunge un nuovo valore alla lista, il

valore essere inserito in testa, in coda, o in una posizione intermedia determinata da un qualche criterio di

posizionamento; la cancellazione rimuove un elemento dalla lista; la visita applica un trattamento comune

a tutti gli elementi della lista; la ricerca determina se la lista contiene un elemento qualificato da una

condizione sul valore. Tipicamente restituisce vero/falso, ma può anche restituire l’indirizzo o la posizione

dell’elemento cercato; l’inizializzazione è un metodo che non corrisponde ad alcuna operazione, se non

quella di fare da costruttore che inizializza la particolare rappresentazione concreta della lista.

Una lista può inoltre essere rappresentata in forma sequenziale o quella collegata tramite puntatori. In

particolare di quest’ultima forma esistono due ulteriori varianti che si differenziano a seconda che

l'informazione sul successore sia codificata usando gli indici di un vettore o i puntatori a un insieme di

variabili. La rappresentazione collegata con arrays e indici memorizza i valori su un buffer e virtualizza la

relazione di sequenza dei valori. Nella struttura di lista si possono osservare informazioni sulla dimensione

dell'array, l'indice dell'elemento dell'array che contiene il primo valore della lista, l'indice di un elemento

libero dell'array a partire dal quale sono concatenati tutti gli elementi liberi dell'array.

Si descriva cosa si intende per array nel linguaggio c e si illustri come esso è dichiarato e referenziato.

Un array è un insieme di variabili dello stesso tipo che possono essere dichiarate collettivamente oppure

essere referenziate attraverso un nome collettivo e un indice numerico che le distingue tra loro. V , oltre

ad essere il nome della variabile array, rappresenta anche l'indirizzo di memoria a partire dal quale l'array è

memorizzato.

L’array è dichiarato: < > < > [< >] dichiara un array di un numero < > di entità del

tipo che sarebbe dichiarato da < > < > e associa all’array il nome che sarebbe associato all’entità

dichiarata da < > < >. Le singole variabili dell’array possono essere referenziate combinando il

nome con un indice (un numero intero non negativo), espresso tra parentesi quadre, che numera gli

elementi dell’array a partire da 0.

Si illustrino le istruzioni di iterazione e condizionali del linguaggio c.

Sono le istruzioni che permettono di rieseguire in maniera ripetitiva un corpo di istruzioni fino al verificarsi

di una certa condizione sui valori delle variabili del programma. Sono tre (equivalenti dal punto di vista

semantico):

· Ciclo FOR: esecuzione ripetitiva di un corpo di istruzioni sotto il controllo di una guardia costituita

da 3 espressioni: assegnamento, guardia, incremento. L’assegnamento viene eseguito una sola

volta, ad ogni iterazione viene testata l’espressione di guardia e, se la condizione è verificata, viene

eseguito il corpo, l’espressione incremento e si torna al punto di ingresso dell’iterazione. Se

restituisce falso, l’iterazione termina e si passa all’istruzione successiva.

· Ciclo WHILE: esecuzione ripetitiva di un corpo di istruzioni fintanto che un’espressione di guardia

restituisce un valore VERO. La guardia viene eseguita, poi se il valore è vero viene eseguito il corpo

e l’esecuzione ritorna all’ingresso della guardia; se è falso il controllo passa all’istruzione successiva.

· Ciclo DO – WHILE: esecuzione simile al ciclo WHILE, ma con la condizione di guardia in coda al

corpo delle istruzioni invece che in testa. Prima si esegue il corpo, poi se la guardia restituisce un

vero si torna ad eseguire il corpo, se restituisce un falso si passa all’istruzione successiva.

Istruzioni condizionali: permettono di decidere direzioni diverse nel flusso di esecuzione di un’istruzione

(corpo) del programma in base al valore restituito da un’espressione di controllo (guardia).

Sono: la Clausola IF: condiziona il corpo alla guardia (se il corpo restituisce un vero allora viene eseguita

l’istruzione, in caso contrario si passa all’istruzione successiva); la Clausola IF-ELSE: permette di avere due

corpi alternativi che vengono eseguiti a seconda che la guardia restituisca un vero o un falso.

Si discutano sintassi e semantica delle espressioni in linguaggio c.

Un linguaggio viene definito mediante la sintassi che determina e classifica cosa può apparire in

un’espressione legale del linguaggio e la semantica che definisce il significato di ogni classe di espressioni

legali. Parti della sintassi sono il vocabolario (insieme di simboli terminali che possono apparire in

∗

un’espressione legale),l’universo linguistico di un vocabolario (insieme di tutte le possibili sequenze

) e il ∗ ⊆ ∗

finite di simboli in linguaggio (sottoinsieme di con ). Entrambe vengono definite dalla

grammatica.

Si discutano i componenti della CPU del processore MIPS R4000.

È formato da 5 blocchi funzionali fondamentali la Memoria che contiene una sequenza lineare di locazioni

di 1 byte che possono essere lette o scritte durante la computazione; il Program Counter (PC): registro a 32

bit che contiene l’indirizzo dell’istruzione corrente, il Banco dei registri: Permette la lettura contemporanea

di due registri e la scrittura di un terzo; il Control Unit (CU): riceve in ingresso un segnale di 6 bit che

codifica l’operazione da eseguire e Genera in uscita vari segnali di controllo che pilotano il funzionamento

dei componenti della CPU. L’Arithmetic Logic Unit (ALU): esegue le operazioni aritmetico-logiche. E da

alcuni componenti minori: addr: ingresso di indirizzamento, read_enable e write_enable: sono due segnali

di controllo di 1 bit ciascuno che controllano le operazioni di lettura e scrittura. Sommatore: ALU

semplificata che esegue la sola operazione di somma. Multiplexor: selettore di canale con 2 ingressi dati

(32 bit);1 uscita dati (32 bit);1 segnale di controllo. La porta AND ha due ingressi da 1 bit ciascuno e genera

una uscita di 1 bit che viene asserito se e solo se entrambi gli ingressi hanno il valore 1. Il Decoder associato

alla ALU genera il segnale di controllo che pilota l’operazione aritmetico- logico da eseguire. Il Modulo di

Estensione da 16 a 32 bit: estende la rappresentazione di un campo immediato da 16 a 32 bit, in modo da

renderlo compatibile con l’ingresso della ALU.

Si illustri cosa si intende per overflow in un'operazione di somma fra valori codificati come interi senza

segno (rappresentazione in forma posizionale) e in un'operazione di somma fra valori codificati come interi

con segno (rappresentazione in complemento a due). In entrambi i casi, si discutano le condizioni che lo

determinano e si fornisca un esempio.

La condizione di Overflow si verifica quando il risultato dell'operazione eccede la dinamica dei valori

rappresentabili. Secondo la rappresentazione in forma posizionale nel caso dell’operazione di somma fra

valori codificati come interi senza segno, si verifica overflow se e solo se è presente un bit di riporto nella

somma dei MSB (perché va oltre la cifra massima rappresentabile).