Suggerimenti
Utiliziamo la seguente
grammatica che verifichiamo essere LL(1), quindi adatta ad un'analisi
discendente:
Program::= Block
B ::= Statement Rest_of_program
R ::= ; S R
R ::= e
S ::= ide := E
S ::= if F then S else S
E ::= T E'
E' ::= + T E'
E' ::= e
T ::= ide
T ::= (E)
T ::= S
F ::= ide F'
F' ::= = ide
F' ::= e
Per lo schema utiliziamo i seguenti
attributi:
usuali: sintetizzato loc per la
locazione del codice generato dall'attraversamento ed ereditato inloc per la locazione del codice generato prima e da comporre
con quello generato dal nuovo attraversamento.
Sebbene LR(1), la grammatica
data non e' adatta per lo schema di traduzione: occorre fattorizzarla in modo
tale da poter eseguire azioni durante il riconoscimento dello stesso comando
while e durante l'attraversamento della sequenza di comandi. La modifichiamo
nel seguente modo:
S::= W do L
W::= I B
I::= while
L::= S
L::= H S
H::= L ;
S::= break on B
S::= other
Per lo schema utiliziamo i
seguenti attributi:
usuali: sintetizzato next per gli
eventuali incompleti del codice generato dall'attraversamento di un comando o
sequenza di comandi. In aggiunta:
end per W
contiene l'incompleto generato dopo l'attraversamento della guardia ed
utilizzato per trasferire il controllo fuori dal comando.
init per I e W
contiene il valore di quad prima dell'attraversamento dell'espressione.
Entrambi servono per la traduzione del comando while in unoschema ascendente.
Per trattare il break introduciamo:
break per tutti
i comandi e le sequenze: contiene incompleti generati dalla'attraversamento di
un break: si differenzia dal next in quanto il next e' completato con l'inizio
del comando seguente, mentre questi incompelti sono completati con l'inizio del
comando che segue il comando while in cui sono inclusi.
Per prima cosa diamo una
grammatica per le strutture che vogliamo visitare. La visita depth-first impone
uno schema di traduzione L-attributato. Possiamo scegliere indifferentemente
uno schema top-down o uno bottom-up. Optiamo per uno bottom-up S-attributato.
Nel definire la grammatica sono infine necessarie altre scelte:
·
Associativita’ degli
operatori:
o
Per gli aritmetici
l’usuale e’ a sinistra (del tutto congeniale al bottom-up)
o
Per la
sequenzializzazione si adotta spesso quella a destra: nella quasi totalita’ dei
casi la scelta e’ semanticamente indifferente. Per uno schema bottom-up non e’,
in generale, la scelta piu’ felice e puo’ condurre all’impiego di attributi
ereditati difficile da trattare. Nel caso specifico non avremo problemi.
Adottiamo quindi associativita’ a destra.
·
Precedenza di operatori.
Adottiamo la seguente:
o
* > + >
if_then_else
·
Marcatori per azioni da
valutare prima di una riduzione:
o
Mseq: per
chiudere incompleti di comandi (non ce ne saranno)
o
Mcond: per
comporre i due casi del condizionale
o
Msum, Mprod:
per comporre i due casi operandi che possono contenete condizionali
Seq1::=
C Mseq Seq2
Seq::= C
C::= Ide := Cond
Cond1::=
if Eq then Mcond
else Cond2
Cond::= Sum
Eq::= Cond1
= Cond2
Sum1::=
Sum2 +
Msum Prod
Sum::= Prod
Prod1::=
Prod2 *
Mprod Term
Prod::= Term
Term::= Ide
Term::= (Cond)
Mseq::=
;
Mcond::=
Cond
Msum::=
e
Mprod::=
e
Introdurremo I seguenti
attributi:
·
Per
gestire analisi dei tipi:
o
Attributo
type con i seguenti possibili valori: {int, bool, error}. Dobbiamo estendere
tale attributi a tutti I simboli: S, A, P, B, id.
·
Per la
generazione di codice (effetti laterali: emit e quad):
o
Usuali
attributi: next per comandi (avendo il solo assegnamento ne potremmo fare a
meno) e .loc per espressioni.
Per prima cosa diamo una
grammatica (ovvero supposto di avere una grammatica per un linguaggio di
comandi, con categoria sintattica S, aggiungiamo le produzioni per il nuovo costrutto).
S::= repcase
E of
n:
S
R
R::= ; n:
S
R
R::= endrep
In aggiunta all’usuale
attributo .next dei comandi, e .loc delle espressioni, introduciamo:
in_next_case ereditato
per R contiene l'incompleto che forma
la guardia per l’accesso al commando.
in_init ereditato
per R contiene il punto di inizio
dell’intero codice.
in_loc ereditato per
R contiene il nome della locazione prodotta dall’attraversamento di E.
Occorre modificare la
grammatica: Fattoriziamo quel tanto che consenta di trattare ereditati come sintetizzati
di opportuni marcatori. (Attenzione: M1, M2, M3 sono 3 distinti marcatori: in
particolare, nella seconda produzione non si confondano i marcatori M1 e M2 con
due istanze di uno steso marcatore M, inesistente.).
S::= M1 endrep
M1::= M2 S
M2::= R n :
R::= M1 ;
R::= M3 E of
Gli attributi sono (in
aggiunta agli usuali):
next sintetizzato
per M1, M2, M3, R contenente
l'incompleto che forma la guardia per l’accesso al commando attraversato in
precedenza.
init sintetizzato
per M1, M2, M3, R contenete il punto
di inizio dell’intero codice.
loc sintetizzato per
M1, M2, M3, R contiene il nome della locazione generata da E.
Esercizio21.1
Utiliziamo la seguente grammatica
che verifichiamo essere LL(1), quindi adatta ad un'analisi discendente:
S ::= Case E of L : S Rest_of_pairs
R ::= ; L : S R
R ::= e
L ::= num L'
L' ::= , num L'
L' ::= e
Per lo schema utiliziamo i seguenti
attributi:
loc
sintetizzato per E contiene la locazione del valore calcolato dall'esecuzione
del codice generato dall'attraversamento di un espressione
inloc ereditato
per L per utilizzare la locazione del valore del codice generato
dall'espressione
init sintetizzato
di L per gli incompleti generati dall'attraversamento di L e che devono essere
completati con l'inizio del codice dello statement associato.
nextcase
sintetizzato di L contiene l' incompleto (un semplice goto --) che deve essere
completato con l'inizio del codice della successiva coppia
lista-statement associato.
next l'usuale
sintetizzato dei comandi.
Utiliziamo la seguente
grammatica che verifichiamo essere LL(1), quindi adatta ad un'analisi
discendente:
P ::= L:S R
R ::= ; L:S R
R ::= .
S ::= ide := ide + ide
S ::= goto L
S ::= if ide = ide goto L
Per lo schema utiliziamo i
seguenti attributi:
inlist
ereditato per R contiene le etichette target di tutte le istruzioni di salto
attraversate precedentemente la derivazione da R.
list
sintetizzato per R contiene le etichette target di tutte le istruzioni di salto
attraversate fino alla derivazione da R inclusa
ref sintetizzato
di S contiene una lista formata dall'etichetta target se S e' istruzione di
salto, vuota altrimenti
Per lo schema utiliziamo le
seguenti strutture ed operazioni:
[]
costruttore di lista
count:
si applica ad una lista ed ad un valore, calcola il numero di occorrenze del
valore nella lista.
Per prima cosa diamo una
grammatica (ovvero supposto di avere una grammatica per un linguaggio di
comandi, con categoria sintattica S, aggiungiamo le produzioni per il nuovo costrutto).
S::= loop
B:
S
R
R::= ; B:
S
R
R::= end
In aggiunta all’usuale
attributo .next dei comandi, e .loc delle espressioni, introduciamo, similmente
a quanto fatto in esercizio 14:
in_next_case ereditato
per R contiene gli incompleti per
l’accesso al commando successivo.
in_init ereditato
per R contiene il punto di inizio
dell’intero codice.
Le analogie si fermano qui. A differenza di esercizio 14, infatti le varie
coppie B,S non sono selezionalbili in modo esclusivo, ovvero selezionata una
coppia il codice dovra’ trasferire il controllo in modo tale da continuare la
visita delle coppie per altre guardie vere. Di conseguenza ad ogni iterazione
dobbiamo sempre attraversare l’intero codice e alla fine verificare se abbiamo
incontrato almeno una guardia vera. A questo scopo, il codice generato conterra’
una variabile di controllo, ad ogni iterazione settata false, che sara’
modificata al valore vero allorche’ una guardia risulti vera. Il codice
generato dovra’ contenere un test finale su tale variabile: decidendo se
iterare nuovamente o terminare. Il nome di tale variabile dovra’ essere
trasmesso alle varie produzioni attraversare a compile time, pertanto avremo l’attributo:
in_flag ereditato per
R contiene il nome della variabile di controllo.
Per prima cosa diamo una
grammatica adatta all’analisi ascendente ed utilizzo di soli sintetizzati. La
nuova grammatica fattorizza a sinistra.
S::= M1 end
M1::= R : S
R::= M1 ; B
R::= M0 B
M0::= loop