•Classificati rispetto alle caratteristiche principali: Linguaggi

(1)

Linguaggi

• Classificati rispetto alle caratteristiche principali:

– potere espressivo che influenza lo stile di programmazione

(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"

(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,...

(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

(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

(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

(7)

Linguaggi Imperativi

– 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

(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)

(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

(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

(11)

Linguaggi Funzionali

– 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)

(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

(13)

Linguaggi Dichiarativi

• Programmazione:

– semplice (occorre solo definire la propria conoscenza del problema)

– avviene tramite una formulazione dichiarativa

• Esempio: Prolog

(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, …

(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:

(16)

Esempio

• Ricerca in un grafo orientato:

– con la richiesta ? go(E) viene determinata 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

D A

E

(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

(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

(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

(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

(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:

(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

(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

(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

(25)

Esempio di grammatica

V: { il, lo, gatto, topo, sasso, mangia, beve }

N: {<frase>, <soggetto>, <verbo>, <compl-oggetto>,

<articolo>}

S: <frase>

P contiene le seguenti produzioni:

<articolo>::= il | lo

<nome>::= gatto | topo | sasso

(26)

Extended BNF

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

X ::= {a}ⁿb 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)

(27)

Esempio di grammatica

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:

<int-senza-segno> ::= <cifra> | <cifra-non-nulla><numero>

<cifra> ::= <cifra-non-nulla> | 0

(28)

Alberi sintattici

• Il processo di derivazione può essere descritto tramite un albero sintattico

<frase>

(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

(30)

Esempio di

diagramma sintattico

<intero> ::=

+

- <cifra-non-nulla>

0

<cifra>

(31)

Sintassi dei linguaggi di 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).

(32)

Esempio di

grammatica ambigua

• Esempio:

• 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

(33)

Esempio di

grammatica ambigua

• Nella definizione dei linguaggi si deve evitare l'ambiguità

• Esempio:

<istruzione-if> ::= if <espressione>

then <istruzione> else <istruzione>

(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,…)

(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