Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
K
• →
Lookahead propagato: b si dice propagato se i = [A α.β, b]. Quindi b è nel lookahead perché
K
faceva parte del lookahead di i .
K
Il simbolo # viene utilizzato per mostrare in maniera piiù chiara quando viene generato un lookahead spontaneo,
ma non è un simbolo della grammatica e non ha altre funzioni specifiche. L’algoritmo di generazione dei
→
lookahead per ogni item i = A α.β del kernel K di un itemset I è il seguente:
1. Calcolo J = closure(i, #)
→ ∈ ̸
2. se [B γ.Xδ, a] J e a = #, allora a è generato spontaneamente.
→ ∈ →
3. se [B γ.Xδ, #] J propago il lookahead da i in I a B γX.δ in goto(I, X).
3.10.2 Costruzione dei kernel LALR(1)
La costruzione dell’automa LALR(1) avviene nei seguenti step:
1. Calcolo i kernel LR(0) e li inserisco nella tabella.
2. Applico l’algoritmo di calcolo dei lookahead ai kernel ed inserisco i risultati in una colonna init.
3. Continuo ad applicare l’algoritmo dei lookahead aggiungendo colonne finché non ottengo due colonne senza
modifiche.
3.10.3 Costruzione tabella FROM-TO
Nella tabella from-to vengono riassunti i risultati delle closure laddove sono possibili delle goto La tabella
FROM-TO viene calcolata nel seguente modo:
nei kernel, calcolo closure([item #]). ATTENZIONE: c’è una riga per
1. Per ogni item from from,
item
ogni item e non una per ogni itemSet.
2. Per ogni item tra gli item della closure con puntatore non alla fine del corpo e con # nel lookahead,
item to
inserisco nella tabella una riga [FROM: (i: TO: (j: dove:
item from), item to)]
• i è l’indice dell’itemset contenente item from.
• j è l’indice dell’itemset contenente con punto shiftato di una posizione.
item to
Ciò perché la presenza del cancelletto nell’item indica che il lookahead di viene propagato
to item from
a Nella tabella FROM-TO andiamo proprio a tenere traccia delle propagazioni.
item to. 15
3.10.4 Costruzione tabella SET-INIT
La tabella SET-INIT viene calcolata nel seguente modo:
• Calcolo la colonna init nel seguente modo:
$
1. Inserisco nella prima riga.
2. Per ogni nei kernel, ricavo dalla closure gli con lookahead diverso da # ed inserisco
item from item to
to nell’itemSet su cui arriva la goto da
tale lookahead nella riga corrispondente all’item item from
(ovvero quello indicato nell’automa LR(0)).
1. Creo una nuova colonna copiando i simboli della colonna precedente.
2. Per ogni riga della tabella FROM-TO, trasferisco ciò che appare (nella colonna precedente) nella riga con
indice pari all’indice nella cella FROM in tutti gli itemset (nella colonna attuale) che appaiono nella cella
TO.
Finché non ottengo due iterazioni uguali.
3.10.5 Costruzione parsing table LALR(1)
Una volta ottenuti tutti i lookahead di ogni item dei kernel, li trascriviamo all’interno di una nuova tabella,
ognuno con il proprio lookahead, e calcoliamo le closure di ogni kernel. A questo punto la parsing table viene
costruita come nell’LR(1).
3.11 Algoritmo di parsing
L’algoritmo di parsing è uguale a prescindere da come è stata costruita la parsing table (SLR, LR canonico o
LALR). L’algoritmo è il seguente:
• $
Costruisco una tabella con le colonne: Stack, Input, Action e Output. Inserisco in Stack e 0 e in
$.
Input la stringa da parsare seguita da
• Finché Action è diversa da Accept.
più a sinistra in Input.
1. Leggo il simbolo a
2. Leggo il numero X in testa a Stack. e lo inserisco in Action:
3. Recupero nella tabella di parsing il contenuto della cella [a,X]
– Se è vuoto, allora il parsing non può essere completato.
– Se è sy, aggiungo y in testa a Stack e rimuovo il simbolo più a sinistra di Input.
– Se è ry: →
(a) Inserisco in Output la y-esima produzione A B.
(b) Rimuovo da Stack B.length() numeri e leggo l’attuale testa Z di Stack.
se non vuota, altrimenti il parsing
(c) Aggiungo in testa a Stack il contenuto della cella [Z,A],
non è possibile.
– Se è Accept, allora ho terminato. 16
4 Traduzione della sintassi
Oltre a scanning e parsing, il front-end della compilazione è composto anche da type-checking statico e
generazione di codice intermedio. Ci concentriamo sulla seconda procedura, effettuata grazie a degli
strumenti formali che estengono le context-free grammars, ovvero:
• Syntax Directed Definitions (SDD): associano regole semantiche alle produzioni della grammatica.
Sono più semplici da leggere.
• Syntax Directed Translation Schemes (SDT): incorporano azioni semantiche nelle produzioni. Sono
più semplici da implementare.
4.1 Sintax Directed Definitions
Nelle SDD associamo informazioni ai costrutti del linguaggio assegnando attributi semantici ai simboli. Un
attributo può essere qualsiasi cosa, come ad esempio il numero di riga oppure il tipo. Vengono utilizzati come
se il simbolo fosse una classe ed essi degli attributi. Esempio
• →
Produzione: E E + T . Disambiguiamo le diverse istanze dello stesso simbolo perché ognuna può avere
1
attributi diversi.
• ′ ′
|| || ||
Regola semantica: E.code = E .code T.code + , dove con si intende concatenazione.
1 □
Analizzando la sinassi della regola semantica nell’esempio, vediamo che l’attributo ”code” del simbolo E è
′ ′
calcolato tramite la concatenazione degli attributi ”code” dei simboli E e T e il simbolo + .
1
4.1.1 Attributi delle SDD *
Una SDD è quindi una CFG arricchita da attributi che dipendono dall’istanza del simbolo. Un simbolo può
avere un numero qualsiasi di attributi ed essi si differenziano in due categorie:
• Sintetizzati se il valore dell’attributo dipende da attributi dei figli del simbolo o del simbolo stesso.
• Ereditati se il valore dell’attributo dipende da attributi dei fratelli, del padre o del simbolo stesso.
Sia A un simbolo non terminale, allora si dice che:
• →
A è padre di B se esiste una produzione A αBβ. B si dice quindi figlio di A.
• →
A è fratello di B se esiste una produzione A αAβBγ
Di base questi strumenti vengono utilizzati solo per la traduzione del codice e mai per la risoluzione.
4.1.2 Tipi di SDD
Una SDD può essere
• S-attributed se tutti gli attributi sono sintetizzati. Si presta all’implementazione tramite parser LR.
• Attribute grammar se non ha side effects che si verificano quando il calcolo degli attributi ha un impatto
su altri aspetti come, ad esempio, lo stato di variabili globali o altri calcoli nell’ambito del compilatore.
• padre o dai fratelli
L-attributed se tutti gli attributi sono sintetizzati oppure ereditati dagli ereditati del
sinistri. Si presta all’implementazione tramite parser top-down. In altri termini, in ogni produzione
→
A X ...X ...X , il simbolo X puo avere attributi ereditati di A, oppure attributi di X , ..., X .
1 i n i 1 i−1
17
4.1.3 Albero annotato
L’albero annotato è l’albero di parsing di una certa stringa in cui vengono annotati anche i valori degli attributi.
Nel caso di attributi sintetizzati, è facile valutare l’albero annotato con approccio bottom-up.
4.1.4 Grafo delle dipendenze
Quando la SDD ha attributi di entrambi i tipi, non è certo che esista un singolo ordine (top-down, bottom-up)
per la valutazione degli stessi, ma potrebbe essere necessario cambiare verso di valutazione. Per risolvere questo
problema si utilizza il grafo delle dipendenze, necessario per mostrare il flusso di informazioni tra gli attributi.
Tale grafo è costruito nel segunete modo:
• Per ogni nodo X dell’albero, esiste nel grafo un nodo per ogni attributo di X.
• Se un nodo A calcola il valore del suo attributo A.b basandosi sul valore di X.c, allora esiste un arco nel
grafo da X.c a A.b.
Per costruzione del grafo, un arco da A.x a B.y implica che A.x deve essere calcolato prima di B.y, quindi
bisogna seguire un certo ordinamento. Si dice ordinamento topologico del grafo un ordinamento in cui i
⇐
nodi sono nell’ordine N , ..., N dove i < j esiste un arco da N a N . La SDD può essere valutata se e solo
1 k i j
se esiste un ordinamento topologico del grafo, ovvero se e solo se il grafo non ha cicli.
4.1.5 Algoritmi di valutazione delle SDD
Come detto, a seconda della classe di SDD abbiamo diversi modi per trattarla.
SDD S-attributed
Nel caso di SDD S-attributed, eseguendo una visita bottom-up non abbiamo problemi, in quando i valori
necessari per il calcolo di un attributo sono stati calcolati nel passo precedente per definizione.
{
p o s t o r d e r (N) {
f o r ( each c h i l d C o f N, from t h e l e a f )
p o s t o r d e r (C ) ;
}
evaluate N attributes ;
}
SDD L-attributed
Nel caso di SDD L-attributed, appena un nodo viene toccato vengono valutati gli ereditati e solo successivamente
quelli sintetizzati. {
d f v i s i t (N) {
f o r ( each f i g l i o M d i N, da s i n i s t r a a d e s t r a )
v a l u t a g l i e r e d i t a t i d i M;
d f v i s i t (M) ;
}
v a l u t a i s i n t e t i z z a t i d i N;
} 18
4.1.6 Applicazioni delle SDD
Albero sintattico da SDD S-attributed
L’albero sintattico è una versione collassata dell’albero di parsing, in cui sono visualizzati solo i simbolo terminali.
Nell’albero sintattico non ho più informazioni sulla grammatica che sto utilizzando, ma solo sul parsing della
stringa attuale. Nel caso delle SDD S-attributed, l’albero sintattico può essere calcolato tramite una semplice
visita postorder. In altre parole, partendo dalla radice dell’albero di parsing, valuto tutte le regole nell’ordine
leftmost delle derivazioni, andando a creare nuovi nodi dove la SDD me lo impone tramite le regole. Esempio
In questo esempio si vede chiaramente come la costruzione dell’albero inizi dal basso e solo una volta arrivati
al primo simbolo T in basso a sinistra. Una volta raggiunta tale posizione, con la risalita verso la radice si va a
costruire tutti i collegamenti e l’intero albero. Le produzioni vengono quindi sviluppate in modo rightmost e si
segue l’ordine delle riduzioni per calcolare l’albero sintattico. □
Albero sintattico da SDD L-attributed
Nel caso di SDD L-attributed la situazione cambia poiché per ogni simbolo abbiamo attributi ereditati (inh) e
sintetizzati (syn). La costruzione dell’albero, in questo caso, avviene dunque in due fasi:
• Fase di discesa: si valuano tutti gli attributi ereditati, ove presenti. Possono essere accomunate a delle
chiamate a funzioni ricorsive.
• Fase di risalita: si valutano tutti gli attributi sintetizzati tramite gli attributi ereditati calcola
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
