Fondamenti di Informatica1 Linguaggi Classificati rispetto alle caratteristiche principali:...

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



• 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



• 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



• 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



• 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



• Programmazione:– semplice (occorre solo definire la

propria conoscenza del problema)– avviene tramite una formulazione

dichiarativa

• Esempio: Prolog



• 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) vienedeterminata 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

DA

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


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


Esempio di grammaticaV: { il, lo, gatto, topo, sasso, mangia, beve }N: {<frase>, <soggetto>, <verbo>, <compl-

oggetto>, <articolo>}S: <frase>P contiene le seguenti produzioni:

<frase>::=<soggetto><verbo><compl-oggetto><soggetto>::=<articolo><nome><articolo>::= il | lo<nome>::= gatto | topo | sasso<verbo>::= mangia | beve<compl-oggetto>::=<articolo><nome>


Extended BNF

X ::= [a]b equivale a X ::= b|abX ::= {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)


Esempio di grammaticaV: { 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


Alberi sintattici

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

<soggetto> <verbo> <compl-oggetto>

<articolo> <nome> <nome><articolo>

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 didiagramma sintattico

<intero> ::=+ -

<cifra-non-nulla>

0

<cifra>


Sintassi dei linguaggidi 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:<expr> ::= x | y | z | (<expr>) | <expr>+<expr> | <expr>*<expr>

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


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

Fondamenti di Informatica1 Linguaggi Classificati rispetto alle caratteristiche principali:...

Documents

Transcript of Fondamenti di Informatica1 Linguaggi Classificati rispetto alle caratteristiche principali:...