Soluzioni Proposte
La grammatica sopra
di esercizio1.1 genera il linguaggio richiesto ed e' analizzabile LR(1).
S::= L S
S::= e
L::= &
L::= A
L::= B
L::= C
La grammatica data e' LL(1), adatta
per analisi discendente.
Una seconda
grammatica, pero', LR(1) e' la seguente:
S::= & L S
S::= T L S
S::= L
S::= e
L::= T
L::= &
T::= A
T::= B
T::= C
Questa grammatica offre alcuni vantaggi nell'analisi richiesta dal resto dell'esercizio, ovvero la possibilita' di vedere sempre i due simboli adiacenti
Utiliziamo la seguente grammatica che verifichiamo essere LL(1), quindi adatta ad un'analisi discendente:
Program::= Block
B::=
begin Declaration; Command Rest_of_program end
R::= ; C R
R::= e
C::= Block
C::= Statement
D::= var ide List_of_identifiers : Type
L ::= , ide L
L::= e
T ::= real
T ::= int
Per lo schema utiliziamo i seguenti
attributi:
per il calcolo della occupazione di memoria:
M
per i non terminali B, D, R, C, T. E' un sintetizzato ed ' usato con significati
diversi a seconda del simbolo. Esso contiene il numero di word
se B: richieste dalla dichiarazione di B e il massimo delle word richieste
dai blocchi occorrenti nel corpo di B
se D: richieste dalle variabili in D
se R, C: richieste dagli statements o blocchi attraversati
se T: richieste per l'allocazione di un tipo int o real
n per il non terminale
L. E' un sintetizzato, contiene il numero di variabili attraversate.
per il calcolo del livello di scoping o profondita':
in per i simboli B, C,
R. E' un ereditato, contiene il livello in cui occorre la struttura derivabile
dal simbolo
H
per i simboli B, C: contiene la profondita' calcolata per la struttura
attraversata.
| P::= {B.in:=0}
B |
| B::= begin
D; {C.in:= B.in +1} C {R.in:= B.in +1} R end {B.M:= D.M + max(C.M, R.M); B.H:= B.in +1} |
| R1::=
; {C.in:= R1.in}
C {R2.in:= R1.in} R2 {R1.M:= max(C.M, R2.M)} |
| R::= e {R.M:= 0} |
| C::= {B.in:= C.in}
B {C.M:= B.M; C.H:= C.in} |
| C::=
S {C.M:= 0; C.H:= C.in} |
| D::= var ide
L : T {D.M:= (1+L.n) * T.M} |
| L1
::= , ide
L2{L1.n:= 1 + L2.n} |
| L::= e {L.n:= 0} |
| T ::= real {T.M:= 4} |
| T ::= int {T.M:= 2} |
Utiliziamo la seguente grammatica che verifichiamo essere LL(1), quindi adatta ad un'analisi discendente:
Program::= Qprocedure Rest_of_procedurePer lo schema utiliziamo i seguenti attributi:
R::= ; Q R
R::= e
Q::= procedure ide Formals; Body
F::= ( List_of_ide)
L::= ide Again_ide
L::= e
A::= , ide A
A::= ide
B::= Declaration Command ; Sequence_of_commands
B::= Command ; Sequence_of_commands
D::= var ide A ;
C::= read ( ide A )
C::= write ( ide A )
C::= ide := ide Expression
C::= while ide = ide do C S od
C::= call ide F
E::= + ide
E::= e
Per la definizione delle azioni, utilizzeremo
liste con la seguente notazione per gli operatori:
[x1,...,xn]
lista di n, eventualmente n=0, valori.
| cons di un valore
ad una lista
+ append di liste
insect predicato
per elementi comuni a due liste
in aggiunta a queste operazioni standard, introduciamo le funzioni
definite induttivamente come di seguito:
filter:
filter([], L2) =
[]
filter(v | L1, L2)
= ([v] insect L2) | (filter (L1,L2)
match:
match([],[]) = []
match(v | L, true
| B) = v | match(L,B)
match(v | L, false
| B) = match(L,B)
select
select(<i,h> |
L, i) = h
select(<i,h> |
L, j) = select (h, j) if i<>j
Nota. L'attributo "a" contiene la lista delle variabili che possono risultare modificate ad ogni invocazione, cio' significa che essa contiene anche variabili che, per qualche esecuzione, non risulteranno essere modificate. La raccolta di queste variabli consente di affermare che se nessuna delle variabili che controllano l'iteratore while occorre nella lista, relativa al corpo dell'iteratore, allora tale iteratore e' certamente non terminante. Possiamo tuttavia, decidere di essere piu' stretti ovvero richiedere di individuare non solo gli iteratori certamente non terminanti pure gli iteratori che potrebbero essere non terminanti in certe computazioni: il testo ci lascia ampia liberta'. In quest'ultimo caso, l'attributo "a" deve contenere la lista delle variabili che sono modificate in tutte le computazioni: ecco allora, che le variabili modificate all'interno di un blocco con accesso condizionato, come gli iteratori, non devono essere poste nella lista.
P::= {Q.inp:= []}
Q {R.inp:= [Q.h]}
R {P.r:= Q.r or R.r}R1::= ; {Q.inp:= R1.inp}
Q {R2.inp:= [Q.h] + R1.inp}
R2 {R1.r:= Q.r or R2.r}R::= e {R.r:= false} Q::= procedure ide
F ; {B.inp:= Q.inp}
B end {Q.h:=<ide.val, filter(F.list,B.a)>; **coppia con i parametri effettivamente modi-
Q.r:= B.r} ficabili ad ogni invocazioneF::= (
L) {F.list:= L.list}L::= ( ide
A) {L.list:= [ide.val] + A.list}L::= e{L.list:= []} A1::= , ide
A2 {A1.list:= [ide.val] + A2.list}A::= ide {A.list:= []} B::= D {C.inp:= B.inp}
C ; {S.inp:= B.inp}
S {B.a:= C.a + S.a - D.list; **la portata dei formali e' coperta da D.list
B.r:= C.r + S.r}B::= {C.inp:= B.inp}
C ; {S.inp:= B.inp}
S {B.a:= C.a + S.a; B.r:= C.r or S.r }D::= var ide
A ; {D.list:= [ide.val] + A.list}C::= read ( ide
A ) {C.a:= [ide.val] + A.list; C.r:= false}C::= write ( ide
A ){C.a:= []; C.r:= false}C::= ide := ide
E {C.a:= [ide.val]; C.r:= false}C1::= while ide1 = ide2 do {C2.inp:= C1.inp}
C2 {S.inp:= C1.inp}
S od {C1.a:= C2.a + S.a **certamente modificati: C1.a:= [] --- nota
C1.r:= C2.r or S.r or (([ide1.val,ide2.val] insect (C2.a + S.a))=[]}C::= call ide
F {C.a:= match(F.list, select(C.inp, ide.val)); C.r:= false}S::= ; {C.inp:= S1.inp}
C{S.inp:= S1.inp}
S {S1.a:= C.a + S2.a; S1.r:= C.r + S2.r}S::= e {S.a:= []; S.r:= false} E::= + ide E::= e
Per lo schema utiliziamo i seguenti attributi:
r
per i non terminali P. E' una lista di coppie identificatore di procedura
lista delle variabili usate o procedure invocate ma non dichiarate (nello
scope)
r
per i non terminali Q. E' una lcoppia identificatore di procedura - lista
delle variabili usate o procedure invocate ma non dichiarate (nello scope)
r
per i non terminali B,R, C, S. E' una lista sintetizzata contiene identificatori
variabile usati o procedura invovate, nella struttura attraversata, ma
non dichiarati
inpV per i non terminali
Q, R, B, C, S. E' un ereditato contiene la lista degli identificatori di
variabile nello scope della struttura da attarversare
inpP per i non terminali
Q, R, B, C, S. E' un ereditato contiene la lista degli identificatori di
procedura nello scope della struttura da attarversare
list per i non terminali
D, A, E. Sintetizzato contenente la lista di identificatori attraversati
dall'analisi del simbolo
s per i non terminali B,
C, S. Sintetizzato booleano contenente true se e solo se una variabile
usata come procedura o viceversa occorre nella struttura attraversata
Per la definizione delle azioni, utilizzeremo
liste con la seguente notazione per gli operatori:
[x1,...,xn]
lista di n, eventualmente n=0, valori.
| cons di un valore
ad una lista
+ append di liste
\ differenza
insect intersezione
| P::= D {Q.inpV:= D.list;
Q.inpP:= []}
Q {R.inpV:= D.list , R.inpP:= [Q.h]} R {P.r:= Q.r + R.r} |
| R1::=
; {Q.inpV:= R1.inpV; Q.inpP:= R1.inpP}
Q {R2.inpV:= R1.inpV; R2.inpP:= [Q.h] + R1.inpP} R2 {R1.r:= Q.r + R2.r} |
| R::= e {R.r:= []} |
| Q::= procedure ide;
{B.inpV:= Q.inpV; B.inpP:= [Q.h] + Q.inpP}
B end {Q.h:=ide.val; Q.r:= <ide.val, B.r, B.s>} |
| A1::=
, ide
A2 {A1.list:= [ide.val] + A2.list} |
| A::= ide {A.list:= []} |
| B::= D {C.inpV:=
B.inpV + D.list; C.inpP:= B.inpP}
C ; {S.inpV:= B.inpV; S.inpP:= B.inpP} S {B.r:= C.r + S.r; B.s:= C.s OR S.s} |
| B::= {C.inpV:= B.inpV;
C.inpP:= B.inpP}
C ; {S.inpV:= B.inpV; S.inpP:= B.inpP} S {B.r:= C.r + S.r; B.s:= C.s OR S.s} |
| D::= var ide
A ; {D.list:= [ide.val] + A.list} |
| C::= read ( ide
A ) {C.r:= ([ide.val]+A.list)\C.inpV; C.s:= (([ide.val]+A.list) insect C.inpP) <> []} |
| C::= write ( ide
A ){C.r:= ([ide.val]+A.list)\C.inpV; C.s:= (([ide.val]+A.list) insect C.inpP) <> []} |
| C::= ide1:= ide2
E {C.r:= ([ide1.val, ide2.va]+E.list)\C.inpV; C.s:= (([ide1.val, ide2.va]+A.list) insect C.inpP) <> []} |
| C1::=
while ide1 = ide2 do {C2.inpV:=
C1.inpV; C2.inpP:= C1.inpP}
C2 {S.inpV:= C1.inpV; S.inpP:= C1.inpP} S od {C1.r:= C2.r + S.r; C1.s:= C2.s OR S.s} |
| C::= call ide {C.r:= [ide.val]\C.inpP; C.s:= ([ide.val] insect C.inpV) <> []} |
| S1::=
; {C.inpV:= S1.inpV; C.inpP:= S1.inpP; }
C{S2.inpV:= S1.inpV; S2.inpP:= S1.inpP} S2 {S1.r:= C.r + S2.r; S1.s:= C.r OR S2.s; } |
| S::= e {S.r:= []} |
| E::= + ide {E.list:= [ide.val]} |
| E::= - ide {E.list:= [ide.val]} |
| E::= e {E.list:= []} |
Utiliziamo la seguente grammatica che verifichiamo essere LL(1), quindi adatta ad un'analisi discendente:
E::= F E
E::=
"|" F E
E::=
e
F::= H F
F::=
. H F
F::=
e
H::= (E)M
H::= "e"
H::= a
H::= b
H::= c
M::= *
M::= e
Per lo schema utiliziamo i seguenti
attributi:
in
per i non terminali E, F, M. E' un ereditato
contiene la rappresentazione del primo operando (gia' attraversato e non
visibile a tali simboli)
instar per i non terminali
E,
F,
M. E' un ereditato contiene un booleano on/off settato on allorche' il
primo operando sia una stella di kleene.
tree per tutti i non terminali. E'
il sintetizzato contenente la rapresentazione di albero astratto per l'espressione
attraversata dal simbolo.
star per tutti i non terminali.
E' il sintetizzato contenente il booleano on/off sul tipo di espressione
attraversata da simbolo.
Per la definizione delle azioni, in
particolare la costruzione degli alberi di sintassi astratta
MkT
_ _: string x forest -> tree // costruisce
un albero con radice etichettata da string e foresta dei figli, forest.
MKE : -> forest //
calcola una foresta vuota
Add _ _ : tree x forest -> forest
//
aggiunge tree come prtimo albero della foresta forest
| E::= F {E.in:=
F.tree; E.instar:= F.star;}
E{E.tree:= E.tree; E.star:= E.star} |
| E1::=
"|" F {E2.in:= MkT("|", Add(E1.in,
Add(F.tree, MKE()))); E2.instar:= "off"}
E2 {E1.tree:= E2.tree; E1.star:= "off"} |
| E::= e {E.tree:= E.in; E.star:= E.instar; } |
| F::= H {F.in:=
H.tree; F.instar:= H.star}
F{F.tree:= F.tree; F.star:= F.star} |
| F1::=
.H
{F2.in:=
MkT(".", Add(F1.in, Add(H.tree, MKE()))); F2.instar:=
"off"}
F2 {F1.tree:= F2.tree; F1.star:= F2.star} |
| H::= ( E {M.in:= E.tree;
M.instar:= E.star}
) M {H.tree:= M.tree, H.star:= M.star} |
| M::= * {M.tree:= if (M.instar="on") then M.in else MkT("*", Add(M.in,MKE())); M.star:="on"} |
| M::= e {M.tree:= M.in; M.star:= M.instar} |
| H::= a {H.tree:= MkT("a",MKE()); H.star:= "off"} |
| H::= b {H.tree:= MkT("b",MKE()); H.star:= "off"} |
| H::= c {H.tree:= MkT("c",MKE()); H.star:= "off"} |
Utiliziamo la seguente grammatica che verifichiamo essere LL(1), quindi adatta ad un'analisi discendente:
TypExpression::= Basic
T::= Structured
B::= integer
B::= real
S::= rec ide : T Rest_of_structure
R::= , ide : T R
R::= endrec
Per lo schema utiliziamo i seguenti
attributi:
Y
per i non terminali T, B, S, R. E' un sintetizzato e contiene la rappresentazione
richiesta per l'espressione o la sottoespressione attraversata dal simbolo.
val per il terminale ide.
E' un sintetizzato, contiene l'identificatore attraversato
Per la definizione delle azioni, in
particolare la generazione degli opportuni puntatori e record della rappresentazione
utilizzeremo:
newtype
_ _: string x pointer3 -> pointer2 // calcola
un puntatore, pointer2, ad un record di due campi, il primo dei quali contiene
la stringa, il secondo un
newfield
_ _ _: string x pointer2 x ponter3 -> pointer3 //
calcola un puntatore, pointer3, ad un record di tre campi contenente quanto
atteso.
null:
puntatore
intoString _: identificatore -> string
//
calcola la stringa corrispondente all'identificatore
| T::= B {T.Y:= B.Y} |
| T::= S {T.Y:= S.Y} |
| B::= integer {B.Y:= newtype("integer",null)} |
| B::= real {B.Y:= newtype("real",null)} |
| S::= rec
ide : T R{temp:= newfield(toString(ide.val), T.Y, R.Y); S.Y:= newtype("rec", temp)} |
| R1::=
,
ide : T R2{R1.Y:= newfield(toString(ide.val), T.Y, R2.Y);} |
| R::= endrec {R.Y:=null} |
un solo attributo sintetizzato:
tree per tutti i non terminali: contiene
una copia dell'alberi di derivazione sintattica attraversato durante la
derivazione dal non terminale
| S::= (TF | S.tree:= MkT("S", Add(MkT("(",MkE()), Add(T.tree, Add(F.tree, MkE())))) |
| T::= L | T.tree:= MkT("T",Add(L.tree, MkE())) |
| T::= [L,S] | T.tree:= MkT("T",Add(MkT("[",MkE()), Add(L.tree, Add(MkT(",", MkE()),Add(S.tree, Add(MkT("]", MkE())))))) |
| F1::=,TF2 | F1.tree:=MkT("F",Add(MkT(",",MKE()),Add(T.tree,Add(F2.tree,MKE())))) |
| F::= ) | F.tree:=MkT("F",Add(MkT(")",MKE())) |
| L::= A | L.tree:=MkT("L",Add(MkT("A",MKE())) |
| L::= B | L.tree:=MkT("L",Add(MkT("B",MKE())) |
| L::= C | L.tree:=MkT("L",Add(MkT("C",MKE())) |
| L::= D | L.tree:=MkT("L",Add(MkT("D",MKE())) |
| L::= E | L.tree:=MkT("L",Add(MkT("E",MKE())) |
La grammatica sopra
di esercizio1.2.
Tre attributi: un booleano ereditato, cmd, un sintetizzato di tipo stringa,
string, ed un sintetizzato di tipo stringa per i simboli attraversati,
val:
cmd per til solo S: contiene true se l'ultimo
simbolo attraversato, prima della derivazione da S, e' il simbolo di controllo
"&".
string per il solo S: contiene la sequenza
di simboli attraversata e risolta rispetto l'uso del simbolo di controllo
"&"
val per til solo L: contiene la stringa costituita
dal simbolo attarversato.
La necessita' di un ereditato del simbolo distinto S comporta la modifica
della grammatica data in esercizio3.1 con la
grammatica estesa: cio' premette di introdurre le azioni per il calcolo
dell'ereditato del simbolo S quando questi sara' istanziato per la prima
volta.
| S'::= {S.cmd:=
false}
S {S'.string:= S.string} |
| S1::=
L
{S2.cmd:= (not S1.cmd) and (L.val = "&")} S2 {S1.string:= if (S2.cmd) then S2.string else if (S1.cmd) and (L.val <> "&") then "cmd("+L.val+")"+S2.string else L.val+S2.string} |
| S::= e{S.string:= if (S.cmd) then "&" else ""} |
| L::= &{L.val:= "&"} |
| L::= A {L.val:= "A"} |
| L::= B {L.val:= "B"} |
| L::= C {L.val:= "C"} |
Utiliziamo la seguente grammatica che verifichiamo essere LR(1), quindi adatta ad un'analisi ascendente, in piu' essa e' fattorizzata a sinistra rispetto alla lista delle dichiarzioni di procedura:
Program::=
Rest_of_procedure Qprocedure
R::= R Q ;
R::= e
Q::= procedure ide Formals; Body
F::= ( List_of_ide)
L::= ide Again_ide
L::= e
A::= , ide A
A::= ide
B::= Declaration Command ; Sequence_of_commands
B::= Command ; Sequence_of_commands
D::= var ide A ;
C::= read ( ide A )
C::= write ( ide A )
C::= ide := ide Expression
C::= while ide = ide do C S od
C::= call ide F
E::= + ide
E::= e
Per lo schema utiliziamo i seguenti
attributi:
p
per i non terminali P, R. E' un sintetizzato e contiene la lista delle
procedure attraversate prima della procedura attraversata con Q. Notare,
peraltro, che esso e' l'attributo richiesto dall'esercizio e tale attributo
e' associato alla procedura attraversata da Q in modo indiretto, ovvero
e' associata al "padre" (che e' comunque, unico).
h per il non terminale Q. E'
un sintetizzato, contiene la coppia nome della procedura - lista dei formali.
list per i non terminali F, L,
A. E' un sintetizzato, contiene la lista degli identificatori occorrenti
nella struttura attraversata
val per il terminale ide. E' un sintetizzato,
contiene il nome dell'identificatore attraversato.
| P::= R Q {P.p:= R.p} |
| R1::= R2Q ; {R2.p:= R1.p + [Q.h]} |
| R::= e {R.p:= []} |
| Q::= procedure ide F ; B end {Q.h:=<ide.val, F.list>} |
| F::= (L) {F.list:= L.list} |
| L::= ( ide A) {L.list:= [ide.val] + A.list} |
| L::= e{L.list:= []} |
| A1::= , ide A2 {A1.list:= [ide.val] + A2.list} |
| A::= ide {A.list:= []} |
| B::= D C ; S |
| B::= C ; S |
| D::= var ide A ; |
| C::= read ( ide A ) |
| C::= write ( ide A ) |
| C::= ide := ide E |
| C1::= while ide1 = ide2 do C2 S od |
| C::= call ide F |
| E::= + ide |
| E::= e |
tre attributi sintetizzati:
forest per S ed F: contiene la lista di alberi
di cui e' stato attraversato l'albero di derivazione sintattica da S o
F rispettivamente
tree per T: contiene l' albero di cui e'
stato attraversato il parse tree da T
label per L: contiene l'etichetta di cui
e' stato attraversato il parse tree da L
| S::= (TF | S.forest:= Add(T.tree, Add(F.forest, MkE())))) |
| T::= L | T.tree:= MkT(L.label,MkE()) |
| T::= [L,S] | T.tree:= MkT(L.label, S.forest) |
| F1::=,TF2 | F1.forest:= Add(T.tree, F2.forest) |
| F::= ) | F.forest:= MKE() |
| L::= A | L.label:= "A" |
| L::= B | L.label:= "B" |
| L::= C | L.label:= "C" |
| L::= D | L.label:= "D" |
| L::= E | L.label:= "E" |
La grammatica sopra
di esercizio1.3.
Soluzione con i marcatori.
1) Partiamo da
una soluzione per l'analisi discendente: noi consideriamo quella data in
esercizio3.2.
2) Inseriamo marcatori
ed e-produzioni, ottenendo
la seguente tabella che tratta ereditati di un simbolo come sintetizzati
del marcatore che lo precede:
| S'::= M1
S {S'.string:= S.string} |
| S1::=
L
M2 S2 {S1.string:= if (M2.cmd) then S2.string else if (S1.cmd) and (L.val <> "&") then "cmd("+L.val+")"+S2.string else L.val+S2.string} |
| S::= e{S.string:= if (S.cmd) then "&" else ""} |
| L::= &{L.val:= "&"} |
| L::= A {L.val:= "A"} |
| L::= B {L.val:= "B"} |
| L::= C {L.val:= "C"} |
| M1::= e {M1.cmd:= false} |
| M2::= e {M2.cmd:= (not S1.cmd) and (L.val = "&")} |
3)
Risolviamo i riferimenti ad attributi non locali mediante riferimenti sullo
stack dei dati ed azioni che calcolano effetti laterali. Per i riferimenti
sullo stack utiliziammo l'invariante seguente:
"ogni maniglia A::=B1,...,Bk ha attributi sintetizzati di Bk-j in Top\j"
| S'::= M1
S {temp:= Top; pop(2); push(temp)} |
| S1::=
L
M2 S2 {temp:= if (Top\1) then Top else if (Top\3) and (Top\2 <> "&") then "cmd("+Top\2+")"+Top else Top\2+Top; pop(3); push(temp)} |
| S::= e {if (Top) then push("&") else push("")} |
| L::= &{push("&")} |
| L::= A {push("A")} |
| L::= B {push("B")} |
| L::= C {push("C")} |
| M1::= e {push(false)} |
| M2::= e {push((not Top\1) and (Top = "&"))} |
Le azioni pop e push mantengono l'invariante richiesto
Questa soluzione e' interamente meccanica
ed e' la soluzione adottata negli strumenti di analisi Cornell Syntetizer.
1) Scriviamo una
nuova grammatica che strutturi le frasi in modo tale che il problema non
richieda piu' attributi ereditati.
| S1::=
S2
L {S1.cmd:= (not S2.cmd) and (L.val = "&") S1.string:= if ((not S2.cmd) and (L.val = "&")) then S2.string else if (S2.cmd) and (L.val <> "&") then S2.string + "cmd("+L.val+")" else S2.string+L.val} |
| S::= e{S.cmd:=false;
S.string:= ""} |
| L::= &{L.val:= "&"} |
| L::= A {L.val:= "A"} |
| L::= B {L.val:= "B"} |
| L::= C {L.val:= "C"} |