Corso di Programmazione

Corso di Programmazione

Linguaggi di Programmazione

Dott. Stefano Ferilli

ferilli@di.uniba.it

Università degli Studi di Bari

Linguaggio

• Insieme di sequenze di simboli

appartenenti ad un definito lessico, giustapposti in sequenza

secondo una opportuna grammatica (o sintassi)

• Per descriverlo è necessario un

meta-linguaggio

Messaggio

• Sequenza di frasi espresse in un linguaggio

– Analizzabile dal punto di vista

• Sintattico

– Si verifica la forma linguistica in cui è codificato (sintassi)

• Semantico

– Si individua il significato associato alla forma linguistica (semantica)

Comunicazione Diretta

• Requisiti per i due interlocutori:

l’estensore del messaggio

– al momento della sua formulazione

e il ricevitore

– al momento della ricezione

diano al messaggio eguale significato

Comunicazione Indiretta

• Cause:

– Il ricevitore non conosce il linguaggio usato per la stesura del messaggio

– Estensore e ricevitore hanno un diverso grado di conoscenza del linguaggio

– Tra i due mancano adeguate convenzioni per un’interpretazione unica del messaggio

• Occorre un traduttore

Programma

• Messaggio di comunicazione fra l’uomo e la macchina

– Insieme di frasi costruite secondo regole molto rigide

• Eliminazione di ambiguità nell’interpretazione dei comandi da parte della macchina

– Necessità di linguaggi molto precisi

• Le istruzioni obbediscono a rigorose regole grammaticali

Sistema di Calcolo

• Gerarchia di componenti software e hardware

– Software applicativo (es. pacchetti ad usi speciali)

• Insieme di programmi da utilizzare per applicazioni particolari

• Generalmente scritti in un linguaggio ad alto livello

• Forniti direttamente da costruttori di computer o ditte specializzate nella produzione di programmi

– Software di sistema (sistemi operativi, traduttori, ecc.)

• Insieme dei programmi che forniscono servizi e svolgono funzioni vitali per il software applicativo

– Hardware (CPU, memorie, dispositivi di I/O, ecc.)

Comunicazione Uomo-Macchina

• Processore nudo

– La macchina comprende il linguaggio macchina

• Costituito da un insieme di istruzioni elementari

• Ogni istruzione è una stringa di cifre binarie che specifica un’operazione e la cella di memoria implicata nell’operazione

• Processore vestito

– Macchina in grado di comprendere un linguaggio di livello superiore

• Usato per facilitare il compito di programmare la soluzione di

Linguaggio Naturale

• Usato per la comunicazione verbale fra esseri umani

– Fonti di ambiguità:

• Evoluzione

– Neologismi, Arcaismi

• Polisemia

– Parole con significati differenti a seconda del contesto

• Intrinseca

– …una vecchia porta la sbarra…

– Inadatto alla comunicazione con la macchina

Linguaggi di Programmazione

• A basso livello

– Più vicini alla struttura reale della macchina ed al suo linguaggio

• Ad alto livello

– Più vicini al linguaggio dei problemi

– Più facili da

comprendere per l’uomo

– Portabili

• Utilizzabili, senza modifiche, su diversi

Linguaggi di Programmazione

ad alto livello

• Procedurali

– Descrivono i passi

necessari per ottenere i risultati desiderati

• “come”

– Basati sui concetti di

• Variabile

• Assegnamento

• Non procedurali

– Esprimono le proprietà dei risultati che si

vogliono ottenere

• “cosa”

– Esempio

Radice quadrata di y

• Quel valore x tale che x*x = y

Linguaggi di Programmazione

Sintassi

• L’insieme delle regole che indicano quali sono le istruzioni formali permesse

– Poche, semplici, rigide

• Il programma va accuratamente controllato dal punto di vista formale per garantire la correttezza sintattica

– Codifica ambigua o non interpretabile

Linguaggi di Programmazione

Semantica

• Riguarda il contenuto informativo ed il significato di una frase

– Il lavoro più grosso è verificare e controllare il programma sul fronte logico per garantire la correttezza a livello semantico

• Informazione trasmessa non corrispondente allo scopo desiderato

– Connessa all’analisi del problema e l’algoritmo

Sintassi e Semantica

Esempio

• “Io ho andato”

– Errata sintatticamente

• “La penna sta mangiando”

– Corretta sintatticamente

• Forma

– Errata semanticamente

• Significato

Traduttore

• Programma che traduce in linguaggio macchina programmi in un linguaggio di livello superiore

– Analizza i messaggi (comandi) e verifica che siano scritti (codificati) in un linguaggio a lui noto

• Correttezza sintattica

– Attribuisce alle sequenze di simboli l’opportuno significato in modo da eseguire le giuste azioni

• Interpretazione unica di ogni istruzione

– Fa parte del software di sistema

• Livello intermedio della gerarchia software-hardware

Traduttori

• Nei programmi ad alto livello operano su due tipi di entità:

– Istruzioni

• Molto più potenti che nel linguaggio macchina

– Strutture di dati (liste, sequenze, alberi, ecc.)

• Non direttamente disponibili al livello di linguaggio macchina

• Devono essere rappresentate in termini di bit, indirizzi e legami tra locazioni

Traduttori

• Interpreti

• Compilatori

– Specifici per ogni linguaggio

– Forniti entrambi dai sistemi di sviluppo del software per i linguaggi supportati

Processore vestito

Linguaggio di Programmazione

Processore nudo Linguaggio

Macchina Traduzione

Interpretazione

• Dopo l’analisi sintattica, la traduzione procede passo passo con l’esecuzione

– Traduzione ed esecuzione istruzione per istruzione

• Ogni istruzione tradotta tante volte quante viene eseguita

Interprete

Programma

Risultati

Compilazione

• Il programma originale (Sorgente) è analizzato sintatticamente e tradotto in codice oggetto, quindi eseguito

– Traduzione completamente effettuata prima che cominci l’esecuzione

• Ogni istruzione è tradotta una sola volta Compilatore

Programma Codice

Oggetto

Macchina Risultati

Interpreti vs. Compilatori

Programma sorgente residente in memoria

+ Semplici – Efficienti

Tempo e Spazio

+ Interattivi

+ Errori comprensibili

Riferiti al sorgente

Programma sorgente

non residente in memoria

+ Ottimizzabili + Efficienti

Tempo e Spazio

– Interattivi

+ Errori scoperti prima

Riferiti al codice oggetto

Processo di Compilazione

Fasi

• Analisi Lessicale

– Divisione della stringa di caratteri del programma in token

• Segni di interpunzione, nomi di dati, operatori, parole riservate

• Analisi Sintattica

– Definizione della struttura sintattica del programma usando le regole grammaticali del linguaggio

• Generazione del Codice

– Generazione di appropriate istruzioni in linguaggio macchina per ogni elemento sintattico del programma

Processo di Compilazione

• Le fasi sono tra loro interrelate

– I moduli di programma responsabili dell’analisi sintattica possono utilizzare

• I moduli dell’analisi lessicale per ottenere un token

• I moduli di generazione del codice per produrre il codice oggetto dell’istruzione analizzata

• Per capire come vengono effettuate le

analisi è necessaria la teoria dei linguaggi

Alfabeto

• Insieme finito e non vuoto di simboli primitivi (caratteri) tramite i quali è

possibile costruire gli elementi base del linguaggio

– Esempio:

Alfabeto dei numeri reali

A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, –, .}

• 23 354.35 –86.6 +5589.0

Concatenazione di Simboli

di un alfabeto

• L’oggetto ottenuto prendendo nell’ordine i simboli da concatenare

– Esempio:

Dato l’alfabeto per i numeri reali

• La concatenazione di 3 e 4 è 34

• La concatenazione di +, 4, 7, . e 5 è +47.5

• La concatenazione di 4, ., 7, . e 5 è 4.7.5 !!!!

– Non tutte le sequenze di simboli che si possono costruire

Stringa o Parola

su un alfabeto

• Sequenza di simboli ottenuta come concatenazione di un numero finito di elementi dell’alfabeto

Λ denota la stringa non contenente alcun simbolo (parola vuota)

• La concatenazione di due parole

– Parola formata dai simboli della prima seguiti da quelli della seconda

– Esempi:

Λp = pΛ = p per ogni parola p

la concatenazione di +3 con 4.5 è +34.5

Prodotto di Insiemi di Parole

su un alfabeto

• Insieme ottenuto concatenando ogni parola di un insieme con ogni parola dell’altro

– Esempio:

concatenando {1, 21, 1.4} con {2, 398}

si ottiene {12, 1398, 212, 21398, 1.42, 1.4398}

Potenza di un Alfabeto A

• A è un particolare insieme di parole su A

– Si possono considerare i prodotti

• AA

• AAA

• …

– Esempio:

per l’alfabeto dei numeri reali fanno parte di A

• 213 3.5 –29 +55 21. .65 4.. …

– Le ultime due stringhe non fanno parte dei numeri reali

Potenza

di un Alfabeto A

• A

– Parole costituite da n simboli dell’alfabeto A

• A⁰ = {Λ}

• A¹ = A

• A² = AA

• A³ = AAA

• …

– n è detta lunghezza della parola

Chiusura

di un Alfabeto A

• Bisogna delimitare l’universo linguistico esprimibile

– Tutte le possibili parole di lunghezza finita costituite da simboli dell’alfabeto

• A

= A

∪ A

∪ … ∪ A

∪ …

– Insieme di tutte le parole su A di lunghezza finita

• Unione di tutti gli insiemi di parole di varia lunghezza

• A

= { Λ } ∪ A

– Chiusura di A

Linguaggio

su un alfabeto A

• Un sottoinsieme di A

– Tra le parole di A

ci sono parole ammesse nel linguaggio e parole non ammesse

• Linguaggio Generato da una Grammatica

– Insieme delle frasi costruite, a partire

dall’alfabeto, secondo le regole specificate da

una grammatica

Simboli Non Terminali

• Non fanno parte dell’alfabeto

– Sono variabili

– Rappresentano opportune sequenze di simboli

• Nomi che specificano le categorie sintattiche

– Componenti delle frasi del linguaggio generato dalla grammatica

• Il loro insieme è detto alfabeto dei simboli non terminali

– Su di esso è costruito il metalinguaggio

Simboli Non Terminali

Esempio

• Linguaggio naturale

– Parole classificate in

• frase, soggetto, predicato, articolo, nome, verbo, ecc.

– <soggetto > → <articolo> <nome>

il cane

• Linguaggio algebrico

– <formula> → <variabile> = <espressione aritmetica>

x = y + z * 12

Regola o Produzione

• Coppia ordinata di parole (p, q) tale che, se

– A è l’alfabeto dei simboli terminali

– N è l’alfabeto dei simboli non terminali

p e q possono appartenere tanto ad A* ∪ N*

• Scriviamo p → q

• “la stringa p produce la stringa q”

• “la stringa p può essere riscritta come q”

– p (≠ Λ) è detta parte sinistra – q è detta parte destra

Regola o Produzione

Convenzione

• Le parti destre di produzioni con la stessa parte sinistra si possono riunire come

alternative in un’unica parte destra, separate col simbolo | (“oppure”)

– Esempio

p → q p → r p → s p → t si può compattare in

p → q | r | s | t

Grammatica

• Insieme delle regole che consentono di definire, tra tutte le possibili sequenze di simboli di lunghezza finita che si possono costruire, quelle lecite (frasi)

– Le regole di formazione delle frasi del

linguaggio si dicono regole di produzione

• Coinvolgono simboli dell’alfabeto ed altri simboli che rappresentano categorie sintattiche

Grammatica

• Quadrupla [Chomsky]

G = < A, N, α , P >

– A alfabeto terminale

– N alfabeto non terminale α scopo della grammatica

(simbolo di partenza)

– P insieme delle regole di produzione

Grammatica

Esempio

• Grammatica che genera il linguaggio dei numeri pari

– A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

– N = { α , β }

∀α indica il numero pari

– Scopo per cui costruiamo la grammatica

∀β indica un numero qualunque

– P = { α → βα | 0 | 2 | 4 | 6 | 8, β → 0 | 1 | 2 | … | 8 | 9 |

β 0 | β 1 | β 2 | … | β 8 | β 9 }

Grammatica

Esempio

• A = {il, la, cane, donna, mangia, dorme}

• N = { <frase>, <soggetto>,

<articolo>, <nome>, <verbo>}

∀ α = <frase>

• P = {

<frase> → <soggetto> <verbo>

<soggetto> → il <nome> | la <nome>

il <nome> → il cane la <nome> → la donna

Generazione di Stringhe

• Una stringa di terminali e non, S

, genera un’altra stringa S

– Direttamente (S₁ ⇒ S₂) – Indirettamente (S₁ ⇒^* S₂)

se quest’ultima si ottiene dalla prima applicando

– Una produzione

– Una sequenza di produzioni

della grammatica

Derivabilità

• Una sequenza di simboli S

è derivabile da un’altra S

se

– Entrambe sono stringhe di terminali e non – S₁ ha almeno un non terminale γ

– C’è una regola che, sostituendo γ con S₃ in S₁, porta a S₂

• La frase w costruita sui simboli terminali di G, con simbolo iniziale α , è derivabile se

∃ n, ∃ s ,…,s ∈ (A ∪ N)

∋′ α → s → … → s → w

Derivabilità

• Una frase w è generata da G se si ottiene

applicando ripetutamente le regole di P, partendo da α

– La struttura del linguaggio dipende dalle regole di

produzione che determinano le modalità di formazione delle frasi del linguaggio generato dalla grammatica – Una grammatica è libera da contesto se le sue regole

sono del tipo b → w

• b simbolo non terminale

• w sequenza di simboli terminali e/o non terminali

Tipi di Grammatiche

• Dipendenti dalle restrizioni imposte alle produzioni

– 0 (Nessuna restrizione)

• p → q p, q ∈ (A∪N)^*

– 1 (Dipendenti dal contesto)

• xay → xby a ∈ N; x,y,b ∈ (A∪N)^*; b ≠ Λ

– 2 (Non contestuali)

• p → q p ∈ N; Λ ≠ q ∈ (A∪N)^*

– 3 (Regolari)

• p → ax p ∈ N; a ∈ A^*; x ∈ N

Albero Sintattico

• Rappresentazione grafica del processo di derivazione

– Radice = scopo della grammatica

– Relazione padre-figlio = applicazione di regole di produzione

– Foglie = simboli terminali

• La sequenza di foglie, lette da sinistra verso destra, è detta frontiera

• Grafo orientato e ordinato aciclico

Albero Sintattico di un Programma

• Albero che si ricava dalle regole di produzione della grammatica di un linguaggio di programmazione

– Radice: <programma>

– Foglie

• caratteri alfanumerici

• simboli speciali

• parole chiave

Analisi Sintattica

• Procedimento di costruzione della derivazione di una frase rispetto ad una grammatica G

• Effettuato da un analizzatore sintattico (parser)

– Programma che opera su una stringa, e

• se questa appartiene al linguaggio generato dalla grammatica, ne produce una derivazione

• altrimenti si ferma segnalando il punto dove si è verificato l’errore

• A seconda dell’ordine seguito nel costruire le

derivazioni, è detta ascendente o discendente

Analisi Sintattica

Esempio

• Produzioni:

1. S → aSAB 2. S → b

3. A → bA 4. A → a 5. B → cB 6. B → a

• Una frase è

S₁

a S₁ A₄ B₆ a S₂ A3 B₆ a a

b b A₃ a b A₄

9

6

1 4 5

3

2

7 8

Analisi Sintattica Ascendente

Esempio

S₁

a S₁ A₄ B₆

a S₂ A₃ B₆ a a

b b A₃ a b A₄

1

2

3 4 7

5

6

8 9

Analisi Sintattica Discendente

Esempio

S₁

a S₁ A₄ B₆

a S₂ A₃ B₆ a a

b b A₃ a

b A

Forma (Normale) di Backus- Naur

• Notazione per scrivere la grammatica BNF

– Usata per specificare la sintassi di un linguaggio di programmazione

• Simboli non terminali scritti fra parentesi uncinate <…>

• Simbolo → sostituito da ::=

Forma di Backus-Naur

Esempio

• Grammatica per i numeri pari (infiniti)

– <numero pari>::= 0 | 2 | 4 | 6 | 8 |

<numero><numero pari>

– <numero> ::= 0 | 1 | 2 | … | 8 | 9 |

<numero> 0 | … | <numero> 9 – 64932 è ottenibile?

• <numero pari>::= <numero><numero pari> ::=

<numero>2 ::= <numero>32 ::= <numero>932 ::=

<numero>4932 ::= 64932

Forma di Backus-Naur

Esempio

• Grammatica per le stringhe palindrome

– Simmetria speculare

– <frase> ::= Λ

– <frase> ::= a<frase>a – <frase> ::= b<frase>b

• È possibile derivare infinite stringhe

Carte Sintattiche

• Grafi costituiti da blocchi uniti da frecce

– Blocchi arrotondati

• Simboli terminali del linguaggio

– Blocchi rettangolari

• Simboli non terminali

– Rimandi alla corrispondente carta sintattica

– Frecce

• Indicano le vie percorribili per costrutti validi

– I bivi rappresentano possibilità alternative

Carte Sintattiche

• Iniziando dalla carta principale, seguire le frecce

– Quando si dipartono scegliere una strada

• Attraversando un blocco arrotondato

– Trascriverne il contenuto

• Attraversando un blocco rettangolare, passare alla carta corrispondente e seguirla

– Ogni carta ha esattamente un inizio e una fine, come il blocco

Carte Sintattiche

• Ogni traiettoria percorsa nel verso delle frecce definisce un costrutto sintattico valido del linguaggio

• Tutti i simboli terminali incontrati nel

percorso ed in quella data sequenza

costituiscono una frase legale del

linguaggio

Carte Sintattiche

Esempio

• Identificatore:

– Lettera seguita (eventualmente) da lettere o cifre

• <identificatore> ::= <lettera> | <lettera><stringa alfanumerica>

• <stringa alfanumerica> ::= <lettera> | <cifra> |

<lettera><stringa alfanumerica> |

<cifra><stringa alfanumerica>

• <lettera> ::= a | b | c | d | e | f | g | h | … | z

• <cifra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

lettera

lettera