Riassunto esame Informatica, prof. Carnevali, libro consigliato Fondamenti di Programmazione, Vicario: teoria

OPERATORI ED ESPRESSIONI:

Esistono 3 tipi di operatori,tramite i quali si compongono espressioni. Questi sono operatori aritmetici,

relazionali e logici. Gli op. aritmetici sono somma,differenza,prodotto,divisione e modulo. Gli op.

relazionali sono i confronti fra valori,ovvero maggiore/minore, mag.uguale/min.uguale, uguale/diverso.

Gli op. logici sono congiunzione,disgiunzione, negazione e assegnamento.

Il linguaggio c si basa sui side effect causati dalle espressiioni, ogni operatore produce diversi side

effects. Il side effect è l'effetto prodotto sul dato dal calcolo di una espressione.

INSTRUZIONI:

Le istruzioni servono a dirigere il flusso dell'esecuzione,esse determinano l'ordine con cui vengono

eseguite le espressioni. Esistono molti tipi di istruzioni.

Una o più espressioni sono una istruzione. Un insieme di istruzioni raccolte dentro parentesi sono una

istruzione Compound. Esse sono raccolte in blocchi e trattate in maniera unitaria.

CONDIZIONE:

è un costrutto che controlla il flusso di esecuzione in base al risultato di una espressione, detta

espressione di guardia. In base al confronto con la guardia, il programma esegua una istruzione (if)

oppure un altra(else).

ITERAZIONE:

Le istruzioni di iterazione (loop) consentono di eseguire un corpo di espressioni finchè non si verifica

una espressione di guardia. Esistono tre tipi di costrutto di iterazione.

Il ciclo FOR si usa quando si conosce il numero di operazioni da eseguire. Il for presenta una guardia

costituita da tre espressioni, una inizializzazione (count=0), una guardia (count <10), e un incremento

(count++). In questo caso il corpo del for viene eseguito finchè si verifica count<10.

Il ciclo WHILE esegue un corpo di operazioni finchè non è verifica una espressione di guardia. La

guardia viene verifica anche prima della prima esecuzione. Il ciclo DO-WHILE è identico al while,

differenzia per il fatto che prima viene eseguito il corpo una volta e poi controllata la guardia.

LINGUAGGIO ASSEMBLER:

L'assembler è il linguaggio delle istruzioni che possono essere eseguite sul preocessore.

Il linguaggio di alto livello viene trasformato in linguaggio assembler(di basso livello, alfanumerico)

attraverso l'assembler, questo linguaggio viene poi trasferito al processore che trasforma in

binario(basso livello, numerico).Consideriamo un assembler RISC(Reduced Istruction Set Computer), il

MIPS.

CALCOLO ESPRESSIONI E ESECUZIONE SEMPLICI ISTRUZIONI:

Istruzioni base:

istruzioni di calcolo

add: corrisponde alla somma fra variabili. Es: a=b+c = add a, b, c → add $x, $y, $z

– questa operazione calcola i valori contenuti nei registri $y e $z e li mette in $x.

Per creare somme con più di due addendi si fa uso di un registro temporaneo su cui inserire la

somma delle prime due, poi si somma tale registro al terzo addendo.

Addi: corrisponde alla somma fra variabile e costante es: addi $x, $y, 3 → $x=$y+3.

– Sub, subi: è la sottrazione e operano come add e addi. Sub a,b,c → a=b-c.

– Mult,Multi: è la moltiplicazione e opera come gli altri. Mult a,b,c → a=b*c.

–

Istruzioni di trasferimento dati

load-word: lw $x,Base[$y]: colloca in $x il valore contenuto nel registro $[Base+y]

– store word: sw $x,Base[$y]: colloca in $[Base+y] il valore contenuto all'indirizzo $x.

–

Controllo del flusso

Brench if equal: beq $x,$y, label Corrisponde alla condizionale del c. Se il contenuto di $x è

– uguale a quello di $y, il controllo passa all'istruzione successiva alla label, altrimenti il codice

prosegue normalmente. Beq è limitato a una condizione di uguaglianza, a differenza di if.

Set on less than: slt $x,$y,$z. Serve per confrontare i valori. Se $y>$z, $x assume il valore 1,

– altrimenti se $y<$z, $x = 0. Combinando beq e slt si creano i test relazionali.

Salto

Jump: J label è il salto incondizionato all'istruzione successiva alla label.(E' il go to del c).

–

DEFINIZIONE DI UN LINGUAGGIO:

Un linguaggio si definisce tramite sintassi e semantica. La sintassi determina cosa e in che forma può

apparire all'interno di un linguaggio, la semantica definisce il significato attribuito ad ogni espressione

legale

SINTASSI:

Un linguaggio è un sottoinsieme di un vocabolario. Un vocabolario V è un insieme di simboli,il suo

universo linguistico V* comprende tutte le sequenze finite composte con tali simboli e un linguaggio è

l'insieme dei costrutti creati con tali simboli,ovvero un sottoinsieme di V*. Definire la sintassi significa

definire i limiti del sottoinsieme del vocabolario,l'universo linguistico V*. Uno dei modi per definire una

sintassi è l'uso di una grammatica.

GRAMMATICA:

Una grammatica è una quadrupla G=<V,N,S,P>, dove:

V è un insieme chiamato vocabolario i cui simboli sono detti simboli terminali. Il vocabolario

– raccoglie tutti i simboli che possono comparire in qualsiasi espressione

N è l'insieme delle categorie sintattiche (es: <var>, <expr>, <op>, ...)

– S è un elemento di N detto simbolo iniziale, a cui è possibile ricondurre ogni produzione

– attraverso un metodo chiamato albero sintattico

P è una relazione fra N e (N V), ovvero un insieme di coppie composte da un elemento di N e

– u

una sequenza di elementi appartenenti a N u V.

Linguaggio definito tramite Grammatica: un linguaggio definito da una grammatica

G=<V,N,S,P> sul vocabolario V, è l'insieme degli elementi delle forme legali di V, V*, che

derivano dal simbolo iniziale S attraverso le categorie sintattiche N e le produzioni P.

Esempio: V = var u {+,-,*,/,(,),} sono i simboli elementari che possono comparire nelle espressioni.

S = expr, è la categoria di cui il linguaggio definisce le espressioni legali.

Adesso è possibile definire le produzioni P che permettono di ridurre la espressione in simboli terminali

S, passando attraverso varie categorie sintattiche N. Ciò accade con la definizione di un albero

sintattico. Un albero sintattico è un insieme di nodi su cui è definita una relazione di successione

tramite i quali si raggiunge un unico predecessore. Quando non è possibile raggiungere un unico

predecessore, l'espressione non è legale per tale linguaggio.

Es: a+b = var op var = expr → legale; a++*b= var op op op var = err. → illegale.

METALINGUAGGIO “BNF” (BACKUS NAUR FORM):

Un Metalinguaggio è un linguaggio con cui si rappresentano altri linguaggi. Tramite un metalinguaggio

è possibile definire la forma delle espressioni legali,definite con una corretta sintassi:

<expr>::= <var>|<expr><var><expr>|<(expr)> → sono tutte forme legali. Tutte le espressioni che non

possono essere ricondotte a questa forma attraverso un albero sintattico, sono espressioni illegali.

L'interpretazione di una espressione si articola in 3 fasi :

Verifica lessicale: si verifica che l'espressione appartenga all'insieme V* del vocabolario, che

– tutti i simboli appartengano a V e che rispettino le relazioni su V definite dal linguaggio.

Verifica sintattica: Si verifica la legalità di una espressione, la quale può essere lessicalmente

– corretta ma può allo stesso tempo presentare errori di sintassi → albero sintattico.

Verifica contestuale : Una espressione lessicalmente e sintatticamente corretta può presentare

– un errore contestuale, ovvero può trovarsi in una situazione in cui questa non ha alcun

significato legate.(es: else senza un precedente if)

SEMANTICA:

La semantica di una espressione consiste nel valore G che essa restituisce. Per definire una semantica

è necessario conoscere il valore G restituito da ogni espressione del linguaggio. Ogni espressione, in

base alle operazioni e al tipo con cui è definita, può avere una diversa semantica.

ESEMPI DI ALBERI SINTATTICI E DICHIARAZIONI IN BNF:

Variabile: <type-decl><identifier> → <type-decl> <decl> → <declaration>

– Puntatore: <type-decl> * <identifier> → “” “” * “” → <declaration>

– Array: <type-decl><identifier>[<const>]<type-decl><decl><[<const>] → <declaration>

– Dato strutturato: struct <identifier> {{ <var_declaration>}} → <struct_def>

–

COMPUTER PROCESSING UNIT (CPU)

La CPU esegue i programmi caricati in memoria, dopo essere stati tradotti in linguaggio assembler.

La CPU contiene 5 blocchi funzionali fondamentali, che sono:

Memoria del programma (data memory) : Contiene una sequenza lineare di locazioni che

– vengono lette e riscritte durante la computazione. E' costituita da 3 ingressi(data_in,data_out)

che regolano l'uscita e l'entrata dei dati e addr, che riceve l'indirizzo,e 2 ingressi di controllo

(wr_enable,rd_enable) che abilitano la memoria a sovrascrivere e leggere i registri.

Memoria delle istruzioni : viene spesso congiunta con la memoria del programma, contiene

– tutta la sequenza di istruzioni che deve essere eseguita. Scambia dati con la memoria ( dopo

essere stati trasformati in 16 bit) del programma e con il banco dei registri.

Banco dei registri: Contiene 32 registri di 32 bit. Permette contemporaneamente la lettura di

– due registri e la scrittura in un terzo(add_wr). Riceve le istruzioni dalla memoria delle istruzioni

e invia le operazioni aritmetiche e logiche alla ALU, codificate in due registri (add_r1 e add_r2)

accompagnati da una cifra che indica il tipo di operazione da eseguire.

ALU (Aritmetical Logic Unit): esegue operazioni aritmetiche e logiche, riceve due ingressi per gli

– operandi e uno per il tipo di operazione, ha due uscite, una per il risultato e un'altra che notifica

quando il risultato è 0.

Program counter: E' un indirizzo di 32 bit che codifica l'indirizzo dell'operazione in atto. Quando

– viene asserito il bit nell'ingresso check, memorizza il valore sulla porta di ingresso, il quale

codifica una istruzione,la quale viene mantenuta in memoria fino al successivo aggiornamento.

Il check arriva dal clock di sistema, per ogni colpo di clock si aggiorna l'operazione da eseguire.

Altri componenti di minore importanza sono:

Sommatore: E' una ALU semplificata che esegue soltanto l'addizione

– Multiplexor: E' un dispositivo che riceve due ingressi e, in base al segnale di controllo, stabilisce

– quale inviare alla componente successiva.

Control Unit (CU) E' una rete combinatoria: Riceve in ingresso un segnale che codifica il tipo di

– operazione da eseguire e, in base a tale segnale, configura tutte le componenti della CPU in

modo da eseguire