1 LINGUAGGI A STRUTTURA DI FRASE a cui appartengono i linguaggi di programmazione.

1

LINGUAGGI

A STRUTTURA DI FRASE

a cui appartengono i linguaggi di programmazione

2linguaggi a struttura di frase

un particolare caso di sistema formale generativo sono le grammatiche a struttura di frase di questo tipo sono le gramatiche dei linguaggi di programmazione

Una grammatica generativa a struttura di frase

produce un linguaggio a struttura di frase

in tali linguaggi una stringa ben formata si dice frasecioe’le stringhe del linguaggio generato dalla grammatica [appunto stringhe ben formate] sono "frasi" del linguaggio


una grammatica generativa a struttura di frase

e' una quadrupla

( V, T, P, S ) dove:

V = Vocabolario = insieme di tutti i simboli usati, terminali e non

T = insieme dei simboli Terminali (ovvero quelli che possono apparire in una s.b.f. o frase del linguaggio,

P = insieme di Produzioni

S = Simbolo iniziale (un solo simbolo di base, S = Sentence)

4linguaggi a struttura di frase // un’osservazione:Grammatica G = ( V, T, P, S ) con : S = Simbolo iniziale,V = vocabolario = insieme simboli usati, terminali e non,T = insieme simboli Terminali (che possono apparire in una s.b.f. o frase del linguaggio), P = insieme delle Produzioni

nota: V = T u N = unione dei due insiemi, con T = insieme dei simboli Terminali e N = ins. dei simb. Non terminali -> N = V-T = simboli Non terminali = insieme delle "categorie sintattiche" = simboli usati nella gramm., ma che non appaiono in una frase del linguaggio (nb: almeno un simbolo NON terminale c’e’ sempre nella parte sinistra delle produzioni)

T = simboli terminali, che NON possono apparire mai da soli a sinistra in una produzione

5

es. di grammatica a struttura di frase: G1 = (V,T,P,S) con:

V = { cane, gatto, morde, guarda, N, V }T = { cane, gatto, morde, guarda} [terminali]P = { p1,p2,p3,p4,p5 } [produzioni]p1: S-> N V N p2: V-> morde p3: V-> guardap4: N-> cane p5: N-> gatto

es. derivazione: S ->1 N V N ->2 N morde N ->4 cane morde N ->4 cane morde caneovvero: S cane morde cane

NOTA che "cane morde N" non e’una frase del linguaggio,infatti qui c’e’ N (simbolo non terminale) che per definizione NON puo' stare in una stringa del linguaggio di G1 esercizio: costruire altre frasi ...

linguaggi a struttura di frase, primo esempio

*

6linguaggi a struttura di frase, primo esempiovediamo ancora cosa produce la grammatica vista

G1 = (V,T,P,S), con: T = { cane,gatto,morde,guarda}V = { cane,gatto,morde,guarda, N, V } e con le produzioni:P = { p1,p2,p3,p4,p5 } con p1: S-> N V N; p2: V-> morde; p3: V-> guarda; p4: N-> cane; p5: N-> gatto;

applicando le produzioni S ->1 N V N e scegliendo altre produzioni (invece di 2,4,4 che da'cane morde cane) avremo

a= cane morde cane, b= cane guarda cane, c= cane morde gatto, d= cane guarda gatto, e= gatto morde cane, f = gatto guarda cane,g= gatto morde gatto, h=gatto guarda gatto.

G1 produce un linguaggio finito di otto frasi:

L1 = { a,b,c,d,e,f,g,h }

7linguaggi a struttura di frase, secondo esempio

aggiungiamo alla grammatica G1 = (V,T,P,S) con:V={cane,gatto,morde,guarda, N, V } T={ cane,gatto,morde,guarda}P = { p1,p2,p3,p4,p5 } con p1: S-> N V N; p2: V-> morde; p3: V-> guarda; p4: N-> cane; p5: N-> gatto;

aggiungo una produzione ed un simbolo terminale "che" :

p6: s V N -> s V N che V N; (s sta per stringa qualsiasi)

e ho: G2 = (V,T,P,S) con: V = { cane,gatto,morde,guarda, che, N, V } vocabolario T = { cane,gatto,morde,guarda, che } simboli terminali P = { p1,p2,p3,p4,p5,p6 } con: p1: S-> N V N; p2: V-> morde; p3: V-> guarda; p4: N-> cane; p5: N-> gatto; p6: s V N -> s V N che V N;

8linguaggi a struttura di frase, secondo esempio

G2: V = { cane,gatto,morde,guarda, che, N, V } T = { cane,gatto,morde,guarda, che } P = { p1,p2,p3,p4,p5,p6 } con: p1: S-> N V N; p2: V-> morde; p3: V-> guarda; p4: N-> cane; p5: N-> gatto; p6: s V N -> s V N che V N;genera frasi del tipo:

S ->1 N V N ->6 N V N che V N ->6 N V N che N V che N V -> ... e, dopo aver sostituito ai N un po’ di cane o gatto e ai V un po’ di guarda o morde otteniamo la frase:

gatto guarda cane che guarda gatto che morde gatto

posso ottenere altre frasi simili->ho un linguaggio INFINITO

9linguaggi a struttura di frase, definizione di linguaggio

Data una grammatica a strutt. di frase,

G = (V,T,P,S) con: [ S = simbolo di partenza] V = { a, b, y, P, Q, ... } = [ vocabolario simboli di G] T = { a, b, y } = [ simboli terminali di G] P = { p1,p2... } = [ produzioni]

definizione: linguaggio a struttura di frase generato da G e' l’insieme delle stringhe sull’ alfabeto T (simboli terminali) che possono essere derivate (direttamente o indirettamente) da S:

L (G) = { w | w c T *, S w } *

G

10linguaggi a struttura di frase, terzo esempio

terzo esempio, G3 = (V,T,S,P), con V = { A, S, a,b }, T = { a, b },P = { p1: S -> a A b; p2: aA -> aaAb; p3: A -> \ }

esempi di derivazioni:S ->1 aAb ->3 aboppure:S ->1 aAb ->2 aaAbb ->3 aabboppure:S ->1 aAb ->2 aaAbb ->2 aaaAbbb ->3 aaabbae quindiL(G3) = { ab, aabb, aaabbb, ... } = { akbk | k>=1 }

11linguaggi a struttura di frase, terzo esempio

continua esempio G3=(V,T,S,P), con V={A,S,a,b}, T={a,b},e P = { p1: S -> a A b; p2: aA -> aaAb; p3: A -> \ }es ( ricorda: si parte sempre da S !! ) S ->1 aAb ->2 aaAbb ->2 aaaAbbb ->3 aaabbb;

quindi: L(G1) = { ab, aabb, aaabbb, ... } = { akbk | k>=1 }

si noti che la produzione p2: aA -> aaAb e’ "ricorsiva", ^1 ^2nel senso che A appare nella parte a sinistra della " -> ", ^1, [parte definita dalla produzione] e appare anche a destra, ^2, [parte definente nella produzione] -->> e quindi

A e’ in parte definita in termini di se’ stessa... ovvero la produzione e' ricorsiva !

12linguaggi a struttura di frase, esempio G4 errata

nota: attenzione alla ricorsione: sappiamo dalla programmazione in C++ che un sottoprogramma ricorsivo DEVE avere un test di fine ricorsione; nel caso delle grammatiche, devo avere una produzione alternativa alla ricorsione che mi consente di fermare la ricorsione:

la grammatica seguente e' errata:

G4 = ( V,T,S, P ), con: V = { x,y,w,z,A,B,S } T = { x,y,w,z } e P = { S -> AB; A -> xA; A -> yA; B -> zB; B -> wB }

vi sono 4 produzioni ricorsive, ma ... mancano (almeno) due produzioni ...

13linguaggi a struttura di frase, G4 corretta

cont. nota: attenzione alla ricorsione:nella la grammatica errata G4 = ( V,T,S, P ), con: V = { x,y,w,z,A,B,S } T = { x,y,w,z } e P = { p1: S -> AB; p2: A -> xA; p3: A -> yA; p4: B -> zB; p5: B -> wB }

mancano (almeno) due produzioni per arrestare la ricorsione, ad es.

p6: A -> x; e p7: B -> z;

esempi: S ->1 AB ->6 xB ->7 xz oppure S ->1 AB ->3 yAB ->5 yAwB ->6 yxwB ->7 yxwz, oppureS ->1 AB ->2 xAB ->2 xxAB ->2 xxxAB ->2 xxxxAB ->6 xxxxxB ->4 xxxxxzB ->4 xxxxxzzB ->4 xxxxxzzzB ->7 xxxxxzzzz ecc

14linguaggi a struttura di frase, grammatica errata

ancora: G5 = ( V, T, S, P ),con: V = { x, y, z, A, C, S }, T = {x,y,z}, P = { p1: S -> AA; p2: A -> xA; p3: A -> C; p4: C -> yC; p5: C -> S; }

problemi in questa definizione? vediamo un es. di derivazione : S ->1 AA ->2 xAA ->2 xxAA ->3 xxCA ->2 xxCxA ->4 xxyCxxA ->3 xxyCxxC ->5 xxySxxC ->5 xxySxxS ...

15linguaggi a struttura di frase, grammatica errata

ancora: G5 = ( V, T, S, P ), V = { x, y, z, A, C, S }, T = {x,y,z}, P = { p1: S -> AA; p2: A -> xA; p3: A -> C; p4: C -> yC; p5: C -> S; }

qui si ha una definizione circolare (ricorsione circolare) :

S e’ definita in termini di A, A e’ definita in termini di C,C e’ definita in termini di S! -> mancano produzioni per eliminare i simboli NON terminali dalle stringhe;

dovremmo ad es. aggiungere qualche produzione del tipo: C -> z; oppure A -> w o altra produzione simile

16linguaggi a struttura di frase, esercizio 3

esercizio:

cosa produce G6 = (V,T,S,P) = G6 = ( { A, a }, { a }, A, { A -> a A A -> a } )

ovvero:

V = { A, a }, T = { a }, S = A, P = { p1: A -> a A; p2: A -> a; }

(segue soluzione)


soluz. esercizio: la grammatica (V,T,S,P) : G6 = ( { A, a }, { a }, A, { A -> a A A -> a } )ovvero: V = { A, a }, T = { a }, S = A, P = { p1: A -> a A; p2: A -> a; }

produce ad es: A ->2 a; A ->1 aA ->2 aa; A ->1 aA ->1 aaA ->2 aaa; A ->1 aA ->1 aaA ->1 aaaA ->2 aaaa; ecc...

cioe’: L(G6) = { ai | i> 0 }


esercizio: cosa produce la grammatica

G7 = ( V, T, S, P ) con

V = { S,A,B, a,b }, T = { a,b }, P = { p1: S -> AB; p2: A-> aA; p3: A -> a; p4: B -> Bb; p5: B -> b }

?


soluz. eserc.: la grammatica G7 = ( V, T, S, P ) con V = { S,A,B, a,b }, T = { a,b }, P = { p1: S -> AB; p2: A-> aA; p3: A -> a; p4: B -> Bb; p5: B -> b }produce ad es:

S ->1 AB ->3 aB ->5 ab; S ->1 AB ->2 aAB ->3 aaB ->5 aab; S ->1 AB ->2 aAB ->4 aABb ->4 aAbb ->3 aabb; S ->1 AB ->2 aAB ->4 aABb ->2 aaABb ->2 aaaABb ->3 aaaaBb ->4 aaaabb;ecc,quindi L(G7) = { aibk | i>0, k>0 }


ripetiamo:grammatiche a struttura di frase, composte da:

G = (V,T,P,S) con: [ S = simbolo di partenza] V = { a, b, y, P, Q, ... } = [ vocabolario simboli di G] T = { a, b, y } = [ simboli terminali di G] P = { p1,p2... } = [ produzioni]

definizione: un linguaggio a struttura di frase generato da G e' l’insieme delle stringhe sull’ alfabeto T (simboli terminali) che possono essere derivate (direttamente o indirettamente) da S:

L (G) = { w | w c T *, S w }

21struttura di una frase e albero sintattico

riprendiamo la G1 = (V,T,P,S),V={cane, gatto, morde, guarda, N, V}T = {cane, gatto, morde, guarda}cinque produzioni: p1: S-> N V Np2: V-> morde p3: V-> guardap4: N-> cane p5: N-> gatto

la frase "gatto morde cane" e' del L(G1), e si deriva con la catena di derivazioni:S ->1 N V N ->2 N morde N ->5 gatto morde N ->4 gatto morde canela derivazione si rappresenta con l' albero sintattico a destra:

NVN

gatto cane

morde

ALBERO SINTATTICO

S1

5 4

2

22struttura di una frase e albero sintatticouna catena di produzioni che porta dal S ad una stringa del linguaggio puo’ essere data in forma grafica:

G7 = ( V, T, S, P ),V = { S, A, B, a, b }T = { a, b }P = { p1: S -> AB; p2: A -> aA; p3: B -> Bb; p4: A -> a; p5: B -> b; }stringa aab del ling.L(G7) ha la struttura a destra

interpretaz. grafica della derivazione:S ->1 AB ->2 aAB ->4 aaB ->5 aab

1 1

2 2

4

5

S

A B

bAa

a

radice

nodiintermedi

foglie o nodi terminali

ALBERO SINTATTICO:

23

G7 = ( V, T, S, P ),V = { S, A, B, a, b }T = { a, b }P = { p1: S -> AB; p2: A -> aA; p3: B -> Bb; p4: A -> a; p5: B -> b; }un’altra derivazione:S ->1 AB ->2 aAB ->2 aaAB ->4 aaaB ->3 aaaBb ->3 aaaBbb ->5 aaabbb stringa con albero a destra

struttura di una frase e albero sintattico

1 1

2 2

S

A B

b

Aa

radice

nodiintermedi

AA

a

2

a

4

2

5b

B

B

b3

3

33

foglie o nodi terminali

24linguaggio delle espressioni aritmetiche senza parentesi

G8: una grammatica semplificata delle espressioni aritmetiche senza parentesi, del tipo a+b*b+a;i simboli terminali sono a,b, +,* non c'e' priorita' tra i due operatori + e *;

G8: T= {a,b,+,*}, V= {a,b,+,*, S}, P = {p1,p2,p3,p4}

p1: S->S+S p2: S->S*S p3: S->a p4: S->ble

produzioni p1 e p2 sono "ricorsive", ad esempio inp1: S -> S + S; qui il simbolo S = a sinistra della " -> " [che e’ la parte definita dalla produzione] (*)appare anche a destra [parte definente nella produzione] ----------------------------------------------------------------------------------------------------------------------------------------------

(*) nb: s -> q leggi: " s produce q", leggi anche:"la stringa q deriva da s", e anche: " s e’ definita come q"

25

continuaG8 = ( V,T,P,S ) = grammatica "espressioni aritmetiche"

T= {a,b,+,*}, V= {a,b,+,*, S}, P = {p1,p2,p3,p4}

p1: S->S+S p2: S->S*S p3: S->a p4: S->b

(nota le produzioni p1 e p2 di tipo ricorsivo)

es. di catene di produzioni:

1) S ->3 a; [ "a" e’ una frase]

2) S ->1 S+S ->4 S+b ->4 b+b;

3) S ->2 S * S ->3 a * S ->4 a * b;

4) S ->2 S*S ->1 S*S+S ->3 a*S+S ->3 a*a+S ->3 a*a+a;

S a*a+a

linguaggio delle espressioni aritmetiche

*

G

26linguaggio delle espressioni aritmetiche

ancora per G8=(T,V,S,P) con T={a,b,+,*}, V= {a,b,+,*, S},P={p1,p2,p3,p4} p1: S->S+S p2: S->S*S p3: S->a p4: S->b

ancora due esempi di derivazione:

5) S ->2 S * S ->2 S * S * S ->1 S * S + S * S ->3 a * S + S * S ->4 a * b + U * S ->3 a * b + a * S ->4 a * b + a * b;

6) S ->1 S+S ->2 S+S*S ->1 S+S*S+S ->3 a+S*S+S ->4 a+b*S+S ->1 a+b*S+S+S ->4 a+b*b+S+S ->5 a+b*b+a+S ->4 a+b*b+a+b

... G8 genera delle stringhe che possono essere interpretate come semplici espressioni aritmetiche senza parentesi.

27linguaggio delle espressioni aritmetiche: albero sintattico

la catena di derivazione implica la struttura di una frase.

G8=(T,V,S,P), T={a,b,+,*}, V={a,b,+,*, S}, P={p1,p2,p3,p4} p1: S->S+S p2: S->S*S p3: S->a p4: S->b

un esempio: derivazione (struttura) della stringa a*a : S ->2 S*S ->3 a*S ->3 a*a

la struttura dell' albero viene dalle derivazioni !

S

S S

a a*

2

2

2

3 3

28

S ->2 S*S ->1 S*S+S ->3 a*S+S ->3 a*a+S ->3 a*a+a; a destra l’albero sintattico corrispond. (radice S in alto, nodi intermedi S, foglie=nodi terminali in basso [a,*,a,+,a]; sui rami sono segnate le produzioni)Quindi a*a+a,frase del linguaggio I8 generato dalla grammat.G8, si interpreta come:

a * (a+a) e non: (a*a)+a !

linguaggio delle espressioni aritmetiche: albero sintattico

la catena di derivazione implica la struttura di una frase.

G8=(T,V,S,P), T={a,b,+,*}, V={a,b,+,*, S}, P={p1,p2,p3,p4} p1: S->S+S p2: S->S*S p3: S->a p4: S->b

S

S S

S S

a a a* +

2

2

2

11

1

3

3 3

29espressioni aritmetiche – grammatiche ambigueattenzione pero’ ... la grammatica G8

G8 = (T,V,S,P) con T= {a,b,+,*}, V= {a,b,+,*, S}, P = {p1,p2,p3,p4} p1: S->S+S p2: S->S*S p3: S->a p4: S->b

se una G permette di ottenere la stessa stringa con catene di produzioni diverse, diremo che e’ una grammatica ambigua,

in G8 la frase a*a+a puo’ essere ottenuta con derivazioni diverse, allora puo’ essere interpretata con strutture diverse:

S ->2 S*S ->1 S*S+S -> a*S+S -> a*a+S -> a*a+a che si interpreta come: a* (a+a) - come visto prima, S ->1 S+S ->2 S*S+S -> a*S+S -> a*a+S -> a*a+a che si interpreta invece come (a*a)+a !quindi la stessa stringa puo’ avere due strutture diverse ...interpretando la struttura, se associo alle variabili dei valori numerici, ottengo due valori diversi! -> G8 non va bene;


come in un dato linguaggio generato da una data grammatica posso produrre la stessa stringa (frase) con due catene di derivazioni diverse, cosi' anche un linguaggio puo' esser prodotto da piu' grammatiche -

def.: se un linguaggio non ha alcuna grammatica che lo generi di tipo non ambiguo (cioe’ tutte le grammatiche che lo generano sono ambigue) allora diremo che e’ un linguaggio ambiguo.

abbiamo visto che G5 = (T,V,S,P), T= {a,b,+,*}, V= {a,b,+,*, S}, P = { p1: S->S+S p2: S->S*S p3: S->a p4: S->b }e’ una grammatica ambigua - ma: vediamo ora che lo stesso linguaggio puo’ essere descritto con una grammatica NON ambigua


la grammatica seguente G9 produce lo stesso linguaggio della G8 ma non e' ambigua. Qui sono introdotti due nuovi simboli non terminali (due categorie sintattiche), T e F(termine e fattore):

G9 = ( V,T,P,S ), con T = {a,b,+,*}, V = {a,b,+,*, S,T,F}, e P = { p1: S->S+T p2: S->T ("termine"= significato...)

p3: T->T*F p4: T->F ( "fattore"=significato... )p5: F->a p6: F->b ( a,b sono "variabili"... ) }

es.:S ->1 S+T ->2 T+T ->3 T*F+T ->4 F*F+T ->4 F*F+F ->3 a*F+F -> a*a+F -> a*a+a

a*a+a ha la struttura sintattica: ( termine + termine )dove il 1.o termine e’ dato da (fattore * fattore)

32G9 = ( V,T,P,S ), con T = {a,b,+,*}, V = {a,b,+,*, S,T,F},

P = {p1: S->S+T p2: S->T p3: T->T*F p4: T->F p5: F->a p6: F->b }

S ->1 S+T ->2 T+T ->3 T*F+T ->4 F*F+T ->4 F*F+F ->3 a*F+F ->5 a*a+F ->5 a*a+a

che ha quindi la struttura( a*a ) + acome riportata dall’albero sintattico a destra:

S

S

T

T

T

F

F

F

a

a

a

+

*

foglie

nodi nonterminali

radice

33es.: due gramm. diverse per lo stesso linguaggio, es. di precedenza di valutazione da destra a sinistra o viceversa:

G10 = ( V,T,S, P ) conV={ a,b,c,-,A,S };T={ a,b,c,-}; P = { S -> A; S -> S - A; A -> a; A-> b; A -> c } -->interpretazion da sinistra a destra

G11 = ( V,T,S, P ) conV={ a,b,c,-,A,S };T={ a,b,c,-}; P = { S -> A; S -> A - S; A -> a; A-> b; A -> c } -->interpretazioneda destra a sinist.

S

S

S

A

A

A

-

-

cb

a

S

S

S

A

A

A -

-a

b

c

a-b-c = (a-b)-cda sinistra a destra

a-b-c = a-(b-c)da destra a sinistra


abbiamo cosi’ visto

alcuni concetti relativi alle

grammatiche a struttura di frase :

* def. di grammatica

* def. di derivazione diretta / catena di derivazione

* albero sintattico / struttura della frase

* ambiguita’ : grammatica ambigua, linguaggio ambiguo

35

grammatiche generative -

analisi sintattica:

accettazione di una stringa ben formataericonoscimento della strutturadi una stringa

36premessa – traduzione

premessa:

alcune osservazioni

introduttive

sui linguaggi di programmazione


un calcolatore esegue delle procedure di elaborazione dati descritte con dei programmi (software) – piu' precisamente, le istruzioni del programma, memorizzate nella memoria centrale, sono eseguite una dopo l'altra dall' unita' centrale.

un programma

e' la descrizione completa di tutta la sequenza delle azioni da fare per ottenere qualcosa da un calcolatore, compresa la descrizione completa dei dati elaborati (iniziali, intermedi, finali) ovvero

* e' una lista di istruzioni (descrive azioni e dati) da far eseguire ad un calcolatore per ottenere un risultato,


un calcolatore esegue delle procedure di elaborazione dati descritte con dei programmi (software) – piu' precisamente, le istruzioni del programma, memorizzate nella memoria centrale, sono eseguite una dopo l'altra dall' unita' centrale.

il programma (la lista istruzioni) deve essere scritto

* in un linguaggio comprensibile direttamente al calcolatore (linguaggio della macchina, o Linguaggio Macchina LM)

* oppure puo' essere scritto in un linguaggio intermedio, comprensibile ad una persona e ad una macchina, ma in tale caso deve prima essere tradotto per poter dopo essere eseguito.


Abbiamo detto che un programma e' la descrizione di tutta la sequenza delle azioni da fare per ottenere qualcosa dal calcolatore, compresa la descrizione completa dei dati (iniziali, intermedi, finali) - il programma deve essere scritto in un linguaggio comprensibile al calcolatore ....

ma: ogni calcolatore ha un suo linguaggio macchina LM:esistono tanti LM quanti sono i diversi calcolatori (vedremo questo in seguito) qui un elenco brevissimo :EDSAC ('48), IBM7090('57), IBM/360('65), Digital PDP11('71), Zilog Z80('75), Intel 8086 ('79), PowerPC 601 ('91), PowerPC G5 (02), Intel Pentium 4 HT (03) ecc

negli anni 50 i programmi venivano effettivamente scritti in linguaggio macchina ....


un programma scritto nel LM di un calcolatore X puo' essere eseguito solo da tale macchina ....

per poter eseguire un programma su macchine diverse e' necessario usare un linguaggio "intermedio" - (nel senso che puo' essere capito "abbastanza" facilmente sia da una persona che da una macchina) non vincolato ad una macchina specifica, dal 55 ad oggi sono state definite diverse migliaia di linguaggi di programmazione (qualche 10000...)

esistono molti tipi di linguaggi intermedi, * procedurali (es. Fortran, C#, ...)* funzionali (es. Lisp)* logici (es. Prolog) ecc ...


diversi tipi di linguaggi intermedi - in particolare ci interessano i linguaggi procedurali - o LP;

i LP sono linguaggi progettati per descrivere procedimenti di calcolo (procedure di calcolo),

alcuni nomi: Fortran ('57..'90..) Cobol ('59), Algol '60, Basic (65), Pascal (71), C ('71), Ada ('78), Java (94)...

-> il programma scritto in LP deve essere tradotto nel LM di un particolare calcolatore

un LP e'definito in modo che la traduzione da LP in LM e' eseguita da una macchina (in modo meccanico) velocemente cioe' da un calcolatore, e il procedimento di traduzione e' specificato nel programma di traduzione o traduttore.

42continua nota sui linguaggi di programmazione:

un programma (testo "sorgente") e' scritto in un dato linguaggio di programmazione LP (C, Pascal, Fortran, ...), il traduttore (il programma di traduzione eseguito su un calcolatore) traduce il programma da LP nel linguaggio macchina LM;

program a;begin write(‘bla’)end.

010101010011001100001111010...

progr. in L.P.(Pascal)

prog. in L.M.(PPCG6)

traduttore esecutore

43il linguaggio LP e' definito in modo che la traduzione puo’ essere meccanica cioe' fatta da un programma traduttore, detto compilatore

prog. in L.M.(PPCG6)

program a;begin write(‘bla’)end.

010101010011001100001111010...

progr. in L.P.(Pascal)

il calcolatore esegue un progtraduttore =

"Compilatore"

il calcolatore esegue il nostroprogramma

il compilatore deve tradurre il nostro programma -> quindi

deve riconoscere se e’ scritto correttamente [se e’ una frase del linguaggio di programmazione usato] e deve riconoscere la sua struttura [per tradurlo!] ...

44

il compilatore esegue * un' analisi lessicale - per individuare i componenti elementari (nomi, operatori, simboli riservati ecc),

* un' analisi sintattica della struttura del programma, e in particolare della struttura sintattica del programma * infine traduce il testo LP in un programma "equivalente" in LM (analisi semantica)

il compilatore deve riconoscere se il programma scritto in un LP rispetta le regole della grammatica di quel linguaggio !

45analisi sintattica: riconoscimento della struttura

data una grammatica G e data una stringa s si deve riconoscere

1) se s appartiene al linguaggio L(G), (cioe’ se s e’ una s.b.f. ovvero se s e’ grammaticalmente corretta)

e 2) come la s e’ producibile dalla G: (cioe’ individuare la catena delle produzioni che produce s a partire da S, e quindi la struttura della s)

questo procedimento si dice analisi sintattica

46analisi semantica

una volta riconosciuta una stringa come frase del linguaggio (ovvero riconosciuto un testo come un programma grammaticalmente corretto) il compilatore ((che a questo punto conosce tutti gli elementi costitutivi di base (identificatori, costanti, separatori, parole chiave, commenti ecc) e la struttura della frase (del programma) )) dicevamo,il compilatore puo' procedere alla traduzione vera e propria, in base a regole (date una volta per tutte) sulla traduzione dei singoli pezzi dal linguaggio (Pascal, C++ ecc) in linguaggio macchina;questa fase si dice analisi semanticasegue un micro esempio..

47traduzione di un'istruzione molto semplice

un esempio banale: c=a+b; (istruzione linguaggio C)dove a,b,c sono variabili di indirizzi di memoria 7700, 7704, 7708per una macchina (unita'centrale) con istruzioni macchinadel tipo:move indirizzo,registro (Load)add registro,registro,move registro,indirizzo (Store)

dopo l'analisi lessicale (calcola indirizzidei simboli a,b,c)e sintattica (struttura)l'istruzione sara' tradotta in linguaggiomacchina, esempio:

move #7708,R7 //indir di c in R7move 7700,R5 // valore di a in R5move 7704,R6 // valore di b in R6add R5,R6 // somma a in bmove R6,(R7) // memor.risult.da R6 // in memoria indir.cche corrisponde all'istruzionec=a+b ovvero ( c = ( a + b) )riscritta in notazione postfissa:cab+= ovvero (c ( ab+ ) = )

48dove sta la grammatica in un compilatore ?

per la maggior parte dei compilatori

la grammatica del linguaggio e' inserita NEL compilatore,una volta per tutte, come pure la descrizione della macchina cui e' destinata la traduzione;

esistono compilatori dove le descrizioni del linguaggio e/o la descrizione della macchina destinazione sono fornite con delle tabelle esterne:

cambiando tabelle cambia il linguaggio cui il compilatore e' destinato, e/o cambia la macchina cui la traduzione e' destinata.

49esempio di grammatica in un compilatore esterna:

PascalProg.p

GrammPascal

COMPILATORE con SINTASSIS e per CPU X

descrizIstruzA

CPU_A

Progr.C++

GrammC++

COMPILATORE con SINTASSIS e per CPU X

descrizIstruzB

CPU_B

gramm S =

= cpu X

= cpu X

esempio: qui il compilatore legge da file esterno la descrizione delal grammatica e la descrizione della macchina cui e' destinata la traduzione ...

gramm S =

50esempio di analisi sintattica: (cenni)

esempio: data una grammatica G19 = (V,T,S,P),

con V = { S, A, x, y, z }, T={ x, y, z },

e con P = { p1: S -> xA; p2: A-> z; p3: A -> yA; }

voglio sapere se la stringa xyyyz e' producibile da G19, ovvero se si puo’ derivare s da S, ovvero se esiste una catena di derivazione S -*> s

diremo che se s deriva da S allora abbiamo riconosciuto s come stringa del linguaggio L(G19)

51esempio di analisi sintattica: (cenni)data G19 = (V,T,S,P), con V = { S,A,x,y,z}, T={x,y,z},e con P = { p1: S -> xA; p2: A-> z; p3: A -> yA; }

riconoscere s = xyyyz significa cercare una catena di derivazione S -*> s in genere s non e' ottenibile da S con una sola produzione - cerco quindi una produzione pk che generi almeno la parte iniziale di s; divido s = xyyyz in due parti: xyyyz==xT, quindi la stringa da riconoscere e' s = xT = xyyyz, (T=yyyz), cerco allora una pk che generi una x iniziale; tra le produzioni trovo p1 che produce una x iniziale: S -> xAal posto del problema trova catena produzioni S -*> xyyyz ho ora xA -*> xyyyz cioe' trova catena A ->* yyyz

52esempio di analisi sintattica: (cenni)data G19 = (V,T,S,P), con V = { S,A,x,y,z}, T={x,y,z},e con P = { p1: S -> xA; p2: A-> z; p3: A -> yA; } ;

riconoscere s = xyyyz equivale a riconoscere

s = xT = xyyyz, (T=yyyz),

cerco allora una pk che generi una x iniziale; tra le produzioni trovo la p1 che produce una x iniziale:

S -> xA

quindi invece di S -*> xyyyz ? possiamo considerare xA -*> xyyyz

possiamo dire di avere riconosciuto x, le due stringhe a sinistra e a destra iniziano entrambe con x, lo tolgo, ... e quindi ora il problema e' trovare se A -*> yyyz

53cont. esempio di analisi sintattica (cenni) :data G19 = (V,T,S,P), con V = { S,A,x,y,z}, T={x,y,z},e con P = { p1: S -> xA; p2: A-> z; p3: A -> yA; }data s = xyyyz; domanda: S s ?

il procedimento consiste nel provare le produzioni possibili, scelgo quella che mi da' la parte iniziale uguale :

S -> xyyyz da’ la parte iniziale di s, qui "x".

p1: S-> xA xyyyz provo p1, "riconosco" x, e lo elimino ora devo riconoscere yyyz come A: (cioe' se A puo' produrre s2 == yyyz) A yyyz s2 inizia con y, scelgo la p3 che da’ y:

p3: A->yA yyyz riconosco y e lo elimino: abbiamo cosi' A yyz riconosciuto i primi due simboli x,y della stringa di partenza xyyyz

*

54cont. esempio di analisi sintattica (cenni) :data G19 = (V,T,S,P), con V = { S,A,x,y,z}, T={x,y,z},e con P = { p1: S -> xA; p2: A-> z; p3: A -> yA; }data s = xyyyz; domanda: S s ?

procedim.: provo le produzioni possibili, scelgo quella che S -> xyyyz da’ la parte iniziale di s, qui "x".p1: S-> xA xyyyz provo con p1, riconosco x, e lo elimino A yyyz s inizia con y, scelgo la p3 che da’ y:p3: A->yA yyyz riconosco y e lo elimino; ripeto con A yyz quello che rimane: A -> yyz ? provop3: A-> yA yyz ancora con p3: yA -> yyz ? riconosco A yz la y iniziale, resta da vedere se A->yzp3: A-> yA yz provo con p3, riconosco y, elimino; A z cerco produz. che da A mi da’ z, e’ p2:p2: A -> z z riconosco z, elimino - e ho finito:

abbiamo ricostruito la catena di derivazione S s

*

*

55cont. esempio di analisi sintattica (cenni) :data G19 = (V,T,S,P), con V = { S,A,x,y,z}, T={x,y,z}, P = { p1: S -> xA; p2: A-> z; p3: A -> yA; }

abbiamo ricostruito la catena di derivazione dellastringa s = xyyyz :

S ->1 xA ->3 xyA ->3 xyyA ->3 xyyyA ->2 xyyyz

e quindi abbiamo anche costruito l’ albero sintatticocioe’ la struttura della frase s

S

x A

A

A

A

y

y

y

z

1 1

3

3 3

33

3

2

56notazione delle produzioni: l'operatore oppure |

nota - vi sono diversi formalismi o modi di scrivere le produzioni (vedremo in seguito la forma piu'usata o "forma normale")

al posto di:

P = { S-> A; S-> B; A -> xA; A -> y; }

scrivo le stesse produzioni anche cosi’:

P = { S -> A | B; A -> xA | y; }

il simbolo "|" sta per alternativa, leggi: "oppure":

S produce A oppure B; A produce xA oppure y;

57problemi di riconoscimento

spesso il procedimento di analisi sintattica di una stringa s (riconoscere la struttura, cioe’ la catena delle produzioni che da S produce s) NON e’ cosi’ semplice. Es:

G20 = ( V= { x,y,z,A,B,S}, T= {x,y,z}, S, P ) .... dove P = { p1: S-> A; p2: S-> B; [cioe’: S produce A oppure B] p3: A -> xA; p4: A -> y; p5: B -> xB; p6: B -> z }

nota: due produzioni p3 e p5 producono entrambe stringhe che iniziano con la x; ... vedremo che questo crea dei problemi)alcuni es. di derivazioni: y e xy appartengono a L(G20):

S ->1 A ->4 y S ->1 A -> 3 xA ->4 xy

58problemi di riconoscimento spesso il procedimento di analisi sintattica di una stringa s (riconoscere la struttura, cioe’ la catena delle produzioni che da S produce s) NON e’ cosi’ semplice. Es:

G20 = ( { x,y,z,A,B,S}, {x,y,z}, S, P ) dove P = {p1: S-> A; p2: S-> B; [cioe’: S produce A oppure B] p3: A -> xA; p4: A -> y; p5: B -> xB; p6: B -> z }(nota: vi sono due produz.,p3 e p5 che producono stringhe che iniziano con la x; vedremo che questo crea dei problemi)

altri esempi di stringhe prodotte dalla G20:

S ->2 B ->6 z S ->2 B ->5 xB ->6 xzS ->1 A ->3 xA -> 3 xxA ->4 xxyS ->2 B ->5 xB ->5 xxB ->6 xxz

quindi y, xy, z, xz, xxy, xxz sono producibili dal L(G20)

59problemi di riconoscimento G20 = ( { x,y,z,A,B,S}, {x,y,z}, S, P ) dove P = { p1: S-> A; p2: S-> B; p3: A -> xA; p4: A -> y; p5: B -> xB; p6: B -> z }

esempio: riconoscere: s = xxz (che abbiamo visto prodotto dalle produzioni 2,5,5,6:S ->2 B ->5 xB ->5 xxB ->6 xxz

considero s = xxz = xt (con t=xz) quindi da riconoscere x:p3 e p5 producono una x iniziale, scelgo la prima, p3; quindi devo riconoscere una A (catena a ritroso: xA prodotto da A prodotto da S ):1) S -> A xxz3) A -> xA xxz ho riconosciuto il 1.o x, rimane da riconoscere se A -> xz quindi cerco ancora una produzione A -> x....

60problemi di riconoscimento G20 = ({ x,y,z,A,B,S}, {x,y,z}, S, P), P= {p1: S->A; p2: S->B; p3: A -> xA; p4: A -> y; p5: B -> xB; p6: B -> z }

da riconoscere: s = xxz, s = xt (con t=xz) quindi da riconoscere x: p3 e p5 producono una x iniziale, scelgo p3; quindi devo riconoscere una A, che e' producibile da S

(derivazioni S->1 A, A ->3 xA ):

p1) S -> A xxz

p3) A -> xA xxz ho riconosciuto il primo x, rimane da riconoscere se A -> xz, uso la p3:

p3) A -> xA xz riconosco x, elimino, resta da riconoscere se A produce z ....


G20 = ({ x,y,z,A,B,S}, {x,y,z}, S, P), P= {p1: S->A; p2: S->B; p3: A -> xA; p4: A -> y; p5: B -> xB; p6: B -> z }da riconoscere: s = xxz, s = xt (con t=xz) quindi da riconoscere x: p3 e p5 producono una x iniziale, scelgo p3; quindi devo riconoscere una A (derivaz.: xA 3<- A 1<- S): S -> xxz1) S -> A xxz3) A -> xA xxz ho riconosciuto il 1.o x, rimane da riconoscere A -> xz, uso la p3:3) A -> xA xz riconosco x, elimino, resta da riconoscere A z ma-unica produz. che produce z e’ la p6, la p6 produce z, MA inizia con B , nessun’altra pk produce z ... concludo che ho sbagliato strada in una delle scelte precedenti! Le scelte per A ->? xA erano senza alternativa, devo cambiare ["ritrattare"] la 1) S -> A

62problemi di riconoscimento: ripensamentiG20 = ({ x,y,z,A,B,S}, {x,y,z}, S, P), P = {p1: S->A; p2: S->B; p3: A -> xA; p4: A -> y; p5: B -> xB; p6: B -> z }da riconoscere: s = xxz, cioe’ da trovare se S -> xxz S -> xxz la scelta 1) ci 1) S -> A xxz porta in un vicolo .... A z ? cieco, quindi ... S -> xxz devo cambiare e2) S -> B xxz scelgo la p2:5) B -> xB xxz poi la p5, infine 5) B -> xB xz riconosco z, e ho6) B -> z z finito,e ho la struttura a fianco:

S

B

B

B

x

x

z

il procedimento di ripensamento [ che si deve applicare se si arriva ad un punto dove non e’ possibile trovare una pro-duzione che vada bene ] si dice "backtracking"

5

2

5

55

6

63nota...

Abbiamo visto due algoritmi a backtracking o a prova e riprova (problema delle 8 regine, problema del cavallo) –ma abbiamo anche visto che i tempi di esecuzione crescono enormemente al crescere della dimensione del problema!

Un programma traduttore deve poter riconoscere la struttura del programma senza troppi tentativi infruttuosi, e senza ripensamenti...

si pensi ai tempi di traduzione di un programma di 100 pagine ovvero 5000 righe ...

in effetti i linguaggi di programmazione sono definiti in modo da consentire un riconoscimento veloce, senza tornare indietro nel testo (testo letto e tradotto in una passata)


talvolta e’ possibile riscrivere la grammatica in modo che il processo di riconoscimento non richieda ripensamenti (senza backtracking): per la G20 di prima,

P = { S-> A|B; A-> xA|y; B-> xB|z } [ricorda: le P della G20 producono stringhe del tipo: y,z,xy,xz,xxy,xxz,xxxy,xxxz ... ]

in due produzioni di G20 la parte destra inizia con lo stesso simbolo x; [questo causa backtracking - da evitare!] ...

al posto delle P della G20 di sopra definiamo le produzioni: P1 = { S-> xS | C; C -> y | z }

dove la prima produzione produce una o piu’ x e la seconda produzione S -> C genera una C al posto di S, C che poi produce o una y o una z; abbiamo ora...

65riconoscimento : una grammmatica migliore

G20bis: P1={p1,2: S-> xS|C; p3,4: C -> y|z}

p1: S -> xS cioe: S produce una o piu’ x, p2: S -> C cioe' S genera una C che poi p3: S -> y|z ovvero C produce una y (p3) o una z (p4)

ora per riconoscere xxz:

S -*> xxz ?

S ->1 xS -*> xxz riconosco x, elimino, guardo il resto: S -*> xz di nuovo la produzione p1 : S ->1 xS -*> xz riconosco x, elimino, guardo il resto: S -*> z per riconoscere z non va bene p1 o p2; S ->2 C -*> z ma indirettamente: C->z, e S->C C ->4 z == z provo con p4, riconosco z e ho finito.

66riconoscimento : una grammmatica migliore

...una grammatica tale da consentire un riconoscimento veloce di una stringa (e quindi tale che permetta una traduzione veloce dei nostri programmi...) deve avere alcune proprieta' ...

per definire una "buona" grammatica che poi consenta un riconoscimento veloce vi sono diverse precauzioni da usare

ma noi ci fermiamo qui ...

67esercizi sull' analisi sintattica - primo esercizio:

esercizio:

definire una grammatica che produce stringhe del tipo:

1.033.224.5E-277.88E+123

(costante floating senza segno)

segue una soluzione

trovare una grammatica per le stringhe date =significa trovare uno schema di struttura comune a tutte queste stringhe ..individuo due parti, la parte cifre e la parte esponente;a loro volta le due parti hanno una struttura...


es.: definire una grammatica che produce stringhe del tipocostante floating senza segno:

1.033.224.5E-277.88E+123

segue una soluzione

trovare grammatica per le stringhe date =significa trovare uno schema di struttura comune a tutte queste stringhe :individuo due parti, la parte cifre e la parte esponente; a loro volta le due parti hanno una struttura:parte cifre e' fatta da due parti intere separate da un punto , parte esponente e' fatta da una E seguita da un segno seguito da un intero...


1.0 2.3 33.22 4.5E-2 3.3E-5 77.88E+123 costante float ha due parti, la parte cifre e la parte esponente; a loro volta le due parti hanno una struttura: parte cifre e' fatta da due parti intere separate da un punto , parte esponente e' fatta da una E seguita da un segno seguito da un intero...

G21 = ( S, T, V, P ), con T = (0,1,2,3,4,5,6,7,8,9,0,+,-,E) S = X | Y (X cost senza parte espon, Y con espon) X = I . I (I intero senza segno) I = C | C I ( C cifra, un Intero e' una o piu' cifre) Y = X E Z I (costante con parte esponente) Z = + | - (segno)

es. di derivazione per le due stringhe 1.0 e 3.3E-5:S -> X -> I.I -> C.I -> 1.I -> 1.C -> 1.0S -> Y -> X E Z I -> I.I E Z I -> C.CEZI -> 3.3EZI -> 3.3E-5

70esercizi sull' analisi sintattica - primo esercizio:riprendiamo la grammatica di costante floating senza segno:

G21 = ( S, T, V, P ), con T = (0,1,2,3,4,5,6,7,8,9,0,+,-,E) S = X | Y (X cost senza parte espon, Y con espon) X = I . I (I intero senza segno) I = C | C I ( C cifra, un Intero e' una o piu' cifre) Y = X E S I (costante con parte esponente) S = + | - (segno)

con questa grammatica posso produrre anche:

1234567987654.12345678987654E+12345678987654321

perche' questa grammatica non specifica limiti;

esempio di stringa non corretta: 1E-2 ... manca il punto (le cifre del dato sono prodotte da X, con la produzione X-> I . I )

71riprendiamo ancora alcune considerazioni...

l’ analisi sintattica e’ alla base di ogni programma traduttore (compilatore) da un linguaggio di programmazione (Pascal, C, Fortran, ...) in linguaggio macchina:

il compilatore deve ricostruire la derivazione S -> programma,e cioe’ l’albero sintattico ovvero la struttura del programma (programma = frase del linguaggio Pascal o C..)

e in base alla struttura traduce il nostro programma in linguaggio macchina

( mantenendo il significato == semantica del programma );

La gramm. e’ (quasi) sempre "incorporata" nel compilatore.

72riprendiamo ancora alcune considerazioni...

l’ analisi sintattica : il compilatore deve ricostruire la catena di deriv. S -> programma, cioe’ l’albero sintattico o la struttura del programma (programma = frase del linguaggio C )

in generale una prima parte del compilatore riconosce le "parole", ovvero gli "identificatori",

e ricostruisce il lessico usato nel programma (fa un "dizionario" delle parole usate nel programma) ... >

questa parte si chiama analisi lessicale

73

programma sorgente

analisi lessicale(identificatori)

analisi sintattica(albero sintattico)

analisi semantica(traduz.in ling.macch)

programma tradotto

traduzione di unprogramma dalla versione Ada o Pascal o Calla versione in linguaggio macchinacon lo stesso significato (stessa semantica)

74esercizi sull' analisi sintattica - secondo esercizio:

data G21 = ( V, T, S, P ), T = { a,b,1,2 }, V = T u { L,C,I,S },P = { p1: S -> I; p2: I -> IL; p3: I -> IC; p4: I -> L; p5: I -> C; p6: L -> a; p7: L -> b; p8: C -> 1; p9: C -> 2 }es:S ->1 I ->3 IC ->2 ILC ->3 ICLC ->4 LCLC ->6 aCLC ->8 a1LC ->6 a1aC ->9 a1a2 (nota: L = lettera, C=cifra, I = Item=elemento)domanda:

2b2 appartiene a L(G21) ?ovvero: e’ producibile dalla grammatica G11 ?

segue soluzione

75

G21: P = { 1: S-> I; 2: I-> IL; 3: I-> IC; 4: I-> L; 5: I-> C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 }

domanda: 2b2 appartiene a (e’ producibile da) L(G21) ?

per riconoscere 2b2 procedo come segue:

? -> 2b2 cerco produz. con 2 in 1.a posiz. a dest., e' la p9C? ->9 2b2 quindi C seguito da ? produce 2 seguito da b2;? -> Cb2 cerco produzione con C in 1.a posiz.a destra:I? ->5 Cb2 solo la p5 produce C come richiesto, quindi

? -> Ib2 ->5 Cb2 ->9 2b2 dopo 2 tentativi di riconoscimento

continua 2.o esercizio sull' analisi sintattica

76continua 2.o esercizio sull' analisi sintattica

G21: P = { 1: S-> I; 2: I-> IL; 3: I-> IC; 4: I-> L; 5: I-> C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 }... (continua) per riconoscere 2b2 abbiamo trovato:? -> Ib2 ->5 Cb2 ->9 2b2 dopo 2 tentativi di riconoscimento

? -> Ib2 devo ottenere I in 1.a posizione a destra - provo (in ordine) le produzioni che soddisfano questa condizione: provo con p1:S ->1 I che da' luogo alla catena di produzioni :S ->1 I ->5 C ->9 2 ... ma: rimane da riconoscere b2 ! -> queste scelte fatte per ricostruire questa catena non e' ok->cambio ? C->9 2 non si puo' cambiare, I->5 C non si puo', cambio S->1 I, scelgo la prossima p che produce I in 1.a posizione: I->2 IL per produrre I in 1.a posizione, ->I ->2 IL ->5 CL ->9 2L ... rimane da trovare se L -> b2

77

G21: P = { 1: S-> I; 2: I-> IL; 3: I-> IC; 4: I-> L; 5: I-> C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 } S -> ? 2b2 ... dopo alcuni tentativi si propone la catena : S ->1 I ->2? IL ->? Ib2 ->5 Cb2 ->9 2b2 rimane da trovare se L -> b2 ...

dopo altri tentativi, sempre applicando le produzioni in ordine, si trova che S ->1 I ->3 IC ->2 ILC ->5 CLC ->9 2LC ->7 2bC -9 2b2

... per riconoscere la stringa molto semplice 2b2 abbiamo dovuto ritrattare piu' volte una scelta di produzione ! ... non e' una grammatica che consenta un riconoscimento veloce ...

continua 2.o esercizio sull' analisi sintattica


G21: P = { 1: S-> I; 2: I-> IL; 3: I-> IC; 4: I-> L; 5: I-> C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 }G21bis: cambio la grammatica in modo da avere le produzioni ricorsive a sinistra invece che a destra, e in modo da non avere lo stesso simbolo all'inizio della parte destra in piu' produzioni: vediamo come si riconosce 2b2 ... P= { 1: S-> I; 2: I-> II; 4: I->L; 5: I->C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 } Cb2 ->9 2b2 I? ->5 Cb2 riconosco 2 come una C, e C come una I poi analizzo il resto della stringa... L? ->7 b2 ? ->? 2 come gia' visto, C ->9 2, e I ->5 C abbiamo cosi' riconosciuto tutta la 2b2:


G21bis: P= { 1: S-> I; 2: I-> II; 4: I->L; 5: I->C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 }

riconoscere 2b2 significa riconoscere 2xx; la produz. 9 da': Cb2 ->9 2b2 (rimane da riconoscere b2) C e' ottenibile da I, e I da S: I? ->5 Cb2 riconosco 2 come una C, e C come una I poi analizzo il resto della stringa, b2: L? ->7 b2 L puo' produrre b, quindi resta ?->2; ? ->? 2 come gia' visto, C ->9 2, e I ->5 C abbiamo cosi' riconosciuto tutta la 2b2: S ->1 I ->2 II ->2 III ->6 ILI ->5 CLI ->5 CLC CLC ->9 2LC ->7 2bC ->9 2b2


esercizio:

fare l'albero sintattico di 2 b 2

per G21bisP= { 1: S-> I; 2: I-> II; 4: I->L; 5: I->C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 }

ovvero esprimere graficamente la catena di derivazione

S ->1 I ->2 II ->2 III III ->6 ILI ->5 CLI CLI ->5 CLC ->9 2LC 2LC ->7 2bC ->9 2b2

81

P= { 1: S-> I; 2: I-> II; 4: I->L; 5: I->C; 6: L-> a; 7: L-> b; 8: C-> 1; 9: C-> 2 }

S ->1 I ->2 II II ->2 III ->6 ILI ILI ->5 CLI ->5 CLCCLC ->9 2LC ->7 2bC 2bC ->9 2b2

S

I

II

1

III

ILI

IbI...

2b2

7

2

2

4

823.o esercizio : G22 = ( V, T, S, P ),

T = { bello, basso, buono, cattivo, ascolta, guarda, mangia, il, un }

V = T u {A,B,C,X,Y }

P = { p1: S -> A B C; p2: A -> X Y; p3: C -> X Y; p4: X -> il | un ; p5: Y -> bello | basso | buono | cattivo; p6: B -> ascolta | guarda | mangia; }

es:S->ABC ->XYBXY -> il bello ascolta il bello

domanda: quante frasi genera la G22?

S

A BC

X Y X Y

il bello ascolta

il bello

833.o esercizio

G22 = ( V, T, S, P ), V = T u {A,B,C,X,Y }T = { bello, basso, buono, cattivo, ascolta, guarda, mangia, il }P = { p1: S-> A B C; p2: A-> X Y; p3: C -> X Y; p4: X-> il | un; p5: Y-> bello | basso | buono | cattivo; p6: B -> ascolta | guarda | mangia; }domanda: quante frasi genera la G22?

il bello ascolta il bello; un bello ascolta il bello; ...un cattivo mangia il cattivo; un cattivo mangia un cattivo;dalla produzione S->ABC ->XYBXY e dalle produzioni seguenti X->.., Y->.., per trasformare XYBXY in una frase ci sono 2 * 4 * 3 * 2 * 4 possibilita' ovvero 8 * 3 * 8 = 192 frasiun numero finito !

84

riassumendo:

GRAMMATICHE a struttura di frase:

G = ( Vocabolario, Terminali, S, Produzioni )

G genera un Linguaggio L, L = tutte le stringhe derivabili da S ("string. ben formate")

una frase s deriva (indirettamente) da S: S s

la catena di derivazione corrisp. all' albero sintattico e quindi da' la struttura della frase

traduzione: l’ analisi sintattica riconosce una s.b.f. e ricostruisce la catena -> la struttura -> l’ albero sintattico

grammatiche "opportune" consentono un riconoscimento veloce

*

854.o esercizio

quarto esercizio:

scrivere una grammatica che produce frasi del tipo:

a = ba = b + ca = a + b + a + cb = c + cc = c

(in generale: S = E (E espressione semplice) )

864.o esercizio

scrivere una grammatica che produce frasi del tipo:a = b a = b + c a = a + b + a + cb = c + c c = c

soluzione:

S->T | T + ST -> a | b | c

87

vediamo una

classificazione delle grammatiche

...

ma prima

vediamo due precisazioni

88 - tassonomia delle grammatiche -

1) rivediamo il concetto di produzione:

G = ( V, T, S, P )con P produzioni (regole di sostituzione che producono da stringhe date altre stringhe. Finora le regole di sostituzione o di produzione erano del tipo: A -> stringa, ma - in generale le produzioni sono regole di sostituzione del tipo:

a A b -> a s b dove:

A = simbolo sostituito = simb. non terminale, di N = V - T,

a,b,s sono stringhe di V* ,

a,b sono stringhe "costanti" per la produzione P, a, b fissano il contesto per A (vedremo subito)

G genera l’insieme L(G) = linguaggio generato da G

89grammatiche e contesto

esempi di produzioni dipendenti dal contesto:

1) b A c B -> b c B c B A produce cB se sta tra b e cB

2) x A y -> x b C y A produce bC se sta tra x e y

3) D A x -> D x A si puo’ togliere se sta tra D e x

4) A C -> C A si puo’ eliminare se e’ seguito da C,

5) zof D -> zof D si puo’ eliminare se preceduto da zof

ecc

90lunghezza delle stringhe nelle produzioni

1) d X d -> d d d d d / si puo’sost. ddd a X se X sta tra d e d

2) x X y -> x f f y / si puo’ sost. ff a X se X sta tra x e y;

3) D A qh -> D AA qh /puoi raddopp. A se sta tra D e qh

le produzioni 1,2,3 allungano la stringa di partenza, mentrele produzioni seguenti accorciano la stringa di partenza:

4) A C -> C / A si puo’ eliminare se e’ seguito da C,

5) D -> / D si puo’ eliminare in ogni situazione

5) i j M o -> i j o / M si puo’eliminare se sta tra ij e o...

91classificazione delle grammatiche secondo Chomsky

insiemi di grammatiche:

gramm. di tipo 0 o generali generano un insieme di linguaggi molto vasto, che contiene come sottoins. le gramm. di tipo 1 o monotone, che a loro volta contengono le gramm. di tipo 2 o libere da contesto, che contengono legrammatiche lineari ...ecc...vediamo una parte ...

0) Gramm.Gener.

1) Gramm.Monot.

2) Gramm.Libere da Contesto

3) Gr.Lineari...

92classificazione delle grammatiche secondo Chomsky

nota:

la classificazione di Chomsky definisce vari insiemi, che sono propriamente contenuti uno nell’altro, nel senso che ad es.

esistono linguaggi di tipo zero che non sono producibili da alcuna grammatica di tipo 1 o piu’ alto, ecc

vediamo meglio i vari tipi ...

93linguaggi di tipo 0

sono i piu’ generali:per tali linguaggi si possono generare ordinatamente tutte le frasi del linguaggio (sono enumerabili) ma

in generale non si puo’ rispondere alla domanda se * data G di tipo zero (V,T,S,P) e * data una stringa s di T* , la s e’ ben formata o no, cioe’ se essa e’ producibile da S cioe’ S s ovvero se appartiene al linguaggio L(G).

nota: se s appartiene a L(G) allora enumerando le frasi di L(G) prima o poi fabbrico anche la s, e ho la risposta SI,ma se s NON appartiene a L(G) allora non arriviamo mai alla risposta...[ per tale motivo i L(G) di tipo zero si dicono semidecidibili ]

*

94grammatiche di tipo 1: c’ e’ un vincolo:

le produzioni delle grammatiche di tipo uno sono monotone, cioe’ per qualunque produzione a -> bla lunghezza della stringa prodotta b e’ sempre maggiore o uguale alla lunghezza della a: |a| <= |b| ovvero a B c -> a s c con |B|=1, e con |s| >= 1 (s mai vuota);

i linguaggi di tipo 1 sono decidibili, nel senso: data s si puo’ sempre rispondere alla domanda se s e’ derivabile da S.

ma in pratica i ling.di tipo 1 sono ancora troppo generali, il procedim. di riconoscimento puo’essere MOLTO lungo ...

95linguaggi di tipo 2 o "liberi da contesto"le produzioni dei linguaggi di tipo 2 sono tutte del tipo:

A -> m con A simbolo non terminale (UNO!), e con m stringa su V* con |m| >= 1

di questo tipo sono le grammatiche dei linguaggi di programmazione, e in particolare le grammatiche esprimibili con i formalismi del tipo:

** grammatiche BNF (Backus Naur Form) ** EBNF (Extended Backus Naur Form) ** diagrammi sintattici ** e altri--------------------------- (*) Backus: partecipo' alla def. del Fortran 57 e, con Naur ed altri, alla definizione dell'Algol 60, da cui derivano C,Pascal, Ada, Java,

96es: una grammatica delle espressioni aritmeticheG23 = ( V,T,E,P ), con V = {E,T,F,A,M,V,C} + T, T = {a,b, 1,2,3,0, (, ) },P = { p1: E -> T | T A E; p2: T -> F | F M T; p3: F -> V | C | ( E ) [ricorda: | si legge oppure ...] p4: A -> + | -; p6: V -> a | b; p5: M -> * | /; p7: C -> 0 | 1 | 2 | 3;

primo di tre esempi di derivazione: costante 0 = un' espressione aritmetica molto semplice.

E ->1a T E produce T (E e' un termine)T ->2a F T produce F (un termine e' un fattore)F ->3b C F produce C (un fattore e' una cifra)C ->7a 0 C produce 0 (una cifra e' uno "0") ... quindi

0 e’ un’espress. aritmetica;

97es: una grammatica delle espressioni aritmetiche

G23 = ( V = {E,T,F,A,M,V,C} + T, T = {a,b, 1,2,3,0, (, ) },P = { p1: E -> T | T A E; p2: T -> F | F M T; p3: F -> V | C | ( E ); p4: A -> + | -; p6: V -> a | b; p5: M -> * | /; p7: C -> 0 | 1 | 2 | 3; )

secondo esempio di derivazione, l'espressione a+a:

E ->1b T A ET A E ->1a T A T T A T ->2a F A T ->2a F A F F A F ->4a F + F ->3a V + F V + F ->3a V + V ->6a a + Va + V ->6a a + a quindi a + a e’ un’espressione aritmetica, e' una frase del linguaggio L(G23); a+a ha significato e struttura come abituali ...

98es: una grammatica delle espressioni aritmetiche

G23 = ( V = {E,T,F,A,M,V,C} + T, T = {a,b, 1,2,3,0, (, ) },P = { p1: E -> T | T A E; p2: T -> F | F M T; p3: F -> V | C | ( E ); p4: A -> + | -; p6: V -> a | b; p5: M -> * | /; p7: C -> 0 | 1 | 2 | 3; )

terzo esempio di derivazione, stringa 3 * ( a + 2 ) – b:E ->1b T A E ->1a T A T T A T ->2b F M F A T ->2a F M F A F F M F A F ->4b F M F - F ->5a F * F - F F * F – F ->3c F * ( E ) - F ->1b F * ( T A E ) - F ->3 F * ( T A T ) - F ->2 F * ( T A T ) - F->2 F * ( F A T ) - F ->2 F * ( F A F ) - F ...->6 3 * ( a + 2 ) - b

quindi 3 * ( a + 2 ) – b e’ un’ espressione aritmetica, con significato e struttura come abituali ...

99grammatiche lineari

sono permesse solo le produzioni del tipo

A -> m

con A non terminale, econ m stringa con al piu’ un simbolo terminale;

le grammatiche dei linguaggi di programmazione sono in gran parte (*) del tipo "lineari destre"dove tutte le produzioni sono del tipo A -> n B(A,B non terminali, n stringa di terminali) oppure A -> n [tali grammatiche consentono una veloce analisi sintattica]------------------------------(*) attenz: alcune parti delle gramm. (Pascal, C, Java) non sono di questo tipo, sono in parte dipendenti dal contesto...

100vediamo la classica notazione BNF per grammatiche

BNF = Backus Naur Form (o Backus Normal Form)

la notazione BNF fu usata nel 1960 per definire la sintassi del linguaggio Algol 60, ed e' tuttora in uso.

Backus (USA) dell'IBM co-autore di Fortran 57 e Algol 60,Naur (Danese), co-autore Algol-60,

in BNF le produzioni sono scritte in modo un po' diverso,i simboli non terminali sono scritti tra parentesi spigolose, il simbolo -> (genera, produce) e' scritto con ::=

es. A -> x (A non terminale, x terminale) in BNF <A> ::= x (A produce x )

la BNF prevede le seguenti operazioni sulle stringhe:* concatenazione * alternativa * ricorsione

101BNF = Backus Naur Form (o Backus Normal Form)

I simboli non terminali sono scritti tra parentesi spigolose, il simbolo -> (genera, produce) e' scrito come ::=

es. A -> x (A non terminale, x terminale) in BNF <A> ::= x

la BNF prevede le seguenti operazioni sulle stringhe:* concatenazione * alternativa * ricorsione

es: produzione gia’ vista: E -> T | T A E ... in BNF:

< Espr > ::= <Term> | <Term > < OpAddiz> < Espr >

che si legge: un’Espressione produce un Termine oppure un Termine seguito da un operatore di Addizione seguito da un’ Espressione ...

102notazione BNF per grammatiche

si noti l’uso della ricorsione diretta nelle produzioni, usata di solito solo per specificare la ripetizione:

a+b+c+a+d

e’ prodotta da E -> T | T A E ovvero (in BNF) :

< Espr > ::= <Term> | <Term > < OpAddiz> < Espr >

E -> T A E -> T A T A E -> T A T A T A E -> T A T A T A T A E -> T A T A T A T A T -> T + T A T A T A T -> ... -> T + T + T + T + T -> ... -> a + b + T + T + T ..-> a+b+c+a+d

103

EBNF extended BNF di Niklaus Wirth (del 1977): - EBNF usa = invece di ::= e mette un punto alla fine di ogni produzione; oltre alle operazioni gia’ note

* concatenazione G = A B leggi:G produce A seguito da B * alternativa : X = A | B leggi: X produce A oppure B

sono aggiunte 3 coppie di simboli particolari (semplificano la notazione e il lavoro dell'analisi sintattica)

* ripetizione (zero o piu’ volte): Y = { A }. leggi: Y produce A ripetuto zero o piu’ volte

* opzionalita’: D = [ d ]. leggi: D produce d oppure nulla

* raggrup- X = ( a | b ) c. leggi: X produce ac oppure bc -pamento

notazione BNF per grammatiche

104EBNF e diagrammi sintattici

la notazione formale EBNF per le grammatiche lineari si puo' esprimere anche in forma grafica:

* concatenazione G = A B .

il diagramma sintattico rappresenta la sequenza degli stati di riconoscimento della struttura sintattica;

se G e' definito dalla concatenazione di A e di B, per riconoscere G devo riconoscere ("attraversare") prima A e poi B, da cui il diagramma sintattico sopra, che appunto rappresenta il percorso o la sequenza di riconoscimento ...

BAG

105EBNF e diagrammi sintattici * concatenazione G = A B .

* alternativa X = A | B .

* ripetizione (zero o +) Y = { A } .

* opzionalita’ D = [ d ] .

* raggruppamento X = ( a | b ) c .

A

Y

d

D

b

X ac

BX

A

BAG

106identificatoriin Pascal, C, ... un programma specifica azioni da eseguire su degli oggetti; generalmente azioni ed oggetti sono indicate riportando un "nome" ovvero un identificatore, che e' una categoria sintattica (simbolo non terminale), con la grammatica:

identificatore = lettera { lettera | cifra }

per cui sono legali a abcd FondamentiDiQualcosa Tasse1995 ImportoLordo31 X2Y3 a1234567890 abcdefghijklmnopqrstuvwxyz0987654321ZA volumeTotale3NON sono legali: 7corsi ieri+oggi+domani Dino.Furlan Toni/Bilos x2(lordo) mi/s-eria ma...

107identificatori

per quanto riguarda gli identificatori,

ATTENZIONE:

usare sempresempre identificatori "auto-esplicativi"

distanza_massima, totale_lordo VotoDiLaurea PesoNetto altezza posizioneX

... <<== vanno bene

... invece NON vanno bene :

x3, b, sx8b, fregnaccia, censura, provvisorio, oggi_piove, mio, cacca, bullshit_e_peggio,

108identificatore – sintassi EBNF

sintassi di un identificatore (nome) di una parte di un programma:

Identifier = Letter { Letter|Digit| "_" }.

Letter = "A" | "B" | "C" | "D" ... | "Z"

| "a" | "b" .. | "z" .

Digit = "0" | "1" | .... | "8" | "9" .

leggi: un identificatore e’ una stringa di lettere e cifre, il primo carattere deve essere una lettera, il resto possono essere lettere, cifre e il simbolo _

109identificatore – sintassi EBNF

Identifier = Letter{Letter|Digit| "_" }.

Letter = "A" | "B" | "C" | "D" ... | "Z"

| "a" | "b" .. | "z" .

Digit = "0" | "1" | .... | "8" | "9" .

identificatori a, a2, utsax7_stat47 OK: media_pesata, scarto_2m Dina_Carmela_Rossi_Coslovi_de_Cabba

identificatori 3, 2hmeljak, 4$, piu’o_meno, NON OK: abra-cadabra, somma*per, non.posso.crederci, Dina Carmela Rossi Coslovi de Cabba,

110EBNF definita in EBNF ancora un esempio: definizione della stessa EBNF scritta in EBNF: (Niklaus Wirth, CACM, 1977, vol.20, n.11) :

Syntax = { Production } . [leggi: una sintassi e’ data da zero o piu’ produzioni ]

Production = Identifier "=" Expression "." . [una produz e’ data da un identificatore seguito dal simbolo = seguito da un’espressione seguita da un punto]

Expression = Term { "|" Term } . [un’espress. e’ data da uno o piu’ termini separati dal simbolo "|" ]

Term = Factor { Factor } . [uno o piu’ fattori ]

Factor = Identifier | Literal | "(" Expression ")" | "[" Expression "]" | "{" Expression "}" .

111ripeto la definizione della EBNF scritta in EBNF:

Syntax = { Production } . Production = Identifier "=" Expression "." . Expression = Term { "|" Term } . Term = Factor { Factor } . Factor = Identifier | Literal | "(" Expression ")" | "[" Expression "]" | "{" Expression "}" .

da aggiungere: (nota l’uso del delimitatore di stringa " nella stringa stessa, es: stringhe di 5 carateri: "12345", "a""a""a", "1""345" )

Literal = """" Character { Character } """" .Identifier = Letter { Letter | Digit } .Letter = "A" | "B" | "C" | "D" ... | "Z" | "a" | "b" .. | "z" .Digit = "0" | "1" | "2" | "3" | "4" | .... | "8" | "9" .Special = " " | "." | "," | "!" | """" | "+" | ... ";" .Character = Letter | Digit | Special .

112Syntax = { Production } . ripeto la definizione della EBNF scritta in EBNF

Production = Identifier "=" Expression "." . Expression = Term { "|" Term } . Term = Factor { Factor } . Factor = Identifier | Literal | "(" Expression ")" | "[" Expression "]" | "{" Expression "}" .Literal = """" Character { Character } """" .Identifier = Letter { Letter | Digit } .Letter = "A" | "B" | "C" | "D" ... | "Z" | "a" | "b" .. | "z" .Digit = "0" | "1" | "2" | "3" | "4" | .... | "8" | "9" .Special = " " | "." | "," | "!" | """" | "+" | ... ";" .Character = Letter | Digit | Special .

es.: A = B | xA | C . A produce uno dei tre termini: B oppure xA oppure C; xA e’ un termine con due fattori x e A.

1131) esercizio sulle grammatiche

riscrivere

S -> S + T S -> T T -> T * F T -> F F -> a F -> b

in BNF, es: <S> ::= <T>

in EBNF, al posto di : S = T | S + T evito la ricorsione per indicare una ripetizione,utilizzando { } :

S = T { "+" T } .

1141) esercizio grammatiche,con la Backus Naur Form:

S -> S + T

S -> T

T -> T * F

T -> F

F -> a

F -> b

soluzione:

<S> ::= <T> | <S> + <T>

<T> ::= <F> | <T> * <F>

<F> ::= a | b

1151) esercizio grammatiche, Extended BackusNaur Form

soluzione:

S = T { "+" T } .

T = F { "*" F } .

F = "a" | "b" .

S -> S + T

S -> T

T -> T * F

T -> F

F -> a

F -> b

116 2) esercizio grammatiche

riscrivere in BNF e in EBNF:

G23 = ( V = {E,T,F,A,M,V,C}+T, T = {a,b, 1,2,3,0, (, ) },

P= { p1: E -> T | T A E; p2: T -> F | F M T; p3: F -> V | C | ( E ); p4: A -> + | -; p5: M -> * | /; p6: V -> a | b; p7: C -> 0 | 1 | 2 | 3; } ) segue soluzione

117 2) esercizio grammatiche riscrivere in BNF e in EBNF:

G23 = ( V = {E,T,F,A,M,V,C}+T, T = {a,b, 1,2,3,0, (, ) },

P= { p1: E -> T | T A E; p2: T -> F | F M T; p3: F -> V | C | ( E ); p4: A -> + | -; p5: M -> * | /; p6: V -> a | b; p7: C -> 0 | 1 | 2 | 3; } )

BNFBackus Naur Form:p1: <E> ::= <T> | <T><A><E>p2: <T> ::= <F> | <F><M><T>p3: <F> ::= <V> | <C> |(<E>)p4: <A> ::= + | -p5: <M> ::= * | /p6: <V> ::= a | bp7: <C> ::= 0 | 1 | 2 | 3

118 2) esercizio grammatiche riscrivere in BNF e in EBNF:

G23 = ( V = {E,T,F,A,M,V,C}+T, T = {a,b, 1,2,3,0, (, ) },

P= { p1: E -> T | T A E; p2: T -> F | F M T; p3: F -> V | C | ( E ); p4: A -> + | -; p5: M -> * | /; p6: V -> a | b; p7: C -> 0 | 1 | 2 | 3; } )

EBNFExtended BackusNaur Formp1: E = T { A E }.p2: T = F { M T }.p3: F = V | C | "(" E ")" .p4: A = "+" | "-".p5: M = "*" | "/".p6: V = "a" | "b".p7: C = "0"|"1"|"2"|"3".

119e con i diagrammi sintattici ? - ricorda:

* raggruppamento: X -> ( a | b ) c

A

Y

d

D

b

X ac

BX

A

BAG * concatenazione G -> A B

* alternativa : X -> A | B

* ripetizione(0,1,2,..): Y -> { A }

* opzionalita’: D -> [ d ]

120esercizio diagrammi sintattici

esercizio:

S -> S + T S -> T T -> T * F T -> F F -> a F -> b riscrivere questagrammatica con idiagrammi sintattici...

conviene ricordarela versione EBNF:

S = T { "+" T } .

T = F { "*" F } .

F = "a" | "b" .

121esercizio diagrammi sintattici

esercizio:

S -> S + T S -> T T -> T * F T -> F F -> a F -> b riscrivere lagrammatica con i diagrammi sintattici...

dalla versione EBNF, che ripetiamo:

S = T { "+" T } . T = F { "*" F } .

F = "a" | "b" .

si ottiene :S

+ TT

"a"

"b"

F

T

* FF

122grammatica di una costante di tipo intero / Pascal

DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .

UNSIGNED_INTEGER = DIGIT {DIGIT} .

da cui: ... sono legali costanti intere senza segno:

1, 33, 1978934567889000000, 0, 1995, 210 ecc

non sono legali costanti intere senza segno:

-1, 3,14, 3.3, X22, 22H, $1AFF77, 99.99, #4, 31 10 1995,

(perche’ ... )

123

il C++ prevede molti tipi di costanti di tipo numero intero:

int 1 -234 31000long int 95000L -2Lunsigned int 50000U 77Uunsigned long 123UL 4000000000UL

float 6.6 31.4E-1 double 123456789.12345E-300long double 2.2L

esadecimale 0xFF (un byte)ottale 012 (un byte, 10 in ottale)

esercizio: sintassi costante float ?

124virgola mobile Pascal, il C++ e' piu' permissivo ...

DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .

UNSIGNED_INTEGER = DIGIT {DIGIT} .

SIGN = "+" | "-" .

SCALEFACTOR = "E" [ SIGN ] DIGIT { DIGIT } .

UNSIGNED_REAL = DIGIT {DIGIT} "." [ {DIGIT} ] [ SCALEFACTOR] .

da cui ad es. le costanti seguenti sono legali: 3.1415927, 123E0, 1.0, 2., 1.995E+003, 77.88E-37, 5.5E+37 mentre le costanti seguenti no: . 5 3,14 123E 1 1.995+003 77.88.00 5.5E-3.5

(perche’ ?)

125virgola mobile in C

in "C":

f_const = i_part "." f_part e_part | i_part "." f_part | i_part "." | "." f_part | i_part e_part |

quindi: 123.456E23 oppure 123.456 oppure 12. oppure .2 oppure 77E66

sono quindi legali anche costanti del tipo: 12E12 oppure 3.meglio scrivere pero’: 12.0E+12 3.0

126

esercizio: (scritto di FI2 22.6.2004 )scrivere una grammatica che produce frasi del tipo: Oggi alle ore 13 telefona Mario. Alle 17 chiama Heinz. Oggi scrive Niki. Domani alle 23 canta Natasha. Oggi dorme Benny. Alle 12 mangia. Oggi telefona Fata. Scrive Momoko. Domani chiama.

127grammatica che produce frasi del tipo: Oggi alle ore 13 telefona Mario. Alle 17 chiama Heinz. Oggi scrive Niki. Domani alle 23 canta Natasha. Oggi dorme Benny. Alle 12 mangia. Oggi telefona Fata. Scrive Momoko. Domani chiama. Quando dorme Diego.

e' facilmente riconoscibile la struttura:

GIORNO TEMPO VERBO NOME

dove solo VERBO appare sempre, quindi:

S = [ GIORNO ] [TEMPO] VERBO [NOME] .con GIORNO = "Oggi" | "Domani" TEMPO = "alle" [ "ore" ] N . N = "12" | "13" | "17" | "23" . NOME = "Mario" | "Heinz" | "Niki" | "Natasha" | "Benny" | "Fata" | "Momoko" | "Diego" .

128

Test FI2 1/4/2004Scrivere una grammatica (produzioni) che produce frasi: for( k=1; k<=77; k++ ) Istruzione; for( k=1, j=2; ! finito; k++, j--) Istruzione; for( ;; n-- ) Istruzione; for( ;; ) Istruzione; note: #) usare i simboli non terminali tipo: EspressioneBooleana, Espressione, Variabile, Istruzione (che si assumono definiti altrove!) e i terminali "for" "=" ";" "," "!" #) specificare in dettaglio le 3 parti di controllo del for che stanno tra parentesi ( ) dopo il simbolo "for".#) dare almeno un esempio di derivazione di un for non vuoto.

129

for( k=1; k<=77; k++ ) Istruzione;for( k=1, j=2; ! finito; k++, j--) Istruzione;for( ;; n-- ) Istruzione;for( ;; ) Istruzione; (usare i simboli non terminali tipo: EspressioneBooleana, Espressione, Variabile, oltre al simbolo non terminale Istruzione)

soluzione:una grammatica (semplificata) in EBNF per la frase for:

FOR = "for" "(" INI ";" TEST ";" INCR ")" ISTRUZ ";" (il for e' fatto da 4 parti, tre stanno tra parentesi separate da ";" ... )INI = [ ASSEGNA { "," ASSEGNA } ] . (zero o piu' istruz. di assegnaz)TEST = [ EspressioneBooleana ] . (puo'essere omesso)INCR = [ INC1 { "," INC1 } ] . (puo'essere omesso)dove:ASSEGNA = Variab "=" Espressione . (frase di assegnazione)INC1 = INCDEC Variab | Variab INCDEC | ASSEGNA .INCDEC = "++" | "--" .

130

esercizio:

definire (almeno in parte) la sintassi del main program,

(header, instr_sequence, block, ...)

131

fine introduzione alle grammatiche

1 LINGUAGGI A STRUTTURA DI FRASE a cui appartengono i linguaggi di programmazione.

Documents

Transcript of 1 LINGUAGGI A STRUTTURA DI FRASE a cui appartengono i linguaggi di programmazione.