Appunti di Linguaggi e Modelli Computazionali

(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