Linguaggi•Classificati rispetto alle caratteristicheprincipali:

(1)

Fondamenti di Informatica 1

Linguaggi

• Classificati rispetto alle caratteristiche principali:

– potere espressivo che influenza lo stile di programmazione

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"

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

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

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)

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

(2)

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

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)

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

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

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)

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

(3)

Linguaggi Dichiarativi

• Programmazione:

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

– avviene tramite una formulazione dichiarativa

• Esempio: Prolog

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

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)

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

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

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

(4)

Sintassi

• Per definire la sintassi di un linguaggio, è necessario definire le grammatiche

• La grammatica è un insieme di regole che servono per costruire una frase

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

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

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

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

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

(5)

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

<verbo>::= mangia | beve

<compl-oggetto>::=<articolo><nome>

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)

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

<cifra-non-nulla> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Alberi sintattici

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

<frase>

il gatto mangia il topo

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

Esempio di diagramma sintattico

<intero> ::=

+ - <cifra-non-nulla>

0

<cifra>

(6)

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

Situazione da evitare!

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

Esempio di grammatica ambigua

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

• Esempio:

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

then <istruzione> else <istruzione>

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