Linguaggi procedurali
Paolo Bison
Fondamenti di Informatica Ingegneria Meccanica
Università di Padova A.A. 2008/09
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.1
Linguaggi procedurali
classe di linguaggi di programmazione basati sull’istruzione di assegnazione: C, Pascal, Fortran
elementi
dati
•
variabili
azioni
•
espressioni
•
istruzioni di controllo
•
istr. di assegnazione
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.2
Espressioni
elementi del linguaggio la cui valutazione fornisce un determinato valore
costituite da operandi, operatori e funzioni
espressioni matematiche
consideriamo
operandi a valore intero
operatori aritmetici (espressioni numeriche) + − × /
operatori di confronto (espressioni logiche/predicati)
= 6= > ≥ < ≤
Come si scrivono le espressioni?
sintassi
descrizione di come si scrivono espressioni corrette combinando simboli base (cifre, operatori, parentesi)
notazioni
infissa op1 oper op2 5 + 3 / 9
postfissa op1 op2 oper 5 3 + 9 /
prefissa oper op1 op2
/ + 5 3 9
Come si valutano le espressioni? - I
TEST: Qual’è il valore di
5 + 3 / 2 1. 6
2. 6.5 3. 4
4. dipende
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.5
Come si valutano le espressioni? - II
semantica
regole per valutare una espressione
significato degli operatori
ordine di valutazione
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.6
Significato degli operatori
operazione matematica associata ai simboli di operatore + addizione
− sottrazione
× moltiplicazione / divisione - intera
- decimale
Ordine di valutazione
la sequenza in cui vengono applicati gli operatori agli operandi
ordine di scrittura
da sx a dx
5 + 3 / 2 = 4
da dx a sx
5 + 3 / 2 = 6
priorità predefinite
× , / valutati prima di + , −
ordine esplicito
parentesi ( )
Espressioni logiche
espressioni che ritornano un valore di verità (vero,falso)
predicati
operatori di confronto
= 6= > ≥ < ≤
esempi
lato quadrato 6= 0
primo numero ≥ secondo numero
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.9
Istruzioni
elementi del linguaggio che definiscono le azioni da svolgere
modifica dati
•
istruzione di assegnazione
flusso di esecuzione
•
istruzioni di controllo
· struttura sequenziale
· struttura condizionale
· struttura iterativa
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.10
Struttura sequenziale
sequenza di istruzioni da eseguirsi una di seguito all’altra
sintassi
sequenza di scrittura
semantica
istuzioni eseguite uno alla volta
ciascuna istruzione è eseguita una sola volta e nessuna è omessa o ripetuta
l’ordine di esecuzione è quello di scrittura
algoritmo termina con il termine dell’ultima istruzione
struttura rigida
esecuzione non può essere modificata
Es. struttura sequenziale
somma delle radici quadrate di tre numeri J, K, L calcola √
J calcola √
K calcola √
L
somma le tre radici quadrate
Struttura di selezione
permette di eseguire istruzioni differenti al verificarsi o meno di una condizione (espressione logica)
sintassi
if predicato istr_1 else
istr_2
semantica
se il predicato è vero si esegue istr_1, altrimenti istr_2
variante ad una sola via if predicato
istr_1
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.13
Es. struttura di selezione
dati due numeri,sommare al primo il valore assoluto del secondo
if il secondo numero < 0 sottrai il secondo dal primo else
somma il primo con il secondo
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.14
Istruzioni di clausola
quali istruzioni sono sotto il controllo di una clausola if o else ?
elementi sintattici { } begin end
identazione
rientranza a dx nella scrittura delle istruzioni
if A > B
somma A con B
moltiplica C con D 6≡ if somma A con B A > B moltiplica C con D
Gerarchie di selezione
sequenze in cascata di costrutti di selezione: if annidati (nested)
scelta del massimo tra tre numeri X,Y e Z
ifX>Y ifX>Z
X è max else
Z è max else
ifY>Z Y è max else
Z è max
Es. ricerca
ricerca di un indirizzo in un archivio dato il nome leggi nome della prima scheda
if è il nome cercato estrai indirizzo else
leggi nome della seconda scheda if è il nome cercato
estrai indirizzo else
if ...
non è possibile esprimere algoritmi la cui lunghezza dipenda da fattori esterni
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.17
Strutture iterativa
ripetizione di un dato numero di istruzioni per un numero arbitrario, ma finito di volte
ciclo (loop)
permette di descrivere una elaborazione di durata indeterminata con un numero finito di istruzioni
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.18
Tipi di iterazione
definita
durata determinata e conosciuta prima dell’esecuzione
termine garantito
indefinita
durata indeterminata
termine dipende dal verificarsi o meno della condizione di terminazione
Ciclo while
sintassi
while predicato istr
semantica
- si valuta il predicato - se vero
- si esegue istr
- e si torna a valutare il predicato altrimenti termina l’esecuzione
iterazione indefinita
Es. while
ricerca in un archivio di schede
leggi nome da prima scheda
while nome non è quello cercato e vi sono ancora schede
leggi nome da scheda successiva if hai trovato il nome
leggi indirizzo da scheda
ciclo errato se archivio vuoto
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.21
Ciclo repeat
sintassi
repeat espressione istr
semantica
- si valuta l’espressione che deve ritornare un valore intero positivo
- si esegue istr per un numero di volte pari a tale valore
iterazione definita
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.22
Es. repeat
stampa di 100 asterischi * repeat 100
stampa *
Variabile
elemento che può assumere un qualunque valore ma che in ogni momento dell’esecuzione è associato ad uno ed uno solo valore
nome (identificatore)
sequenza di caratteri alfanumerici ris x0 st
etichetta di un contenitore
ris -150
x0 3.67
st hello
operandi in espressioni
condivisione di dati tra istruzioni
Operazioni su variabile
accesso al valore attuale x0+ris-7
ris 34
x0 -10
valore dell’espressione: 17
modifica del valore associato
istruzione di assegnazione
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.25
Istruzione di assegnazione
sintassi
id ← espressione
aaaltri simboli := =
semantica
al termine dell’esecuzione alla variabile id è associato il valore ottenuto valutando l’espressione
esempio
ris ← 34
•
prima: ris -150
•
dopo: ris 34
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.26
Significato identificatori nell’assegnazione cnt ← cnt + 1
lato destro
accesso al valore corrente
cnt 17
lato sinistro
riferimento al contenitore
cnt 17
risultato
cnt 18
Ordine di esecuzione
n ← m
m ← r 6≡ m ← r n ← m
dati
m 17 n 23 r 31
n ← m
m ← r ⇒ m 31 n 17 r 31
m ← r
n ← m ⇒ m 31 n 31 r 31
Scambio tra due variabili
scambio di valori tra m e n
ERRATO
•
scambio diretto m ← n
n ← m
CORRETTO
•
uso di una terza variabile per salvare il valore di una delle due da scambiare
t ← m m ← n n ← t
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.29
Programmazione strutturata
teorema di Jacopini-Böhm
ogni algoritmo può essere espresso utilizzando solo tre strutture di controllo
struttura sequenziale
struttura di selezione
un ciclo indefinito ( while )
Linguaggi procedurali, Paolo Bison, FI08, 2008-09-29 – p.30
Programma equivalente per repeat