Che materia stai cercando?

Appunti di Linguaggi e Modelli Computazionali

Conoscenze e abilità da conseguire
Introduzione al rapporto fra linguaggi e progettazione a livello algoritmico e sistemistico. Metodi per la definizione della sintassi e della semantica dei linguaggi di programmazione e di specifica e analisi dei relativi modelli computazionali. Tecniche di riconoscimento e valutazione.

Programma/Contenuti
Fornire una descrizione ragionata... Vedi di più

Esame di Linguaggi e Modelli Computazionali M docente Prof. E. Denti

Anteprima

ESTRATTO DOCUMENTO

2.9.1.1 Dalla grammatica all’espressione regolare

Per passare dalla grammatica alle espressioni regolari, si interpretano le produzioni come equazioni sintat-

tiche, dove i simboli terminali sono i termini noti, e i simboli non terminali sono le incognite. Successi-

vamente, si prosegue la risoluzione con le normali regole delle equazioni algebriche. Prendendo ad esempio

una grammatica regolare destra, si procede come:

→ |α |α | · · · |α · · ·

• Riscrivere tutte le produzioni del tipo come .

X α X = α + α + α + + α

1 2 3 n 1 2 3 n

• Poiché la grammatica è regolare a destra, tutte le produzioni sono nella forma . Si raccolgono

X uX

k

quindi a destra tutti i simboli non terminali, ottenendo una forma del tipo:

· · · ∪ · · · ∪ · · ·

X = (u + u + )X (z + z + )X ,

1 2 1 1 2 n

|V |,

Si ottiene quindi un sistema di equazioni in incognite, con ossia uguale al numero

M M M = N

di simboli non terminali.

• Eliminare dalle equazioni le ricorsioni dirette, data l’equivalenza:

∪ ⇐⇒

X = uX δ X = (u) δ.

• Risolvere il sistema rispetto ad per eliminazioni successive (metodo di Gauss), eventualmente

S

riapplicando i passi precedenti per raffinamenti successivi.

La soluzione del sistema è il linguaggio regolare cercato. Nel caso di grammatiche regolari sinistre si

procede in maniera analoga, con alcuni passaggi svolti in maniera speculare.

Occorre notare che a seconda dell’ordine in cui le operazioni vengono svolte si possono ottenere espres-

sioni regolari diverse che risultano però equivalenti ed è possibile passare da una all’altra manipolandole

opportunamente secondo le regole dell’algebra. Questo metodo risulta alquanto complesso, per cui è più

conveniente operare sulle corrispondenti macchine in grado di riconoscere il linguaggio che descrivono, dato

che esistono degli algoritmi pratici per fare ciò.

2.9.1.2 Dall’espressione regolare alla grammatica

Questo metodo risulta più semplice, ed è basato sulla sostituzione, in ordine di priorità, dei simboli:

• Sequenza: sono simboli accostati nella grammatica.

|

• simbolo di alternativa nella grammatica.

+:

∗:

• ricorsione nella grammatica.

Esempio 2.7 Dato il linguaggio generato dall’espressione regolare:

{a

L = b},

si sostituisce ad una produzione che diventerà ricorsiva. Si nota quindi che tutte le frasi di questa

a A,

grammatica terminano con e che possono iniziare o meno con Si scrive quindi:

b, a.

S Ab|b,

dove può essere definita sia come grammatica regolare destra, sia come sinistra:

A → →

oppure

A aA A Aa.

16

Capitolo 3

Riconoscitori a stati finiti

Un ultimo modo di descrivere un linguaggio è quello di rappresentarlo attraverso l’automa ri-

conoscitore, e tale procedimento risulta equivalente a rappresentarlo attraverso una grammatica.

Interpretando un automa secondo una logica top-down, cioè dallo scopo allo stato finale, si ge-

nera una grammatica regolare lineare a destra. Viceversa, interpretando un automa secondo la

derivazione bottom-up, cioè partendo dalla frase in input e riducendosi allo scopo, si ottiene una

grammatica regolare lineare sinistra.

Un riconoscitore a stati finiti è una specializzazione dell’automa a stati finiti. Esso offre come uscita un

booleano per definire se la sequenza in ingresso sia una frase che fa parte o meno del linguaggio che la

⟨I,

macchina riconosce. Un automa a stati finiti è definito dalla quintupla Un riconoscitore

O, S, mf n, sf n⟩.

a stati finiti è sempre definito da una quintupla, ma cambiano gli elementi che la compongono (poiché,

appunto, si specializza la macchina): ∗

⟨A, ⟩

S, S , F, sf n :

0

• rappresenta l’insieme dei simboli dell’alfabeto;

A

• rappresenta l’insieme degli stati della macchina;

S ∈

• rappresenta lo stato iniziale della macchina;

S S

0

• rappresenta l’insieme degli stati finali;

F ∗ ∗

• rappresenta la funzione di stato estesa, la quale mette in relazione e lo stato attuale della

sf n A

macchina con lo stato futuro, Si usa la chiusura di e non solo per comodità, in quanto questa

A A

notazione permette di processare più caratteri in una volta sola.

Per ogni riconoscitore a stati finiti si ha che la stringa vuota non incide in alcun modo sull’automa. Si

ε

ha infatti la regola Si fornisce inoltre la definizione di funzione di stato in maniera ricorsiva:

sf n (ε, s) = s. ∗ ∗

data la stringa in input alla macchina, questa viene processata come

xa sf n (xa, s) = sf n(a, sf n (x, s)),

∈ ∈

con quindi è una sequenza di simboli dell’alfabeto mentre è il singolo simbolo processato.

x A , a A, x a

Si dice frase accettata una frase che, presa in ingresso, porta il riconoscitore dallo stato iniziale a uno

S 0

stato finale . Poiché in un linguaggio è normale che si ottengano più frasi errate che corrette, gli stati

f F

di errori si omettono e, se un carattere non è presente nello stato corrente, si sottintende che non possa

essere dato e che porti quindi allo stato d’errore.

Si dice che un linguaggio è infinito se la rappresentazione grafica del suo automa riconoscitore

L(R)

presenta cicli. Se ciò non è verificato è invece detto finito. è detto se, e solo se, il

Teorema 3.1 – Linguaggio non vuoto Un linguaggio non vuoto

L(R)

riconoscitore accetta una stringa di lunghezza minore del numero di stati dell’automa.

R x L N

x

Questo permette di stabilire se un automa ha almeno uno stato finale poiché, avendo una lunghezza

massima e un alfabeto finito, il numero possibile di stringhe da valutare è finito; provandole tutte si ha quindi

la garanzia che, se c’è uno stato finale, questo venga raggiunto. Questo teorema è utile per progettare test

secondo il modello black box (in cui non si conosce come è costruito l’automa). Il teorema si può applicare

anche a frasi più lunghe di , eliminando le parti della frase che ripassano per lo stesso stato, ottenendo

N

quindi frasi di lunghezza inferiore di .

N 17

Teorema 3.2 – Linguaggio infinito Un linguaggio è detto infinito se, e solo se, il riconoscitore

L(R)

accetta una stringa di lunghezza , con numero di stati dell’automa.

R x N L < 2N N

x

In maniera analoga al teorema precedente, se è possibile passare due volte per uno stesso stato è allora

possibile passarvi più e più volte, pertanto esiste una stessa stringa che può essere ripetuta all’infinito al-

l’interno di una frase.

Sulla base dei due teoremi appena proposti, decidere se un linguaggio regolare è vuoto o infinito diventa

un problema risolubile. Come si vedrà anche per i linguaggi di tipo 2 diventeranno risolubili questi due

problemi, mentre rimarranno irresolubili per i linguaggi di tipo 0 e 1.

Il modo più pratico di ottenere un grafo sarebbe quello di avere uno stato iniziale dal quale tutte le frecce

partono e uno stato finale dove tutte le frecce arrivano: in pratica, solo frecce uscenti dallo stato iniziale

e solo frecce entranti dallo stato finale. Se ora si sostituisce alla parola accettare la parola generare si è

appena creato un automa generatore di frasi di linguaggio.

Si definisce quindi il seguente mapping:

• agli stati corrispondono i simboli non terminali;

• alle transizioni corrispondono le produzioni;

• allo scopo corrisponde uno stato particolare.

A seconda del punto di vista, da uno stesso grafo è possibile ottenere una grammatica regolare a destra

o a sinistra. Se si legge in uno stato da dove arrivano le frecce si avrà una grammatica regolare sinistra, se

invece si legge nel verso delle frecce, ossia dove vanno, si otterrà una grammatica regolare destra. Ma come

si arriva a tali grammatiche? La soluzione più intuitiva sarebbe quella di porsi nelle vesti di un osservatore

del grafo e ricavarne la grammatica regolare sinistra e quella destra percorrendolo, ma esiste un mapping

molto più schematico fra grammatiche e riconoscitori.

3.1 Mapping tra grammatiche e riconoscitori

Per effettuare il mapping di una grammatica in un riconoscitore si possono adottare due tipi di approcci: se

la grammatica è regolare a destra si utilizzerà un approccio top-down, mentre se una grammatica è rego-

lare sinistra si utilizzerà un approccio bottom-up. Allo stesso modo, se si interpreta un riconoscitore con

approccio top-down si otterrà una grammatica regolare destra, se invece lo si interpreta con un approccio

bottom-up si otterrà una grammatica regolare sinistra.

Data una grammatica regolare a destra, un riconoscitore di tale grammatica:

• ha tanti stati quanti simboli non terminali;

• ha come stato iniziale lo scopo S;

• per ogni regola del tipo , l’automa dallo stato con ingresso si porta nello stato ;

X xY X x Y

• per ogni regola del tipo l’automa dallo stato con ingresso si porta nello stato finale .

X x, X x F

La derivazione top-down parte dallo scopo della grammatica e tenta di coprire la frase data tramite

produzioni successive.

Data una grammatica regolare a sinistra, il riconoscitore:

• ha tanti stati quanti simboli non terminali;

• ha come stato finale lo scopo S;

• per ogni regola del tipo riduce lo stato allo stato con ingresso ossia si porta allo

X Y x, Y X x,

stato dallo stato con ingresso

X Y x;

• per ogni regola del tipo l’automa con ingresso riduce lo stato iniziale allo stato ossia

X x, x I X,

si porta allo stato dallo stato iniziale con ingresso

X x.

18

Per convenzione, lo stato iniziale si omette nell’approccio bottom-up, mentre lo stato finale si omette

in quello top-down. Ma se un grafo non ha un solo stato finale? Lo sviluppo top-down non ne risente,

ma lo sviluppo bottom-up non sa quale dei due stati finali vada fissato come scopo. Un primo approccio

potrebbe essere quello di generare due grammatiche, una per ogni stato finale, ma la loro unione, ottenuta

sovrapponendo i due stati scopo dei grafi ottenuti, non sarebbe deterministica. Questa situazione implica

che l’unione di due linguaggi deterministici non sia sempre deterministica. Per renderla deterministica si può

|S | · · · |S

prendere ogni stato finale ed identificarlo come sotto-scopo , quindi porre come scopo .

S S = S 0 1

k k

c, d

A

Esempio 3.1 – Stati finali multipli Dato il grafo in Figura 3.1, si nota che si c

presentano come stati finali e Per un approccio bottom-up si inizia da uno dei

A B. I

due e si ricava la produzione ipotizzandola come scopo, così da ottenere: d B d

≡ → ≡ →

S A Ac|Ad|c, S B Bd|d,

1 2 Figura 3.1: Grafo de-

gli stati relativo all’E-

→ |S

successivamente si uniscono i due scopi , lasciando e a destra e

S S A B

1 2 3.1.

sempio

aggiungendo le loro produzioni:  →

 S Ac|Ad|Bd|d|c

A Ac|Ad|c ,

 →

B Bd|d

in questo modo, si evita di riconoscere frasi errate (mentre se si fossero uniti gli stati e sarebbero state

A B,

accettate frasi come dc). b b

S F I S

Esempio 3.2 Dato il grafo in Figura 3.2a che rispecchia la

grammatica definita come: a a

a a

b b

→ → B B

S aB|b, B bS|a; (a) (b)

Grafo degli Grafo rino-

come evitare che lo stato sia stato di transizione per

S B? stati. minato.

Si rinominano, per comodità, gli stati come in Figura 3.2b e si

analizzano secondo l’approccio bottom-up come: b

I S b

← ← ← ← a

Ib S Ia B, Ba S, Bb I; a b

B A

si nota come abbia archi in ingresso: Per evitare quindi che

I Bb I. a

sia stato di transizione, si aggiunge uno stato che dà luogo a due

I A (c) Grafo modificato.

produzioni in quanto, usando un approccio bottom-up, lo stato iniziale

può essere ignorato o no. In una produzione, diventa in quanto usato Figura 3.2: Grafi relativi all’E-

I A sempio 3.2.

come stato di transito; nell’altra, viene rimosso in quanto stato iniziale

I

di un approccio bottom-up. Partendo dal grafo in Figura 3.2c è possibile perciò riscrivere la grammatica

bottom-up come: → → →

S Ab|b|Ba, B Aa|a, A Bb,

in quanto le alternative sono generate dalla doppia valenza del vecchio stato che ora non è più di transi-

I,

zione. Si è quindi dimostrato che una grammatica può sempre essere riscritta, cambiando approccio, senza

che gli stati iniziali o finali siano stati di transizione, aggiungendo uno stato ausiliario che ne faccia le veci.

3.1.1 Considerazioni

Dato che il mapping tratta in modo particolare gli stati iniziali e finali, rispettivamente nell’approccio

bottom-up e top-down, è possibile evitare le Si potrebbe effettuare il mapping anche in modo

ε-rules. 2.1.

tradizionale accettando la presenza delle per poi eliminarle come visto nell’Esempio

ε-rules, 19

3.2 Implementazione

La realizzazione di un automa a stati finiti è facilmente implementabile tramite un linguag-

deterministico

gio imperativo, ma le scelte che si fanno per programmarlo possono influenzarne fortemente l’estendibilità,

la modularità e la leggibilità:

• In un primo caso banale, si potrebbe pensare al riconoscitore come ad una sequenza di Questa

if.

soluzione risulta però estremamente cablata, illeggibile e non estendibile.

• Un’ipotesi alternativa, che migliora di poco la leggibilità, è lo Essa presenta tuttavia gli stessi

switch.

svantaggi.

• Un’ipotesi più interessante è invece quella di realizzare un ciclo che prelevi i dati che gli servono

while

da una tabella esterna. Cambiando la tabella si ottiene un diverso riconoscitore, garantendo così un

automa non più cablato nel codice ed estendibile a piacere.

3.3 Automi non deterministici

Un automa è non deterministico se, per ogni frase di esiste almeno una computazione che porta

L(G),

l’automa dallo stato iniziale allo stato finale . Un automa deterministico ha invece esattamente una

S F

e una sola computazione per arrivare a riconoscere una frase. Si può affermare con un teorema che un

linguaggio di tipo 3 non deterministico, se modificato opportunamente, diventa deterministico. Realizzare un

riconoscitore non deterministico è semplice se si utilizza un linguaggio dichiarativo come Prolog, che permette

di scrivere una riga di codice per ogni produzione. Sarà poi il compilatore sottostante ad occuparsi di tentare

ogni possibile riconoscimento, operando anche con degli undo in caso abbia scelto una strada sbagliata.

Costruendo l’automa con un linguaggio imperativo, essendo questo capace solo di eseguire comandi e non

avendo il concetto di undo, si ricostruirebbe il livello di non determinismo di Prolog.

3.3.1 Da automi non deterministici a deterministici

Per eliminare il non determinismo, seguendo l’esem- a b

pio in Tabella 3.1, si cominciano a rinominare gli [S] [B] [E]

a

stati in logico fra loro, sostituendoli con il nome b

OR [B] [B, F ] [S]

di un nuovo stato, come nel caso di che con input

B S B E [B, F] [B, F, E] [S, E]

può andare nello stato o . Si introduce quin-

a B F B B/F S [S, E] [B, E] [E]

di un nuovo stato che significa oppure .

[B, F ], B F F E E [B, E] [B, F, E] [S, E]

Questo nuovo stato, con ingresso può andare in

a E E E [B, F, E] [B, F, E] [S, E]

oppure secondo quanto ottenuto mettendo

B, F E (a) Originale. [E] [E] [E]

in OR tutti gli stati successivi di e con ingresso

B F

mentre con ingresso può andare in oppure

a, b S E. (b) Tabella deterministica.

Per ogni nuova combinazione di stati si proce- Tabella 3.1: Esempio di eliminazione del non determini-

de quindi ad aggiungere un nuovo stato combinato smo.

“unendo” le righe della tabella originale o di quella

nuova che si sta generando. A questo punto è possibile dare loro un nome appropriato, ottenendo una tabella

deterministica. Il concetto che permette questa conversione si basa sull’aggiunta di nuovi stati all’automa.

Questi nuovi stati rappresentano dove si è arrivati a processare l’ingresso. Utilizzando questo approccio

s’immagazzinano dati finché non si ottiene un unico risultato. Aggiungendo stati si è quindi nascosto il

problema della decisione, che sarebbe risultato non deterministico, finché i dati in ingresso hanno permesso

di renderlo deterministico. La tabella così ottenuta solitamente non risulta ottimale in quanto modella un

automa non minimo; si può quindi procedere a ricavare l’automa minimo corrispondente.

Una volta tradotto l’automa da non deterministico a deterministico esso si può implementare sia con

linguaggi imperativi sia con linguaggi dichiarativi. Nel caso in cui un automa sia deterministico anche Prolog

può evitare di tentare più soluzioni con l’uso del predicato cut che indica al motore sottostante di non

!,

20

esaminare alternative (risparmiando così molte operazioni inutili). Nei linguaggi dichiarativi come Prolog

è possibile, con alcune avvertenze, usare lo stesso programma di riconoscimento anche come generatore di

linguaggi.

Un punto importante relativo ai linguaggi dichiarativi è il modo in cui essi esplorano i sotto-alberi. Prolog

si muove in profondità di ogni ramo e, se questo non termina mai, continua a generare frasi valide solo

relative al primo ramo. Più efficace è invece la navigazione dei sotto-alberi per ampiezza, che consente di

operare su rami diversi parallelamente a discapito della profondità.

Teorema 3.3 L’insieme dei linguaggi riconosciuti da un automa a stati finiti coincide con l’insieme dei

linguaggi regolari, ossia quelli descritti da espressioni regolari.

Questo teorema pone un paragone su due metodi descrittivi appartenenti a due differenti categorie:

• Gli automi a stati finiti sono un metodo di descrizione operazionale, in quanto evidenziano i passi

computazionali da compiere per riconoscere le frasi.

• Le espressioni regolari sono un metodo di descrizione denotazionale, in cui un’entità è specificata

tramite operatori di tipo matematico.

In questo capitolo si sono messe a confronto le grammatiche regolari con gli automi a stati finiti e

con le espressioni regolari. Si può passare da una forma all’altra in maniera univoca, al più con qualche

accorgimento. Ciò fa capire che questi tre metodi descrivono la stessa realtà sotto diversi punti di vista, per

3.3.

i quali è possibile passare attraverso le transizioni illustrate in Figura

eq. sintattiche Espressioni

Grammatica regolari

S aS|b ∗

{a

L = b}

mapping

mapping mapping

grammatiche-RSF regex-RSF

Automa

• Minimizzabile

• Controllo equivalenza

• Eseguibile

Figura 3.3: Diverse rappresentazioni dei linguaggi regolari.

21

Capitolo 4

Riconoscitori PDA

Il limite intrinseco degli automi a stati finiti è legato alla struttura a stati, incapace di memorizzare

stringhe di lunghezza non nota a priori. Questo limite viene facilmente superato facendo uso di

uno stack. I linguaggi di tipo 2, possono richiedere vincoli sulla struttura della frase in input

(come ad esempio il bilanciamento delle parentesi) che in un automa a stati finiti richiederebbe

un numero infinito di stati, mentre con il semplice uso di uno stack, saranno sufficienti pochi

stati. Pur non avendo le potenzialità di una macchina di Turing, questa classe di automi è ideale

per riconoscere linguaggi di tipo 2.

Un riconoscitore a stati finiti non può riconoscere linguaggi di tipo 2 perché possiede un limite intrinseco

strutturale legato alla sua limitata capacità di memorizzazione. Per poter riconoscere un linguaggio di tipo

2 occorre infatti un automa che fa uso di memoria, la cui quantità non sia definibile a priori. Si ricorre

perciò all’uso di riconoscitori a stack o Push Down Automaton PDA.

Un PDA è una sestupla di valori: ⟨A, ⟩

S, S , sf n, Z, Z

0 0

dove:

• è l’alfabeto dei simboli utilizzati nel linguaggio;

A

• è l’insieme degli stati dell’automa;

S ∈

• è lo stato iniziale dell’automa;

S S

0 ∗

∪ × × → ×

• è la funzione di stato definita come con sottoinsieme finito di ;

sf n (A ε) S Z Q, Q S Z

• è l’alfabeto di simboli interni allo stack, che non per forza devono essere uguali a quelli del linguaggio;

Z ∈

• simbolo iniziale dello stack.

Z Z

0

Come in un RSF, anche nel PDA una stringa è ritenuta valida se porta l’automa dallo stato iniziale a

uno stato finale. Nel PDA vale un ulteriore criterio, chiamato criterio dello stack vuoto, poiché l’automa

reputerà valida una qualsiasi stringa che, processata dall’automa, lascerà lo stack vuoto. Lo stack è una

memoria First In First Out FIFO, cioè da cui si può inserire o estrarre un elemento per volta e l’elemento

estratto è sempre l’ultimo ad essere stato inserito.

Esempio 4.1 Si consideri il linguaggio generato da

{0, {S → {wordcword },

R

A = 1, c}, P = 0S0|1S1|c}, L =

{Zero, {Q },

Z = Uno, Centro}, S = , Q

1 2

S = Q , Z = Centro

0 1 0

R

dove indica il ribaltamento di

word word.

Questa grammatica è di tipo 2. Se la si volesse generare con un RSF, si dovrebbe conoscere a priori la

lunghezza della stringa in ingresso per definire il numero di stati. Ciò non accade con un PDA, perché si

può far uso dello stack per memorizzare la stringa. Di norma, infatti, gli stati di un PDA sono molto pochi

e, spesso, solo due: uno di accumulo e uno di svuotamento.

22

Si definisce quindi il PDA come in Tabella 4.1a e si nota, intuitivamente, che è lo stato di accumulo

Q 1

mentre è lo stato di svuotamento. Quando si trova l’elemento centrale si commuta da a .

Q c Q Q ε,

2 1 2

che corrisponde al simbolo iniziale , è stato definito Centro per non dover definire un ulteriore simbolo in

Z 0

In Tabella 4.1b è riportato l’esempio della stringa valida con i passaggi che l’automa compie per

Z. 01c10

verificarla. ∗

∪ ×

A ε S Z S Z

×

0 Centro Centro, Zero

Q Q

1 1 × Stato

1 Centro Centro, Uno

Q Q

1 1 Input Stack Stato Pop Push

× futuro

c Centro Centro

Q Q

1 2 ×

0 Zero Zero, Zero

Q Q

1 1 0 Centro Centro Centro, Zero

Q Q

1 1

×

1 Zero Zero, Uno

Q Q

1 1 1 Centro, Zero Zero Zero, Uno

Q Q

1 1

×

c Zero Zero

Q Q

1 2 c Centro, Zero, Uno Uno Uno

Q Q

1 2

×

0 Uno Uno, Zero

Q Q

1 1 1 Centro, Zero, Uno Uno

Q Q ε

2 2

×

1 Uno Uno, Uno

Q Q

1 1 0 Centro, Zero Zero

Q Q ε

2 2

×

c Uno Uno

Q Q

1 2 Centro Centro

ε Q Q ε

2 2

×

0 Zero

Q Q ε

2 2 ×

1 Uno (b)

Q Q ε Step dell’automa con ingresso 01c10.

2 2 ×

Centro

ε Q Q ε

2 2

(a) Funzione di stato. Tabella 4.1: PDA dell’Esempio 4.1.

4.1 PDA non deterministici

Come le macchine a stati finiti, anche i PDA possono essere non deterministici. In tal caso la funzione sf n

∗ ∗

×

produce elementi di , con definito come sottoinsieme di . Il non determinismo dell’automa può

Q Q S Z

emergere sotto due aspetti:

• L’automa, in un certo stato , con simbolo interno in cima allo stack e ingresso può portarsi in

q z x,

0

un qualsiasi stato degli stati futuri previsti:

{(q

sf n(q , x, z) = , z ), (q , z ), . . . , (q , z )}.

0 1 1 2 2 N N

• L’automa, in un certo stato , con simbolo interno in cima allo stack e ingresso può leggere

q z x,

0

o non leggere il simbolo in ingresso, poiché sono state definite entrambe le regole e

sf n(q , x, z)

i

sf n(q , ε, z).

i

Teorema 4.1 La classe dei linguaggi riconosciuti da un PDA non deterministico coincide con la classe

dei linguaggi context-free, pertanto qualunque linguaggio context-free può sempre essere riconosciuto da un

opportuno PDA non deterministico. Possono però emergere vari problemi:

• La complessità di calcolo del PDA non deterministico può essere esponenziale con un algoritmo non

ottimizzato.

• I migliori algoritmi hanno complessità dell’ordine del cubo della lunghezza della stringa da riconoscere,

che si riduce al quadrato se la grammatica non è ambigua. Sarebbe però preferibile una complessità

lineare.

Sarebbe quindi utile fare a meno dei PDA non deterministici, ma ci si domanda se ciò sia possibile.

La risposta è, in generale, negativa, poiché esistono linguaggi context-free riconoscibili solo da PDA non

deterministici; con opportuni vincoli sulle grammatica però si possono ottenere PDA solo deterministici. Le

proprietà dei linguaggi di tipo 2 deterministici sono:

• L’unione, l’intersezione e il concatenamento di due linguaggi deterministici non sono necessa-

riamente deterministici. 23

• Il complemento di un linguaggio deterministico è deterministico, poiché basta invertire i risultati

dello stesso linguaggio.

Se si pongono in relazione i linguaggi di tipo 2 deterministici e quelli regolari si ottiene che:

• Se è un linguaggio context-free deterministico e un linguaggio regolare, allora il linguaggio

L R

quoziente ossia l’insieme delle stringhe di private di un suffisso regolare, è deterministico.

L/R, L ·

• Se è un linguaggio context-free deterministico e un linguaggio regolare, il concatenamento

L R L R,

ossia l’insieme delle stringhe di con un suffisso regolare, è deterministico.

L

Per i PDA deterministici, inoltre:

• Il criterio dello stack vuoto risulta meno potente del criterio degli stati finali, cioè il criterio degli

stati finali permette di riconoscere più linguaggi.

• Una limitazione sul numero di stati interni o sul numero di configurazioni finali riduce l’insieme dei lin-

guaggi riconoscibili, ossia un PDA deterministico richiede un numero maggiore di stati per riconoscere

uno stesso linguaggio (in maniera simile a ciò che accade in § 3.3.1).

• L’assenza di riduce l’insieme dei linguaggi riconoscibili.

ε-rules

4.2 PDA deterministici

Per realizzare un PDA deterministico, per quanto si possa seguire la definizione di PDA deterministico,

risulta più pratico manipolare uno stack con la stessa logica di un PDA, considerando che:

• La presenza dello stack è la vera differenza rispetto al RSF.

• Una macchina virtuale che abbia uno stack può essere fatta funzionare come un PDA, pilotandola

“opportunamente”.

• Si potrebbe pilotare uno stack in modo esplicito “a mano”, oppure…

• Sfruttare eventuali costrutti dei linguaggi di programmazione che lo facciano per noi, come le chiamate

ricorsive di funzioni e procedure.

4.2.1 Analisi ricorsiva discendente

Sfruttando le funzioni e le procedure che già utilizzano uno stack, il quale si dealloca alla fine della loro

esecuzione, nasce l’analisi ricorsiva discendente. Essa si articola nei seguenti passi:

• Si introduce una funzione per ogni meta-simbolo della grammatica e la si chiama ogni volta che si

incontra quel meta-simbolo.

• Ogni funzione copre le regole di quel meta-simbolo, ossia riconosce il sotto-linguaggio corrispondente.

Questa funzione:

– Termina normalmente, o restituisce un segno di successo, se incontra simboli coerenti con le

proprie regole.

– Abortisce, o restituisce un segno di fallimento, se incontra simboli che non corrispondono alle

proprie regole.

Ipotesi 4.1 Si supponga che il carattere sia già stato letto, e che quindi ogni funzione esegua la lettura

alla fine della sua esecuzione per la prossima funzione.

24

Esempio 4.2 Si riprenda il linguaggio definito come:

S 0S0|1S1|c,

si ottiene una funzione per S:

char

1 ch; // Variabile globale

2 bool S() {

char

3 first ;

4 bool result ;

5 ch = nextchar ();

switch

6 (ch) {

case

7 'c':

8 ch = nextchar ();

9 result = true;

break;

10 case

11 '0': // Sia per 0 sia per 1 viene eseguito lo stesso codice

case

12 '1':

13 first = ch;

if

14 (S()) {

if

15 (ch == first) {

16 ch = nextchar ();

17 result = true;

else

18 }

19 result = false;

else

20 }

21 result = false;

default

22 :

break;

23

24 }

return

25 result ;

26 }

Come si può notare, se richiamasse altri metasimboli, il codice cambierebbe solamente per introdurre

S

la chiamata alla funzione che definisce quei meta-simboli.

Questo può essere riassunto in una tabella di funzioni specificando, per ogni carattere dell’alfabeto, come

risponde la funzione con quel determinato ingresso. Se in ingresso si trova un carattere inatteso, basterà

completare la tabella segnalando l’errore. Dato il linguaggio:

{if c then cmd(endif|else cmd)}

L =

con produzioni: → →

if c then cmd endif|else cmd,

S X, X

in Tabella 4.2 si vede un esempio di questo approccio.

if c then endif else cmd

→ if c then cmd errore errore errore errore errore

S S X → →

errore errore errore endif else cmd errore

X X X

Tabella 4.2: Esempio tabella PDA deterministico.

L’analisi ricorsiva discendente non è sempre applicabile. Se infatti un linguaggio diventa non determi-

nistico, ossia due produzioni iniziano con lo stesso carattere, bisognerebbe complicare il riconoscitore, il che

risulterebbe molto oneroso. Una soluzione adottata da molti linguaggi, tra cui Bash, è quella di modificare

la grammatica al fine di togliere le ambiguità, ma sarebbe preferibile ottenere scelte univoche senza modi-

ficare la grammatica. Per fare ciò si può conoscere il futuro immediatamente prossimo, ovvero il minimo

indispensabile a capire la strada da seguire. 25

4.3 Grammatiche LL(k)

Si definiscono grammatiche quelle che sono analizzabili in modo deterministico:

LL(k)

• procedendo left-to-right;

• applicando la left-most derivation;

• guardando avanti al più di simboli.

k

Rivestono particolare interesse le grammatiche ossia quelle dove è sufficiente guardare avanti di un

LL(1),

solo simbolo per poter operare in modo deterministico.

Esempio 4.3 Si consideri la grammatica:  →

 S pX|qY

{p, {S, }, X aXb|x

V T = q, a, b, d, x, y}, V N = X, Y P .

 →

Y aY d|y

Si nota come le parti destre di uno stesso meta-simbolo inizino tutte con simboli terminali diversi. È quindi

sufficiente guardare avanti di un carattere per scegliere con certezza la produzione con cui proseguire l’analisi,

mentre in caso non esistano produzioni compatibili con quell’ingresso si giunge nello stato d’errore.

Si sviluppa quindi la parsing table relativa alla grammatica come in Tabella 4.3.

p q a b d x y

→ → errore errore errore errore errore

S S pX S qY → →

errore errore errore errore errore

X X aXb X x

→ →

errore errore errore errore errore

Y Y aY d y y

Tabella 4.3: Parsing table dell’Esempio 4.3.

Se si volesse scrivere il codice relativo al PDA, il main sarebbe uguale per ogni PDA, indipendentemente

dalla grammatica:

char

1 ch; // Variabile globale visibile alle funzioni

2 main () {

3 ch = nextchar (); // Si astrae dal concetto di lettura

if

4 (S())

5 printf ("Frase accettata ");

else

6

7 printf (" Errore ");

8 }

Mentre le funzioni e si occupano solo di implementare ciò che compete loro:

S, X Y

1 bool S(){

switch

2 (ch){

case

3 'p':

4 ch = nextchar ();

return

5 X();

case

6 'q':

7 ch = nextchar ();

return

8 Y();

9 }

return

10 false;

11 } 26

4.3.1 Starter Set ∈

Data l’importanza di operare con grammatiche si definisce starter set del non-terminale

LL(1), A V N

l’insieme dei simboli terminali per cui può iniziare una frase originata dal meta-simbolo Una definizione

A.

matematica è: ∗

+

{a ∈ |A ⇒ ∈

SS(A) = V T = aβ}, β V ,

si definisce inoltre starter set della riscrittura l’insieme:

α

∗ ∗

{a ∈ |α ⇒ ∈ ∈

+

SS(α) = V T = aβ}, α V , β V .

Condizione necessaria perché una grammatica sia è che gli starter set dei meta-simboli con cui

LL(1)

iniziano le parti destre di produzioni alternative siano disgiunti.

Esempio 4.4 Si prenda in considerazione la grammatica definita come:

 → |T

 S RY Z

 →

 R pXb

 →

T qY d

{p, {S,

V T = q, a, b, d, y}, V N = X, Y, T, Z, R}, P .

→ ···

 Z

 →

X aXb|x

 →

Y aY d|y

In questo caso gli starter set dei meta-simboli e , che sono i meta-simboli con cui può iniziare lo scopo

R T

{p} {q}.

sono: e Essi sono disgiunti, quindi la grammatica può essere Poiché

S, SS(R) = SS(T ) = LL(1).

nessuna produzione genera la stringa vuota, la condizione vista precedentemente è anche sufficiente.

Domanda 4.1 – Perché la stringa vuota fa la differenza? Se una produzione genera la stringa

vuota, quel meta-simbolo può sparire quando viene sostituito in un’altra regola, facendo sì che regole che

sembrano iniziare con un certo meta-simbolo inizino in realtà con il successivo.

Esempio 4.5 Si prendano in considerazione le produzioni

→ → →

S AB|B, A aA|ε, B bB|c. →

Come si può notare, lo starter set di non caratterizza più completamente la produzione in

A S AB,

quanto può generare la stringa vuota e quindi delegare a il compito di esporre uno starter set per tale

A B

produzione. Si ottiene quindi che l’intersezione fra le due produzioni possibili di non è vuota; ciò significa

S

formalmente che le grammatiche che ammettono le possano non essere anche con starter set

ε-rules LL(1)

disgiunti.

Domanda 4.2 – Come risolvere? La soluzione banale sarebbe quella di eliminare la stringa vuota

agendo per sostituzione; in questo modo si modifica però la grammatica, e ciò rappresenta una scelta molto

scomoda. In alternativa, si può ampliare il concetto di starter set, per arrivare a determinare se un linguaggio

è con precisione.

LL(1)

4.3.2 Director symbol set →

Si definisce director symbol set della produzione l’unione di:

A α

• starter symbol set;

• il nuovo following symbol set, ossia l’insieme dei simboli che diventerebbero iniziali considerando le

potenziali produzioni di ε: ∗ ∗

{a ∈ |S ⇒ ∈

F OLLOW (A) = V T = γAaβ}, γ, β V .

27 →

Si definisce quindi il director symbol set della produzione come:

A α ∗

→ ∪ ⇒

DS(A α) = SS(α) F OLLOW (A), α = ε.

Si ottiene così una condizione necessaria e sufficiente affinché una grammatica sia se i director

LL(1):

symbol set relativi a produzioni alternative sono disgiunti, la grammatica è LL(1).

Domanda 4.3 – Il linguaggio generato da una grammatica è In generale, stabilire se

LL(1)?

una grammatica sia è un problema decidibile, ma stabilire se lo è un linguaggio non lo è, questo

LL(1)

risulta problematico perché le grammatiche più immediate per un linguaggio non sempre sono Si

LL(1).

approfondirà successivamente, con strumenti non matematici, quali linguaggi siano interessanti e con quali

grammatiche realizzarli, al fine di non porsi di fronte a questo problema.

4.3.3 Il problema della ricorsione sinistra

Come si è visto, se un linguaggio è risulta semplice progettare un riconoscitore con un semplice

LL(1)

linguaggio imperativo. Sussistono tuttavia problemi di ambiguità che non si sono ancora considerati.

Esempio 4.6 Si analizzino le seguenti produzioni:

→ → →

A Bb|Cc, B dBe|f, C dCg|h.

Se si prova a manipolare queste produzioni per determinare i director symbol set, si ottiene:

→ → → →

A dBeb|dCgc, A f b|hc, B dBe|f, C dCg|h.

La prima regola, che conteneva due alternative, si suddivide perciò in quattro alternative, ma per quanto si

tenti di raccogliere il problema che si ripropone è sempre lo stesso: e hanno sempre lo stesso starter

B C

set e non si può determinare a priori la strada giusta da seguire.

4.4 Oltre l’analisi LL(k)

Come si è visto, le grammatiche consentono l’analisi deterministica delle frasi left-to-right, con left-

LL(k)

most derivation e usando simboli di lookahead. Questa tecnica di riconoscimento è molto potente in

k

relazione al costo computazionale che comporta, tuttavia, a volte, si rende necessario l’utilizzo di strumenti

computazionalmente più complessi, che però possono risolvere una classe più ampia di problemi. Questo è il

caso dell’analisi LR che, pur essendo meno naturale e molto più difficile da progettare, rende deterministici

molti problemi che, con la non lo sono.

LL(k), 28

Capitolo 5

Dai riconoscitori agli interpreti

Si è fino ad ora definito come sviluppare un automa riconoscitore, ossia un automa che, data una certa

sequenza di simboli in input, determini se essa appartiene ad un determinato linguaggio. Nonostante questo

sia un risultato rilevante, esso non è tuttavia di alcuna utilità se non si associa un senso alla frase. Un

interprete non si limita a controllare se la frase è giusta, ma se lo è gli assegna un significato.

Domanda 5.1 – Cosa vuol dire dare significato a una frase? Concettualmente dare significato a

una frase significa:

• Eseguire un’azione che la frase descrive, producendo cioè l’output dell’azione. In questo caso si parla

di interprete.

• Produrre un risultato che, quando l’utente lo richiederà, interpreterà il significato di quella frase. In

questo caso si parla di compilatore.

Un interprete è composto da:

1

• Scanner: analizza singolarmente lettere o simboli per aggregarli in token, ossia parole grammati-

calmente corrette solitamente descritte da grammatiche regolari.

• Parser: analizza pattern di token per assegnargli un significato semantico.

5.1 Analisi lessicale lettera lettera,

F

Come si è detto, un riconoscitore che si limita a definire se una sequenza di ca- 1 cifra

I

ratteri è legittima in un determinato linguaggio svolge una funzione chiave per cifra

F

l’interpretazione di una frase, ma, allo stesso tempo lascia inalterato il contenuto 2

cifra

informativo di tale sequenza di caratteri. Figura 5.1: Grafo degli

Lo scanner non si limita a dire se un token è corretto o no; durante il processo di stati di uno scanner.

riconoscimento, infatti, esso raggruppa in categorie i token, senza però cristallizza-

re nella sua implementazione dettagli semantici. Nei moderni linguaggi di programmazione, come C e Java,

lo scanner, oltre a raggruppare in token i caratteri di un programma, suddivide i token in due macro-insiemi:

identificatori (F ) e numeri (F ), com’è possibile vedere in Figura 5.1. È per questo motivo che non si può

1 2

far cominciare un identificatore con una cifra numerica, altrimenti non sarebbe deterministico.

Domanda 5.2 – Come gestisco le parole chiave? Se si volesse delegare allo scanner il compito di

valutare se un identificatore è anche una parola chiave si dovrebbe stabilire, per ogni lettera in ingresso, se

il token è un identificatore, quindi creare, per ogni parola chiave, un insieme di stati ad hoc (si pensi che

è una parola chiave, mentre non lo è). Si delega quindi al livello superiore, ossia quello semantico,

if ifi

di determinare se un token è una parola chiave o un identificatore. A livello scanner questi, infatti, sono

1 Non è necessario ricrearlo da zero ogni volta, Java per esempio mette a disposizione la classe per definire

StringTokenizer

semplicemente i possibili separatori, la classe in combinazione con per un approccio più sofisticato e flessibile e

Scanner Regex

il metodo per separare una stringa in un array di token sulla base di espressioni regolari.

String.split() 29

entrambi identificatori.

In questo modo si sono aggiunte delle capacità allo scanner, senza aggiungere stati a cascata in base

alla frase in input; inoltre, l’operazione risulterà più estendibile se eseguita a livello semantico, tramite

l’uso di opportune tabelle. La struttura di uno scanner, rispettando una grammatica regolare destra, è

implementabile con un automa a stati finiti che, in base allo stato finale raggiunto, aggiunge un’informazione

al token analizzato.

5.2 Analisi sintattica

In presenza di grammatiche l’analisi top-down ricorsiva discendente offre una tecnica semplice e

LL(1),

diretta per costruire il riconoscitore. Negli esempi visti, ogni funzione restituiva un booleano, ma per

passare da un puro riconoscitore a un interprete occorre propagare qualche informazione in più. Questa può

essere:

• un valore, se l’obiettivo è la valutazione immediata;

• un albero, se l’obiettivo è la valutazione differita.

Si supponga di voler riconoscere espressioni aritmetiche con le quattro operazioni: e Un puro

+, -, * /.

riconoscitore si limita a dire se la sequenza di simboli in input è un’espressione, mentre un’interprete

deve anche dire quanto vale e, a seconda del dominio di riferimento, dovrà fornire un intero, un reale o, se

l’obbiettivo è la valutazione in differita, un opportuno oggetto adatto a rappresentare un albero.

5.2.1 Sintassi

Si introducono, tra i simboli terminali, anche le parentesi per esprimere priorità associativa non standard

(il concetto di priorità tra operatori verrà gestito successivamente).

5.2.2 Semantica

Nel dominio aritmetico convenzionale è opportuno fare alcune considerazioni:

• i valori numerici si assumono espressi in notazione posizionale decimale;

• il significato inteso dei quattro operatori è quello di somma, sottrazione, moltiplicazione e divi-

sione;

• si introducono le nozioni di:

– priorità fra operatori diversi;

– associatività fra operatori equi-prioritari.

Esempio 5.1 – Differenza di semantica Se si prende la calcolatrice standard di Windows e si digita

l’equazione questa darà come risultato 35, poiché non rispetta la priorità degli operatori, mentre se

3+4*5,

si imposta la calcolatrice scientifica, questa darà il risultato corretto, cioè 23.

5.2.3 Grammatica

Un primo approccio per definire una grammatica che identifichi espressioni aritmetiche, ipotizzando che ci

sia uno scanner che definisca è il seguente:

num,

{EXP }, {+, *, -, /,

V N = V T = num}, S = EXP,

30

 +EXP

EXP ::= EXP

 -EXP

EXP ::= EXP *EXP

EXP ::= EXP

P .

 /EXP

EXP ::= EXP

 EXP ::= num

Questa tipologia di grammatica è ambigua poiché, come si può vedere in Figura 5.2, se si hanno più

operazioni concatenate è possibile ottenere diversi alberi per la stessa espressione algebrica.

E E

+ +

E E E E

+ +

5 5

3 3

4 4

(a) (b)

Associatività a sini- Associatività a destra.

stra.

Figura 5.2: Possibili alberi di derivazione dell’espressione 3+4+5.

Nasce quindi il bisogno di una nuova struttura di grammatiche, al fine ottenere il concetto di priorità

degli operatori. Si può fornire una struttura gerarchica alle espressioni, esprimendo così intrinsecamente

priorità e associatività degli operatori. Si definisce quindi la grammatica come:

{EXP, {+, *, -, /, (, ),

V N = T ERM, F ACT OR}, V T = num},

 EXP ::= T ERM

 +T

EXP ::= EXP ERM

 -T

 EXP ::= EXP ERM

 T ERM ::= F ACT OR

P .

 *F

T ERM ::= T ERM ACT OR

 /F

T ERM ::= T ERM ACT OR

 F ACT OR ::= num

 (EXP )

F ACT OR ::=

Suddividendo gerarchicamente la grammatica è assicurata la presenza di un solo albero, poiché le EXP

non verranno risolte fino a che i non verranno risolti; questi ultimi, a loro volta, non saranno risolti

T ERM

finché i non avranno assegnato ad ogni numero il loro valore e ad ogni espressione fra parentesi

F ACT OR

il suo risultato numerico. Questo meccanismo genera tre linguaggi distinti nella stessa grammatica, ognuno

che adempie alle operazioni di sua competenza e delega al livello sottostante le operazioni più prioritarie,

per poi offrire al livello superiore il proprio risultato. La priorità è sempre assegnata in base alla profondità:

i livelli più in superficie hanno il livello più basso di priorità e verranno eseguiti per ultimi (ecco perché in

cima si trovano il e il mentre scendendo è possibile trovare operatori più prioritari come il e il

+ -), * /.

Priorità massima è invece data alle parentesi e ai singoli numeri.

La soluzione proposta, com’è possibile vedere in Figura 5.3, genera un E

solo albero e rispetta la priorità degli operatori, assicurando che, a parità +

E T

di operatore, venga eseguito quello più a sinistra. Questa soluzione, pur

essendo accettabile da un punto di vista algoritmico, non è però imple- +

E T F

mentabile, poiché presenta una ricorsione sinistra, ossia forza l’albero a

espandersi a sinistra; per una macchina a stack questo vuole dire andare 5

T F

in overflow con altissima probabilità. Se si decidesse di introdurre una 4

F

ricorsione destra, per ovviare a quella sinistra, si perderebbe il concetto

di priorità a sinistra delle operazioni con uguale operatore. Bisognerà 3

quindi trovare un approccio più sofisticato per far fronte a questo proble- Figura 5.3: Albero di derivazione

ma implementativo. In generale, si nota che una grammatica di tipo 2 si univoco dell’espressione 3+4+5.

ottiene come composizione di più linguaggi di tipo 3 e, con la ricorsione,

si stabilisce come si aggreghino entità di pari livello. 31

5.2.4 Ricorsione sinistra

Se si provasse ad implementare la ricorsione sinistra su un’espressione, l’automa riconoscitore dovrebbe

valutare tutti i possibili tentativi per riconoscere se è composta da se stessa o da un singolo ;

EXP T ERM

questo porterebbe a tentativi infiniti e, quindi, a riempire la memoria senza mai trovare una soluzione. Se

invece si eliminasse la ricorsione sinistra, sostituendola con una ricorsione destra, si perderebbe l’associatività

delle operazioni a sinistra. L’unica soluzione che rispetti le proprietà delle operazioni e che, allo stesso tempo,

sia implementabile da una macchina a stack è quella di manipolare opportunamente la grammatica.

Seguendo il principio di delega, si analizza la grammatica ricavata da quella precedente sostituendo, alla

ricorsione, una delega dei compiti al livello sottostante:

 EXP ::= T ERM

 +T

EXP ::= T ERM ERM

 -T

 EXP ::= T ERM ERM

 T ERM ::= F ACT OR .

P  T ERM ::= F ACT OR*F ACT OR

 T ERM ::= F ACT OR/F ACT OR

 F ACT OR ::= num

 (EXP )

F ACT OR ::=

Questa grammatica risolve il problema della ricorsione sinistra, ma perde l’associatività, introducendo

l’obbligo di usare le parentesi ad ogni operazione svolta. L’espressione algebrica analizzata prima 3+4+5

diventa illecita per il linguaggio, il quale accetta solo Questa soluzione, che risulta la migliore

(3+4)+5.

considerando gli strumenti a disposizione fin’ora, è più accettabile delle precedenti, ma vincola ad usare un

linguaggio più verboso che non si è disposti ad accettare.

5.3 Parser

Riprendendo la grammatica originale, che pur non essendo implementabile soddisfaceva i requisiti per

generare il linguaggio correttamente, si evidenziavano due problemi:

• la presenza della ricorsione sinistra;

• la grammatica non è cioè l’analisi ricorsiva discendente non è applicabile.

LL(1),

Per rendere la grammatica si procede con:

LL(1)

1. Si nota che i primi due linguaggi sono regolari, si possono quindi definire da espressioni regolari come:

∗ ∗

L(EXP ) = T ERM (+/- T ERM ) , L(T ERM ) = F ACT OR(*// F ACT OR) .

2. Essendo regolari a destra, è possibile crearne un ciclo che, a differenza della ricorsione, non porta in

overflow lo stack.

3. Si definiscono quindi i due sotto-linguaggi su regole EBNF, i quali descrivono un processo computa-

zionale iterativo, implementabile senza fare uso della ricorsione:

{(+|-)T },

EXP ::= T ERM ERM T ERM ::= F ACT OR{(*|/)F ACT OR}.

5.3.1 Applicazione pratica

Per realizzare quanto detto fin’ora, si procede in tre passi:

1. Si realizza una procedura, o funzione, per ogni simbolo non terminale, limitando l’invocazione ricorsiva

solamente alla grammatica che implementa il self-embedding (nell’esempio (EXP )).

F ACT OR =

32

2. Ogni funzione restituisce:

• un booleano nel caso di puri riconoscitori;

• un opportuno valore o oggetto nel caso di parser completi che effettuino anche una valutazione.

3. Ogni funzione termina quando:

• la stringa in input finisce, cioè trova un terminatore;

• incontra un simbolo non appartenente al sotto linguaggio di sua competenza, noto come approccio

prudente.

5.4 Valutatore

Fino ad ora ci si è limitati a riconoscere frasi di un linguaggio, generandone una grammatica non ambigua.

Il valutatore che si vuole realizzare toglie all’utente la facoltà di scrivere secondo il suo lessico comune,

poiché spesso i linguaggi usati, per quanto intuitivi e utili nel primo approccio ad un problema, risultano

essere estremamente ambigui nei dettagli. Con i linguaggi si possono risolvere tali ambiguità leggendo

LL(1)

il token successivo a quello che si sta analizzando, scegliendo così, tra le opzioni possibili, l’alternativa corretta

senza procedere per tentativi. Imponendo l’uso delle parentesi, inoltre, si è sostituita la ricorsione sinistra

(che si è visto essere deleteria per la macchina) con un’iterazione.

5.4.1 Specificare la semantica

Si deve quindi associare ad ogni frase corretta del linguaggio il suo significato univoco. Si può pensare

al significato di una frase come una funzione che associa ad ogni frase uno e un solo significato in un

determinato codominio La stessa frase può tuttavia avere più significati se si cambia il codominio (per

Z.

esempio, alla stringa posso associare il significato numerico o quello fonetico [’kwattro]).

4

5.4.1.1 Semantica denotazionale

Se una semantica è espressa descrivendo per ogni frase il suo significato si parla di semantica denotazio-

nale. Questa tipo di semantica risulta molto utile se le frasi possibili sono poche e risulta possibile creare

una tabella di associazioni; per i linguaggi potenzialmente infiniti, l’uso di una semantica denotazionale

risulta inefficace, pertanto ci si occupa di mappare la composizione delle regole base.

Riprendendo la grammatica definita per le espressioni algebriche, si cerca di sfruttare al meglio il lavoro

già svolto per applicarlo alla semantica.

 

 

EXP ::= T ERM f Expr(term) ::= f T erm(term)

 

 

 

 

+T

EXP ::= EXP ERM f Expr(exp+term) ::= f Exp(exp) + f T erm(term)

 

 

 

  −

-T

 

EXP ::= EXP ERM f Expr(exp-term) ::= f Exp(exp) f T erm(term)

 

 

 

T ERM ::= F ACT OR f T erm(factor) ::= f F actor(factor)

, .

×

 

*F

T ERM ::= T ERM ACT OR f T erm(term*factor) ::= f T erm(term) f F actor(factor)

 

 

 

 

/F

T ERM ::= T ERM ACT OR f T erm(term/factor) ::= f T erm(term) / f F actor(factor)

 

 

 

 

 

 

F ACT OR ::= num f F actor(num) ::= valueof (num)

 

 

(EXP )

F ACT OR ::= f F actor((exp)) ::= f Expr(exp)

La funzione si occupa solo di definire il concetto di addizione e di sottrazione, delegando

f Expr()

a ciò che non comprende; questa a sua volta delegherà a tutto ciò che non è né

f T erm() f F actor()

moltiplicazione né divisione.

Nella situazione presentata i simboli matematici coincidono con i simboli usati per implementare la somma,

tuttavia si sarebbe potuta ottenere, allo stesso modo, una concatenazione di stringhe, cambiando il significato

del simbolo +. 33

Esempio 5.2 Per interpretare l’equazione si procede come segue:

3+4*18/(7-1)

1. L’espressione ha la forma a cui corrisponde l’interpretazione

exp+term,

f Expr(exp+term) ::= f Exp(3) + f T erm(4*18/(7-1)).

2. L’espressione si riconduce a

f Expr(3) f F actor(3) ::= valueof (3) = 3.

3. Il termine ha la forma poiché, se venisse analizzata come la

4*18/(7-1) term/factor term*factor,

funzione restituirebbe errore (sarà quindi necessario guidare l’interprete affinché

f F actor(18/(7-1))

ciò non accada). L’espressione viene quindi espansa come:

f T erm(term/factor) ::= f T erm(4*18) / f F actor((7-1)).

4. Dal termine si ricava l’interpretazione dei due numeri tramite la e e la

4*18 f F actor(4) f F actor(18)

ne darà il risultato

f T erm() 72.

5. Allo stesso modo l’espressione verrà valutata da la quale permette di ottenere

(7-1) f F actor((7-1)),

una nuova espressione che restituirà come risultato la differenza dei valori e ossia

7 1, 6.

6. Il termine conoscendo i fattori, darà come risultato

72 / 6, 12.

7. L’espressione darà il risultato totale

3 + 12 15.

Si può ora determinare un che analizza i cui simboli terminali sono e

+, - term.

parseExp() L(EXP ),

Il analizza i cui simboli terminali sono e Infine,

*, / factor.

parseT erm() L(T ERM ), parseF actor()

analizzerà il cui alfabeto terminale è costituito da e

(, ) exp.

L(F ACT OR),

5.5 Alberi sintattici astratti

Fino ad ora si è sfruttata la comodità di associare alla grammatica la rispettiva semantica. Nel caso

si volesse sfruttare la stessa frase in input per più interpreti, tuttavia, questo approccio non risulterebbe

ottimale, poiché, una volta valutato l’input, non se ne tiene traccia. Converrebbe quindi, anziché interpretare

direttamente tutta l’espressione, generare un albero che, all’occorrenza, venga utilizzato da tutti gli interpreti

che ne hanno bisogno.

Se si decidesse di salvare un albero di derivazione esso rischierebbe, ragionando su interi programmi,

di crescere esponenzialmente con le linee di codice. Sono stati inventati, pertanto, alberi che astraggono

dall’albero completo, mantenendo solo i token fondamentali a generare le azioni. Questa tipologia di albero

non tiene traccia dei vincoli grammaticali formali, ma memorizza solamente la sequenza di azioni, ricavando,

dalla propria struttura, l’ordine in cui esse vengono svolte. Sarebbe inoltre comodo, per proprietà peculiari,

che l’albero sia binario; nel ricavare l’Abstract Syntax Tree AST si cercherà, pertanto, di rendere

quest’ultimo binario. −

Esempio 5.3 Si consideri come esempio l’albero in Figura 5.4a, generato dall’espressione 13 (4 + 5).

Si noti come molti nodi non denotano vere e proprie azioni, ma identificano l’entità che la eseguirà. Questi

nodi risultano inutili al fine dell’interpretazione dell’albero, perciò se ne deduce che tutti i nodi con un

solo nodo figlio si elimineranno, collegando direttamente la foglia con il primo nodo della “catena”. Le

parentesi, inoltre, si possono elidere, in quanto la struttura gerarchica bidimensionale dell’albero offre già

priorità crescente ai calcoli, in base alla profondità a cui questi si trovano. Per modificare ulteriormente

l’albero e renderlo binario si noti che, ad ogni nodo che non sia foglia e che abbia più di un figlio, è

associata una e una sola operazione, la quale può essere quindi assegnata direttamente al nodo padre; ci si

riconduce quindi all’albero in Figura 5.4b. Si ottiene quindi un albero, che contiene tante tipologie di nodo

quante sono le operazioni, più una tipologia di nodo che ne identifica le foglie (ossia i numeri).

34

E

E T

-

T F

( )

F E

13 E T

+ −

T F +

13

5

F

4 4 5

(a) (b)

Albero concreto e univoco. AST.

Figura 5.4: Alberi di derivazione dell’espressione 3+4+5.

5.5.1 Sintassi astratta

Una sintassi astratta ha l’obiettivo di descrivere come è fatto l’albero sintattico astratto. Essa si potrebbe

descrivere, in base alle specifiche viste nell’esempio precedente, come:

 + EXP

EXP ::= EXP

 −

 EXP ::= EXP EXP

× EXP

::=

EXP EXP

 EXP ::= EXP / EXP

 EXP ::= num

Questa sintassi non è unica. Si può decidere, infatti, di rappresentare lo stesso albero di derivazione con un

diverso albero astratto, avente più o meno nodi a seconda della rappresentazione interna. Questa grammatica

non sarebbe andata bene per descrivere il parser, poiché ambigua. L’uscita del parser, tuttavia, essendo già

stata processata non genera più ambiguità di interpretazione anche se descritta da una grammatica ambigua.

Un interprete che legge l’albero sintattico secondo queste regole, riuscirà infatti a trarne il risultato corretto

senza più eseguire le operazioni lui stesso, ma richiamando la appropriata.

EXP

5.5.2 Implementazione Exp

Se si volesse rappresentare l’albero appena citato in un lin-

guaggio ad oggetti, si potrebbe sfruttare il polimorfismo per

generare, da una stessa interfaccia, classi concrete diverse OpExp NumExp

ed interrogare le interfacce per avere informazioni sul tipo

di classe che le implementano. Una scelta di questo tipo

complica il modello delle classi da realizzare, ma consente PlusExp MinusExp TimesExp DivExp

di evitare l’interrogazione di oggetti per capirne lo stato in-

terno. Una scelta alternativa sarebbe quella di utilizzare Figura 5.5: Modello delle classi per modellare le

la stessa classe concreta e differenziare gli oggetti in base espressioni

al loro stato interno; ciò semplificherebbe lo schema grazie

all’utilizzo di più attributi e metodi per interrogare gli oggetti. Le scelte d’implementazione, come quelle

della sintassi da utilizzare per rappresentare l’albero astratto, non sono uniche. Tuttavia, lavorando con

un linguaggio ad oggetti, risulta più performante operare con la definizione di più classi, piuttosto che con

l’interrogazione di numerosi oggetti al fine di valutarne gli attributi. Il modello risultante da questa analisi

è rappresentato in Figura 5.5. 35

5.5.3 Verifica del modello −

Esempio 5.4 Si prenda, ad esempio, l’operazione Essa si può codificare come:

3 5.

new new

1 Exp s1 = MinusExp (new NumExp (3) , NumExp (5));

× −

Esempio 5.5 Si consideri ora l’espressione Essa si può codificare come:

2 + 5 4 1.

new

1 Exp s1 = MinusExp (new PlusExp (

new

2 NumExp (2) ,

new

3 TimesExp (

new

4 NumExp (5) ,

new

5 NumExp (4))),

new

6 NumExp (1));

Esempio 5.6 Se, date le espressioni:

new

1 Exp s1 = MinusExp (new NumExp (5) ,

new

2 MinusExp (

new

3 NumExp (3) ,

new

4 NumExp (1)));

new

5 Exp s2 = MinusExp (new MinusExp (

new

6 NumExp (5) ,

new

7 NumExp (3)),

new

8 NumExp (1)));

ne si calcola la si otterrà, per entrambe, Per renderle diverse bisognerà introdurre

toString(), 5-3-1.

nuovamente le parentesi, al fine di rispettare la profondità dell’albero in una struttura monodimensionale

come una stringa. Ciò introdurrà una notazione più verbosa, ma corretta.

5.5.4 Compilatore

Si è così convenuto che una macchina capace solo di interpretare le frasi in ingresso e fornirne un risultato

in uscita, per quanto estremamente utile, non lasci traccia delle operazioni svolte e, nel caso un altro

interprete volesse processare lo stesso input, ciò risulterebbe un processo difficile tanto quanto quello del

primo interprete. Si correrebbe così il rischio che l’input, se fornito da tastiera, sia già stato usato e, quindi,

non sia più reperibile nei buffer di sistema.

Può quindi tornare utile uno strumento che, pur non fornendo un risultato interpretato della frase in input,

trasformi quest’ultima in una rappresentazione più facilmente utilizzabile dagli interpreti: questo componen-

te è il compilatore. Esso, data una frase in input, ne fornisce l’albero sintattico astratto, ossia l’insieme di

operazioni in ordine gerarchico di priorità che un interprete deve eseguire per interpretare semanticamente

la frase data. Ciò consente sia il possibile riutilizzo di uno stesso input per più interpreti (fornendo come

input l’albero in uscita dal compilatore), sia una più rapida interpretazione da parte degli interpreti, che

devono ora gestire una normale struttura ad albero già analizzata dal compilatore anziché la frase, priva

di controlli, in ingresso. La differenza sostanziale tra un compilatore e un interprete è l’interpretazione del

risultato come finale (interprete) o come meta-risultato (compilatore), ma i due strumenti lavorano allo

stesso modo. Il vantaggio di un compilatore è di fornire un risultato che contiene le informazioni sulla frase

che lo ha generato. Uno strumento che interpreta un albero astratto posto in ingresso è detto valutatore.

− valutatore 13

1

+ 4 ..

AST

frase token

input .

parser

scanner

2+3*5-4 device ×

2 235*+4-

valutatore N

3 5

Figura 5.6: Schema di un compilatore e successivi interpreti.

36

5.5.5 Valutatore

Ottenuto l’albero sintattico dal compilatore, si pone il problema di come interpretarlo, ossia come un valu-

tatore leggerà l’albero. Sarà pertanto necessario capire se il valutatore lavorerà meglio con una notazione

prefissa, infissa o postfissa.

5.5.5.1 Notazione prefissa

La notazione prefissa è quella comunemente usata in matematica per definire le funzioni; essa consiste

nell’anteporre la funzione ai termini cui essa è applicata. Un generico lettore otterrebbe un’interpretazione

univoca dell’espressione che, per quanto possa risultare poco intuitiva, fornisce un risultato corretto e privo

di ambiguità, e risulta pertanto ottima per l’utilizzo da parte di un valutatore.

Esempio 5.7 L’espressione verrà obbligatoriamente interpretata come la moltiplicazione fra

* + 3 4 5

la somma dei termini 3 e 4 e il termine 5. Nella notazione infissa, più comunemente usata per le espressioni,

×

questa sarebbe rappresentata come (3 + 4) 5.

Per navigare l’albero astratto con notazione prefissa si legge prima la radice e, successivamente, le foglie,

in ordine da sinistra verso destra. Questa definizione si applica ricorsivamente nel caso le foglie siano a loro

volta radici di altre foglie.

5.5.5.2 Notazione infissa

La notazione infissa è la meno adatta alla corretta interpretazione di espressioni aritmetiche, in quanto non

definisce intrinsecamente delle priorità nelle operazioni da svolgere, ma introduce concetti come la priorità

degli operatori, le parentesi e l’associatività, le quali non possono essere dedotte dal testo (se non

con una loro descrizione formale). Questa notazione è usata dall’uomo per convenzione, ma non trae alcun

vantaggio dalle strategie di rappresentazione usate.

Per navigare l’albero astratto con notazione infissa, si legge prima la foglia sinistra (ricorsivamente nel

caso questa presenti ulteriori foglie), la radice ed infine la foglia destra (anche questa ricorsivamente se in

presenza di altre foglie).

5.5.5.3 Notazione postfissa

La notazione postfissa è speculare alla notazione prefissa. Nell’ordine, essa impone prima la presenza degli

operandi e, successivamente, quella dell’operatore. Questo tipo di rappresentazione è usata dalle macchine,

poiché gli operandi vengono memorizzati in uno stack e, quando si incontra il simbolo di un’operazione, gli

ultimi operandi memorizzati vengono caricati nell’ALU, la quale esegue il calcolo e ne inserisce il risultato

nello stack.

Esempio 5.8 L’espressione verrà obbligatoriamente interpretata come la moltiplicazione fra

5 4 3 + *

la somma dei termini 3 e 4 ed il termine 5. Nella notazione infissa, più comunemente usata per le espressioni,

×

questa sarebbe rappresentata come 5 (3 + 4).

Si è quindi trovato il metodo più adatto per navigare l’albero astratto, ossia leggere prima le foglie

(nell’ordine da sinistra a destra), applicando questa definizione ricorsivamente nel caso le foglie siano a loro

volta radici di altre foglie, ed infine la radice. 37

Capitolo 6

Stili di interpretazione

Si pone ora il problema di come implementare la funzione di valutazione, al fine di permetterne l’esecuzione

da parte di una macchina a stack. Le principali soluzioni di implementazione sono:

• Funzione statica: una funzione che assume in ingresso un albero e ne restituisce la valutazione come

risultato.

• Metodo: la traduzione ad oggetti di una funzione statica.

• Sfruttando il polimorfismo.

6.1 Funzione statica

L’implementazione, per ogni valutatore, di una funzione di valutazione rende modulare il progetto, poiché

separa l’albero dalla sua valutazione; tuttavia essa presenterebbe le scomode catene di al fine di deter-

if

minare cosa si sta valutando. Questa soluzione è tipica dei linguaggi a base procedurale, i quali offrono

soluzioni ridondanti e inefficienti.

6.1.1 Metodo

Per implementare un valutatore con un linguaggio ad oggetti, un primo approccio potrebbe essere quello di

creare un metodo Ci si domanda, però, quale classe implementi questo metodo. La soluzione

eval(Exp e).

migliore è che ogni specializzazione di noto il tipo di operatore, si valuti, contenendo quindi, per ogni

Exp,

valutatore, un metodo che restituisce la valutazione di se stessa.

eval()

Questo approccio presenta alcuni punti deboli poiché, per quanto in questo modo non siano più presenti

le catene di (poiché le linee di codice sono infatti posizionate al posto giusto), all’aggiunta di un nuovo

if

valutatore si dovranno modificare tutte le classi precedentemente realizzate. Questo approccio presenta il

vantaggio di rendere il codice più leggibile e facilmente estendibile a nuove produzioni, poiché è sufficiente

definire una nuova sottoclasse con il relativo metodo di valutazione, ma presenta come svantaggio la scarsa

manutenibilità ed estensione dei valutatori.

6.2 Soluzione polimorfica

Si cerca, quindi, un’implementazione che preservi i vantaggi del metodo funzionale (ossia la facile introdu-

zione di nuove interpretazioni) e di quella object-oriented (ossia la facilità di aggiungere nuove produzioni),

evitandone i difetti. L’ingegneria del software fornisce un pattern per assolvere questa necessità: il pattern

visitor. 38

6.3 Pattern visitor Visitor

Il pattern visitor (Figura 6.1) si basa sulla definizione di una classe

contenente tutti i metodi di valutazione Ciò

visit(PlusExp e). + visit(in exp: NumExp) : void

+ visit(in exp: PlusExp) : void

rende compatte le modifiche da apportare nel caso si voglia mo- + visit(in exp: MinusExp) : void

dificare un valutatore. Ogni classe che estende dovrà imple-

Exp + visit(in exp: TimesExp) : void

+ visit(in exp: DivExp) : void

mentare un metodo che consenta al visitor

accept(Visitor v),

di valutarla. All’interno del metodo infatti, il visitor

accept(),

passato come parametro richiamerà un suo metodo visit(this), ParExpVisitor TreeVisitor EvalVisitor

passando l’espressione stessa che lo ha accettato come parametro.

Questo meccanismo del metodo incapsula l’azione di va-

accept() Figura 6.1: Pattern visitor.

lutazione nel visitor stesso ma, dentro l’espressione che lo chiama

e in base alla classe di quest’ultima, esso richiama il metodo corrispondete. Si è così ottenuto un approc-

cio che sfrutta il polimorfismo al fine di determinare quale metodo invocare, e che incapsula l’interprete

all’interno di una classe. Ciò permette di apportare modifiche all’interpretazione senza modificare le classi

che generano l’AST.

Con questo metodo il pattern visitor gode di tutti i vantaggi della metodologia funzionale, non soffrendo

degli svantaggi strutturali (quali catene di e cast, evitati grazie al polimorfismo). L’unica aggiunta al

if

modello delle espressioni sarà quella di aggiungere, ad ogni classe che estende il metodo

Exp, accept(Visitor

Esso infatti, essendo comune a tutte, può essere definito nella classe astratta così da rendere il

v). Exp,

codice leggibile e estendibile ad altri tipi di espressioni che verranno aggiunte in futuro.

Facendo riferimento alla Figura 6.1 si è quindi realizzato:

• stampa l’espressione con la stessa sintassi voluta dal parser (possibilmente con

ParExpVisitor:

l’aggiunta di parentesi per esplicitare i livelli dell’albero).

• stampa l’espressione con parentesi e notazione prefissa, o postfissa (per far risaltare

TreeVisitor:

l’ordine delle operazioni).

• calcola il risultato dell’espressione.

EvalVisitor:

Ognuno di questi visitor avrà bisogno di mantenere in memoria il risultato di ogni visita in un attributo

(o meglio e un metodo accessor per ottenere il risultato (finale o parziale che sia).

private protected), 39

Capitolo 7

L’interprete esteso

Ogni linguaggio di programmazione introduce le nozioni di variabile ed assegnamento. Sebbene si utilizzi

l’operatore l’assegnamento non è però un’uguaglianza o un’equazione in senso matematico. Si pone

=,

pertanto il problema di estendere l’interprete delle espressioni con il concetto di assegnamento, che è invece

più affine ad un’istruzione.

7.1 Assegnamento

L’assegnamento di un valore ad una variabile ha il significato di rendere uguale il contenuto della variabile

a sinistra dell’uguale con quello della variabile, o valore, a destra. Questo simbolo non è né simmetrico,

né riflessivo. Scrivendo infatti il compilatore dovrà immagazzinare, nel contenitore il valore

x=25, x, 25,

mentre scrivendo il compilatore restituirà errore, poiché il valore non può essere un contenitore per

25=x 25

la variabile x.

Le variabili poste a sinistra (L-Value) dell’uguale avranno significato di contenitore, ossia la cella di

memoria a cui quell’alias punta, mentre se scritte a destra (R-Value) avranno il significato di valore

contenuto. Questo comportamento diversificato non potrà più essere supportato da un linguaggio LL(1):

gli interpreti di linguaggi C-like come C++, Java e C# sono infatti LL(2).

Un altro elemento caratteristico di questa famiglia di linguaggi è il concetto di assegnamento distrut-

tivo. Diversamente dalle dimostrazioni matematiche, nelle quali ogni variabile è associata ad un valore che

resta immutato durante tutta la dimostrazione, leggendo un programma che implica assegnamenti distrut-

tivi, questo risulterà impossibile da comprendere senza simularne l’evoluzione. Nasce quindi il concetto di

ambiente (o environment) che, nella sua forma più semplificata, è una tabella a due colonne contenente

il nome e il valore delle variabili definite in un determinato punto del programma. Mentre le operazioni

tradizionali usano l’environment per leggere il valore delle variabili, l’assegnamento modifica l’environment,

aggiungendo una nuova riga alla tabella o, se l’assegnamento è distruttivo, cambiando una riga già esistente.

Questa possibilità di cambiare l’environment, messa a disposizione dai linguaggi imperativi, è data dal fatto

che le celle di memoria sono ad uso di tutti, e pertanto tutti possono cambiarne il valore. Al contrario, per

i linguaggi logici, ciò genera un errore di redefine.

La generazione di environment porta così un programma ad avere environment multipli, i quali per-

mettono di evitare confusione tra i vari blocchi di codice. Ciò può però risultare di dubbia utilità, poiché può

generare fraintendimenti su chi sia il proprietario di una variabile o chi gli abbia assegnato un determinato

valore.

Per introdurre l’assegnamento in un linguaggio occorre quindi stabilire:

• la sintassi dei nomi delle variabili (molti linguaggi differenziano, infatti, gli R-Value dagli L-Value,

come ad esempio Bash che usa il per identificare i R-Value);

$

• se l’assegnamento è distruttivo o meno;

• se la scrittura di assegnamento sia un’istruzione o un’espressione (ossia se è solo un’azione o

x=value

denota anche un valore di ritorno);

• se l’assegnamento restituisce un valore significa che il linguaggio supporta l’assegnamento multiplo.

40

7.1.1 Assegnamento multiplo

L’assegnamento semplice, per propria natura, ha lo scopo di modificare l’environment e non quello di fornire

un risultato. Si dice pertanto che esso ha natura di istruzione. Ciò impone un limite al tipo di assegnamenti

che si possono effettuare in un linguaggio: essi non possono infatti essere posti in cascata.

L’assegnamento multiplo è una proprietà che rende l’assegnamento non più una semplice istruzione di

modifica dell’environment, ma anche una espressione che ha come risultato il valore assegnato alla variabile.

Ciò rende possibili istruzioni come: Analizzando l’istruzione, si nota che:

x=y=3-2-1.

• l’assegnamento è associativo a destra. Infatti, finché non ha assunto un valore, nemmeno potrà

y x

assumerlo;

• l’assegnamento restituisce un valore affinché possa essere assegnato ad x.

7.2 Estensione dell’interprete

Per estendere l’interprete precedentemente ottenuto e per supportare, oltre alle espressioni aritmetiche,

anche gli assegnamenti, occorrerà aggiungere:

• l’espressione di assegnamento e .

ASSIGN ::= ident=EXP EXP ::= ASSIGN

• una nuova produzione per accettare gli identificatori a destra dell’uguale: F ACT OR ::= ident.

• il concetto di variabile nelle sue due interpretazioni di:

– L-Value il nome di variabile indica il contenitore.

x=...:

– R-Value il nome di variabile indica il contenuto.

...=x+2:

Occorre, infine, decidere se adottare, per le due valenze, la stessa sintassi oppure, come nel caso di

Bash, una sintassi differenziata. Sulla base della gerarchia illustrata in § 5.5.2, si introduce quindi una

nuova produzione per : l’espressione di assegnamento, derivante dal nuovo concetto, che associa ad

EXP

un (L-Value) un (R-Value). Ciò genera tre nuovi tipi di nodi nell’albero, ossia tre

IdentExp IdentValExp

nuove classi: (che estende e

AssignExp OpExp), IdentExp IdentValExp.

Risulterà perciò, nel modello delle classi, che la classe sia una specializzazione della

IdentValExp IdentExp

(che a sua volta estende Si tenga tuttavia presente che questo modello, pur essendo l’unico possibile

Exp).

relativamente agli strumenti introdotti finora, non rispetta le definizione di variabile e di assegnamento, in

quanto non è concettualmente corretto definire un’espressione che denoti il valore di una variabile come

specializzazione della variabile generica.

7.2.1 Nuove azioni semantiche

Si vuole ora cercare di capire come si possano modificare i visitor al fine di introdurre e riuscire ad interpre-

tare l’assegnamento. Grazie al pattern stesso, la classe astratta resta inalterata, altrimenti si

ExpVisitor

dovrebbero implementare nuovi metodi anche nelle classi già definite. Si aggiunge quindi una specializzazio-

ne, la classe astratta che definisce un nuovo metodo per ogni classe introdotta

ExpAssignVisitor, visit()

nel modello.

I visitor che si occupano della stampa dell’espressione rimangono pressoché inalterati in quanto, appog-

giandosi alle delle varie classi, il risultato parziale sarà sempre di tipo Il visitor che

toString() String.

calcola il risultato dell’espressione, tuttavia non può rimanere inalterato poiché, con i concetti introdotti, il

risultato può non essere più un numero. Occorre quindi generalizzare il concetto di risultato di un’espres-

sione, al fine di comprendere anche le variabili e rendere il risultato parziale di tipo (ci si occuperà

Object

successivamente di come sarà strutturato). Si dovrà quindi introdurre l’environment: esso può essere im-

plementato come una che memorizzi le coppie variabile-valore e, nativamente, offra

Map<String, Integer>

i metodi per estrarre o scrivere un valore a seconda del lato dell’= in cui si trova la variabile, ossia, quale

classe la rappresenta: per la lettura e per la scrittura.

IdentValExp IdentExp

41

7.3 Verso il compilatore

Risulta a questo punto semplice l’introduzione del concetto di sequenza (espresso dal simbolo Questo

,).

operatore infatti, come tipo di ritorno, presenta solamente il risultato dell’ultima operazione assegnata

sulla base delle operazioni avvenute precedentemente. Considerando ad esempio una volta

x=3,y=4,z=x+y,

assegnato un valore alle variabili, si tiene conto del solo valore finale dell’ultima espressione, ossia quello di

7.

z, Utilizzando le sequenze, la grammatica si appesantisce, a causa dell’aggiunta della regola:

,EXP

EXP ::= ASSIGN ,

si restringe, inoltre, la possibilità alle sole sequenze che contengono una o più assegnazioni e, successivamente,

un’espressione. È opportuno, quindi, creare un nuovo livello che astragga dal concetto di assegnamento ed

espressione. , ossia definito come:

Il contesto suggerisce pertanto la presenza di un livello più astratto di EXP SEQ,

|EXP

SEQ ::= SEQ,EXP

e quindi la ricorsione di richiamerà il nuovo scopo della grammatica:

F ACT OR (SEQ).

F ACT OR ::=

Se si volesse sviluppare un visitor compilatore, basterebbe conoscere la macchina sottostante e generare,

al posto dei risultati, il codice macchina che esegua le stesse operazioni interpretate.

Per un esempio più completo si rimanda a § A. 42

Capitolo 8

Riconoscitori LR

Fino ad ora si è utilizzato, per l’analisi delle grammatiche, l’approccio LL, ossia un approccio top-down che

consente di costruire l’albero sintattico dalla radice alle foglie. Questo metodo si è dimostrato di semplice

utilizzo e, apportando opportune modifiche alla grammatica, si è riusciti a riscrivere quest’ultima in modo

che fosse possibile analizzarla principalmente con un parser ossia un parser che, conoscendo il token

LL(1),

immediatamente successivo a quello analizzato, riesce a definire il contenuto nell’albero sintattico. I parser

in generale, risultano di semplice realizzazione, e possono analizzare un ampio numero di grammatiche

LL(k),

(al più modificando opportunamente le regole della grammatica, al fine di rendere il linguaggio derivante da

questa di tipo LL).

8.1 Proprietà, potenzialità e limiti

I riconoscitori LR sono utilizzati per risolvere una classe di problemi complementare a quella risolta dai

riconoscitori LL. Pur essendo più potenti rispetto ai riconoscitori LL, essi presentano una difficoltà imple-

mentativa e computazionale maggiore, pertanto vengono costruiti solamente nel caso in cui una grammatica

non si possa modificare a piacere e venga ammessa una ricorsione sinistra che manderebbe in loop infinito

un riconoscitore LL.

Il riconoscitore LR si basa su un approccio bottom-up per ricostruire l’albero sintattico. Esso analizza

prima le foglie, quindi risale fino alle radici. Ciò costituisce il vantaggio di questi riconoscitori, i quali non

soffrono più il problema della ricorsione sinistra: essi sanno infatti quando uscire dal loop ricorsivo, poiché

ricostruiscono l’albero direttamente dalle foglie.

I parser in generale, a parità di risolvono una classe di problemi maggiore dei parser

LR(k), k LL(k).

Essendo però i parser di complessa realizzazione, acquistano importanza teorica anche i parser

LR(k) LR(0),

i quali fungono da base per lo sviluppo di un parser completo (spesso ingestibile per le grammatiche

LR(1)

dei tipici linguaggi di programmazione) o le sue versioni semplificate Simple LR SLR e la più completa

LookAhead LR LALR, che comunque non ha la potenza di LR(1).

8.2 Funzionamento

Questo tipo di approccio parte dai token per ricostruire l’albero e, se un token appartiene ad un ramo non

ancora creato, esso viene memorizzato nello stack, in attesa della creazione. Il parser procede nello stesso

modo con i token successivi, fino all’ottenimento di un albero per le frasi corrette o un errore per le frasi

che non fanno parte del linguaggio. Non vi è più alcuna ambiguità nelle grammatiche. Le informazioni

relative alla grammatica, ossia quelle sull’appartenenza di un token ad un determinato ramo, sono dette

informazioni di contesto. Esse dovranno essere gestite opportunamente da un componente detto oracolo.

Le operazioni di un parser, eseguite su indicazione dell’oracolo, sono due:

• Shift: proseguimento della lettura del prossimo token, memorizzandolo nello stack.

• Reduce: costruzione di un pezzo dell’albero senza lettura dell’input.

43

Le uniche componenti per la generazione di un parser LR sono un controller, che si occupa della lettura

e della creazione dell’albero, uno stack, in cui vengono memorizzati gli input e le parti dell’albero, e un

oracolo (risulterà la parte più complessa da realizzare), che assume le decisioni e le comunica al controller.

8.2.1 Analisi top-down vs bottom-up

Un analisi top-down si basa sul riconoscimento dello scopo della frase dalle produzioni che lo compongono

e, da queste, del riconoscimento delle successive produzioni fino al raggiungimento delle foglie (che rappre-

sentano i singoli token). Ciò corrisponde ad una derivazione canonica sinistra, poiché le foglie alla stessa

altezza vengono scritte da sinistra verso destra nell’albero. S

S

S A B

S A B a b

A B A

a b

A B A

S a a

(a) (b) (c) (d) (e)

Figura 8.1: Costruzione dell’albero della frase secondo una grammatica usando un approccio top-down.

aab G L

L’analisi bottom-up ricostruisce l’albero partendo dalle foglie e, in base alle informazioni di contesto,

costruisce le produzioni al contrario. Se non possiede le informazioni necessarie, bufferizza l’input senza

costruire alcun nodo dell’albero. Poiché essa non è una vera e propria derivazione, ma una derivazione

inversa, si parla di riduzione canonica destra. S

A A B A B

A A A A

a a a a a a a a a a

b b b b b

(a) (b) (c) (d) (e)

Figura 8.2: Costruzione dell’albero della frase secondo una grammatica usando un approccio bottom-up.

aab G L

8.2.2 L’informazione di contesto

Il riconoscimento del contesto rappresenta l’operazione più onerosa del parser LR poiché, basandosi sulla

semplice lettura dell’input, deve poter capire come costruire l’albero. Creare un contesto significa pertanto

generare informazioni sufficienti per permettere all’oracolo di stabilire se occorre eseguire un’operazione di

shift o di reduce. Il contesto può essere interpretato come un riassunto delle regole della grammatica rispetto

alla frase che si sta analizzando. L’oracolo dovrà, in base al contesto in cui si trova, capire se quel contesto

è sufficiente per identificare una produzione oppure, se non ha ancora informazioni sufficienti per decidere,

continuare la lettura e la memorizzazione dell’input nello stack.

Esempio 8.1 – Ricorsione sinistra Non avendo ancora affrontato nei dettagli come vengono estra-

polate le informazioni di contesto, si procede in maniera intuitiva. Sia la grammatica:

G

 →

 aAb|aaBba

S →

A Aa|b

G  →

B ε

44

Poiché il simbolo compare in tre possibili produzioni, non è sufficiente leggerlo per capire quale produzione

b

sia quella corretta da usare o se non ve ne sia alcuna. Si assuma, ad esempio, la frase leggendo il primo

abb:

carattere non si può riconoscere in che produzione ci si trova, si effettuerà quindi uno shift.

a

La lettura del carattere successivo essendo preceduto da una sola determinerà che l’unica produzione

b, a,

che possa aver generato sia la produzione e che l’unica produzione a poter generare la singola

b b, a

A

seguita dal meta-simbolo sia lo scopo Leggendo la successiva si concluderà il riconoscimento

aAb. b

A S

e la generazione dell’albero.

8.3 Parser LR(0)

Per studiare le grammatiche di tipo LL, si è partiti dal caso più semplice Il caso più semplice per

LL(1).

i parser LR risulta però risultava infatti inutile poiché non vi era alcuna scelta disponibile,

LR(0), LL(0)

l’approccio LR invece permette scegliere basandosi sulla storia passata, quindi sull’input memorizzato nello

stack.

Generalmente questo genere di parser risolve una classe molto limitata di grammatiche: esso consente

infatti di operare solo dopo aver memorizzato il carattere in input, ma in alcune circostanze ciò non risulta

sufficiente e risulta necessaria una grammatica Si procede quindi al calcolo dei contesti per

LR(1). LR(0)

ogni produzione e, nel caso non siano presenti collisioni (ossia contesti uguali o simili per produzioni

diverse), allora la grammatica risulta riconoscibile dal parser LR(0).

Esempio 8.2 – Grammatica Data la grammatica e i relativi contesti:

LR(0)

 → {aAb}

 aAb,

S

 → {aaBba}

 aaBba,

S → {aAa}

A Aa,

G ,

 → {ab}

 b,

A

 → {aa}

B ε,

non sono presenti collisioni. Infatti, pur essendo presenti prefissi comuni nella 2° e nella 5° produzione (il

prefisso della 5° viene detto prefisso improprio di dopo di essi è presente nella 5° il carattere di fine

S),

stringa, mentre nella 2° è presente un meta-simbolo. Se il meta-simbolo fosse stato un simbolo terminale,

1 essa richiede però

sarebbe stato necessario conoscere il simbolo successivo per comprenderne la produzione;

una produzione già riconosciuta (e quindi salvata sullo stack), pertanto non sussiste ambiguità di percorso

e la grammatica risulta di tipo LR(0).

Supponendo di avere ingresso la frase il parser procede secondo l’ordine che segue, ricostruendo

abab,

l’albero come in Figura 8.3:

• non essendo presenti caratteri nello stack non può assumere alcuna decisione, pertanto effettua uno

shift memorizzando il carattere nello stack;

a

• non essendo presenti contesti contenenti il singolo carattere effettua un altro shift memorizzando il

a,

carattere b;

• viene quindi trovata la produzione di poiché nello stack è presente il contesto riducendo il

ab,

A,

carattere ad

b A;

• non potendo stabilire un contesto di (ossia dai nodi senza radice), esegue quindi un altro shift e si

aA

memorizza a;

• il contesto è presente nella produzione di quindi viene ridotto ad

aAa A, Aa A;

• il contesto è ora Poiché esso non è presente in nessuna delle produzioni, esegue uno shift

aA.

memorizzando nello stack;

b

• il contesto è presente nello scopo Esso verrà pertanto allo scopo e la frase

ridotto accettata.

aAb S. S

L’ultima riduzione prende il nome di accettazione.

1 La comprensione della produzione sarebbe stata possibile solo se la grammatica fosse di tipo LR(1).

45 S

A A

A A A

a a a a a a a a

b b b b b b b b

(a) (b) (c) (d)

Figura 8.3: Albero generato dalla frase abab.

Supponendo ora di avere in ingresso la frase il parser procede secondo l’ordine che segue, ricostruendo

aaba,

l’albero come in Figura 8.4:

• non essendo presenti informazioni nello stack non può assumere alcuna decisione, pertanto esegue uno

shift;

• non essendo presenti contesti contenenti il singolo carattere effettua un altro shift memorizzando il

a,

carattere successivo;

• il contesto viene ridotto a riducendo la stringa vuota. Aggiunge quindi la foglia dopo il

aa B, B

contesto;

• il contesto non è presente, pertanto esegue uno shift;

aaB

• il contesto non è presente, pertanto esegue uno shift;

aaBb

• il contesto viene ridotto ad e la frase accettata.

aaBba S S

B B

a a a a a a a a a

b b b

(a) (b) (c)

Figura 8.4: Albero generato dalla frase aaba.

Nel caso in cui lo scopo sia presente nel lato destro di qualche produzione si genera, per evitare

S →

ambiguità, una produzione di top-level che funga da nuovo scopo e, nel caso sia raggiunto e la

Z S S

2

frase finita, generi senza ambiguità l’accettazione. Si dimostra che tutte le grammatiche dei contesti LR(0)

sono regolari sinistre. Si può quindi ricondurre l’oracolo ad un automa a stati finiti che fa uso di stack

per tenere traccia di quanto è già stato letto e parzialmente ridotto.

8.3.1 Calcolo dei contesti LR(0)

Si pone ora il problema del calcolo dei contesti di una grammatica Per realizzarlo si può operare in

LR(0).

due modi:

• Definire, in modo formale, cosa sia un contesto e applicare tale definizione a tutte le produzioni della

grammatica. Si progetta infine l’automa a stati finiti per riconoscere le frasi di quella grammatica.

• Definire, in modo formale, cosa sia un contesto e realizzare, a livello pratico, un procedimento appli-

cativo per costruire iterativamente l’automa.

2 La quale altrimenti, in una grammatica risulterebbe in sospeso poiché non si può sapere se la frase prosegua o

LR(0),

termini. 46

Il contesto di una produzione è un insieme di stringhe dove è l’insieme di

LR(0) A α γ = βα, β

tutti i possibili prefissi di una qualsiasi forma di frase che usi la produzione all’ultimo passo della

A α

derivazione canonica destra. La conseguenza diretta di questa definizione è che tutte le stringhe hanno la

γ

forma e differiscono solo per il prefisso Formalmente, ciò diventa:

βα, β. ∗ ∗

→ {γ|γ ⇒ ⇒ ∈ }.

LR(0)ctx(A α) = = βα, Z = βAw βαw, w V T

Si definisce insieme dei contesti sinistri l’insieme di tutti i (ossia i soli prefissi variabili della

β

produzione e si indica con leftctx(A). Per definire leftctx(A) è noto che:

A) {ε}),

• Lo scopo per definizione, ha come prefissi la sola stringa vuota (ossia poiché

Z, ε lef tctx(Z) =

lo scopo non viene mai utilizzato nella parte destra delle produzioni.

• Data una produzione i prefissi che si possono presentare davanti ad sono quelli di

B γAδ, A B,

· {γ}).

seguiti dalla stringa (un primo contributo a si ottiene quindi da In

γ lef tctx(A) lef tctx(B)

altre parole, l’insieme è dato da tutti i prefissi delle produzioni che contengono nella

lef tctx(A) A

parte destra, concatenato con i contesti sinistri delle produzioni che la generano.

Esempio 8.3 Sia data la grammatica:  →

 Z S

 → aSAB|BA

S

G ,

 aA|B

A

 → b

B

per ricavare i contesti si procede come segue: {ε}.

• Il prefisso di è la singola stringa vuota:

Z lef tctx(Z) =

• I prefissi di sono tutti i prefissi dove compare a destra della produzione. Le uniche produzioni

S S

→ →

dove compare sono e aSAB:

Z S S

– una parte dell’insieme dei prefissi di sarà l’insieme dei prefissi di ossia la stringa vuota:

S Z,

lef tctx(S) lef tctx(Z);

– l’altra parte dei prefissi di sarà data dal contesto sinistro della produzione che la genera, ossia

S ⊇ · {a}.

seguito dal simbolo terminale a:

S, lef tctx(S) lef tctx(S)

• Dalla stessa produzione si ricavano anche:

aSAB|BA

S

⊇ · {aS} →

– dalla produzione aSAB;

lef tctx(A) lef tctx(S) S

⊇ · {aSA} →

– dalla produzione aSAB;

lef tctx(B) lef tctx(S) S

⊇ · {ε} →

– dalla produzione

lef tctx(B) lef tctx(S) S BA;

⊇ · {B} →

– dalla produzione

lef tctx(A) lef tctx(S) S BA.

• Dalla produzione si ricava che:

aA|B

A

⊇ · {a} →

– dalla produzione aA;

lef tctx(A) lef tctx(A) A

⊇ · {ε} →

– dalla produzione

lef tctx(B) lef tctx(A) A B.

Si può notare come tutti i contesti si comportino come grammatiche regolari necessariamente sinistre: si

avranno i terminali immediatamente precedenti a destra, mentre i delle produzioni che generano

lef tctx

la produzione verranno anteposti ai terminali successivamente. È ora possibile riscrivere i contesti come

grammatica regolare ausiliaria:  ⟨LctxZ⟩ →

 ε

 ⟨LctxS⟩ → ⟨LctxZ⟩|⟨LctxS⟩a

Lctx .

⟨LctxA⟩ → ⟨LctxS⟩aS|⟨LctxS⟩B|⟨LctxA⟩a

 ⟨LctxB⟩ → ⟨LctxS⟩aSA|⟨LctxS⟩|⟨LctxA⟩

47

Risolvendo le equazioni, è possibile ricavare le espressioni regolari dei vari contesti:

 {ε}

 lef tctx(Z) =

 ∗

{a }

lef tctx(S) = ,

∗ ∗ ∗

{(a }

 aS a

lef tctx(A) = + B)a

 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

{a } {a }

aSA a aS a a

lef tctx(B) = + + (a + B)a = (aSA + ε) + (aS + B)a

da queste espressioni dei contesti sinistri, si trovano i contesti aggiungendo i rispettivi suffissi per

LR(0)

ogni produzione possibile:

 → {ε}S {S}

 LR(0)ctx(Z S) = =

 ∗

→ {a

 aSAB) aSAB}

LR(0)ctx(S =

 ∗

→ {a

LR(0)ctx(S BA) = BA} ;

∗ ∗ ∗

→ {(a

 aA) aS a aA}

LR(0)ctx(A = + B)a

 ∗ ∗ ∗

 → {(a aS a

LR(0)ctx(A B) = + B)a B}

 ∗ ∗ ∗

→ {a

b) a b}

LR(0)ctx(B = (aSA + ε)b + (aS + B)a

si noti come i simboli (terminali e non) della grammatica originale diventino i simboli terminali della

grammatica dei contesti.

Occorre ora costruire un RSF che riconosca l’unione di questi linguaggi. In caso esso risulti determi-

nistico (ossia se non esistono conflitti fra i contesti si è realizzato l’oracolo.

LR(0)),

Per realizzare tale automa, si seguono due regole:

• ogni stato finale è etichettato con una produzione, ciò significa che l’oracolo ordinerà una reduce al

controller;

• ogni volta che si è raggiunto uno stato finale, si ordina al controller la reduce, quindi si riparte dallo

stato iniziale:

1. si eseguono i passi secondo quanto presente sullo stack;

2. si ordina una shift per leggere un altro carattere dall’input oppure una reduce se si è giunti in

uno stato finale.

Si ottiene così il diagramma degli stati in Figura 8.5. Esso risulta deterministico in quanto ogni stato

finale è etichettato da una sola produzione e nessuno stato finale ha archi uscenti etichettati da simboli

terminali (il che rende realmente finali gli stati).

B →

Z S

10 a

S a S 3

1 2

b b

B b

B A

b b

→ 5

4 b

B 11

B A B

a b →

→ → aSAB

S

A B S BA a

12 13 15

6

B a

A

→ aA

14 A

Figura 8.5: Automa a stati finiti risultante dall’analisi LR(0).

48

Se si volesse analizzare ora la frase in ingresso si otterrebbe un’evoluzione dello stack come in

abbabb,

Tabella 8.1. Rileggendo lo stack al contrario si deduce che essa è una derivazione canonica destra, pertanto

viene detta riduzione canonica destra. b b

B A B

b a a a

B A A A A

b B B B B S S S S S S S

a a a a a a a a a a a a a S Z

Tabella 8.1: Evoluzione dello stack dato in input la frase abbabb.

8.3.1.1 Miglioramenti

Nel modello computazionale illustrato, ogni volta che si raggiunge uno stato finale si ripercorre l’ASF dallo

stato iniziale. Poiché si hanno già in memoria tutti gli stati raggiunti, sarebbe sufficiente uno stack ausiliario

che memorizzasse lo stato dal quale ripartire una volta che l’oracolo ha raggiunto uno stato finale. Questo

meccanismo realizza l’idea di cache: essa serve a velocizzare l’automa a stati evitando, con memorizzazioni

opportune, di ripercorrere sempre gli stessi stati ricordando il percorso fatto, ripartendo dall’ultimo

stato utile. Questa nuova struttura viene denominata stack ausiliario degli stati.

8.3.2 Condizione LR(0)

Per sapere se una grammatica è analizzabile mediante analisi (ossia non esistono conflitti fra i contesti

LR(0)

delle produzioni) si sfrutta la condizione sufficiente affinché una grammatica sia LR(0):

→ →

Date le due produzioni e con:

A α B ω ∗

∈ → ∈ ∪

• ;

θ LR(0)ctx(A α), θ (V T V N )

∈ → ∈

• ;

θw LR(0)ctx(B ω), w V T

la grammatica è se risulta

LR(0) w = ε, A = B, α = ω.

In altre parole ogni stato di riduzione (ossia lo stato finale) dell’automa ausiliario deve essere etichettato

3

da una produzione unica e non deve avere archi di uscita etichettati da terminali.

Teorema 8.1 Una grammatica analizzabile tramite analisi non è mai ambigua.

LR(0)

8.3.3 Procedimento operativo

L’automa ottenuto tramite i contesti è risultato lungo, complesso e non facilmente meccanizzabile.

LR(0)

Non potendo ignorare la complessità del riconoscitore, si può tuttavia adottare un procedimento operativo

che regolarizzi la realizzazione dell’automa senza calcolare esplicitamente i contesti. I principi alla base di

questo procedimento sono i seguenti: →

• Si parte dalla regola di top-level (dove è usato come convenzione di terminatore di ogni

$

Z S$

frase valida) e si analizzano le situazioni che si presentano:

– si genera ogni situazione di ogni possibile caso chiamato LR item;

– si introduce l’astrazione cursore per indicare la posizione attuale. Essa determina, alla sua

.

sinistra, cosa è già stato analizzato e, alla sua destra, cos’è ancora da analizzare e cosa può essere

analizzato alla prossima lettura;

3 Possono invece presentarsi archi di uscita dati da produzioni, poiché queste sono presenti nello stack, mentre i simboli

terminali, dovendo essere letti, non costituirebbero una grammatica LR(1).

49

– quando una regola ne usa un’altra, ossia un meta-simbolo compare subito a destra del cursore,

la si include nel LR item.

• In conclusione si studiano le possibili evoluzioni, costruendo ogni LR item caso per caso partendo dallo

scopo della grammatica. 8.3, si illustra di seguito lo svolgimento dei primi passi di questo

Basandosi sulla grammatica dell’Esempio

procedimento.

8.3.3.1 LR item 1

Si parte dalla produzione dove si analizzano tutti i casi possibili per ottenere questa produzione. Per fare

Z,

ciò ci si serve delle produzioni intermedie, al fine di ottenere tutte le possibili situazioni che si potrebbero

presentare. Si ottiene quindi il primo LR item, denominato 1:

 →

 .S$

Z → .aSAB|.BA

S

1 .

 → .b

B

Si studiano ora le sue quattro possibili evoluzioni:

• Nel primo caso, se nello stack è presente una troveremo uno stato finale, dato dalla

.S$,

Z S

riduzione Z S$. →

• Nel secondo caso, verrà generato un’ulteriore LR item denominato 2 basato sullo stato

.aSAB,

S

→ a.SAB.

S →

• Nel terzo caso, verrà generato un’ulteriore LR item denominato 4 (per coerenza con

.BA,

S →

l’automa già ottenuto) basato sullo stato S B.A.

→ →

• Nel quarto caso, si andrà direttamente in un nuovo stato finale di riduzione

.b,

B B b.

8.3.3.2 LR item 2

Analizzando ora LR item 2, esso si può descrivere come:

 →

 a.SAB

S → .aSAB|.BA

S

2 ,

 → .b

B

e presenta quattro alternative:

• Nel primo caso, sarà presente una produzione che porterà alla generazione di un nuovo LR item

S

denominato 3, basato sullo stato aS.AB.

S

• Nel secondo caso, sarà presente nello stack una che porterà nuovamente nella situazione iniziale di

a,

questo stato.

• Nel terzo caso, si otterrà, come in precedenza, LR item 4.

• Nel quarto caso, si andrà nello stato finale di riduzione b.

B

8.3.3.3 LR item 4

LR item 4 è descritto come:  →

 S B.A

→ .aA|.B

A

4  → .b

B

e avremo quattro alternative:

• Nel primo caso, sarà presente la produzione e si trova una riduzione con la definizione di un nuovo

A

stato finale S AB. 50

• Nel secondo caso, sarà presente il carattere e si otterrà un nuovo LR item 6 basato sullo stato

a

→ a.A.

A →

• Nel terzo caso, sarà presente la produzione e si andrà in un nuovo stato finale di riduzione

B A B.

• Nel quarto caso, sarà presente il carattere e si andrà nello stato finale

b b.

B

8.3.3.4 Considerazioni

Come è possibile notare, le alternative rappresentano le frecce dell’automa, gli item LR rappresentano gli

stati di transizione e gli stati finali sono ottenuti dalle riduzioni possibili. Ad ogni freccia corrisponderà

uno shift (se l’arco contiene un terminale), un goto (ossia una lettura da stack) se l’arco contiene un

meta-simbolo e, ad ogni stato finale, una reduce (con il caso particolare della accept nello stato Z S$).

Questo procedimento, estremamente lungo per essere svolto dall’uomo, risulta ideale per essere eseguito da

una macchina: può essere infatti realizzato un programma che, tramite cicli iterativi e ricorsioni, automatizzi

il processo di generazione. Per questo motivo, il procedimento operativo è quello usato per generare gli oracoli

LR(0).

8.3.4 Costruzione parser LR(0)

Per costruire il parser, si costruisce la tabella di parsing LR. Essa è una tabella nella quale ogni cella

contiene l’indicazione dell’azione da compiere: shift, goto, reduce, accept (oltre alle indicazioni accessorie

necessarie al proseguimento).

La notazione adottata per i quattro comandi è:

• s5 per indicare all’automa di eseguire uno shift e portarsi nello stato 5;

• g5 per indicare all’automa di eseguire un goto e portarsi nello stato 5;

• r5 per indicare all’automa di eseguire una reduce usando la produzione numero 5, riportarsi allo stato

iniziale e seguire i cambiamenti di stato utilizzando i simboli posti sullo stack;

• a per indicare all’automa di accettare la frase e terminare.

Sfruttando i nomi degli stati dell’automa introdotti in Figura 8.5 e assegnando i nomi alle produzioni

come  →

 b

1. B

 →

 2. A B

3. S BA

 →

 aA

4. A

 → aSAB

5. S

8.2.

si ottiene la tabella di parsing in Tabella

1 2 3 4 5 6 10 11 12 13 14 15

s2 s2 s6 s6 s6 r1 r2 r3 r4 r5

a s11 s11 s11 s11 s11 s11 r1 r2 r3 r4 r5

b a r1 r2 r3 r4 r5

$ g10 g3

S g5 g13 g14

A g4 g4 g12 g12 g15 g12

B Tabella 8.2: Tabella di parsing dell’automa LR(0).

51

8.3.5 Controesempio

Data la grammatica  →

 Z E

→ +E|T

E T

G  → a

T

e calcolando i contesti  →

 LR(0)ctx(Z E) = E

 ∗

→ +E) +) +E

LR(0)ctx(E T = (T T

 +)

(T T

LR(0)ctx(E T ) =

 ∗

→ a) +) a

LR(0)ctx(T = (T

risulta evidente come nel 2° e 3° contesto vi sia un conflitto mostrando come in questo caso una grammatica

non sia sufficiente per evitare ambiguità. Esso non potrà mai essere risolto in quanto l’automa non

LR(0)

può leggere il simbolo successivo (come invece accade nelle grammatiche e non può sapere se eseguire

LR(1))

uno shift o una reduce, avendo salvato nello stack una serie di simboli coerenti con l’espressione regolare

∗ . Si otterrà quindi nell’automa uno stato che è sia finale, sia di transito, pertanto l’automa stesso

+)

(T T

non potrà essere deterministico.

8.4 Verso l’analisi LR(1)

Si è appena visto come le grammatiche risultino molto utili per generare automi deterministici. Allo

LR(0)

stesso tempo però, esse non sono adatte a tutte le grammatiche, poiché alcune richiedono di conoscere il

simbolo terminale successivo non ancora letto. Si cerca quindi di descrivere come giungere alla grammatica

(senza prestare eccessiva attenzione allo svolgimento dei calcoli).

LR(1)

8.4.1 Definizione →

Formalmente, il contesto di una produzione è definito come:

LR(k) A α

∗ ∗

→ {γ|γ ⇒ ⇒ ∈ ∈ }.

k

LR(k)ctx(A α) = = βαu, Z = βAuw βαuw, w V T , u V T

Tutte le stringhe del contesto della produzione si presentano nella forma Esse

LR(k) A α βαu.

differiscono per il prefisso e per la stringa La stringa appartiene all’insieme delle

β u. u F OLLOW (A)

k

stringhe di lunghezza che possono seguire il simbolo non terminale di

k A.

Nel caso specifico dell’LR(1) (ossia quello di interesse), non è altro che l’insieme dei

F OLLOW (A)

1

following symbol dell’analisi LL. Ogni stato dell’automa andrebbe arricchito con tante frecce quanti

LR(0)

sono i simboli terminali della grammatica, portando quindi in altri nuovi stati.

8.4.2 Considerazioni

Potenzialmente una grammatica con simboli terminali e meta-simboli può portare ad un diagram-

LR(k) t n

4

− · k

ma degli stati di stati. L’algoritmo per la generazione della tabella di parsing, tuttavia, resta

(n 1) t

invariato. Esso deve solamente tenere in considerazione il carattere che potrà leggere successivamente ed

aggiungere molti più stati, ma sempre secondo lo stesso metodo (seppur opportunamente esteso) dell’LR(0).

Ciò che rende la progettazione onerosa è il chiedersi, per ogni stato, quale simbolo terminale potrebbe

seguire in ingresso per mantenere la frase valida, quindi generare una nuova freccia e, se necessario, aggiungere

altri stati. In questo contesto, anche il procedimento operativo diventa complesso da definire. Per questi

motivi, nonostante risultino utili, le macchine vengono progettate solo in caso di stretta necessità.

LR(1)

Si ricerca pertanto una soluzione intermedia tra l’LR(0), che limita in maniera importante le grammatiche

gestibili, e l’LR(1), che analizza in maniera eccessivamente dettagliata l’input, generando un oracolo oneroso

da progettare.

4 Per questo motivo verranno presentati esempi molto limitati di questa tipologia di grammatica.

52

8.5 Approssimazioni del contesto LR(1)

Storicamente si sono spesso utilizzate tipologie semplificate dell’LR(1), le quali hanno permesso di non dover

rinunciare alle potenzialità di tale contesto, ma evitando totalmente i suoi onerosi costi di progettazione. I

due modelli, sviluppati con l’obiettivo di risparmiare sul numero degli stati (secondo modalità differenti),

sono SLR e LALR.

8.5.1 Parser SLR

A differenza dell’LR(1), che determina quale carattere può seguire dopo una certa sequenza di caratteri già

letti, il parser SLR definisce quali caratteri possono seguire successivamente, senza curarsi della porzione di

frase letta fino a quel punto. Ciò permette di risparmiare gli onerosi calcoli dell’LR(1), il quale dovrà essere

usato solo nel caso peggiore, ossia quello in cui sono ancora presenti dei conflitti.

Il contesto di una produzione è definito come:

SLR(k) A α

→ → ·

SLR(k)ctx(A α) = LR(0)ctx(A α) F OLLOW (A)

k

e può quindi essere calcolato facilmente a partire dal contesto Il contesto ottenuto mediante questa

LR(0).

metodologia risulta essere un soprainsieme del contesto ma che è possibile adottare nel caso non

LR(1),

siano presenti conflitti nelle produzioni. Queste sono date dai contesti spuri, ossia i contesti aggiuntivi

generati dal metodo SLR rispetto al parser i quali entrano in conflitto con contesti corretti di altre

LR(1),

produzioni.

Esempio 8.4 Riprendendo la grammatica introdotta in § 8.3.5 ed i relativi contesti:

 →

 LR(0)ctx(Z E) = E

→ 

 Z E ∗

→ +E) +) +E

LR(0)ctx(E T = (T T

→ +E|T

E T ,

G ,

 +)

LR(0)ctx(E T ) = (T T

→ 

a

T ∗

→ a) +) a

LR(0)ctx(T = (T

calcolando i contesti SLR, il simbolo risulta ora evidenziato, perché per il calcolo dei contesti SLR si

$

considerano anche i simboli che seguono (e non più solo i prefissi). Risulta quindi:

 →

 SLR(1)ctx(Z E) = E

 ∗

→ +E) +) +E$

SLR(1)ctx(E T = (T T .

 +) $

SLR(1)ctx(E T ) = (T T

 ∗

→ a) +) a($|+)

SLR(1)ctx(T = (T

Essendo stato aggiunto il terminatore, le due produzioni risultano ora non più conflitto, e la grammatica

risulta analizzabile con il contesto Non è quindi necessario ricorrere alla progettazione del parser

SLR(1).

poiché la mancanza di un controllo minuzioso non ha generato conflitti. Come è possibile notare

LR(1),

dall’automa a stati in Figura 8.6, infatti, l’aggiunta dello stato 2 rispetto all’automa non deterministico

LR(0)

permette al parser di sfruttare il prossimo simbolo al fine di determinare lo stato successivo senza alcuna

ambiguità di percorso. → →

→ Z E E T

Z E $

E

E +

+ $

T E

T E →

3 5

1 2 +E

→ → E T

3

1 +E

E T E T a T

T

a a

a → 4

a

→ T

a

T $,+

(a) (b)

Automa originario. Automa SLR.

LR(0)

Figura 8.6: Automa a stati finiti risultante dall’analisi (si noti come questa analisi porti alla generazione di

SLR(1)

stati inutili come il 4 e il 5). 53

8.5.1.1 Procedimento operativo

Il procedimento operativo si basa sull’analisi dell’automa quindi sulla rimozione delle ri-

SLR(1) LR(0),

duzioni che, sfruttando il lookahead, risultano incompatibili. Sfruttando la possibilità di poter analizzare

anche i caratteri successivi risulta possibile semplificare l’automa: si eliminano le celle incompatibili con la

realtà corrente, ossia con la conoscenza del prossimo simbolo.

8.5.2 Parser LALR

Il parser LALR nasce dall’esigenza di trovare un’alternativa al parser SLR: se anche quest’ultimo generasse

dei conflitti dati dai contesti spuri, infatti, si dovrebbe ricorrere al parser pertanto si affronta un’altra

LR(1),

approssimazione di quest’ultimo.

Questa nuova logica si basa sul concetto di similitudine fra stati, poiché molti stati dell’LR(1) sono infatti

distinguibili solamente per i simboli futuri. Il parser LALR, così denominato poiché ignora le differenze

sui simboli LookAhead del parser LR, si basa sul collasso degli stati che sono indistinguibili per un solo

simbolo futuro, confidando nel fatto che non si presenti il caso che li distingue in un secondo momento.

54

Capitolo 9

Processo computazionale iterativo e

ricorsivo

A partire dai primi linguaggi di programmazione esistenti, per realizzare le funzioni più semplici è risultato

utile utilizzare l’iterazione e, successivamente, la ricorsione. Questi due strumenti non sono legati al lin-

guaggio di programmazione usato, bensì ai modelli computazionali generati dalla loro esecuzione. Si cer-

cherà quindi di fornire una loro definizione indipendente dal linguaggio di programmazione, e di riconoscere,

indipendentemente dall’implementazione, cosa caratterizza e differenzia i due modelli computazionali.

9.1 Iterazione

Nei linguaggi imperativi, il costrutto linguistico che esprime un processo computazionale iterativo è, in

generale, il ciclo. Un ciclo è un modello generico che rispetta determinate caratteristiche:

accumulatore;

• esiste sempre una variabile che funge da

• questa variabile è inizializzata prima del ciclo (tipicamente al valore neutro dell’operazione che si

eseguirà su di essa) e modificata nel ciclo stesso;

• al termine del ciclo, l’accumulatore conterrà il risultato dell’iterazione.

Il processo iterativo computa quindi in (ossia, al passo l’accumulatore conterrà l’n-esimo

avanti n-esimo

risultato parziale calcolato).

Durante l’iterazione, l’accumulatore contiene quindi un risultato parziale dell’iterazione. Questa è la

principale caratteristica che identifica l’iterazione, ed è basata sul concetto di assegnamento distruttivo.

Senza di esso risulterebbe infatti impossibile ottenere un’entità che, ad un determinato ciclo fornisca il

n,

risultato parziale è pertanto necessario sovrascrivere il valore precedente. In generale l’iterazione,

n-esimo:

all’interno di un programma, genera confusione, poiché non è possibile capire dal codice (a meno di non

simularne pazientemente l’andamento) il suo flusso di valori interni. I linguaggi dichiarativi, pur simulando

l’iterazione e non ammettendo l’assegnamento distruttivo, non la supportano.

9.2 Ricorsione

Il concetto di ricorsione è più recente del concetto di iterazione e, a differenza di esso, è sempre descritto

tramite l’uso di funzioni ricorsive. Esso è basato su:

• assenza di un accumulatore; −

• la chiamata ricorsiva ottiene il risultato parziale (n 1)-esimo;

• il corpo della funzione ricorsiva opera sul risultato per ottenere il risultato

(n 1)-esimo n-esimo.

Il processo ricorsivo computa quindi all’indietro (ossia, l’ultima funzione invocata conterrà il primo risultato

parziale, e la prima invocata conterrà il risultato finale).

55

9.3 Differenze tra i modelli computazionali

Stabiliti i modelli computazionali di iterazione e ricorsione, se ne analizzano ora le principali differenze:

• mentre l’iterazione aggiorna un risultato parziale, la ricorsione non ne fa uso e sintetizza nuovi valori

sullo stack anziché sovrascriverlo;

• se si interrompe la ricorsione non si ha un risultato parziale poiché, fintanto che non si eseguono tutte

le chiamate ricorsive, non verrà assegnato alcun valore alle variabili nello stack;

• un’iterazione, per definizione, non potrà mai costituire una ricorsione, mentre una funzione ricorsiva,

manipolata opportunamente, può essere usata per simulare un’iterazione.

9.4 Iterazione simulata tramite ricorsione

Per definizione, la ricorsione viene sempre identificata con una funzione ricorsiva, ma non è sempre vero

che una funzione ricorsiva esprima il modello computazionale di ricorsione. Se una chiamata ricorsiva viene

opportunamente modificata può infatti generare un modello computazionale iterativo. Le modifiche da

apportare sono:

• la chiamata ricorsiva è l’ultima istruzione eseguita dalla funzione;

• il risultato viene calcolato alla chiamata e passato come parametro alla funzione

k-esimo k-esima

successiva.

In questo caso il modello computazionale è inverso rispetto a quello ricorsivo: se si ferma infatti la ricorsione

ad una chiamata essa conterrà il risultato parziale conformandosi alla definizione di iterazione.

k, k-esimo,

Si parla quindi di tail-recursion. Tale ricorsione, pur utilizzando sempre lo stack per memorizzare le

1

variabili, potrebbe sovrascrivere lo stack della funzione ricorsiva precedente, in quanto contiene ugualmente,

nei suoi parametri, un risultato parziale per calcolare il risultato parziale successivo. Sarà tuttavia

necessario passare anche l’indice dell’iterazione al fine di tenere traccia dell’avanzamento (la computazione

avviene in avanti). Questo tipo di ottimizzazione è denominata Tail-Recursion Optimization TRO.

Computazionalmente la TRO è identica al modello computazionale iterativo, e consente anche ai lin-

guaggi dichiarativi di simulare l’iterazione. In tutti i linguaggi che non esprimono esplicitamente l’idea di

ciclo questa ottimizzazione ricorsiva è implementata.

Un programma viene definito iterativo o ricorsivo a seconda del suo processo computazionale. Si definisco-

no modelli computazionali iterativi quelli la cui immagine a runtime definisce un’iterazione, mentre

si definiscono computazionalmente ricorsivi quelli che, a runtime, generano una ricorsione.

Esempio 9.1 – Il linguaggio Scala Nella JVM non esegue unicamente il linguaggio Java, ma anche

Scala, un linguaggio blended, ossia ibrido. Essendo ibrido, esso può decidere di procedere in modo impe-

rativo o dichiarativo. Il compilatore Java produce solo bytecode imperativo, mentre quello di Scala, di

default, intercetta la tail-recursion e la ottimizza. È possibile disabilitare quest’ottimizzazione con l’opzione

quindi utilizzare il disassemblatore per confrontare il bytecode di un programma

-g:notailcalls, javap -c

con (codice di sinistra) e senza la TRO (codice di destra):

1 In generale, ciò è implementato nei linguaggi dichiarativi più usati.

56

1 iload_2 1 iload_2

2 iload_3 2 iload_3

3 if_icmple 7 3 if_icmple 9

4 iload_1 4 iload_1

goto

5 ireturn 5 20 // ireturn

6 iload_2 6 aload_0

7 iload_1 7 iload_2

8 imul 8 iload_1

9 iload_2 9 imul

10 iconst_1 10 iload_2

11 iadd 11 iconst_1

12 iload_3 12 iadd

13 istore_3 13 iload_3

14 istore_2 14 invokevirtual #16 // Invocazione di

15 istore_1 funzione

goto

16 0 15 ireturn

È possibile notare come l’invocazione della funzione sia sostituita da un semplice con aggiornamento

goto

dei valori sullo stack.

9.4.1 Guadagni della TRO

In termini di guadagno, la TRO risparmia, rispetto alla ricorsione semplice, circa il in termini di tempo

20 %

d’esecuzione, e presenta un guadagno ancora più consistente nell’occupazione di circa il in meno dello

60 %

stack. 57

Capitolo 10

Basi di programmazione funzionale

Storicamente i linguaggi funzionali erano considerati una minoranza e non integrabili con il moderno mondo

della programmazione imperativa. Nell’ultimo decennio, tuttavia, sono state introdotte nei linguaggi più

utilizzati (come Java, C# e C++) funzionalità nate proprio nei linguaggi funzionali.

10.1 Funzioni come first-class entities

La quasi totalità dei linguaggi di programmazione consente di passare funzioni come parametri ad altre

funzioni, ma non tutti i linguaggi trattano le funzioni come tipi di dato (come gli interi o i caratteri). C,

ad esempio, definisce le funzioni come blocchi di codice i quali, in quanto tali, rimangono confinati nella

parte di codice del programma e non nell’area dati. Questa separazione, essenziale per mantenere robusto

il linguaggio, rende le funzioni delle second-class entities, ma al contempo causa genericità, come la

necessità di introdurre il tipo generico per eludere il type-checker.

void*

Affinché le funzioni siano first-class entities esse devono poter essere:

• assegnate a variabili (di tipo funzione);

• passate come argomento ad altre funzioni;

• restituite come risultato da un’altra funzione;

• definite e usate come ogni altro valore, anche al volo;

• usate anche senza che sia loro assegnato un nome.

In Java i metodi sono sempre parte di un oggetto e definiti in una classe che li implementa. Se si vuole

assegnare un metodo ad un pulsante, è necessario creare un classe che implementi una determinata interfaccia

come Tale interfaccia deve quindi sovrascrivere un determinato metodo che incapsuli il

ActionListener.

codice da eseguire: si passa pertanto l’oggetto contenente il metodo, e non il metodo stesso.

Questo problema era stato reputato inizialmente marginale, ma successivamente si è notato come il rende-

re le funzioni delle first-class entities riduca drasticamente la quantità di codice necessario per lo svolgimento

di un compito oggi tra i più comuni.

I linguaggi funzionali possono iniettare, come comportamento, una funzione in un oggetto, diversa-

mente da Java dove si incapsula tutto in un oggetto, poiché le funzioni possiedono una definizione soltanto

all’interno di una classe come suoi metodi. Questo cambiamento non porta ad un effettivo cambiamento

delle potenzialità del linguaggio, ma permette una notevole riduzione della quantità di codice necessario per

raggiungere lo stesso scopo.

Nei linguaggi funzionali, infatti, le funzioni sono un tipo di dato e vengono memorizzate nella parte dati

del programma. La conseguenza più immediata di questo fatto è che, essendo la parte di dati modificabile

a runtime, non è possibile conoscere a tempo di compilazione l’intero codice di tale programma, poiché è

possibile iniettarvi codice tramite i dati stessi.

Java introduce un supporto parziale alle funzioni come first-class entities solo in Java 8 grazie alle lambda

expressions: esse possono essere definite come literal e passate come argomenti. Esse non definiscono

tuttavia un tipo vero e proprio, ma sono espresse tramite interfacce funzionali. C# utilizza i delegati ed il

58

costruttore JavaScript nasce invece come linguaggio debolmente tipizzato, ed utilizza da sempre

Func<...>.

il costruttore e la keyword per specificare funzioni anonime. Poiché questo linguaggio

Function function

rappresenta uno degli strumenti di programmazione più potenti verrà preso ad esempio ed analizzato nel

dettaglio.

10.2 JavaScript come linguaggio funzionale

Pensando ad una funzione come oggetto, in un linguaggio ad oggetti, bisogna determinarne il tipo, chi può

generarlo e come attivarne il codice contenuto. In Java le lambda expression non permettono certi costrutti,

poiché risulterebbero di difficile gestione da parte dei programmatori. Ad esempio, le variabili passate

come parametro alle lambda expressions possono essere di sola lettura: se questa restrizione non ci fosse si

formerebbero pericolose condizioni di sincronizzazione nell’accesso in scrittura, cosa di per sé dannosa per

la parte dati della memoria, ancora di più se questa viene a verificarsi su una variabile che contiene codice

da eseguire successivamente.

10.2.1 Funzioni in JavaScript

Le funzioni in JavaScript:

• Sono di tipo function.

• La keyword definisce oggetti-funzione. Ciò permette di dichiarare funzioni anonime poiché,

function

se queste sono un tipo di dato, possono essere assegnate ad una variabile ed usate come “valore-

funzione”: var function return

1 f = (z) { z * z }

• Una funzione può riceverne un’altra come argomento:

var function return

1 ff = (f, x) { f(x) }

Questa è una factory di funzioni, a cui associa parametri variabili.

• È possibile passare una funzione che incrementa una variabile dichiarata al suo esterno come argomento

a un’altra: function

1 loop( (z) { i++ }, 10) ()

• È possibile restituire un risultato-funzione:

var function return function return

1 f = (z) { (r) { r + 10 } }

Richiamando la funzione si ottiene un oggetto-funzione che, se eseguito, incrementa una variabile

assunta da esso in ingresso.

• È possibile creare una nuova funzione a partire da una stringa:

var new

1 square = Function ("x", " return x*x")

Ciò implica che, passando delle variabili lette da input, è possibile generare codice da tastiera. Questa

funzionalità, per quanto potente, risulta però anche molto pericolosa, perché permette di generare

codice non testato e non compilato (motivo per cui, in Java, questa scelta non è stata fatta).

10.3 Chiusure

Con l’aggiunta del tipo di dato funzione, i linguaggi che lo implementano devono quindi gestire questo tipo

di dato, con le potenzialità e le criticità che esso comprende.

Un primo problema che si pone è come tipizzare le funzioni, questo risulta impossibile nei linguaggi

fortemente tipizzati poiché richiederebbe di specificare ogni singola tipologia di funzione dichiarabile (per

59

questo nei linguaggi di questo tipo si tende solo ad approssimare la funzione a un vero e proprio tipo di

dato). In linguaggi debolmente tipizzati questo problema non si pone, poiché non si pretende una definizione

esaustiva del tipo di dato e si rendono così le funzioni implementabili come vere e proprie first-class entities.

Promuovendo le funzioni a first-class entities, poiché queste possono essere generate da altre funzioni e usare

variabili della funzione generatrice, non è più possibile usare lo stack, perché queste variabili verrebbero

deallocate terminata la funzione generatrice. I linguaggi che implementano le funzioni come first-class

entities, infatti, utilizzano obbligatoriamente l’heap per evitare la deallocazione delle variabili.

Le funzioni come first-class entities permettono di rappresentare uno stato privato e nascosto continuando

a tenere vive variabili della funzione “esterna” che le ha definite, permettendo quindi di creare una comu-

nicazione nascosta. La possibilità di passarle come parametri permette inoltre di creare nuove strutture di

controllo o migliorare API esistenti con interfacce semplificate.

Un secondo problema da affrontare è quello della chiusura di una funzione, cioè dell’ambiente di varia-

bili visto all’interno di essa. Poiché una funzione può usare variabili non dichiarate nel suo corpo, è necessario

stabilire quale variabile con lo stesso nome verrà modificata o utilizzata dalla funzione, determinando quindi

il criterio di visibilità delle variabili esterne denominato criterio di chiusura.

10.3.1 Criteri di chiusura

Un altro problema da affrontare quando si crea il tipo di dato funzione, deriva dalla capacità di modificare

variabili dichiarate al di fuori di esse. Allo stesso tempo è necessario stabilire il criterio di visibilità delle

variabili dichiarate fuori dalla funzione, al fine di definire quale variabile verrà modificata da essa.

10.3.1.1 Catena lessicale

Nella chiusura a catena lessicale l’ambiente di variabili è dato dal testo del programma: la variabile scritta

immediatamente prima sarà quella a venire modificata.

var

1 x = 20

function return

2 provaEnv (z) { z + x }

3 function

4 testEnv () {

var

5 x = -1;

return

6 provaEnv (18)

7 }

La funzione a cui è applicata una catena lessicale, restituirà il valore poiché all’interno

provaEnv(18), x,

38,

della funzione, verrà vista come la variabile dichiarata immediatamente prima nel testo del programma e

non si seguirà pertanto l’ordine di esecuzione. Per quanto questa logica non segua il corso del programma,

risulta la più comoda e la più usata dai linguaggi che supportano chiusura, in quanto facilita il debug, senza

dover simulare il programma per identificare qual è il valore della variabile, in più la funzione è resa statica

poiché non dipende più dal contesto in cui è chiamata ma solamente da dove è dichiarata nel programma.

10.3.1.2 Catena dinamica

In un linguaggio che implementa la chiusura a catena dinamica, l’ambiente è dato dal flusso di esecuzione

del programma, e le variabili più vicine sono quelle che vengono dichiarate per ultime nel ciclo d’esecuzione

del programma.

La stessa funzione definita in § 10.3.1.1, valutata in catena dinamica, darà come risultato poiché nel

17,

flusso di esecuzione l’ultima variabile con alias x a venir dichiarata è Questa tipologia di catena

var x = -1.

rispecchia l’andamento logico del programma ed è anche il più facile da gestire a livello macchina, tuttavia

risulta illeggibile dal programmatore in quanto la funzione cambia il suo risultato a seconda dei contesti di

utilizzo. 60

10.3.2 Chiusura nei linguaggi più comuni

Storicamente, nessun linguaggio imperativo è nato supportando la chiusura, ma molti di essi negli anni

hanno sviluppato tecnologie per supportarla o al più rendere i loro paradigmi simili ad essa:

• C: non supporta chiusura e usa lo stack per allocare memoria alle funzioni. L’unico modo per innestare

comportamento è quello di passare a una funzione un per indicarne un tipo generico, e la funzione

void*

dovrà comunque conoscerne la signature.

• Java: pur non ammettendo la tipizzazione di funzioni, ammette le più limitate lambda expression.

In questi pseudo-tipi funzione l’accesso alle variabili esterne è solo in lettura, scelta fatta dagli svilup-

patori di Java poiché lasciare il libero arbitrio al programmatore non esperto nel gestire le scritture

(specie nei programmi multithreading) risultava estremamente delicato, e se avessero sviluppato un

livello software per devolvere il tutto alla JVM, si sarebbero ottenute situazioni di deadlock senza

potervi mettere mano. Le lambda expression in Java si definiscono con la sintassi:

return

1 (int x) -> { x + 1; } // Versione completa

2 (int x) -> x + 1; // Funzione a singola espressione

3 x -> x + 1; // Funzione a singola operazione e singolo argomento

Si può dichiarare una variabile lambda expression in base al tipo di ritorno e ai parametri come:

1 IntFunction <Integer > h = (int x) -> x + z;

Le variabili esterne come devono essere trattate come anche se il compilatore consente di

z final,

ometterlo nella definizione, le variabili esterne non possono essere modificate all’interno delle lambda

expressions.

• C#: adotta i delegati, che rappresentano una forma blanda del tipo funzione, tuttavia anch’esso non

supporta la piena chiusura, ma ne simula il comportamento.

int int

1 { x, y => x + y; } // Funzione a più argomenti

int

2 { x => x+1; } // Funzione a singola operazione e singolo argomento

• Scala: si basa sulla stessa Virtual Machine di Java, tuttavia supporta la chiusura e quindi offre funzioni

come first-class entities grazie a uno strato software gestito ad hoc che genera classi e interfacce per

renderlo possibile. La notazione per creare un oggetto funzione in Scala è (params) => body.

• JavaScript: essendo object-based, include le funzioni come oggetti di tipo e istanziabili dal

function

costruttore utilizzabile anche autonomamente per sintetizzare funzioni a runtime. Oltre ad

Function,

essere oggetti, le funzioni sono anche eseguibili, evocandole tramite parentesi e lista di parametri (al

più vuota).

10.4 Modelli computazionali per la valutazione di

funzioni

Un argomento non ancora preso in considerazione, che spesso viene dato per scontato, è il come valutare

una funzione una volta dichiarata e inserita all’interno del codice. Ogni linguaggio che introduca funzioni

deve prendere un modello computazionale per la loro valutazione. Questo modello deve stabilire:

• quando si valutano i parametri;

• cosa si passa alla funzione;

• come si attiva la funzione.

10.4.1 Modello applicativo

Tradizionalmente questo è il modello più usato e si basa sul:

61


PAGINE

104

PESO

515.28 KB

PUBBLICATO

5 mesi fa


DESCRIZIONE APPUNTO

Conoscenze e abilità da conseguire
Introduzione al rapporto fra linguaggi e progettazione a livello algoritmico e sistemistico. Metodi per la definizione della sintassi e della semantica dei linguaggi di programmazione e di specifica e analisi dei relativi modelli computazionali. Tecniche di riconoscimento e valutazione.

Programma/Contenuti
Fornire una descrizione ragionata sui concetti essenziali dei linguaggi di programmazione, correlandoli ai diversi modelli computazionali alla base dei diversi linguaggi e al problema del loro riconoscimento. Analizzare l'impatto dei diversi linguaggi e modelli sulla produzione del software medianti esempi comparati in diversi stili. Introduzione ai formalismi delle Reti di Petri e dei linguaggi fondazionali. Contenuti di dettaglio: Descrizione formale e implementazione dei linguaggi: grammatiche formali e loro proprietà, classificazione di Chomsky. Relazione fra grammatiche e automi riconoscitori. Analisi lessicale e tecniche di analisi sintattica top-down e bottom-up per linguaggi regolari e context-free. Cenni sulla descrizione formale della semantica. Organizzazione e costruzione di interpreti e compilatori e relativi supporti a tempo di esecuzione: architettura ed esempi concreti in Java. Strumenti semi-automatici per la generazione di analizzatori lessicali e sintattici. Introduzione agli stili di programmazione non imperativi: cenni al linguaggio Prolog come possibile caso di esempio di analisi lessicale, sintattica, e di costruzione di interpreti e compilatori in stile non imperativo. Programmazione multi-paradigma e multi-linguaggio: Javascript come esempio di linguaggio dinamico, funzionale e a oggetti basato su prototipi; Scala come esempio di linguaggio blended su piattaforma Java. Cenni al lambda calcolo.


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria informatica
SSD:
Università: Bologna - Unibo
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher piscoTech di informazioni apprese con la frequenza delle lezioni di Linguaggi e Modelli Computazionali M e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Bologna - Unibo o del prof Denti Enrico.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea magistrale in ingegneria informatica

Domande di Teoria di Sicurezza dell'Informazione
Appunto
Appunti di Sicurezza dell'Informazione
Appunto