1

Linguaggi di Programmazione - elementiLinguaggi di Programmazione - elementi

Corso di Laurea in InformaticaCorso di Laurea in Informatica(AA 2004/2005)(AA 2004/2005)

Gabriella Pasi e Carla SimoneGabriella Pasi e Carla Simone

gabriella.pasi@itc.cnr.itgabriella.pasi@itc.cnr.itsimone@disco.unimib.itsimone@disco.unimib.it

2

EsempioEsempio: V = {a,b,c,d} N = {A,S} Start Symbol S

P = {S cAd,A bAb|a}

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

ESERCIZIOESERCIZIO

Grammatica di tipo context free

Derivazione per cbabb? Non esiste!

Derivazione per cbbbabbbd?

S cAd cbAbd cbbAbbd cbbbAbbbd cbbbabbbd

3

Dato il linguaggio L = {anbcdn | n 0} costruire una grammatica che lo genera.

V = {a,b,c,d} N = {A,S} Start symbol S

P = {S A,A aAd|bc}

E’ possibile utilizzare una grammatica regolare? Se si, dare la sua definizione.NO

ESERCIZIOESERCIZIO

4

Dato il linguaggio L = {anbcdm | n 0, m 0} costruire una grammatica che lo genera. V = {a,b,c,d} N = {A,S} P = {S A;

A aAd|bc|aA|Ad}P = {S A

A aA|bc|Ad}E’ possibile utilizzare una grammatica regolare? Se si, dare la sua definizione.SI

S aS|bCC cD|cD dD|d

ESERCIZIOESERCIZIO

5

P = {S bC | aAA aA | bCC cD |cD dD | d

Regolare?

SI

L = {anbcdm | n 0, m 0}

6

Data la grammatica V = {x} N = {S,X,B} P = S xX X x X xB B xXA) di che tipo e’ la grammatica?

ESERCIZIOESERCIZIO

regolare, lineare a destra

D) Esiste una grammatica context free che lo genera? Se si, dare la sua definizione.

L(G) = {x2n |n>=1}

S XX xXx|xx

B) mostrare una derivazione per xxxxx e una per xxxxS xX xxB xxxX xxxx

Non esiste derivazione per xxxxxC) qual’e’ il linguaggio generato?

7

Dato il linguaggio L = {abncdn | n 0} costruire una grammatica che lo genera.

V = {a,b,c,d} N = {A,S} P = {S aA,

A bAd|c}

E’ possibile utilizzare una grammatica regolare? Se si, dare la sua definizione.NO

ESERCIZIOESERCIZIO

8

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

P = {S a|aA,A a|b|aA|bA}

Linguaggio generato da G: il linguaggio delle stringhe non vuote su {a,b} che iniziano per a

A) Di che tipo e’ la grammatica?

B) Derivazione per baab? Questa stringa non e’ generabile

C) Derivazione per abba?

S aA abA abbA abba

regolare, lineare a destra

ESERCIZIOESERCIZIO

9

V = {a,b,c} N = {S,X} S assioma

P = {S X|,X aXa|bXb|c}

Linguaggio generato da G: il linguaggio delle stringhe palindrome su {a,b,c} con una e una sola c al centro, piu’ la stringa vuota.

A) Di che tipo e’ la grammatica?

B) Derivazione per abcba?

S X aXa abXba abcba

context free

ESERCIZIOESERCIZIO

10

Dato il linguaggio L = {anb2n | n > 0} costruire una grammatica che lo genera.

V = {a,b} N = {S,X} Start Symbol S

P = {S X,X aXbb|abb}

ESERCIZIOESERCIZIO

11

V = {a,b,c} N = {S,A} S assioma

P = { S aSc|AA bAc|}

Linguaggio generato da G?

L(G) = {anbmcn+m |n,m0}

P = {S AA aAc|B B bBc|}

Regole di produzione senza ricorsione su S:

N = {S,A,B}

ESERCIZIOESERCIZIO

12

Il linguaggio L(G) = {anb |n 0} puo’ essere generato da una grammatica regolare?

V = {a,b} N = {S,A} S assioma

P = {S Ab|bA Aa|a}

ESERCIZIOESERCIZIO

Usare una context-free non da’ vantaggi

13

Definire una grammatica che generi il linguaggio L(G) = {anbn |n 0}

V = {a,b} N = {S,A} S assioma

P = {S AA aAb|ab|}

ESERCIZIOESERCIZIO

14

– 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

15

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 sottostante• portabilità dei programmi;• maggiore semplicità di uso• esistono librerie di programmi già pronti;• per essere eseguiti devono essere tradotti in linguaggio macchina.

Linguaggi di programmazioneLinguaggi di programmazione

16

17

Affinchè un programma scritto in un qualsiasi linguaggio di programmazione sia comprensibile (e quindi eseguibile) da un elaboratore occorre tradurlo dal linguaggio originario al linguaggio macchina. Questa operazione viene normalmente svolta da programmi speciali, detti traduttoritraduttori.

Linguaggi di programmazioneLinguaggi di programmazione

18

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 (senza eseguirlo!) e producono in uscita il programma convertito inlinguaggio macchina• gli InterpretiInterpreti traducono ed eseguono immediatamente ogni singola istruzione del programma sorgente.

TraduttoriTraduttori

19

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

TraduttoriTraduttori

20

Analisi lessicaleAnalisi lessicale

L’analizzatore lessicale o scannerscanner, verifica la correttezza delle parole utilizzate ed estrae i cosiddetti token (parole chiave, identificatori, costanti, operatori, ecc.)

Lo scanner trasforma un testo in una sequenza di token. Ad esempio l’istruzione x:=100 viene trasformata nella sequenza: identificatore, operatore di assegnamento, costante.

==> Grammatiche regolari (LEX)

21

Analisi sintatticaAnalisi sintatticaL’analizzatore sintattico o parserparser, verifica la correttezza delle espressioni (frasi) nel programma sulla base della corretta applicazione delle regole sintattiche (regole di produzione, definite in BNF o mediante grafi sintattici).

Analisi semanticaAnalisi semanticaL’analizzatore semantico ha lo scopo di stabilire se un’espressione ha significato. Non è possibile verificare ciò per qualsiasi espressione: quello che i compilatori sono in grado di fare è stabilire la violazione di alcune regole semantiche. Ad esempio operazioni tra operandi di tipi non compatibili, applicazione di funzioni con un numero di parametri diverso da quelli dichiarati (ordine e tipo), uso di oggetti non dichiarati, operatori illegali per il tipo di oggetti a cui sono applicati.

==> Grammatiche context-free (YACC)

22

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 unico programma eseguibile.DebuggerDebugger: consente di eseguire passo-passo un programma, al fine di scoprire ed eliminare errori non rilevati in fase di compilazione.

23

24

Il processo di TraduzioneIl processo di Traduzione

linker loadercompilatore

25