Fondamenti di Informatica - Appunti e Slide PDF

Fondamenti di informatica, slide + appunti lezioni Fondamenti di informatica Università degli Studi di Firenze (UNIFI) 88 pag. Document shared on https://www.docsity.com/it/fondame...

Fondamenti di informatica, slide + appunti lezioni Fondamenti di informatica Università degli Studi di Firenze (UNIFI) 88 pag. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  FONDAMENTI DI INFORMATICA 28/02 Elaboratore, Algoritmi, Programmi e Linguaggi Elaborazione automatica: insieme di processi eseguiti da un'unità elettronica/digitale automatica (elaboratore o calcolatore elettronico) su dei dati in ingresso (input) per ottenere dei risultati in uscita (output). Algoritmo: procedura per risolvere un generico problema (se risolvibile) attraverso un set finito di istruzioni che, applicate ai dati in ingresso, li trasformano nei risultati del problema in uscita. Programma: implementazione di un algoritmo in un linguaggio comprensibile ed eseguibile dall'elaboratore, utilizzando una specifica sintassi che dipende dal linguaggio di programmazione. Infatti, l'insieme dei processi, routine e operazioni da eseguire deve essere comunicato all'elaboratore attraverso un linguaggio comprensibile ed eseguibile dall'elaboratore stesso. Solitamente i linguaggi di programmazione sono quello: simbolico: uso di simboli per rappresentare variabili e operatori di alto livello: elevato livello di astrazione, maggiore espressività. Per essere eseguiti dal calcolatore, le istruzioni di alcuni programmi scritti in linguaggi di alto livello devono essere tradotte in linguaggio a basso livello dal compilatore. Successivamente le istruzioni in linguaggio di basso livello, per poter essere eseguite, devono essere ulteriormente tradotte in linguaggio macchina dall’assemblatore. Formalizzazione di un problema attraverso algoritmi Passi necessari per creare un programma (algoritmo eseguibile dal calcolatore) per risolvere un generico problema: 1. Analisi e modellazione del problema 2. Implementazione dell'algoritmo attraverso un linguaggio formale, definendo: operazioni (operatori, funzioni, procedure...), dati e codifica dell'algoritmo nel linguaggio di programmazione. CONDIZIONI DI VALIDITÀ PER UN DIAGRAMMA DI FLUSSO (flow-chart) Condizioni di validità generale: ∙ Deve esistere un blocco di inizio e uno di fine ∙ Ogni freccia deve entrare in un blocco ∙ Dal blocco di inizio deve essere possibile raggiungere qualsiasi altro blocco e da ogni blocco deve essere possibile raggiungere il blocco di fine Condizioni specifiche: ∙ Il blocco di elaborazione (rettangolo) e di input/output (parallelogramma) devono avere una sola freccia in entrata e una sola freccia in uscita ∙ Il blocco di controllo (romboidale) deve avere una sola freccia in entrata e due frecce in uscita - VEDI EX. FATTORIALE DEL NUMERO INTERO N – Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) La rappresentazione dà ad un algoritmo una forma che può essere eseguita su un elaboratore. In questo assume un ruolo fondamentale il linguaggio di programmazione (come il linguaggio C). Rappresentazione: Tipi, Variabili e Costanti Il linguaggio C rappresenta i dati attraverso tipi. Un tipo è caratterizzato dall’insieme dei valori che rappresenta e dall’insieme delle operazioni che si possono effettuare su tali valori. I tipi sono invariabili. I tipi elementari del C sono: · unsigned int, int = numeri interi rappresentati mediante un numero di byte dipendenti dall'architettura del processore (32, 64 bit) - VEDI INTERI A 32BIT - · float = numeri razionali in virgola mobile (floating point) · double = numeri razionali in virgola mobile con precisione doppia rispetto ai float · char = caratteri rappresentati su 8 bit (256 caratteri set del codice ASCII) · void = tipo nullo, usato quando la sintassi del linguaggio richiede di specificare un tipo di dato ma · la semantica non lo prevede In C non esistono valori booleani ma sono sostituiti da numeri interi: lo zero O codifica il valore booleano “false”, qualsiasi altro intero con valore diverso da zero (tipicamente 1) codifica il valore booleano “true”. Variabile: locazione di memoria che contiene un valore di un tipo. Il valore può variare durante la computazione. Una variabile è associata anche ad un nome che permette di riferirsi ad essa senza doverne specificare l’indirizzo fisico in memoria. Il nome della variabile può essere una qualsiasi sequenza di caratteri alfabetici e/o numerici (con uso di _ ) a patto che il primo carattere del nome della variabile non sia numerico. La lunghezza della sequenza è arbitraria ma il compilatore non distingue tra variabili i cui nomi sono formati da sequenze che non differiscono sui primi 32 caratteri. Il nome viene associato alla variabile tramite una dichiarazione. (ex. int n; ex2. float media; ) Per associare un valore ad una variabile si ricorre ad un'assegnazione. (ex. n=10; ex2. media=25.5f; ) Variabile Array: insieme di variabili dello stesso tipo che possono essere referenziate tramite un nome collettivo e un indice che le identifica (denotandone lo scostamento, od offset, rispetto all'inizio dell'array). Ex. int V; V è il riferimento alla prima variabile dell'array V è il riferimento all'ultima variabile dell'array V , oltre ad essere il nome della variabile array, rappresenta anche l'indirizzo di memoria a partire dal quale l'array è memorizzato. Costante: valore di un certo tipo che non cambia durante la computazione. Le costanti non possono essere modificate all'interno del programma e sono rappresentate in maniera diversa a seconda del tipo: int: 10 float: 43.25f double: 43.25 #define PI 3.141592 (no ; dopo) const int max speed = 130; In particolare, #define è una direttiva a livello di pre-processore: prima di eseguire la compilazione, il compilatore sostituisce tutte le istanze delle costanti con il loro valore. Viene così definito un identificatore tramite cui la costante sia utilizzabile da tutto il codice del programma. const definisce una variabile di sola lettura che non può essere modificata all'interno del programma. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Rappresentazione: operatori ed espressioni Espressione: combinazione di variabili e costanti attraverso degli operatori. Il calcolo di un’espressione restituisce un valore e produce un effetto sui dati Side-effect (effetto collaterale): effetto sui dati prodotto dal calcolo di un’espressione; sono una componente del linguaggio. Un esempio è l’assegnamento (=). In C i dati sono elaborati proprio attraverso i side-effects. Operatori: sono classificati per tipo di operazione: ∙ Aritmetici: + - * / % ∙ Relazionali: < = > != ∙ Logici: && || ! ∙ Incremento e decremento: ++ -- Rappresentazione: istruzioni. Istruzioni: determinano la sequenza delle espressioni da eseguire e quindi il flusso di lavoro del programma. L'esecuzione di un'istruzione consiste nel calcolare l'espressione, producendone i side-effects, e poi passare il controllo del flusso del programma all'istruzione successiva. L’esecuzione di un’istruzione avviene: · tramite sequenza di istruzioni semplici : un'espressione seguita da punto e virgola ( ; ) · con istruzioni Compound: un’espressione raccolta entro parentesi graffa { … }, la sua utilità è di trattare le istruzioni in maniera unitaria. Rappresentazione: Istruzioni condizionali. 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. 1/3 Rappresentazione: Istruzioni di iterazione (loop). 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. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  · 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. Quando in un programma troviamo i simboli:  tutto quello racchiuso tra essi è irrilevante ai fini dell’esecuzione del programma; //  tutto quello che appare fino alla fine della linea è un commento. Se si estende su più linee si deve ripetere il simbolo su ciascuna di esse. Rappresentazione dei Dati: Numeri, Codifica Posizionale, Rappresentazione Binaria. Numero: ente caratterizzato da un suo significato intrinseco e che può essere descritto tramite rappresentazioni differenti che dipendono dalla combinazione di più convenzioni: › Posizionalità della codifica: un numero rappresentato con una codifica posizionale è un numero nel quale il peso di ciascuna cifra dipende dalla posizione che quella cifra occupa nella rappresentazione del numero; › Base di rappresentazione; › Numero di cifre che si hanno a disposizione per la rappresentazione; › Codifica del segno; › Rappresentazione di parti frazionarie e valori razionali. Codifica Posizionale: la codifica di un insieme di numeri avviene attraverso una base finita di 𝑁 cifre (nella codifica decimale le cifre da 0 a 9), che serve a rappresentare anche tutti gli altri numeri combinando più cifre sulla base di una notazione posizionale (il peso delle cifre dipende dalla loro posizione). Differenti convenzioni/notazioni: · Little Endian: in ultima posizione si trova la cifra meno significativa (Least Significant Digit LSD). · Big Endian: in ultima posizione si trova la cifra più significativa (Most Significant Digit MSD). La base di numerazione a cui siamo abituati è quella in base 10 ma l’elaboratore utilizza la base 2. Rappresentazione binaria: è la minima base che include cifre diverse (0 e 1), e che quindi può rappresentare i numeri in maniera posizionale, semplificando inoltre l’implementazione di algoritmi da parte dell’unità aritmetico logica del processore. L’algoritmo di conversione della base di rappresentazione di un numero si basa su: 1. Ottenere la rappresentazione polinomiale del numero nella base di partenza 2. Effettuare la conversione di coefficienti e potenze nella base di arrivo 3. Eseguire somme e prodotti nella base di arrivo La conversione base di rappresentazione può avvenire sfruttando l’aritmetica della base di arrivo o con l’algoritmo dei resti successivi. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ARITMETICA BASE DI ARRIVO: per effettuare la conversione da base 10 a base 2, il numero iniziale viene sviluppato in forma polinomiale nella base di partenza, i singoli coefficienti e le potenze che ne risultano sono convertiti nella base di arrivo e successivamente si sommano e si moltiplicano i dati ottenuti nella base di arrivo. ALGORITMO DEI RESTI SUCCESSIVI: algoritmo di codifica della base di rappresentazione che sfrutta l’aritmetica della base di partenza e si usa per convertire da base 10 a base 2 un numero 𝐴. Avremo che: 𝑎0 = 1 se e solo se 𝐴 è dispari, quindi 𝑎0 rappresenta il resto della divisione intera 𝐴/2. Si procede in maniera analoga per determinare gli altri coefficienti finché il quoziente della divisione per due è zero. La sequenza dei resti sono i coefficienti in ordine inverso (dal LSB al MSB). Rappresentazione dei Dati: Codifica Esadecimale. La Base Esadecimale: 16 cifre: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Questa è tipicamente utilizzata per rappresentare gli indirizzi di memoria, permettendo di esprimere in maniera più compatta i numeri. › Per convertire da base 2 a base 16, si formano gruppi da 4 bit del numero in base 2, dopodiché si convertono i numeri rappresentati da ognuno dei gruppi; › Per convertire da base 16 a base 2, si converte ogni cifra in base esadecimale nella rappresentazione a 4 bit in base 2. 7/3 Rappresentazione dei Dati: Conversione di Parti Frazionarie Una Parte Frazionaria è numero razionale minore dell’unità. Per convertire la parte frazionaria si possono seguire i due diversi approcci: · Algoritmo di conversione che impiega l’aritmetica della base di arrivo: la parte frazionaria è sviluppata in forma polinomiale nella base di partenza, i termini vengono convertiti nella base di arrivo e infine si eseguono le operazioni in base di arrivo. · Algoritmo di conversione di parti frazionarie che impiega la base di partenza: viene eseguito un algoritmo di moltiplicazioni per 2 sulla parte frazionaria, si sottrae dal risultato ottenuto la sua parte intera e si continua. La sequenza delle parti intere sottratte fornisce la rappresentazione voluta. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Rappresentazione dei Dati: Numeri Interi senza Segno unsigned int: serve a rappresentare una variabile dichiarata in C. Viene rappresentato su N bit di memoria che variano a seconda dell’architettura del processore (tipicamente, 32 o 64 bit). Per 𝑁 = 32 bit si possono rappresentare gli interi compresi tra 0 e 2−32 − 1. Rappresentazione dei Dati: Caratteri Caratteri: codifica posizionale in base 2 su 8 bit (con i quali è possibile rappresentare numeri interi senza segno da 0 a 255). Sono rappresentati in C dal tipo char (char c; ) La corrispondenza tra caratteri e numeri naturali compresi nell’intervallo 0, … , 255 è definita dalla Tabella dei Caratteri ASCII, che include la codifica per: ∙ caratteri alfanumerici: cifre decimali, lettere dell’alfabeto maiuscole e minuscole ∙ segni di interpunzione e parentesi: ( ) ,. ; : ? ! + - [ ] { } ∙ simboli aritmetici: + - * / ∙ caratteri di vario genere: @ # … ∙ caratteri di controllo: il segno di a capo, lo spazio di tabulazione, … N.B. Il carattere 0 è codificato da 48 e l’1 da 49. All’intero 0 è associato un carattere speciale, ovvero '\0’ che non codifica un carattere utile ma è utilizzato come segno di terminazione nella codifica delle stringhe. Rappresentazione dei Dati: Numeri Interi con Segno Int: rappresenta una variabile dichiarata in C e vengono rappresentati su V bit tramite la rappresentazione «Complemento a 2» (simile allo sviluppo polinomiale), in cui però il Most Significant Bit ha peso negativo. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Teniamo a mente che un numero è negativo se e solo se 𝑎𝑁 − 1 = 1. Il suo opposto si determina determinando il suo complemento a 2, ovvero complementando i bit uno ad uno e sommando 1 al risultato. Eccezione: l'opposto del minimo numero rappresentabile cade fuori dalla dinamica dei valori, quindi non possibile rappresentarlo con bit in complemento a 2. Il complemento a 2 del minimo numero rappresentabile è quindi il numero stesso. Rappresentazione dei Dati: Overflow La condizione di Overflow si verifica quando il risultato dell'operazione eccede la dinamica dei valori rappresentabili. › Interi senza segno: si verifica overflow se e solo se è presente un bit di riporto nella somma dei MSB. › Interi con segno: si verifica overflow se e solo se i due addendi sono concordi ma il segno del risultato è opposto a quello dei due addendi. In fase di programmazione, quando si verifica overflow tipicamente viene generata un'eccezione che porta ad un risultato tipico di un'aritmetica modulare: sommando 1 al massimo valore positivo si ottiene il minimo valore negativo. Rappresentazione dei Dati: Sottrazione in Complemento a 2 CASO 1) Minuendo maggiore del sottraendo: il risultato è positivo; non si considera eventuale riporto sul MSB. CASO 2A) Minuendo minore del sottraendo: il risultato è negativo; si considera l'eventuale riporto sul MSB. Non si ha overflow se il riporto su MSB è 0. Il modulo del risultato è il complemento a 2 (cioè l'opposto) del risultato. CASO 2B) Minuendo minore del sottraendo: il risultato è negativo; si considera l'eventuale riporto sul MSB. Si ha overflow se il riporto su MSB è 1. Rappresentazione dei Dati: Numeri in Virgola Mobile Viene utilizzata nel linguaggio C per rappresentare i numeri float e double. Un generico numero può essere rappresentato in forma esponenziale: S * m * 𝑩𝒄 › s = ± 1 è il segno; › m è la mantissa, un valore reale non negativo; › c è la caratteristica, un intero con segno; › B è la base di rappresentazione. Poiché esistono più rappresentazioni in forma esponenziale dello stesso numero, è necessario stabilire una rappresentazione univoca. Lo standard IEEE 754 stabilisce che la rappresentazione esponenziale di un numero si dice in forma normale quando: 1/B ≤ m < 1. Secondo lo standard, i float sono rappresentati su 32 bit: 1 bit per il segno S, 23 bit per la mantissa m, 8 bit per la caratteristica C, 1 per il segno (s = 0 il numero è positivo; s =1 il numero è negativo). Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) La caratteristica c si rappresenta in forma polarizzata (anziché in complemento a 2 come gli interi con segno). Questa rappresentazione è detta anche rappresentazione in eccesso 127. in particolare se: ∙ e = 0 (c = -127), m = 0, s = 0 codifica il valore +0; ∙ e = 0 (c = -127) m = 0, s = 1 codifica il valore -0; ∙ e = 0 (c= -127), m # 0, S ∈ {0,1}, rappresenta numero denormalizzato; ∙ e = 255 (c = 128), m # 0,5 ∈{0,1}, rappresenta un valore non accettabile (NaN: Not a Number); ∙ e = 255 (c = 128), m = 0, S = 0 codifica +00; ∙ e = 255 (c = 128), m = 0, s = 1 codifica --00; ∙ Il caso e ∈ [1,254] (c ∈ [-126,127]), V m, S ∈{0,1}, rappresenta un numero normalizzato, ovvero i numeri con caratteristica C ∈ [-126,127] (cioè e ∈ [1, 254]). Il minimo ordine di grandezza rappresentabile per i numeri normalizzati è 𝟐−𝟏𝟐𝟔 Il massimo ordine di grandezza rappresentabile per i numeri normalizzati è 𝟐𝟏𝟐𝟕 , un valore molto elevato che di fatto risolve il problema dell'overflow. Un numero normalizzato codifica il numero decimale: Inoltre poiché e considerando che 𝑠 ∈ 0,1 , l’intervallo di numeri rappresentati è dato da: ∙ i valori che stanno al oltre questi intervalli sono numeri troppo grandi per essere rappresentati, ovvero appartengono all’intervallo di overflow. ∙ i valori che rientrano tra questi due intervalli sono numeri troppo piccoli per essere rappresentati (sono minori della sensibilità di rappresentazione), ovvero appartengono all’intervallo di underflow perché sono numeri più piccoli in valore assoluto dei numeri normalizzati. La più piccola mantissa rappresentabile è 2−23 : 𝑚 ∈ [ 2−23, 1). Considerando che 𝑠 ∈ 0,1 , l’intervallo di numeri rappresentati è dato da un intervallo di underflow poiché la rappresentazione dei numeri denormalizzati permette un underflow più graduale. Rappresentazione: Precisione finita ed errore relativo La rappresentazione della mantissa con un numero finito di bit comporta un problema di precisione finita. Per ogni ordine di grandezza identificato dalla caratteristica è possibile rappresentare 223 valori distinti. Avere lo stesso numero di valori codificato su ordini di grandezza diversa implica che la densità con cui sono rappresentati i numeri razionali non è uniforme. - VEDI PROBLEMA DI PRECISIONE FINITA IN VIRGOLA MOBILE – Esprimiamo l’errore relativo di precisione finita (che è invariante, a differenza dell’errore assoluto) tra un dato numero razionale 𝑥 e il suo valore approssimato in floating point e ne ricaviamo che: · l’errore relativo vale: · l’errore assoluto vale: ovvero il prodotto tra l’ordine di grandezza e l’errore relativo. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) L’impatto dell’errore di precisione si può ridurre introducendo i numeri rappresentati tramite il tipo double (precisione doppia), i quali sono rappresentati in virgola mobile a 64 bit: · 1 bit per il segno 𝒔; · 52 bit per la mantissa 𝒎; · 11 bit per la caratteristica 𝒄. Rappresentazione: Precisione finita nelle operazioni tra float Il problema di precisione finita si presenta non solo nella codifica di float, ma anche nel caso di operazioni aritmetiche tra float (il cui risultato potrebbe non essere rappresentabile come float ma va ulteriormente approssimato, in quanto l’insieme dei float non è chiuso rispetto alla somma e al prodotto). Caso di errore peggiore: se la differenza tra le caratteristiche dei due addendi è maggiore del numero di cifre utilizzate per rappresentare la mantissa, si perdono tutte le cifre dell’addendo minore, e il risultato sarà quindi pari all’addendo con caratteristica maggiore. N.B. Gli int non sono gli interi dell’aritmetica ma sono solo quelli che rientrano in un determinato range; i float non sono i razionali ma un loro sottoinsieme finito formato da tutti i valori razionali che ammettono una forma normalizzata con una mantissa nella quale siano nulli tutti i bit oltre il 24esimo. Inoltre, mentre gli int sono soggetti a overflow, i float introducono solo errori di approssimazione. 8/3 Processo di Compilazione, Assemblaggio, Collegamento e Caricamento. Rappresentazione: Linguaggio Assembly e Sistemi di Calcolo. Linguaggio assembly è il linguaggio delle istruzioni che possono essere eseguite su un processore (dipende quindi dall’architettura del processore stesso). Sistema di calcolo è l’insieme di un processore e il suo codice assembly (stretta corrispondenza tra l’organizzazione dell’hardware di un processore e la struttura delle istruzioni assembly che vengono eseguite). Un sistema di calcolo è caratterizzato tipicamente dalla sua espressività. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) La teoria della computabilità è basata su un sistema di calcolo astratto: la Macchina di Touring, un sistema di calcolo astratto che qualifica la potenza espressiva di un sistema di calcolo senza fare riferimenti all’implementazione di uno specifico processore. Per la compilazione di un programma in C possiamo considerare un caso più concreto, ovvero MIPS R4000 della Silicon Graphics: assembly di tipo RISC (Reduced Instruction Set Computer) che veniva eseguito sui processori. Rappresentazione: Linguaggio Assembly - Istruzioni per operazioni Le istruzioni per eseguire operazioni aritmetiche e logiche ed assegnamenti. L’istruzione add calcola la somma e ha sempre due addendi. La somma di più addendi si esegue sequenzialmente. Da questo esempio si nota il gap semantico tra le istruzioni C e le istruzioni in linguaggio assembly (rapporto uno-a-molti): una singola istruzione del C corrisponde tipicamente a più istruzioni in assembly (il quale può quindi introdurre anche variabili temporanee aggiuntive). ESEMPIO: add a, b, c a ← b + c esegue il calcolo della somma di b e c e assegna il risultato alla variabile a. add a, b, 0 a ← b si assegna il valore di b alla variabile a. 𝑥 = 𝑎 + 𝑏 + 𝑐 verrà eseguita come: add tmp, a, b tmp ← a + b e add x, tmp, c x ← tmp + c Rappresentazione: Linguaggio Assembly - I Registri Le operazioni non vengono eseguite su variabili allocate in memoria, ma su variabili contenute in un banco di registri all’interno del processore che permettono un accesso più veloce. Nel caso dell’R4000 i registri sono 32 ($0, $1, …, $31).All’inizio di ogni istruzione il registro $0 contiene il valore 0, ogni registro è di 32 bit, il che definisce anche la dimensione di una parola (word): 32 bit = 4 byte. Nel caso dei registri, si indirizza il singolo registro, mentre in memoria si indirizza il singolo byte. Rappresentazione: Linguaggio Assembly – Istruzioni. Le istruzioni per trasferire i dati dai registri alla memoria e viceversa sono: ∙ load word (lw): lw $x, base[$y] x,y ∈ ℕ, x,y ∈ [0, 31] , base ∈ ℕ carica nel registro $x il contenuto della parola (4 byte) contenuta in memoria a partire all’indirizzo individuato dalla somma del valore intero base con il contenuto del registro $y. ∙ store word (sw): sw $x, base[$y] x,y ∈ ℕ, x,y ∈ [0, 31] , base ∈ ℕ scrive il contenuto del registro $x nella locazione di memoria che si trova a partire dall’indirizzo individuato dalla somma del valore intero base con il contenuto del registro $y. Le costanti vengono trattate in linguaggio assembly con istruzioni dedicate (ad esempio, addi, add immediate). ∙ addi: addi $x, $y, value scrive nel registro $x il contenuto della somma del valore value con il contenuto del registro $y. In questo caso il valore dell’operando value non è contenuto in un registro, ma rappresentato in modo immediato nell’istruzione. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ add (somma): add $z, $x, $y esegue il calcolo della somma del contenuto del registro $x e del registro $y e scrive il risultato nel contenuto del registro $z. ∙ conditional branch beq (branch if equal): beq $x, $y, label permette un controllo condizionato del flusso di esecuzione, selezionando la prossima istruzione in base all’esito di un test di uguaglianza: se il contenuto dei registri $x e $y sono uguali, il controllo viene passato all’istruzione successiva ovvero all’etichetta label, altrimenti il controllo viene trasferito all’istruzione successiva a beq. ∙ label: label rappresenta un’etichetta, ovvero un nome qualunque definito dall’utente (sequenza qualsiasi di caratteri che deve essere diversa da tutte le parole chiave del linguaggio). Quando viene tradotta In linguaggio macchina, viene tradotta con un intero che rappresenta lo scostamento (differenza) in termini di numero di byte fra l’istruzione successiva a beq e l’istruzione di destinazione del salto. ∙ slt (set on less than): slt $x, $y, $z permette di eseguire test basati su diseguaglianze e assegna al registro $x valore 1 se $y < $z, il valore 0 se $z >= $y: ∙ jump (salto incondizionato): j label permette di passare il controllo senza eseguire alcun test e trasferisce il controllo all’istruzione successiva all’etichetta label. I)n questo caso label rappresenta la differenza tra l’indirizzo dell’istruzione destinataria del salto e l’indirizzo della prima istruzione del programma (che si assume abbia indirizzo 0). Nell’assembly RISC non esistono istruzioni che traducano direttamente i costrutti iterativi for, while, do- while ma questi sono realizzati tramite opportune combinazioni di salti condizionati. - VEDI ESEMPI LINGUAGGIO ASSEMBLY – Rappresentazione: Linguaggio Macchina Il C è un linguaggio simbolico di alto livello perché utilizza simboli per denotare variabili e operatori e ha un’unica istruzione codifica operazioni che richiedono l’esecuzione di più istruzioni da parte del processore. La codifica di programma scritto in C (codice sorgente), prima che il programma possa essere eseguito, deve essere tradotta in una sequenza di istruzioni, sempre simboliche, ma di basso livello (codice assembly) questa operazione prende il nome di compilazione e viene eseguita dal compilatore. Assembly: è un linguaggio simbolico e di basso livello: una singola istruzione corrisponde ad una singola operazione eseguibile dal processore. Le istruzioni di basso livello vengono poi tradotte in forma numerica (codice macchina) dall’Assemblatore tramite un processo di collegamento svolto dal Linker, che collega eventuali sezioni di codice compilate separatamente e collegate mediante istruzioni di trasferimento del controllo i cui indirizzi di destinazione rimangono indeterminati fino a quando il Linker non effettua il collegamento. Infine viene prodotto il file eseguibile. Il MIPS: codifica istruzioni a 32 bit. I primi 6 bit codificano il campo operativo, ovvero permettono di definire un set di 64 istruzioni; i restanti 26 bit sono organizzati diversamente a seconda del tipo di operazione a cui si riferiscono. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Le istruzioni add e sub sono codificate su 6 campi (rispettivamente di 6, 5, 5, 5, 5 e 6 bit): ∙ Op = o per tutte le istruzioni aritmetico logiche; queste si differenziano in base al campo funct. ∙ 5 bit sono sufficienti a codificare i 32 registri disponibili per $rd, $rs, $rt. ∙ Il formato delle istruzioni add e sub è detto Formato R (Register), in quanto tutti gli operandi coinvolti sono definiti tramite registri che li contengono. L’istruzione addi necessita la codifica di due soli registri e un campo immediato: Per le istruzioni load word lw e store word sw: Il formato delle istruzioni addi, lw e sw è detto Formato I (Immediate). L’istruzione beq (formato I) codifica i due registri comparati e la distanza, dall’istruzione corrente, dell’istruzione a cui passare il controllo nel caso venga eseguito il salto: L’istruzioni slt codifica tre registri (dunque è in formato R), ed è considerata come operazione aritmetico logica con op=0: L’istruzioni j di salto incondizionato è in formato J, e dedica 26 bit alla codifica dell’ampiezza del salto (estende l’ampiezza del salto condizionato di beq, che ha a disposizione solo 16 bit): Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  14/3 Rappresentazione: Esecuzione su un processore. - VEDI QUAD. - Il funzionamento di un processore (CPU – central processing unit) si può comprendere tramite le sue componenti. È formato da 5 blocchi funzionali fondamentali: › Memoria: contiene una sequenza lineare di locazioni di 1 byte che possono essere lette o scritte durante la computazione. › Program Counter (PC): registro a 32 bit che contiene l’indirizzo dell’istruzione corrente. Al ciclo di clock successivo il PC viene aggiornato con l’indirizzo della successiva istruzione. › Banco dei registri: 32 registri di 32 bit ciascuno. Permette la lettura contemporanea di due registri e la scrittura di un terzo: 3 registri di indirizzamento: addr_rd1 e addr_rd2 selezionano i due registri da cui leggere; addr_wr1 seleziona il registro su cui scrivere; 2 uscite dati: out_1 e out_2 presentano in uscita il contenuto dei registri indirizzati da addr_rd1 e addr_rd2; › Control Unit (CU): riceve in ingresso un segnale di 6 bit che codifica l’operazione da eseguire. Genera in uscita vari segnali di controllo che pilotano il funzionamento dei componenti della CPU. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  › Arithmetic Logic Unit (ALU): esegue le operazioni aritmetico-logiche. 2 ingressi per gli operandi e 1 uscita per il risultato (32 bit); 1 ingresso di controllo che seleziona l’operazione da eseguire; 1 segnale di controllo di 1 bit (zero_bit) asserito quando il risultato dell’operazione è zero. E da alcuni componenti minori: › addr: ingresso di indirizzamento, (pleiona una locazione di memoria; 32 bit =› 3^32 locazioni indirizzabili) › 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, derivato da: ultimi 6 bit dell’istruzione (campo funct) per istruzioni di formato R; segnali di controllo della CU per le istruzioni di formato I. › 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. In base al valore del segnale di controllo, il Multiplexor presenta in uscita uno dei due ingressi. I blocchi sono collegati da linee che connettono le porte per l’ingresso e l’uscita dei dati, le linee di controllo sono invece tratteggiate. Le linee possono trasferire dati di uno o più bits paralleli. ESEMPI. Esempio di esecuzione istruzione add su CPU. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  › I bit da 0 a 5 (campo operativo) che codificano l’operazione da eseguire sono presentati all’ingresso della CU che li decodifica per generare i segnali di controllo: · segnali di selezione per i 4 Multiplexor; · segnale write_enbale per il banco dei registri; · segnale per il decoder che genera il segnale di comando per la ALU in base al campo funct. › I bit 6:10 e 11:15 contengono gli indirizzi dei registri $rs e $rt, e vengono collegati agli ingressi di indirizzamento addr_rd1 e addr_rd2. › Il banco dei registri presenta sulle uscite dati (out_1 e out_2) il contenuto dei registri $rs e $rt, che sono a loro volta presentati in ingresso alla ALU che esegue l’operazione di somma (codificata nel campo funct) e il risultato è presentato sull’ingresso dati data_wr. Poiché wr_enable è asserito, il valore data_wr viene scritto nel registro indirizzato da addr_wr (specificato nei bit 16:20 che codificano il campo rd) e il sommatore incrementa di 4 il valore del PC. Tale risultato viene scritto nel PC al successivo ciclo di clock. Esempio di esecuzione istruzione addi su CPU › I bit da 0 a 5 che codificano l’operazione da eseguire sono presentati all’ingresso della CU. › La ALU riceve in ingresso il contenuto del registro $rs e il campo immediato value (esteso a 32 bit dal modulo di estensione da 16 a 32 bit). Il risultato della somma è presentato all’ingresso dati del banco dei registri (data_wr). › Poiché il segnale wr_enable del banco dei registri è asserito, il risultato della somma viene scritto sul registro indirizzato dall’ingresso di indirizzamento addr_wr e il Multiplexor in ingresso alla porta addr_wr serve per selezionare l’indirizzo del registro di destinazione. Esempio di esecuzione istruzione sw su CPU Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  › La ALU riceve in ingresso il contenuto del registro $rt e il campo immediato value esteso a 32 bit. › Il risultato della somma dei due operandi è presentato all’ingresso di indirizzamento della memoria dati (addr). › Il segnale wr_enable abilita la memoria a scrivere a partire dall’indirizzo base+$rt il valore presentato sulla porta di ingresso dati data_in. Tale valore è il contenuto del registro $rs. Esempio di esecuzione istruzione lw su CPU › La ALU riceve in ingresso il contenuto del registro $rt e il campo immediato value esteso a 32 bit. › Il risultato della somma dei due operandi è presentato all’ingresso di indirizzamento della memoria dati (addr). › La memoria riceve il segnale rd_enable asserito e presenta in uscita (sulla porta data_out) il valore contenuto nella locazione indirizzata. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  › Il valore presentato in uscita dalla memoria dati viene presentato all’ingresso dati del banco dei registri (data_wr). Il banco dei registri riceve il segnale wr_enable asserito e scrive il valore sul registro $rd. Esempio di esecuzione istruzione beq su CPU › La ALU esegue la differenza (sub) tra $rs e $rt, e se il risultato è 0 ($rs e $rt sono uguali), viene asserito il segnale zero_bit. › Solo nel caso dell’istruzione beq il segnale branch è asserito. Questo implica che, nel caso dell’istruzione beq, l’uscita dalla porta AND e, quindi, la selezione della linea in ingresso al PC siano determinate dal segnale zero_bit: ∙ se lo zero_bit è disasserito, il segnale portato in ingresso al PC è PC+4; ∙ se zero_bit è asserito, il segnale portato in ingresso al PC è PC+4+label (salto di label + 4 bytes) 15/3 Rappresentazione: Definizione di un Linguaggio. Un linguaggio viene definito mediante: · sintassi: determina e classifica cosa può apparire in un’espressione legale del linguaggio; · semantica: definisce il significato di ogni classe di espressioni legali. Parti della sintassi sono: · vocabolario: insieme 𝑉 di simboli elementari (detti simboli terminali) che possono apparire in un’espressione legale. EX: 𝑉 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑙, 𝑚, 𝑛, 𝑜, 𝑝, 𝑞, 𝑟, 𝑠,𝑡, 𝑢, 𝑣, 𝑧 sono le lettere dell’alfabeto italiano. · universo linguistico di un vocabolario: insieme 𝑉∗ di tutte le possibili sequenze finite di simboli in 𝑉. EX: rappresenta tutte le parole di qualsiasi lunghezza finita formate dalle lettere dell’alfabeto; Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  · linguaggio su un vocabolario: sottoinsieme 𝐿 di 𝑉∗ con 𝐿 ⊆ 𝑉∗ EX: 𝐿 = 𝑎𝑏𝑎𝑐𝑜, 𝑎𝑏𝑎𝑡𝑒, … , rappresenta tutte le parole di senso compiuto nella lingua italiana. Definire la sintassi di un linguaggio vuol dire definire i limiti del sottoinsieme di 𝑉∗ che costituisce il linguaggio. Per fare questo, l’approccio più comune è quello di utilizzare delle regole organizzate secondo una grammatica rappresentata da una quadrupla: 𝐺 = 𝑉, 𝑁, 𝑆, 𝑃. Nella quadrupla: 𝑽 è il vocabolario, i cui elementi sono detti simboli terminali 𝑵 è un insieme, distinto da 𝑉 (𝑁 ∩ 𝑉 = ∅), i cui elementi sono detti categorie sintattiche 𝑺 è un elemento di 𝑁 (𝑆 ∈ 𝑁), detto simbolo iniziale di 𝑁 𝑷 è l’insieme delle produzioni Una produzione è una coppia 𝜂, 𝑛 , (in cui 𝜂 è una categoria sintattica e 𝑛 è una sequenza di elementi che appartiene a 𝑁 o a 𝑉) con 𝜂 ∈ 𝑁 e 𝑛 ∈ (𝑁 ∪ 𝑉)∗. Più precisamente è una relazione di 𝑁 su (𝑁 ∪ 𝑉)∗, un sottoinsieme del prodotto cartesiano di 𝑁 e (𝑁 ∪ 𝑉)∗ : 𝑃: 𝑁 → (𝑁 ∪ 𝑉) ∗ 𝑃 ⊆ 𝑁 × (𝑁 ∪ 𝑉)∗ La regola tramite cui una grammatica definisce un linguaggio è descritta mediante tre definizioni: 1. Derivazione diretta: siano 𝑝𝑟𝑒 e 𝑝𝑜𝑠𝑡 due elementi di (𝑁 ∪ 𝑉)∗. Sia 𝑎0 ∈ 𝑁 e 𝛼1 ∈ (𝑁 ∪ 𝑉)∗. Si dice che 𝑝𝑟𝑒 𝛼1 𝑝𝑜𝑠𝑡 deriva direttamente da 𝑝𝑟𝑒 𝑎0 𝑝𝑜𝑠𝑡, e si scrive 𝑝𝑟𝑒 𝑎0 𝑝𝑜𝑠𝑡 → 1 𝑝𝑟𝑒 𝛼1 𝑝𝑜𝑠𝑡, se ⟨𝑎0, 𝛼1⟩ ∈ 𝑃. 2. Derivazione indiretta: siano 𝛼0 ∈ (𝑁 ∪ 𝑉)∗ e 𝛼𝐾 ∈ (𝑁 ∪ 𝑉)∗. Si dice che 𝛼𝐾 deriva da 𝑎0, e si scrive 𝑎0 → 𝛼𝐾, se esiste una sequenza di elementi 𝛼𝑖 ∈ (𝑁 ∪ 𝑉)∗ tali che ∀𝑖 ∈ 1,𝐾 𝛼𝑖−1→ 1 𝛼𝑖. 3. Linguaggio definito da una grammatica: il linguaggio 𝐿𝐺 definito dalla grammatica 𝐺 = ⟨𝑉, 𝑁, 𝑆, 𝑃⟩ sul vocabolario 𝑉 è l’insieme degli elementi di 𝑉∗ che derivano dal simbolo iniziale 𝑆 attraverso le categorie sintattiche 𝑁 e le produzioni 𝑃. ESEMPIO: Consideriamo il linguaggio delle espressioni aritmetiche che combinano le variabili di un insieme 𝑣𝑎𝑟 tramite gli operatori +, −, ∗, / e le parentesi ( ). Il linguaggio deve includere l’espressione 𝑎 + 𝑏 ∗ 𝑐 − 𝑑 ed escludere l’espressione 𝑎 + 𝑏 −∗ 𝑐. › Definiamo il Vocabolario 𝑽: 𝑉 = 𝑣𝑎𝑟 ∪ +, −,∗,/, (, ) › Definiamo le Categorie Sintattiche 𝑵: 𝑁 = {𝑒𝑥𝑝𝑟, … } › Definiamo il Simbolo iniziale 𝑺, nel nostro caso quella delle espressioni aritmetiche: 𝑆 = 𝑒𝑥𝑝𝑟 › Definiamo le Produzioni 𝑷: 𝑒𝑥𝑝𝑟 → 𝑣𝑎𝑟  Permette di derivare un elemento di 𝑣𝑎𝑟 dal simbolo iniziale 𝑒𝑥𝑝𝑟 → (𝑒𝑥𝑝𝑟) 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟  combinazione di due espressioni legali Quest’ultima produzione introduce una categoria sintattica aggiuntiva, 𝑜𝑝, che rappresenta gli operatori e che richiede la definizione delle produzioni: 𝑜𝑝 → + 𝑜𝑝 → − 𝑜𝑝 → ∗ 𝑜𝑝 → / Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Quindi: › 𝑃 = {𝑒𝑥𝑝𝑟 → 𝑣𝑎𝑟, 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 , 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟, 𝑜𝑝 → +, 𝑜𝑝 → −, 𝑜𝑝 → ∗, 𝑜𝑝 → /} › 𝑁 = {𝑒𝑥𝑝𝑟, 𝑜𝑝, 𝑣𝑎𝑟} 1) Verifichiamo se l’espressione 𝑎 + 𝑏 ∗ 𝑐 − 𝑑 è un’espressione legale nella grammatica appena definita: - supponiamo che 𝑎, 𝑏, 𝑐 e 𝑑 siano simboli di 𝑣𝑎𝑟 e riscriviamo l’espressione come 𝑣𝑎𝑟 + 𝑣𝑎𝑟 ∗ (𝑣𝑎𝑟 − 𝑣𝑎𝑟) se applichiamo la produzione 𝑒𝑥𝑝𝑟 → 𝑣𝑎𝑟 e otteniamo: 𝑣𝑎𝑟 + 𝑣𝑎𝑟 ∗ 𝑣𝑎𝑟 − 𝑣𝑎𝑟 ← 𝑒𝑥𝑝𝑟 + 𝑒𝑥𝑝𝑟 ∗ (𝑒𝑥𝑝𝑟 − 𝑒𝑥𝑝𝑟) ; se applichiamo 𝑜𝑝 → +, 𝑜𝑝 → −, 𝑜𝑝 → ∗ otteniamo invece: 𝑒𝑥𝑝𝑟 + 𝑒𝑥𝑝𝑟 ∗ 𝑒𝑥𝑝𝑟 − 𝑒𝑥𝑝𝑟 ← 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 ; se applichiamo due volte la produzione 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 e la produzione 𝑒𝑥𝑝𝑟 → (𝑒𝑥𝑝𝑟): 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 ← 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 ; Infine, se applichiamo di nuovo la produzione 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 avremo: 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 ← 𝑒𝑥𝑝𝑟 - Concatenando tutte le riduzioni si ottiene: 𝑎 + 𝑏 ∗ 𝑐 − 𝑑 ← 𝑒𝑥𝑝𝑟 ∎ 2) Verifichiamo se l’espressione 𝑎 + 𝑏 −∗ 𝑐 è un’espressione legale nella grammatica appena definita.: - Supponiamo che 𝑎, 𝑏, 𝑐 e 𝑑 siano simboli di 𝑣𝑎𝑟 e riscriviamo l’espressione come: 𝑣𝑎𝑟 + 𝑣𝑎𝑟 −∗ 𝑣𝑎𝑟 se applichiamo la produzione 𝑒𝑥𝑝𝑟 → 𝑣𝑎𝑟 otteniamo: 𝑣𝑎𝑟 + 𝑣𝑎𝑟 −∗ 𝑣𝑎𝑟 ← 𝑒𝑥𝑝𝑟 + 𝑒𝑥𝑝𝑟 −∗ 𝑒𝑥𝑝𝑟 se applichiamo le produzioni 𝑜𝑝 → − e 𝑜𝑝 → ∗ otteniamo: 𝑒𝑥𝑝𝑟 + 𝑒𝑥𝑝𝑟 −∗ 𝑒𝑥𝑝𝑟 ← 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑜𝑝 𝑒𝑥𝑝𝑟 se applichiamo 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 otteniamo: 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑜𝑝 𝑒𝑥𝑝𝑟 ← 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑜𝑝 𝑒𝑥𝑝𝑟 ∙ Tale forma non può essere ulteriormente ridotta attraverso l’applicazione di alcuna delle produzioni in 𝑃. In questo caso la riduzione non si chiude sul simbolo iniziale, quindi l’espressione 𝑎 + 𝑏 −∗ 𝑐 non è un’espressione legale per la grammatica precedentemente definita. Rappresentazione: Definizione di un Linguaggio - Albero sintattico Il processo di riduzione di una sequenza di simboli del vocabolario 𝑉 al simbolo iniziale 𝑆 viene tipicamente rappresentata da un albero sintattico. Albero: insieme di nodi sui quali è definita una relazione di successione per cui: ∙ ogni nodo ha un unico predecessore e un numero di successori non limitato a priori; ∙ il nodo radice non ha alcun predecessore e, in modo analogo, i nodi foglia non hanno alcun successore. Nel caso dell’albero sintattico: ∙ i nodi sono simboli elementari e produzioni, elementi di (𝑁 ∪ 𝑉)∗ ; Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ gli archi rappresentano relazioni di derivazione diretta tra i nodi in base alle produzioni della grammatica. Assegnata una sequenza di simboli nel vocabolario, se sulla sequenza può essere costruito un albero che si chiude su una radice, allora la sequenza è una istanza della categoria sintattica associata alla radice. - VEDI EX. – Rappresentazione: Definizione di un Linguaggio - Metalinguaggio BNF Il Metalinguaggio BNF (Backus Naur Form) è un formalismo che semplifica la comprensione e rappresentazione delle produzioni rispetto alla notazione elementare 𝜂 → 𝑛, ovvero è una sequenza di elementi che appartiene a 𝑁 o a 𝑉. Esistono numerose estensioni e rappresentazioni del BNF, definite come Extended BNF (EBNF). Le più usate sono: › 𝜂 ∷= 𝑛  𝑃 contiene la produzione 𝜂 → 𝑛, ovvero 𝜂 → 𝑛 ∈ 𝑃 ; › 𝜂 ∷= 𝑛1|𝑛2  𝑃 contiene le produzioni 𝜂 → 𝑛1 e 𝜂 → 𝑛2 ; › 𝜂 ∷= 𝑛𝑝𝑟𝑒 [𝑛]𝑛𝑝𝑜𝑠𝑡  𝑃 contiene le produzioni 𝜂 → 𝑛𝑝𝑟𝑒 𝑛 𝑛𝑝𝑜𝑠𝑡 e 𝜂 → 𝑛𝑝𝑟𝑒 𝑛𝑝𝑜𝑠𝑡 ; › 𝜂 ∷= 𝑛𝑝𝑟𝑒 {𝑛}𝑚𝑎𝑥 𝑚𝑖𝑛 𝑛𝑝𝑜𝑠𝑡  𝑃 contiene le produzioni che riducono 𝜂 in una sequenza aperta dal prefisso 𝑛𝑝𝑟𝑒 e chiusa dal prefisso 𝑛𝑝𝑜𝑠𝑡 , contenente un numero di ripetizioni del termine 𝑛 compreso tra un minimo 𝑚𝑖𝑛 e un massimo 𝑚𝑎𝑥. Si assume per convenzione che le categorie sintattiche vengano espresse racchiuse dai delimitatori < >. Quindi le produzioni descritte in un precedente esempio: 𝑃 = {𝑒𝑥𝑝𝑟 → 𝑣𝑎𝑟, 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟, 𝑒𝑥𝑝𝑟 → 𝑒𝑥𝑝𝑟 𝑜𝑝 𝑒𝑥𝑝𝑟, 𝑜𝑝 → +, 𝑜𝑝 → −, 𝑜𝑝 → ∗, 𝑜𝑝 → /, 𝑣𝑎𝑟 → ⋯ } vengono espresse in forma compatta come: < 𝑒𝑥𝑝𝑟 > ∷= < 𝑣𝑎𝑟 > < 𝑒𝑥𝑝𝑟 > < 𝑒𝑥𝑝𝑟 > < 𝑜𝑝 > < 𝑒𝑥𝑝𝑟 > < 𝑜𝑝 > ∷= + − ∗ | /. Rappresentazione: Definizione di un Linguaggio - Semantica e Sintassi La grammatica definisce la sintassi e permette anche di definire in maniera non ambigua la semantica. I vincoli contestuali riducono la non-ambiguità di un linguaggio permettendo di ottenere grammatiche più compatte e comprensibili. Il processo di interpretazione si basa quindi su una verifica lessicale, una sintattica e una contestuale. Induzione strutturale: processo di definizione della semantica per cui il significato di un’espressione è ridotto alla composizione dei significati delle parti che la compongono attraverso le produzioni della grammatica. Esempio: linguaggio delle espressioni della logica Booleana. Denotiamo un’espressione con la categoria < 𝑒𝑥𝑝𝑟 > che rappresenta l’insieme delle espressioni combinando ricorsivamente variabili < 𝑣𝑎𝑟 > di tipo booleano attraverso: ∙ Congiunzione ∧ (AND logico) ∙ Disgiunzione ∨ (OR logico) ∙ Negazione ¬ (NOT logico) Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ Uso delle parentesi ( ) Potremo quindi esprimere le espressioni della logica booleana come: < 𝑒𝑥𝑝𝑟 > ∷= < 𝑣𝑎𝑟 > | < 𝑒𝑥𝑝𝑟1 > ∧ < 𝑒𝑥𝑝𝑟2 > | < 𝑒𝑥𝑝𝑟1 > ∨ < 𝑒𝑥𝑝𝑟2 > ¬< 𝑒𝑥𝑝𝑟1 > (< 𝑒𝑥𝑝𝑟 >) La semantica di un’espressione < 𝑒𝑥𝑝𝑟 > consiste nel valore Γ che essa restituisce. Quindi è necessario che per ogni diversa riduzione di < 𝑒𝑥𝑝𝑟 > sia definito il valore di Γ(< 𝑒𝑥𝑝𝑟 >) in funzione del valore restituito dalle eventuali espressioni che la compongono. Si adottano le seguenti clausole per le riduzioni di < 𝑒𝑥𝑝𝑟 > : › se < 𝑒𝑥𝑝𝑟 > ∷= < 𝑣𝑎𝑟 > , allora Γ ( < 𝑒𝑥𝑝𝑟 > ) è il valore della variabile 𝑣𝑎𝑟 (true o false in quanto booleana); › se < 𝑒𝑥𝑝𝑟 > ∷= ( < 𝑒𝑥𝑝𝑟1 > ) , allora Γ ( < 𝑒𝑥𝑝𝑟 > ) = Γ ( < 𝑒𝑥𝑝𝑟1 > ) ,ovvero il valore restituito dall’espressione 𝑒𝑥𝑝𝑟 è il valore restituito dall’espressione 𝑒𝑥𝑝𝑟1 dentro parentesi; › se < 𝑒𝑥𝑝𝑟 > ∷= ¬< 𝑒𝑥𝑝𝑟1 >, allora Γ ( < 𝑒𝑥𝑝𝑟 > ) = ¬Γ ( < 𝑒𝑥𝑝𝑟1 > ) ; › se < 𝑒𝑥𝑝𝑟 > ∷= < 𝑒𝑥𝑝𝑟1 > ∧ < 𝑒𝑥𝑝𝑟2 >, allora Γ ( < 𝑒𝑥𝑝𝑟 > ) = Γ ( < 𝑒𝑥𝑝𝑟1 > ∧ Γ < 𝑒𝑥𝑝𝑟2 > ) ; › se < 𝑒𝑥𝑝𝑟 > ∷= < 𝑒𝑥𝑝𝑟1 > ∨ < 𝑒𝑥𝑝𝑟2 >, allora Γ ( < 𝑒𝑥𝑝𝑟 > ) = Γ ( < 𝑒𝑥𝑝𝑟1 > ) ∨ Γ ( < 𝑒𝑥𝑝𝑟2 > ). La semantica degli operatori ¬ , ∧ e ∨ può essere espressa dalle tabelle di verità: - VEDI EX. – Rappresentazione: Il Linguaggio C - Tipi, Variabili e Costanti. In un linguaggio di programmazione, un tipo è caratterizzato da: › insieme dei valori rappresentati; › operazioni che possono essere eseguite su tali valori; › modalità di codifica dei valori; › algoritmi utilizzati per realizzare le operazioni. Il c include 5 tipi elementari: char, int, float, double e void. Al tipo int possono essere applicati opzionalmente i modificatori short, long e unsigned: < 𝑡𝑦𝑝𝑒 > ∷= 𝑐ℎ𝑎𝑟 | [𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑] [𝑠ℎ𝑜𝑟𝑡 | 𝑙𝑜𝑛𝑔] 𝑖𝑛𝑡 | 𝑓𝑙𝑜𝑎𝑡 | 𝑑𝑜𝑢𝑏𝑙𝑒 | 𝑣𝑜𝑖𝑑 char rappresenta i caratteri della tabella ASCII ; int rappresenta i numeri interi con segno: ∙ long aumenta a 8 il numero di bytes per la codifica; ∙ short diminuisce a 2 i bytes per la codifica; Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ unsigned permette di rappresentare gli interi senza segno. float rappresenta i numeri razionali in formato floating point ; double rappresenta i numeri razionali in formato floating point a doppia precisione ; void è il tipo nullo (non esistono variabili di tipo void), serve a specificare un tipo dove questo non ha nessun particolare effetto, ma permettendo così di mantenere regolarità nel linguaggio (ha quindi un ruolo sintattico ma non semantico). 21/3 Una variabile è una locazione di memoria che contiene un valore di un tipo che può essere modificato durante la computazione, mentre il tipo è invariante. Una variabile è associata a un nome (caratteristica di un linguaggio simbolico di denotare variabili e operatori attraverso simboli). La dichiarazione di una variabile permette di fare riferimento alla variabile attraverso il suo nome determinando quindi il nome e il tipo della variabile. < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > ∷= < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; < 𝑑𝑒𝑐𝑙 > ∷= < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > | … < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > ∷= < 𝑡𝑦𝑝𝑒 >< 𝑑𝑒𝑐𝑙 >; < 𝑑𝑒𝑐𝑙 > ∷= < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > | … dove < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > è il nome della variabile. Consideriamo: Il nome di un variabile può essere una sequenza arbitraria di caratteri alfanumerici e con possibile uso del simbolo ‘_’ (underscore). Per convenzione i nomi iniziano con una lettera minuscola e viene usato il simbolo underscore come separatore. ∙ Semantica di una dichiarazione < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 >: consiste nell’associare un nome e un tipo ad un’entità referenziabile dal programma. Ex: < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > ∷= < 𝑡𝑦𝑝𝑒 >< 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 >; il nome < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > viene associato a una variabile di tipo < 𝑡𝑦𝑝𝑒 >. Il compilatore provvede inoltre ad allocare in memoria lo spazio in cui la variabile viene mantenuta. ∙ Semantica di un riferimento a variabile < 𝑣𝑎𝑟 >: consiste nell’individuare una variabile, ovvero nell’identificare una locazione di memoria e un tipo. Ex: < 𝑣𝑎𝑟 > ∷= < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > < 𝑣𝑎𝑟 > … N.B. < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > è un riferimento alla variabile associata al nome < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > che deve comparire in una precedente dichiarazione di tipo < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > in cui è stato specificato anche il tipo della variabile. - VEDI EX. – Le costanti rappresentano valori che non cambiano durante la computazione. Hanno un tipo che può essere definito esplicitamente o derivato dal compilatore in base al formato: ∙ 9 costante intera ∙ unsigned 9 costante intera senza segno ∙ 9.F costante float ∙ 9. costante double Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ 0xABF12C costante esadecimale ∙ 'A' carattere (i caratteri devono essere indicati tra apici) Le costanti tipicamente non sono memorizzate in locazioni di memoria, bensì sono codificate in modo immediato tramite istruzioni addi. Se lo spazio disponibile per l’operando immediato non è sufficiente, il compilatore può all’occorrenza mappare la rappresentazione di una costante su una variabile (in maniera trasparente per il programmatore). Rappresentazione: Il Linguaggio C - Operatori ed Espressioni Le espressioni combinano riferimenti a variabile e costanti attraverso degli operatori. I termini elementari con cui può essere formata un’espressione sono costanti e riferimenti a variabili: < 𝑒𝑥𝑝𝑟 > ∷= < 𝑐𝑜𝑛𝑠𝑡 > < 𝑣𝑎𝑟 > … Sulle variabili di tipo intero possono essere applicati gli operatori incremento e decremento (nella forma prefissa e suffissa): La combinazione di espressioni con alcuni operatori produce un’altra espressione: Dove: < 𝑜𝑝2 > rappresenta operatori binari (aritmetici, relazionali, logici, operatori di manipolazione dei bit): < 𝑜𝑝1 > rappresenta operatori unari (operatore logico di negazione e negazione bit a bit): L’assegnamento del risultato di un’espressione alla variabile identificata da un riferimento è anch’essa un’espressione, rappresentata con la forma compatta in cui un operatore binario viene prefisso al segno di uguale in un assegnamento: Per raccogliere, concatenare e sequenzializzare un’espressione si usano rispettivamente le parentesi ( ), la virgola , e l’operatore ternario ? : Il cast permette di controllare il tipo con cui viene restituito il risultato di un’espressione: Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) La semantica di un’espressione ha due componenti: › valore restituito dall’espressione  ha anche un tipo che assume il significato di tipo dell’espressione › effetti prodotti dal calcolo dell’espressione sulle variabili (side effect). Solo le espressioni di assegnamento, incremento e decremento hanno effetti sulle variabili. Nel caso di combinazione di espressioni con operatori, il valore restituito si ottiene applicando la semantica dell’operatore specifico ai valori restituiti dalle espressioni composte: Gli operatori aritmetici di somma, sottrazione, prodotto, divisione eseguono operazioni in aritmetica finita, con la possibilità di generare overflow/underflow e/o di errori di troncamento. Operatori che hanno la stessa espressione sintattica possono avere una diversa semantica a seconda del tipo delle variabili a cui sono applicati (ad esempio, la divisione tra int e float viene rappresentata dal simbolo /, ma viene eseguita compilando istruzioni diverse). - VEDI EX. – L’operatore aritmetico di modulo ( < 𝑜𝑝2 > ∷= % ) restituisce il resto della divisione intera tra gli operandi. Il tipo del valore restituito è il tipo delle espressioni che restituiscono gli operandi. Quando gli operandi hanno valori di tipo diverso, la semantica dell’operazione include la conversione dell’operando più debole al formato del più forte (la forza corrisponde sostanzialmente all’ampiezza dell’insieme dei valori rappresentati): char < int < float < double Gli operatori relazionali servono a testare condizioni di ordinamento e uguaglianza tra valori: Restituiscono: ∙ il valore 1 (nel tipo intero) se la relazione testata è verificata; Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ il valore 0 (nel tipo intero) se la relazione testata non è verificata. Se gli operandi hanno tipo diverso, prima della operazione il tipo più debole è convertito al formato più forte. In C non esiste il tipo Booleano ma è sostituito dagli interi con la convenzione che qualunque valore diverso da 0 (solitamente 1) è interpretato come vero e il valore 0 è interpretato come falso. Gli operatori logici realizzano le operazioni della logica Booleana: ∙ ∙ 𝑋 && 𝑌 restituisce 1 (vero) se X e Y valgono entrambi un valore diverso da 0, e restituisce 0 (falso) se uno almeno tra X e Y vale 0. ∙ 𝑋 || 𝑌 restituisce vero se uno almeno tra X e Y è vero, e restituisce falso se X e Y sono entrambi 0. ∙ ! 𝑌 restituisce vero se Y è falso, e restituisce falso se Y è vero. Gli operandi possono essere espressi in qualsiasi tipo, mentre il risultato è sempre restituito come intero. Short-circuit o lazy evaluation: · < 𝑒𝑥𝑝𝑟1 > && < 𝑒𝑥𝑝𝑟2 >: si calcola 𝑒𝑥𝑝𝑟1 e si producono i suoi side effects, se 𝑒𝑥𝑝𝑟1 restituisce vero si calcola 𝑒𝑥𝑝𝑟2 e si producono i suoi side effects. · < 𝑒𝑥𝑝𝑟1 > || < 𝑒𝑥𝑝𝑟2 > : si calcola 𝑒𝑥𝑝𝑟1 e si producono i suoi side effects, se 𝑒𝑥𝑝𝑟1 restituisce vero si calcola 𝑒𝑥𝑝𝑟2 e si producono i suoi side effects. - VEDI EX. – 22/3 Rappresentazione: Il Linguaggio C – Puntatori Puntatori: variabili i cui valori sono indirizzi di locazioni a partire da cui sono memorizzate altre variabili. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  ∙ Il valore di un puntatore è un numero compreso nell’intervallo [0, 2N – 1] che coincide con l’intervallo di rappresentazione dei numeri unsigned int. È l’indirizzo del primo byte a partire dal quale è memorizzata la variabile puntata, ma non indica quanti bytes occupa la variabile puntata, né quale sia il suo tipo di codifica. ∙ Il tipo di un puntatore è diverso da quello di un unsigned int, perché il tipo è caratterizzato, oltre dai valori che rappresenta, anche dalle operazioni che si possono effettuare su tali valori; le operazioni che si possono effettuare sui puntatori e sugli unsigned int differiscono. Il tipo viene specificato nella dichiarazione, introducendo un modificatore * prima del nome della variabile. ∙ Un riferimento a un puntatore appartiene alla categoria sintattica < 𝑣𝑎𝑟 >, e può quindi apparire in un’espressione in qualunque posizione possa apparire il riferimento ad una variabile. Dichiarazione di un puntatore: - VEDI EX. PUNTATORI- › Il simbolo * agisce come modificatore della dichiarazione base: < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; › La semantica di una < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > identifica generalmente un nome e un tipo. › Per ipotesi induttiva assumiamo che < 𝑡𝑦𝑝𝑒 > ∗ < 𝑑𝑒𝑐𝑙 > abbia una semantica e siano 𝑁 e 𝑇 il nome e il tipo che essa identifica. La semantica della dichiarazione < 𝑡𝑦𝑝𝑒 > ∗ < 𝑑𝑒𝑐𝑙 > associa ad un’entità referenziabile dal programma il nome 𝑁 e il tipo «puntatore a un’entità di tipo 𝑇». < 𝑡𝑦𝑝𝑒 > ∗< 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > int *x_ptr; › La definizione ricorsiva di < 𝑑𝑒𝑐𝑙 > permette un numero arbitrario di modificatori * prima del termine < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > Operazioni aritmetiche sui puntatori La somma tra il valore di un puntatore ed un numero intero restituisce il valore del puntatore incrementato per il numero intero moltiplicato per la dimensione in byte del tipo della variabile puntata. La differenza tra due puntatori a variabili dello stesso tipo restituisce un numero intero che esprime il numero di variabili di quel tipo che possono essere memorizzate tra le locazioni puntate dai due puntatori. Operazioni di prodotto, divisione e modulo NON si applicano ai puntatori. ESEMPIO. I. L’operatore di de-referenziazione prefisso * permette di fare riferimento a una variabile attraverso un puntatore che ne contiene l’indirizzo (de-referenziazione di un indirizzo). L’operatore * è applicato in forma prefissa ad un’espressione che restituisce un valore del tipo di un puntatore (cioè, un valore di tipo indirizzo di una variabile di un tipo) e restituisce un riferimento alla variabile puntata. Dal punto di vista sintattico, fa parte delle clausole che definiscono la categoria sintattica, Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  che andrà estesa: Il tipo di una variabile non può essere void, quindi non si può applicare l’operatore * ad un puntatore a void. Tuttavia, è possibile dichiarare un puntatore a void, utili per realizzare iteratori che operano su insiemi di dati di tipo diverso. In tal caso il compilatore: › è comunque in grado di allocare lo spazio necessario alla rappresentazione del puntatore (in quanto la dimensione e il formato di un indirizzo non dipendono dal tipo della variabile puntata); › è anche in grado di compilare operazioni di assegnamento, in cui al puntatore viene assegnato il valore di un indirizzo (di qualsiasi tipo); › può compilare espressioni in cui compare l’operatore * solo se il tipo della variabile puntata è specificato tramite l’operatore cast. A tale scopo è necessario estendere la categoria sintattica < 𝑐𝑎𝑠𝑡_𝑡𝑦𝑝𝑒 >: II. Operatore di indirizzo & (concettualmente inverso a ∗), applicato in forma prefissa ad una variabile, ne restituisce l’indirizzo. Sintatticamente si colloca nelle espressioni < 𝑒𝑥𝑝𝑟 > , la cui clausola andrà estesa: &x è un’espressione (di tipo indirizzo di variabile del tipo di x) e non un riferimento a variabile. Questo significa che &x non può apparire a sinistra di un assegnamento (ovvero, non è possibile modificare l’indirizzo di una variabile). L’espressione & < 𝑣𝑎𝑟 > non produce side effects e restituisce il valore dell’indirizzo della variabile referenziata da < 𝑣𝑎𝑟 > , nel tipo di un indirizzo di variabile del tipo di < 𝑣𝑎𝑟 >. Gli operatori ∗ e & hanno un ruolo congiunto nel linguaggio C ma › ∗ serve a denotare una variabile, il compilatore deve conoscere il tipo della variabile alla quale ∗ è applicato; › & serve a restituire un valore, richiede la stessa implementazione indipendentemente dal tipo della variabile a cui è applicato. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) ESEMPI. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  28/3 Rappresentazione: Il Linguaggio C – Array 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. L’array è memorizzato su una sequenza di locazioni contigue di memoria e ogni locazione è identificata da un indirizzo di base e un offset. Il nome collettivo rappresenta anche una costante di tipo indirizzo che rappresenta l’indirizzo di partenza dell’array. Dichiarazione di variabili array: occorre stabilire il numero e il tipo delle variabili, e anche il nome dell’array. Estendiamo la categoria sintattica < 𝑑𝑒𝑐𝑙 > con il modificatore suffisso [< 𝑐𝑜𝑛𝑠𝑡 >] : < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > ∷= < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; < 𝑑𝑒𝑐𝑙 > ∷=< 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > |∗< 𝑑𝑒𝑐𝑙 > | < 𝑑𝑒𝑐𝑙 > [< 𝑐𝑜𝑛𝑠𝑡 >] | … Definiamo la semantica della dichiarazione < 𝑡𝑦𝑝𝑒 >< 𝑑𝑒𝑐𝑙 > [< 𝑐𝑜𝑛𝑠𝑡 >] tramite un principio di induzione strutturale. Sappiamo già che < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; ha una semantica. Dunque < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 > [< 𝑐𝑜𝑛𝑠𝑡 >] : · dichiara un array di un numero < 𝑐𝑜𝑛𝑠𝑡 > di entità del tipo che sarebbe dichiarato da < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; · associa all’array il nome che sarebbe associato all’entità dichiarata da < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 > Il compilatore alloca in un numero di locazioni contigue di memoria le variabili dell’array. La dimensione di questo segmento di memoria è pari a: < 𝑐𝑜𝑛𝑠𝑡 > sizeof(< 𝑡𝑦𝑝𝑒 >). La clausola che definisce < 𝑑𝑒𝑐𝑙 > ha una struttura ricorsiva che permette di associare a un < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > un numero arbitrario modificatori prefissi ∗ e suffissi [< 𝑐𝑜𝑛𝑠𝑡 >]. Questo introduce una ambiguità sull’ordine con cui devono essere considerati i modificatori ∗ e [< 𝑐𝑜𝑛𝑠𝑡 >]. Per risolvere tale ambiguità si definisce una priorità: il modificatore suffisso < 𝑐𝑜𝑛𝑠𝑡 > ha priorità sul modificatore prefisso ∗ ( int *V; ). Rappresentazione: Il Linguaggio C - Array: Dichiarazioni Complesse. Potendo combinare puntatori e array, l’interpretazione della dichiarazione di una variabile può diventare complessa. Regola del pollice: 1. Si legge la dichiarazione a partire dal nome che identifica la variabile; 2. Si espande poi la lettura della dichiarazione prima verso destra (fintanto che ci sono modificatori suffissi), e poi verso sinistra (fino ad arrivare al tipo). ESEMPIO. int **A; Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Analogamente, per scrivere una dichiarazione, si applica il processo inverso: - si scrive il nome della variabile - si estende l’espressione verso destra finché si trovano termini del tipo «array di…», poi a sinistra finché si trovano termini del tipo «puntatore a…»; - infine si applica il tipo elementare. Non tutte le dichiarazioni possono essere realizzate con la sintassi fin qui definita. Tale limite si supera estendendo la categoria sintattica < 𝑑𝑒𝑐𝑙 > con l’introduzione delle parentesi tonde che forzano le priorità nella lettura della dichiarazione: < 𝑑𝑒𝑐𝑙𝑎𝑟𝑎𝑡𝑖𝑜𝑛 > ∷= < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; < 𝑑𝑒𝑐𝑙 > ∷= … | (< 𝑑𝑒𝑐𝑙 >)| … < 𝑑𝑒𝑐𝑙 > ∷== < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > |∗< 𝑑𝑒𝑐𝑙 > | < 𝑑𝑒𝑐𝑙 > | [< 𝑐𝑜𝑛𝑠𝑡 >] | (< 𝑑𝑒𝑐𝑙 >) … Semantica della dichiarazione < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 > ; < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 > ; agisce come modificatore della dichiarazione base < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; < 𝑡𝑦𝑝𝑒 > (< 𝑑𝑒𝑐𝑙 >) definisce una variabile che ha stesso nome e stesso tipo della variabile definita da < 𝑡𝑦𝑝𝑒 > < 𝑑𝑒𝑐𝑙 >; nella lettura di una dichiarazione i modificatori dentro parentesi hanno precedenza su quelli esterni; nella scrittura di una dichiarazione si aggiunge una coppia di parentesi ogni volta che un termine «puntatore a…» è seguito da un termine «array di…». Rappresentazione: Il Linguaggio C - Riferimento a Variabili Array. Sintassi per il riferimento a variabili array. › Il nome associato a una variabile array rappresenta il valore (costante) dell’indirizzo a partire dal quale l’array è memorizzato. › Il tipo di tale valore è quello di un puntatore a variabili del tipo di quelle dell’array. 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. < 𝑣𝑎𝑟 > ∷= < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > |∗< 𝑒𝑥𝑝𝑟 > | < 𝑒𝑥𝑝𝑟1 > | [< 𝑒𝑥𝑝𝑟2 >] < 𝑒𝑥𝑝𝑟1 > restituisce un valore di tipo indirizzo (a partire dal quale l’array è memorizzato); < 𝑒𝑥𝑝𝑟2 > restituisce un valore di tipo intero (indice della variabile all’interno dell’array); l’indice può essere ottenuto come valore (intero) restituito da un’espressione, mentre il riferimento all’array può essere espresso come valore di un’espressione che restituisce un puntatore a variabile del tipo delle variabili nell’array. Semantica del riferimento < 𝑒𝑥𝑝𝑟1 > [< 𝑒𝑥𝑝𝑟2 >]: › sia ptr il valore restituito da < 𝑒𝑥𝑝𝑟1 >; › sia N il valore restituito da < 𝑒𝑥𝑝𝑟2 >; › sia T il tipo della variabile a cui punta ptr; Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  › il riferimento < 𝑒𝑥𝑝𝑟1 > [< 𝑒𝑥𝑝𝑟2 >] denota la variabile di tipo T che si trova a partire dall’indirizzo ptr + N (intesa con la semantica della somma tra puntatori); ovvero la N+1-esima variabile di tipo T che si trova memorizzata a partire dall’indirizzo ptr. In base a ciò possiamo notare che il riferimento < 𝑒𝑥𝑝𝑟1 > [< 𝑒𝑥𝑝𝑟2 >] equivale al riferimento ∗ (< 𝑒𝑥𝑝𝑟1 >+< 𝑒𝑥𝑝𝑟2 >) ESEMPI. 2) Rappresentazione: Il Linguaggio C - Array Multi-Dimensionali. Array multi-dimensionali: è possibile dichiarare un array di variabili che sono a loro volta degli array. EX. int A; › A è una costante di tipo puntatore ad array di 4 variabili di tipo intero, o equivalentemente A è l’indirizzo di array di 4 variabili di tipo intero; › A, …, A sono costanti di tipo puntatore a intero, ovvero di tipo indirizzo di intero; › A[i][j] (con 𝑖,𝑗 ∈ ℕ, 𝑖 ∈ {0,1, … , 7}, 𝑗 ∈ {0,1,2,3}) denota la j-esima variabile di tipo int dell’i-esimo array di 4 int a partire dall’indirizzo di A (A è un valore di tipo puntatore ad array di 4 int); › A[i][j] è la variabile all’indirizzo A+i*(4*sizeof (int))+j*sizeof (int): ∙ A è un valore di tipo puntatore ad array di 4 float; ∙ A[i] è un valore di tipo puntatore a float. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Nella pratica della programmazione C, le matrici a più dimensioni sono comunemente dichiarate come array monodimensionali, lasciando al programmatore la gestione dell’indicizzazione. Notiamo che C[i][j] si trova nella posizione i*J+j, dove J è il numero delle colonne di C. Quindi, una matrice di dimensioni I × J si può dichiarare come un array monodimensionale di dimensioni I∗J, e un generico elemento [i][j] è selezionato con l’indice [i*J+j]. Riscriviamo il precedente esempio tramite array monodimensionali: Nel caso di matrici a 3 dimensioni l’elemento viene referenziato come [i*J*K+j*K+k], dove J e K denotano il numero di valori del secondo e del terzo indice: Rappresentazione: Il Linguaggio C - Allocazione dinamica. Nella dichiarazione di un array è necessario specificare al compilatore il numero di elementi per determinare l’ampiezza del segmento di memoria che deve essere riservato all’array che può essere una limitazione in molti contesti di programmazione. Se volessimo calcolare il prodotto di due matrici di dimensioni variabili, dovremmo sostituire tutte le occorrenze delle varie dimensioni nel programma e ricompilare il programma. Questo è un processo inefficiente e suscettibile ad errori. Per mitigare questa limitazione, conviene definire il numero di righe e il numero di colonne attraverso delle costanti con la direttiva di pre-processing #define. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) ESEMPIO. Rappresentazione: Il Linguaggio C - Allocazione dinamica (malloc). La direttiva #define , tuttavia, non permette di trattare array la cui dimensione è determinata durante la l’esecuzione del programma (run-time). Per superare questa limitazione occorre che lo spazio per rappresentare l’array sia allocato durante l’esecuzione del programma. Questo è possibile usando la funzione malloc ( ) (definita nella libreria standard ). Tramite la funzione malloc ( ) viene allocato uno spazio di memoria di tanti byte quanti sono indicati nell’argomento di malloc. La funzione restituisce il puntatore al primo byte della locazione della memoria a partire dalla quale è stato riservato lo spazio per l’array. Il tipo restituito è void: void *malloc(). Riprendiamo l’esempio precedente del prodotto tra due matrici le cui dimensioni sono determinate durante l’esecuzione del programma: Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) La funzione malloc ( ) fallisce se il sistema operativo non dispone di uno spazio contiguo di memoria della dimensione richiesta. In tal caso restituisce null (che è lo 0 dei puntatori, ed è definito da una direttiva #define dentro la libreria ). Nella realizzazione di un programma è necessario introdurre dei controlli che impediscano al programma di fare uso di quelle variabili la cui allocazione sia fallita. Un segmento di memoria allocato con la funzione malloc ( ) resta in uso fino al termine del programma, o fino a quando, nel caso in cui questo non sia più utile al programma, non venga rilasciato attraverso l’uso della funzione free ( ) che libera la memoria precedentemente associata ad un puntatore con malloc ( ), ed è definita nella libreria standard < stdlib.h >. Ricapitolando sulle differenze tra la dichiarazione di una variabile array allocata › staticamente float As; in questo caso lo spazio di memoria è allocato nel segmento stack › dinamicamente float *Ad; Ad=(float *)malloc(128*sizeof(float)); in questo caso lo spazio di memoria è allocato nello heap Entrambe restituiscono un valore di tipo indirizzo di float. As è una costante di tipo indirizzo di float che punta fin dall’inizio ad un segmento di memoria riservato di 128 float, Ad è una variabile di tipo puntatore a float che è inizialmente impredicibile. Il segmento di memoria che viene allocato tramite la chiamata a malloc ( ) non è contiguo alle altre variabili del programma, ma l’area di allocazione è gestita dal sistema operativo. ESEMPIO. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  5/4 Rappresentazione: Il Linguaggio C – Istruzioni. Le Istruzioni controllano il flusso di esecuzione di un programma. Esistono differenti tipologie di istruzioni: 1. Espressione: istruzione elementare, composta da un’espressione e punto e virgola. < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= < 𝑒𝑥𝑝𝑟 >; | … La semantica consiste nel calcolare il valore dell’espressione e passare il controllo all’istruzione successiva. 2. Sequenze: istruzione rappresentata da due o più istruzioni che possono essere combinate in sequenza e/o raccolte in compound. < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … | < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡1 >< 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡2 > | < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > La semantica della sequenza consiste nell’eseguire < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡1 >, poi < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡2 >, e passare il controllo all’istruzione successiva; quella del compound consiste nell’eseguire < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > dentro il compound, e poi passare il controllo all’istruzione successiva. 3. Condizione: permettono di condizionare l’esecuzione di un’istruzione (corpo), al valore restituito da un’espressione (guardia): < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … | 𝑖𝑓(< 𝑒𝑥𝑝𝑟 >) < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡1 > | 𝑖𝑓 < 𝑒𝑥𝑝𝑟 > < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡1 > 𝑒𝑙𝑠𝑒 < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡2 > | … La semantica dell’istruzione if consiste nel calcolare inizialmente l’espressione < 𝑒𝑥𝑝𝑟 >. Se il valore restituito è diverso da zero (cioè se è true) viene eseguita l’istruzione < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡1 >. Se la guardia è false viene eseguito il corpo alternativo < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡2 >. In entrambi i casi il controllo viene passato all’istruzione successiva. 4. Iterazione(loop): eseguire ripetitivamente un corpo di istruzioni fino al momento in cui una espressione di guardia diventa falsa. Esistono tre diverse istruzioni di iterazione: for, while e do- while, che differiscono nel modo in cui è espressa la guardia: for: Nella semantica dell’istruzione for, inizialmente viene eseguita l’espressione di inizializzazione < 𝑒𝑥𝑝𝑟_𝑖𝑛𝑖𝑡 >. Viene poi calcolata l’espressione di guardia < 𝑒𝑥𝑝𝑟_𝑔𝑢𝑎𝑟𝑑 >: se il risultato restituito è diverso da 0 (true), viene eseguito il corpo < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 >, viene calcolata l’espressione di incremento < 𝑒𝑥𝑝𝑟_𝑖𝑛𝑐 >, e il controllo viene riportato all’espressione di guardia; se invece il risultato restituito è uguale a 0, (false), allora l’iterazione termina e il controllo viene passato all’istruzione successiva. while: < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … | 𝑤ℎ𝑖𝑙𝑒 < 𝑒𝑥𝑝𝑟_𝑔𝑢𝑎𝑟𝑑 > < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > | … Nella semantica dell’istruzione while, viene inizialmente calcolata l’espressione di guardia < 𝑒𝑥𝑝𝑟_𝑔𝑢𝑎𝑟𝑑 >; se il valore restituito è diverso da 0 (true), viene eseguito il corpo e il controllo viene riportato all’espressione di guardia; quando l’espressione di guardia restituisce un valore false l’iterazione termina e il controllo viene passato all’istruzione successiva. do-while: < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … | 𝑑𝑜 < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > 𝑤ℎ𝑖𝑙𝑒 < 𝑒𝑥𝑝𝑟_𝑔𝑢𝑎𝑟𝑑 > | … Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  Nella semantica dell’istruzione do-while, viene inizialmente eseguito il corpo e poi calcolata l’espressione di guardia. Se la guardia restituisce true, il controllo torna all’esecuzione del corpo, se invece restituisce false, il controllo passa all’istruzione successiva. N.B. Il ciclo for è adatto quando il numero di iterazioni è noto a priori; while e do-while sono invece adatti quando il numero di iterazioni non sono note a priori. Nei cicli for e while la guardia è determinata prima di raggiungere il corpo; in do-while la guardia può essere determinata dal corpo delle istruzioni. I cicli for e while garantiscono che la guardia è vera prima dell’esecuzione del corpo; in do-while la guardia può non essere vera prima dell’esecuzione del corpo. Sia while che do-while garantiscono in uscita che la condizione di guardia è falsa. 5. Salto: utilizzate per trasferire il controllo ad istruzioni non contigue. L’istruzione goto label passa il controllo alla prima istruzione successiva all’etichetta label. < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … 𝑔𝑜𝑡𝑜 < 𝑙𝑎𝑏𝑒𝑙 >; … Dove: < 𝑙𝑎𝑏𝑒𝑙 > ha lo stesso formato di < 𝑖𝑑𝑒𝑛𝑡𝑖𝑓𝑖𝑒𝑟 > (nome di variabile) ed equivale all’istruzione jump incondizionato di un linguaggio assembly. È sconsigliato perché lascia indeterminata l’istruzione di salto che porta alla label. Potrebbe essere usato per entrare e Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected])  uscire dai limiti del corpo di una istruzione condizionale o di iterazione senza che venga valutato il controllo della guardia. L’istruzione switch è un goto aritmetico, e rappresenta di fatto un’istruzione condizionale. Presenta: - una guardia in testa (< 𝑒𝑥𝑝𝑟 >) che deve restituire un valore intero; - un corpo delimitato da parentesi graffe, che contiene un numero di etichette, ciascuna associata a un diverso valore costante < 𝑐𝑜𝑛𝑠𝑡 >, anch’esso di tipo intero. L’etichetta è opzionale. Viene calcolata l’espressione < 𝑒𝑥𝑝𝑟 >: se il valore restituito è uguale a quello di una delle costanti che appaiono in un’etichetta 𝑐𝑎𝑠𝑒, allora il controllo viene trasferito a quell’etichetta e l’esecuzione prosegue fino al termine del corpo dell’istruzione; se nessuna delle costanti coincide con il valore restituito allora il controllo viene trasferito alla chiusura del corpo dello 𝑠𝑤𝑖𝑡𝑐ℎ, oppure all’etichetta 𝑑𝑒𝑓𝑎𝑢𝑙𝑡: (quando questa è presente). L’istruzione break può comparire solo all’interno del corpo di un’istruzione di iterazione o di uno switch. < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … 𝑏𝑟𝑒𝑎𝑘; … Il controllo viene trasferito alla prima istruzione successiva all’istruzione di iterazione o lo switch che la contiene. Se l’istruzione break è contenuta in uno switch, le istruzioni associate alle diverse etichette sono eseguite in maniera alternativa invece che incrementale. L’istruzione continue può comparire solo all’interno del corpo di un’istruzione di iterazione. < 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 > ∷= … 𝑐𝑜𝑛𝑡𝑖𝑛𝑢𝑒; … Trasferisce il controllo al termine dell’iterazione corrente (ovvero al termine dell’esecuzione corrente del copro di istruzioni). ESEMPI. 1. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) 2. 3. 11/4 Rappresentazione: Il Linguaggio C – Funzioni. Una funzione è un costrutto di controllo del flusso del programma, è una sezione di codice (sequenza di dichiarazioni e istruzioni) associata ad un nome. Ogni qualvolta una funzione viene invocata (chiamata) facendo riferimento nel codice al suo nome, il controllo viene trasferito a quella sezione di codice; quando la sezione di codice della funzione termina (tramite un’istruzione return o per esaurimento delle istruzioni), il controllo torna al punto della sezione di codice che ha invocato la funzione (ritorno del controllo). Un programma C è generalmente costituito da un insieme di funzioni: il controllo è inizialmente attribuito a una funzione principale che ha nome main() e termina quando la funzione principale main() restituisce il controllo. Document shared on https://www.docsity.com/it/fondamenti-di-informatica-slide-appunti-lezioni/10119621/ Downloaded by: giii3 ([email protected]) Una funzione è dunque una sorta di salto con ritorno condizionato che permette di restituire il controllo al particolare punto dal quale è stata chiamata.: una volta che la sezione di codice della funzione è terminata, il controllo viene restituito al punto della sezione di codice chiamante che ha invocato la funzione. Una funzione permette chiamate nidificate e ricorsive e separa lo spazio delle variabili dalla sezione di codice chiamante/chiamata, quindi: › possono esistere variabili con lo stesso nome in sezioni di codice diverse; › si ha il meccanismo di information hiding. Rappresentazione: Il Linguaggio C - Funzioni (Legame tra Parametri). 3 Meccanismi di comunicazione tra sezioni di codice: 1. Tramite Variabili Globali: variabili dichiarate al di fuori di qualsiasi funzione, ovvero sono visibili in tutte le funzioni del programma. Questo è un meccanismo generalmente da evitare. 2. Tramite Valore Restituito: la funzione chiamata ad un certo punto restituisce il controllo alla funzione chiamante, e può restituire anche un valore. 3. Tramite Parametri: › parametri formali: variabili che assumono una realizzazione concreta al momento in cui la funzione chiamata riceve il controllo; › parametri attuali: variabili specificate dalla funzione chiamante che vengono legati ai parametri formali in modo da attribuire loro un’identità e un valore. Il legame tra parametri formali e attuali è un meccanismo di comunicazione bidirezionale tra funzione chiamante e funzione chiamata, in cui vengono scambiati i valori di ingresso sui quali applicare la computazione della funzione chiamata e i risultati prodotti nella computazione. Il legame tra i parametri può avvenire in due modalità: · per riferimento (C++, Java): un 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 e la funzione chiamante e la funzione chiamata condividono le variabili specificate come parametri attuali. · per valore (C): un parametro attuale è un’espressione, al momento della chiamata viene creata una variabile temporanea (visibile solo alla funzione chiamata), che viene inizializzata con il valore restituito dal corrispondente parametro attuale. La funzione chiamata non ha accesso alla variabile