Linguaggi di Programmazione
(AA 2002/2003)
Corso di Laurea in Informatica
Gabriella Pasi
[email protected]
Programma del corso
INTRODUZIONE
I linguaggi: sintassi e semantica
Grammatiche
I principali paradigmi di programmazione
Java e C
IL PARADIGMA CONCORRENTE
IL PARADIGMA FUNZIONALE
IL PARADIGMA LOGICO
Linguaggi e programmi
Dato un algoritmo, un programma è la sua descrizione in un
particolare linguaggio di programmazione
Un linguaggio di programmazione è caratterizzato da due
aspetti:
l’insieme di regole formali che definiscono
le modalità per costruire espressioni
– SINTASSI
corrette (valide) del linguaggio
– SEMANTICA
Il significato da attribuire alle frasi
(sintatticamente corrette) costruite nel
linguaggio.
NB: una frase può essere sintatticamente corretta e tuttavia non
avere significato!
SINTASSI DEI LINGUAGGI
ELEMENTI BASE DELLA SINTASSI DI UN LINGUAGGIO
V : alfabeto Un alfabeto è un insieme finito. I suoi elementi
sono detti lettere o simboli. L’insieme di tutte le sequenze finite di
lettere in V, dette parole su V, è denotato da V*
V* : universo linguistico su V
L : un linguaggio su V è un sottoinsieme di V* generato da
una grammatica.
GRAMMATICHE
Una grammatica G = (V,N,P,S) è definita da:
V: insieme di simboli terminali,
N: insieme di simboli non terminali (categorie sintattiche
come per esempio: <frase>, <soggetto>, <verbo>,
<complemento>, <articolo>, <nome>, ...)
P: insieme finito di regole sintattiche (o produzioni) del tipo
XY
S : elemento di N (assioma o simbolo iniziale)
GRAMMATICHE
Il linguaggio generato da una grammatica G(V,N,P,S) è
l’insieme delle stringhe di soli simboli terminali ottenibili
applicando un insieme di regole.
Esempio: V = {a,b} N = {A,S}
P = { S A;
A  bAb;
Aa}
Linguaggio generato da G:
L(G) = {bnabn |n0}
Si dice forma di frase (sentential form) una qualsiasi
stringa comprendente sia simboli terminali sia simboli
non terminali derivabile dall’assioma S.
Si dice frase una forma di frase comprendente solo
simboli terminali.
GRAMMATICHE INDIPENDENTI DAL CONTESTO
(context free)
Le produzioni sono della forma A  w,
dove A  N e w  (V  N)*
Data una grammatica G = (V,N,P,S), diciamo che da una
stringa u = u1Au2  (V  N)* possiamo derivare in un passo
una stringa v = u1wu2  (V  N)* se esiste una produzione
A  w e scriviamo u  v
Diciamo che v è derivabile da u, e scriviamo u * v , se esiste
una catena finita di stringhe u1, u2 ….. un  (V  N)* tale
u = u1  u2  …..  un = v
GRAMMATICHE INDIPENDENTI DAL CONTESTO
(context free)
L’insieme delle forme sentenziali di G è l’insieme delle parole
su V  N derivabili a partire da s, cioè le parole su V  N tali
che s * v.
Il linguaggio definito dalla grammatica G è l’insieme delle
forme sentenziali che sono parole su V (vale a dire, non
contengono simboli non terminali).
GRAMMATICHE INDIPENDENTI DAL CONTESTO
(context free)
GRAMMATICHE INDIPENDENTI DAL CONTESTO
(context free)
GRAMMATICHE INDIPENDENTI DAL CONTESTO
(context free)
GRAMMATICHE INDIPENDENTI DAL CONTESTO
(context free)
Sintassi: notazioni
Le regole sintattiche sono espresse attraverso notazioni formali,
come ad esempio
• BNF (Backus-Naur Form)
• EBNF (Extended BNF)
• diagrammi sintattici
BACKUS NAUR FORM
BACKUS NAUR FORM esempio
EXTENDED BACKUS NAUR FORM
EXTENDED BACKUS NAUR FORM
X ::= [a]b
equivale a X ::= b|ab
X ::= {a}nb equivale a
ripetendo a fino a n volte
X ::= b|ab|aab|…
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)
EXTENDED BACKUS NAUR FORM esempi
EXTENDED BACKUS NAUR FORM esempio
V: { 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
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
DIAGRAMMI SINTATTICI: ESEMPIO
Sintassi di un numero naturale
0
DIAGRAMMI SINTATTICI: ESEMPIO
Identificatore in Java
letterale
letterale
cifra
cifra
0 - 9
cifra
Unicode
escape
DIAGRAMMI SINTATTICI: ESEMPIO
Istruzione condizionale
if
(
espressione
)
istruzione
else
istruzione
ANALISI SINTATTICA
Data una grammatica G si pone il problema di verificare se
una data stringa appartiene al linguaggio L(G):
–analisi lessicale: controlla che i simboli utilizzati
appartengano all'alfabeto
–analisi grammaticale: verifica il rispetto delle regole
grammaticali
Linguaggi di programmazione
Linguaggio macchina: binario, implica la conoscenza
della macchina e dei metodi di rappresentazione delle
informazioni.
Linguaggio assembler: linguaggio macchina in cui nomi e
simboli prendono il posto dei codici numerici associati a
istruzioni, e riferimenti alle celle di memoria (indirizzi)
maggiore leggibilità.
Linguaggi di “alto livello”:
astrazione dall’architettura sottostante
portabilità dei programmi;
maggiore semplicità di uso
esistono librerie di programmi già pronti;
per essere eseguiti devono essere tradotti in linguaggio
Traduttori
Il traduttore converte il testo di un programma scritto in un
particolare linguaggio di programmazione (sorgente) nella
corrispondente rappresentazione in linguaggio macchina
(eseguibile).
Due categorie di traduttori:
• i Compilatori traducono l’intero programma (senza
eseguirlo!) e producono in uscita il programma convertito in
linguaggio macchina
• gli Interpreti traducono ed eseguono immediatamente
ogni singola istruzione del programma sorgente.
Traduttori
Quindi:
• nel caso del compilatore, lo schema viene percorso una volta
sola prima dell’esecuzione
• nel caso dell’interprete, lo schema viene invece attraversato
tante volte quante sono le istruzioni che compongono il
programma.
AMBIENTI DI PROGRAMMAZIONE: caso 1 (compilatori)
Editor: serve per creare file che contengono testi (cioè sequenze
di caratteri). In particolare, l’editor consente di scrivere il
programma sorgente.
Compilatore: opera la traduzione di un programma
sorgente (scritto in un linguaggio ad alto livello) in un
programma oggetto.
Linker: ( collegatore) nel caso in cui la costruzione del programma
eseguibile richieda l’unione di più moduli (compilati
separatamente), il linker provvede a collegarli formando un unico
programma eseguibile.
Debugger: consente di eseguire passo-passo un programma,
al fine di scoprire ed eliminare errori non rilevati in fase di
compilazione.
Il processo di Traduzione
compilatore
linker
loader