fondamenti di informatica1 linguaggi classificati rispetto alle caratteristiche principali:...
TRANSCRIPT
Fondamenti di Informatica 1
Linguaggi
• Classificati rispetto alle caratteristiche principali:– potere espressivo che influenza lo stile
di programmazione
Fondamenti di Informatica 2
Linguaggi - basso livello
• Il linguaggio macchina specifica solo le operazioni che l'elaboratore può eseguire– sintattica molto elementare"– diverso per ogni processore
• dipende dalle caratteristiche architetturali
• E' più orientato alla macchina che ai problemi da trattare– è infatti definito di "basso livello"
Fondamenti di Informatica 3
Linguaggi - basso livello
• Una prima evoluzione è stata l'introduzione di linguaggi simbolici: linguaggi assemblativi– ancora orientati alla macchina e non
ai problemi– più immediati da utilizzare– definiscono variabili, simboli,...
Fondamenti di Informatica 4
Linguaggi - alto livello
• Altri linguaggi sono basati su:– la descrizione del problema in modo
intuitivo, dimenticandosi che verranno eseguiti da un calcolatore
– obiettivo: fornire un mezzo espressivo per specificare all'elaboratore il compito da eseguire
Fondamenti di Informatica 5
Linguaggi - alto livello
• Caratteristiche:– ognuno ha i propri paradigmi che
garantiscono forme espressive appropriate per alcuni problemi specifici
– questa specificità ha favorito la loro proliferazione (fenomeno intrinseco alla natura del linguaggio come forma di comunicazione)
Fondamenti di Informatica 6
Linguaggi Imperativi
• Linguaggi più evoluti:– permettono di descrivere operazioni più
complesse di quelle che l'elaboratore può eseguire
– livello di astrazione più alto– risalgono agli anni '50– detti di alto livello di tipo imperativo– Es: Basic, Fortran, Pascal
Fondamenti di Informatica 7
Linguaggi Imperativi
• Caratteristiche:– di utilizzo più semplice– indipendenti dall'elaboratore– purtroppo ancora legati al modello di
Von Neumann:• i programmi sono ancora una sequenza di
istruzioni; l'evoluzione del calcolo è costituita da una variazione dello stato della memoria
Fondamenti di Informatica 8
Linguaggi Imperativi
• Eseguono 3 tipi di operazioni:– trasferimento dati– operazioni aritmetiche– alterazione del flusso del programma
• Già discussi in precedenza• Basic (semplice ma poco espressivo)
• Fortran (molto usato per il calcolo scientifico e le librerie molto complete)
Fondamenti di Informatica 9
Linguaggi Funzionali
• Non sono legati al modello di Von Neumann ma al concetto di programmazione funzionale
• Il primo linguaggio funzionale:– Lisp (List Processing), fine anni '50– caratteristiche di manipolazione
agevole di informazioni di tipo simbolico
Fondamenti di Informatica 10
Linguaggi Funzionali
• Differenze con i linguaggi imperativi:– il calcolo è basato sul calcolo di valori e
non sull'assegnamento di valori a variabili
– basato su valori e non su effetti– il risultato è il risultato di una funzione,
non l'effetto causato dalla esecuzione di una sequenza di operazioni
Fondamenti di Informatica 11
Linguaggi Funzionali
• Caratteristiche:– meccanismo di definizione funzionale
per casi (tipo switch in C)– è possibile la ricorsione (utilizzando
tali costrutti condizionali)– Il Lisp, però, consente anche
l'iterazione e l'assegnamento (tipico dei ling. Imperativi)
Fondamenti di Informatica 12
Linguaggi Dichiarativi
• Basati sulla logica– obiettivo: formalizzare il ragionamento– caratterizzati da meccanismi deduttivi
• Programmare significa:– descrivere il problema con formule del
linguaggio– interrogare il sistema, che effetua
deduzioni sulla base delle definizioni
Fondamenti di Informatica 13
Linguaggi Dichiarativi
• Programmazione:– semplice (occorre solo definire la
propria conoscenza del problema)– avviene tramite una formulazione
dichiarativa
• Esempio: Prolog
Fondamenti di Informatica 14
Linguaggi Dichiarativi
• Un programma Prolog è costituito da:– Asserzioni incondizionate (fatti): A – Asserzioni condizionate (o regole):
A IF B,C,D,…• A: è la conclusione (conseguente)• B,C,D: sono le premesse (o antecedenti)
• Una interrogazione ha la forma: ? A, B, C, …
Fondamenti di Informatica 15
Esempio
• Il fattoriale:Fatt (0,1)Fatt (z,w) IF Dec(z,z1), Fatt(z1,w1),Prod(z,w1,w)
• Problemi risolubili:– calcolo del fatoriale: ? Fatt(3, x)– calcolo di quel numero il cui fattoriale è
noto: ? Fatt(x, 6)
Fondamenti di Informatica 16
Esempio
• Ricerca in un grafo orientato:
– con la richiesta ? go(E) vienedeterminata la sequenza E, C, A
go(A)arc(A,B) arc(B,C) arc(D,C)arc(A,C) arc(B,D) arc(C,E)go(y) IF arc(x,y), go(x)
B
C
DA
E
Fondamenti di Informatica 17
Sintassi e Semantica
• Nei linguaggi naturali si distinguono:– sintassi (si occupa della forma delle
frasi, delle regole per la loro creazione)– semantica (significato delle frasi)
• Analogamente per i linguaggi di programmazione:– sintassi: definisce i programmi legali– semantica: significato dei programmi
Fondamenti di Informatica 18
Sintassi e Semantica
• Dopo la definizione di un linguaggio (con sintassi e semantica) serve un sistema che possa eseguire i programmi scritti in tale linguaggio
• Si parla di implementazione di un linguaggio– generalmente è un traduttore verso il
linguaggio macchina di un dato elaboratore
Fondamenti di Informatica 19
Sintassi
• Per definire la sintassi di un linguaggio, è necessario definire le grammatiche
• La grammatica è un insieme di regole che servono per costruire una frase
Fondamenti di Informatica 20
Grammatica
• La grammatica è definita da:– V: un alfabeto di simboli terminali
(l'alfabeto del linguaggio)– N: un alfabeto di simboli non terminali– S: un simbolo iniziale (o assioma)– P: un insieme finito di regole sintattiche
(dette produzioni) espresse nella forma: X a
Fondamenti di Informatica 21
Grammatica
• Le produzioni possono essere scritte:– anche nella forma alternativa:
X ::= a– se esistono più produzioni con parte
sinistra uguale,X ::= a X ::= b X ::= c
allora si può scrivere: X ::= a | b | c
Fondamenti di Informatica 22
Grammatica
• Derivazioni:– una stringa c deriva dalla stringa b se
esse possono essere decomposte in:b = m A n c = m a n
con m e n simboli non terminali e se esiste la produzione
A ::= a
Fondamenti di Informatica 23
Grammatica
• Data una grammatica, il linguaggio generato è definito come l'insieme delle frasi derivabili a partire dall'assioma S
• Le frasi di un linguaggio di programma-zione sono dette programmi
Fondamenti di Informatica 24
Formalismo di Backus-Naur
(Backus -Naur Form, BNF)
• Il modo visto per definire una grammatica è detto di Backus-Naur– introdotto negli anni '50 da Backus e
Naur
• Esiste anche una estensione (Extended BNF, EBNF) che permette una scrittura più sintetica
Fondamenti di Informatica 25
Esempio di grammaticaV: { il, lo, gatto, topo, sasso, mangia, beve }N: {<frase>, <soggetto>, <verbo>, <compl-
oggetto>, <articolo>}S: <frase>P contiene le seguenti produzioni:
<frase>::=<soggetto><verbo><compl-oggetto><soggetto>::=<articolo><nome><articolo>::= il | lo<nome>::= gatto | topo | sasso<verbo>::= mangia | beve<compl-oggetto>::=<articolo><nome>
Fondamenti di Informatica 26
Extended BNF
X ::= [a]b equivale a X ::= b|abX ::= {a}nb equivale a X ::= b|ab|aab|… ripetendo a fino a n volte
X ::= {a}b equivale a X ::= b|ab|aab|… ripetendo a un numero di volte indefinito
Equivale ad avere nella grammatica la produzione X ::= b | aX (ricorsiva)
Fondamenti di Informatica 27
Esempio di grammaticaV: { 0,1,2,3,4,5,6,7,8,9,+,- }N: {<intero><int-senza-segno><numero>
<cifra-non-nulla><cifra>}S: <intero>P contiene le seguenti produzioni:
<intero> ::= [+ | - ] <int-senza-segno><int-senza-segno> ::= <cifra> | <cifra-non-nulla><numero><numero> ::= <cifra> | <cifra><numero><cifra> ::= <cifra-non-nulla> | 0<cifra-non-nulla> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Fondamenti di Informatica 28
Alberi sintattici
• Il processo di derivazione può essere descritto tramite un albero sintattico <frase>
<soggetto> <verbo> <compl-oggetto>
<articolo> <nome> <nome><articolo>
il gatto mangia il topo
Fondamenti di Informatica 29
Diagrammi sintattici
• Sono dei grafi:– nodi: etichettati con simboli (terminali
e non terminali), collegati da archi orientati
– un arco da i a j significa che il simbolo i è seguito dal simbolo j
– più archi rappresentano alternative– si possono aggiungere nodi fittizi per
rappresentare le diramazioni
Fondamenti di Informatica 30
Esempio didiagramma sintattico
<intero> ::=+ -
<cifra-non-nulla>
0
<cifra>
Fondamenti di Informatica 31
Sintassi dei linguaggidi programmazione
• Considerazioni sui linguaggi:– uno stesso linguaggio può essere
generato da più di una grammatica– alcune grammatiche sono ambigue:
cioè esistono diversi elementi che possono essere generati da diverse derivazioni (esistono cioè diversi alberi sintattici). Situazione da evitare!
Fondamenti di Informatica 32
Esempio di grammatica ambigua
• Esempio:<expr> ::= x | y | z | (<expr>) | <expr>+<expr> | <expr>*<expr>
• All'espressione x+y*z possono essere associati due alberi sintattici diversi– questo influenza anche il modo con cui
viene attribuito il significato all'espressione
Fondamenti di Informatica 33
Esempio digrammatica ambigua
• Nella definizione dei linguaggi si deve evitare l'ambiguità
• Esempio:<istruzione-if> ::= if
<espressione> then <istruzione> else <istruzione>
Fondamenti di Informatica 34
Analizzatore sintattico
• L'analisi della correttezza è eseguita dall'elaboratore: è suddiviso in 3 passi:– analisi lessicale: controlla che i simboli
utilizzati appartengano all'alfabeto– analisi grammaticale: verifica il rispetto
delle regole grammaticali– analisi sintattica contestuale: verifica
restrizioni di tipo contestuale (tipi di dati, identificatori non definiti,…)
Fondamenti di Informatica 35
Analizzatore sintattico
• Generalmente l'analizzatore sintattico esegue le tre verifiche simultaneamente
• Si dice "ad una passata "• Durante la scansione, se viene
trovato un errore, si cerca di recuperare e si prosegue fino al termine