Linguaggi di ProgrammazioneLinguaggi di Programmazione(AA 2002/2003)(AA 2002/2003)

Corso di Laurea in InformaticaCorso di Laurea in Informatica

Gabriella PasiGabriella Pasigabriella.pasi@itim.mi.cnr.itgabriella.pasi@itim.mi.cnr.it

Programma del corsoProgramma del corso

INTRODUZIONEINTRODUZIONE

IL PARADIGMA CONCORRENTEIL PARADIGMA CONCORRENTE

IL PARADIGMA FUNZIONALEIL PARADIGMA FUNZIONALE

IL PARADIGMA LOGICOIL PARADIGMA LOGICO

I linguaggi: sintassi e semanticaGrammaticheI principali paradigmi di programmazioneJava e C

Linguaggi e programmiLinguaggi e programmi

Dato un algoritmo, un programma è la sua descrizione in un particolare linguaggio di programmazione

Un linguaggio di programmazione è caratterizzato da due aspetti:

– SINTASSI

– SEMANTICA

NB: una frase può essere sintatticamente corretta e tuttavia non avere significato!

Il significato da attribuire alle frasi (sintatticamente corrette) costruite nel linguaggio.

l’insieme di regole formali che definiscono le modalità per costruire espressioni corrette (valide) del linguaggio

SINTASSI DEI LINGUAGGISINTASSI DEI LINGUAGGI

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 grammaticagrammatica.

ELEMENTI BASE DELLA SINTASSI DI UN LINGUAGGIOELEMENTI BASE DELLA SINTASSI DI UN LINGUAGGIO

Una grammatica G = (V,N,P,S) è definita da:

V: insieme di insieme di simboli terminalisimboli terminali,

N: insieme di simboli non terminalisimboli non terminali (categorie sintattichecategorie sintattiche come per esempio: <frase>, <soggetto>, <verbo>, <complemento>, <articolo>, <nome>, ...)

P: insieme finito di regole sintatticheregole sintattiche (o produzioniproduzioni) del tipo X Y

S : elemento di N (assiomaassioma o simbolo inizialesimbolo iniziale)

GRAMMATICHEGRAMMATICHE

GRAMMATICHEGRAMMATICHE

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.

EsempioEsempio: V = {a,b} N = {A,S}

P = { S A;

A bAb;

A a }

Linguaggio generato da G: L(G) = {bnabn |n0}

Si dice forma di frase (sentential form) forma di frase (sentential form) una qualsiasistringa comprendente sia simboli terminali sia simboli non terminali derivabile dall’assioma S.Si dice frasefrase una forma di frase comprendente solosimboli terminali.

GRAMMATICHE INDIPENDENTI DAL CONTESTOGRAMMATICHE INDIPENDENTI DAL CONTESTO(context free)(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 derivarederivare in un passo una stringa v = u1wu2 (V N)* se esiste una produzione A w e scriviamo u u vv

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

L’insieme delle forme sentenziali di G è l’insieme delle parole su V N derivabiliderivabili 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 CONTESTOGRAMMATICHE INDIPENDENTI DAL CONTESTO(context free)(context free)

GRAMMATICHE INDIPENDENTI DAL CONTESTOGRAMMATICHE INDIPENDENTI DAL CONTESTO(context free)(context free)

GRAMMATICHE INDIPENDENTI DAL CONTESTOGRAMMATICHE INDIPENDENTI DAL CONTESTO(context free)(context free)

GRAMMATICHE INDIPENDENTI DAL CONTESTOGRAMMATICHE INDIPENDENTI DAL CONTESTO(context free)(context free)

GRAMMATICHE INDIPENDENTI DAL CONTESTOGRAMMATICHE INDIPENDENTI DAL CONTESTO(context free)(context free)

Le regole sintattiche sono espresse attraverso notazioni formali, come ad esempio

• BNF (Backus-Naur Form)• EBNF (Extended BNF)• diagrammi sintattici

Sintassi: notazioniSintassi: notazioni

BACKUS NAUR FORMBACKUS NAUR FORM

BACKUS NAUR FORM esempioBACKUS NAUR FORM esempio

EXTENDED BACKUS NAUR FORMEXTENDED BACKUS NAUR FORM

X ::= [a]b equivale a X ::= b|ab

X ::= {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)

EXTENDED BACKUS NAUR FORMEXTENDED BACKUS NAUR FORM

EXTENDED BACKUS NAUR FORM esempiEXTENDED BACKUS NAUR FORM esempi

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

EXTENDED BACKUS NAUR FORM esempioEXTENDED BACKUS NAUR FORM esempio

DIAGRAMMI SINTATTICIDIAGRAMMI 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: ESEMPIODIAGRAMMI SINTATTICI: ESEMPIO

Sintassi di un numero naturale

0

Identificatore in JavaIdentificatore in Java

letterale

letterale

cifra

cifra

Unicodeescape

cifra

0 - 9

DIAGRAMMI SINTATTICI: ESEMPIODIAGRAMMI SINTATTICI: ESEMPIO

DIAGRAMMI SINTATTICI: ESEMPIODIAGRAMMI SINTATTICI: ESEMPIO

Istruzione condizionaleIstruzione condizionale

if )(

else

espressione

istruzione

istruzione

–analisi lessicaleanalisi lessicale: controlla che i simboli utilizzati appartengano all'alfabeto

–analisi grammaticaleanalisi grammaticale: verifica il rispetto delle regole grammaticali

Data una grammatica G si pone il problema di verificare seuna data stringa appartiene al linguaggio L(G):

ANALISI SINTATTICAANALISI SINTATTICA

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 sottostanteportabilità dei programmi;maggiore semplicità di usoesistono librerie di programmi già pronti;per essere eseguiti devono essere tradotti in linguaggio macchina.

Linguaggi di programmazioneLinguaggi di programmazione

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 CompilatoriCompilatori traducono l’intero programma (senzaeseguirlo!) e producono in uscita il programma convertito inlinguaggio macchina• gli InterpretiInterpreti traducono ed eseguono immediatamenteogni singola istruzione del programma sorgente.

TraduttoriTraduttori

Quindi:• nel caso del compilatorenel caso del compilatore, lo schema viene percorso una volta una volta solasola prima dell’esecuzione• nel caso dell’interpretenel caso dell’interprete, lo schema viene invece attraversato tante volte quante sono le istruzionitante volte quante sono le istruzioni che compongono il programma.

TraduttoriTraduttori

AMBIENTI DI PROGRAMMAZIONE: caso 1 (compilatori)AMBIENTI DI PROGRAMMAZIONE: caso 1 (compilatori)

EditorEditor: serve per creare file che contengono testi (cioè sequenze di caratteri). In particolare, l’editor consente di scrivere il programma sorgente.

CompilatoreCompilatore: opera la traduzione di un programma sorgente (scritto in un linguaggio ad alto livello) in un programma oggetto.

LinkerLinker: ( 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 unicoprogramma eseguibile.

DebuggerDebugger: consente di eseguire passo-passo un programma, al fine di scoprire ed eliminare errori non rilevati in fase di compilazione.

Il processo di Traduzione

linker loadercompilatore