Soluzioni Proposte

Esercizio1.1

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.

P::= B

B::= C
R

R₁::= C
R₂

R::= e

S::= ide :=
E {emit(ide.loc ':=' E.loc); S.loc:=ide.loc}

S₁::= if F {init_else:=[quad]; emit('if' F.loc '= false goto' --);}
         then S₂ {t:=newtemp(); emit(t':=' S₂.loc); end_if:=[quad]; emit('goto' --); BK(init_else,quad)}
         else S₃ {t:=newtemp(); emit(t':=' S₃.loc); BK(end_if, quad); S₁.loc:=t}

E::= T {E'.inloc:= T.loc}
      E' {E.loc:= E'.loc}

E'₁ ::= + T {t:=newtemp(); emit(t ':=' E'₁.inloc +.val T.loc); E'₂.inloc:=t}
E'₂ {E'₁.loc:= E'₂.loc}

E'::= e {E'.loc:= E'.inloc}

T ::= ide {T.loc:= ide.loc}

T ::= ( E ) {T.loc:= E.loc}

T ::= S {T.loc:= S.loc}

F ::= ide {F'.inloc:= ide.loc}
F' {F.loc:= F'.loc}

F'₁::= = F'₂ {t:=newtemp(); emit('if' F'₁.inloc '=' F'₂.loc 'goto' quad+3); emit(t ':= false'); 
                       emit('goto' quad+2); emit(t ':= true'); F'₁.loc := t}

F'::= e {t:=newtemp(); emit('if' F'₁.inloc '=' 0 'goto' quad+3); emit(t ':= true'); 
                       emit('goto' quad+2); emit(t ':= false'); F'.loc := t}

Esercizio 3

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.

S::= W do L end {BK(L.next, W.init);  S.next = W.end + L.break;  S.break:= []}

W::= I B {W.end:= [quad]; emit('if' B.loc '= false goto' --); W.init:= I.init}

I::= while {I.init:= quad}

L::= S {L.next:= S.next; L.break:= S.break}

L::= H S {L.next:= S.next; L.break:= S.break}

H::= L ; {BK(L.next, quad); H.break:= L.break}

S::= break on B {S.break:= [quad]; emit('if' B.loc '= true goto' --); S.next:= []}

S::= other {S.next:= other.next; S.break:= []}

Esercizio 4

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 M_seq: per chiudere incompleti di comandi (non ce ne saranno)

o M_cond: per comporre i due casi del condizionale

o M_sum, M_prod: per comporre i due casi operandi che possono contenete condizionali

Seq₁::= C M_seq Seq₂
Seq::= C
C::= Ide := Cond
Cond₁::= if Eq then M_cond else Cond₂
Cond::= Sum
Eq::= Cond₁ = Cond₂
Sum₁::= Sum₂ + M_sum Prod
Sum::= Prod
Prod₁::= Prod₂ * M_prod Term
Prod::= Term
Term::= Ide
Term::= (Cond)
M_seq::= ;
M_cond::= Cond
M_sum::= e
M_prod::= e

Per lo schema utiliziamo i seguenti attributi:
usuali: sintetizzato next per gli eventuali incompleti del codice generato dall'attraversamento di un comando (vedi C) o sequenza di comandi (vedi Seq). Sintetizzato loc per le espressioni.In aggiunta:
next anche per le espressioni che, contenendo condizionali, richiedono di operare trasferimenti di controllo.
quad per M_seq che mantiene il valore di quad dopo la generazione del codice di ogni commando ed ancora per M_sum e M_prod che devono ricordare il valore di quad prima della traduzione del secondo operando.
Else per M_cond che mantiene il valore di quad prima della traduzione del ‘ramo’ else del condizionale.

Seq₁::= C M_seq Seq₂ {BK(C.next, M_seq.quad}

Seq::= C {BK(C.next, quad); Emit(‘Halt’)}

C::= Ide := Cond {BK(Cond.next, quad); Emit(Ide.loc ‘:=’ Cond.loc); C.next:=[]}

Cond₁::= if Eq then M_cond else Cond₂ {BK(Eq.else, M_cond.else); Emit(M_cond.loc ‘:=’Cond₂.loc); Cond₁.loc:= M_cond.loc; Cond₁.next:= M_cond.next}

Cond::= Sum {Cond.loc:= Sum.loc; Cond.next:= Sum.next}

Eq::= Cond₁ = Cond₂ {Eq.else:=[quad]; Emit(‘if’ Cond₁.loc ‘≠’ Cond₂.loc ‘goto –‘}

Sum₁::= Sum₂ + M_sum Prod {BK(Sum₂.next, M_sum.quad); temp:=newtemp(); BK(Prod.next, quad); emit(temp ‘:=’ Sum₂.loc [+]Prod.loc); Sum₁.loc:= temp; Sum₁.next:= []}

Sum::= Prod {Sum.loc:= Prod.loc; Sum.next:= Prod.next}

Prod₁::= Prod₂ * M_prod Term {BK(Prod₂.next, M_prod.quad); temp:=newtemp(); BK(Term.next, quad); emit(temp‘:=’Prod₂.loc [*]Term.loc); Prod₁.loc:= temp; Prod₁.next:= []}

Prod::= Term {Prod.loc:= Term.loc; Prod.next:= Term.next}

Term::= Ide {Term.loc:= Ide.loc; Term.next:= []}

Term::= (Cond) {Term.loc:= Cond.loc; Term.next:= Cond.next}

M_seq::= ; {M_seq.quad:= quad}

M_cond::= Cond {temp:=newtemp(); BK(Cond.next, quad); Emit(temp:=Cond.loc); M_cond.loc:= Cond.loc; M_cond.next:=[quad]; Emit(‘goto –‘); M_cond.else:=quad}

M_sum::= e {M_sum.quad:=quad}

M_prod::= e {M_prod.quad:=quad}

Esercizio 6

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.

S::= id := A {Emit(id.loc ‘:=’A.loc); S.next=[];

S.type = if (A.type=int) and (id..type=int)

then int

else error} // utiliziamo un meta con espressioni condizionali

S::= id := B {Emit(id.loc ‘:=’B.loc); S.next=[];

S.type = if (B.type=bool) and (id..type=bool)

then bool

else error}

A₁::= A₂ * P {temp:=newtemp(); Emit(temp ‘:=’ A₂.loc [*] P.loc); A₁.loc:= temp;

A₁.type = if (A₂.type=int) and (P.type=int)

then int

else error}

A::= P {A.loc:= P.loc; A.type:= P.type}

P::= id {P.loc:= id.loc; P.type:= id.type }

P::= (A) {P.loc:= A.loc; P.type:= A.type }

B::= A₁ = A₂ {temp:=newtemp(); Emit(temp ‘:=’ A₁.loc [=] A₂.loc); B.loc:= temp;

B.type = if (A₁.type= A₂.type)

then A₁.type

else error}

Esercizio 13.a

Per prima cosa diamo una grammatica (ovvero supposto di avere una grammatica per un linguaggio di espressioni, con categoria sintattica exp, aggiungiamo le produzioni per il nuovo costrutto).

Exp::= prod
Exp₁
with ide to
Exp₂

Per lo schema utiliziamo gli usuali attributi delle espressioni: In particolare, e’ vero che il costrutto espressione prod nasconde un iteratore e come tale potrebbe dover gestire trasferimenti di controllo. Tuttavia la traduzione che diamo non richiede alcun attributo next.:

Exp::= prod {temp:=newtemp()}
Exp₁ {Emit(temp:= Exp₁.loc)}
with ide to {Emit(ide.loc ‘:=’ #1)}
Exp₂ {loop:= quad;

Emit(temp:= temp [*] ide.loc);

Emit(ide.loc ‘:=’ ide.loc [+] #1);

Emit(‘if’ ide.loc [<=] Exp₂.loc ‘goto’ loop);

Exp.loc:= temp}

Esercizio 13.b

Dovendo utilizzare solo attributi ereditati, occorre modificare la grammatica: la fattoriziamo a sinistra di quanto necessario per trasformare ereditati in sintetizzati:

Exp::= M Exp
M::= prod Exp with ide to

Per lo schema utiliziamo gli usuali attributi delle espressioni. In aggiunta, il marcatore M deve mantenere come sintetizzati gli attributi:

loc = locazione dell’identificatore ide
temp = nome locazione contenente i prodotti parziali

Exp₁::= M Exp₂ {loop:= quad;

Emit(M.temp ‘:=’ M.temp [*] M.loc);

Emit(M.loc ‘:=’ M.loc [+] #1);

Emit(‘if’ M.loc [<=] Exp₂.loc ‘goto’ loop);

Exp₁.loc:= M.temp}

M::= prod Exp with ide to {temp:=newtemp(); Emit(temp:= Exp.loc); Emit(ide.loc ‘:=’ #1

M.temp:=temp; M.loc:= ide.loc}

Esercizio 14.a

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.

S₁::= repcase {init:= quad}

E of n: {next_case:= [quad]; Emit(‘if’ E.loc [<>] n.val ‘goto --’) }

S₂ {BK(S₂.next, quad); Emit(‘goto’ init);

R.in_init:= init; R.in_next_case:= next_case; R.in_loc:= E.loc}

R{S₁.next := R}

R₁::= ; n: {BK(R₁.in_next_case, quad);

next_case:= [quad]; Emit(‘if’ R₁.in_loc [<>] n.val ‘goto --’)}

S {BK(S.next, quad); Emit(‘goto’ R₁.in_init);

R₂.in_init:= R₁.in_init; R₂.in_next_case:= next_case; R₂.in_loc:= R₁.in_loc}

R₂{R₁.next := R₂.next}

R::= endrep {R.next:= R.in_next_case)}

Esercizio 14.b

Occorre modificare la grammatica: Fattoriziamo quel tanto che consenta di trattare ereditati come sintetizzati di opportuni marcatori.

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

S::= M1 endrep {S.next:= M1.next)}

M1::= M2 S {BK(S.next, quad); Emit(‘goto’ M2.init);

M1.init:= M2.init; M1.loc:= M2.loc; M1.next:= M2.next}

M2::= R n: {M2.init:= R.init; M2.loc:= R.loc; BK(R.next, quad); M2.next:= [quad];

Emit(‘if’ R.loc [<>] n.val ‘goto --’)}

R::= M1 ; {R.init:= M1.init; R.loc:= M1.loc; R.next:= M1.next}

R::= M3 E of {R.init:= M3.init; R.loc:= E.loc; R.next:= []}

Si confronti la soluzione con la variante che utilizza attributi ereditati

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.

S₁::= Case E of {L.inloc:= E.loc}
       L:  {BK(L.init,quad)}
       S₂ {R.instart:= L.nextcase; R.inloc:=E.loc}
       R  {S₁.next:= S₂.next + R.next}

R₁::= {BK(R₁.instart, quad); L.inloc:=R₁.inloc}
       ; L {BK(L.init,quad)}
: S {R₂.instart:= L.nextcase; R₂.inloc:=R₁.inloc}
      R₂ {R₁.next:= S.next + R₂.next}

R::= e {R.next:= R.instart}

L::= num {list:= [quad]; emit('if' L.inloc '=' num.val 'goto' --); L'.inloc:=L.inloc}
L' {L.init:= list + L'.init; L.nextcase:= L'.nextcase}

L'₁::= , num {list:= [quad]; emit('if' L'₁.inloc '=' num.val 'goto' --); L'₂.inloc:=L'₁.inloc}
L'₂{L'₁.init:= list + L'₂.init; L'₁.nextcase:= L'₂.nextcase}

L'::= e {L'.nextcase:= [quad], emit('goto' --)}

Esercizio22.1

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.

P::=  L : S {R.inlist:= S.ref}
       R {P.ref:= count(L.val, R.list)}

R₁::= ; L : S {R₂.inlist:= R₁.inlist + S.ref}
        R₂ {R₁.ref:= count(L.val, R₂.inlist}

R::= .{R.list:= R.inlist}

S::= ide := ide + ide {S.ref:= []}

S::= goto L {S.ref:= [L.val]}

S::= if ide = ide goto L {S.ref:= [L.val]}

Esercizio 24.a

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.

S₁::= loop {flag:= newtemp();init:= quad; Emit(flag ‘:= false’)}

B: {next_case:=[quad]; Emit(‘if’ B.loc [<>] ‘#true goto --’); Emit(flag ‘:= #true’)}

S₂ {R.in_init:= init; R.in_next_case:= next_case + S₂.next; R.in_flag:= flag}

R{S₁.next := R}

R₁::= {BK(R₁.in_next_case, quad)}

; B: {next_case:=[quad]; Emit(‘if’ B.loc [<>]‘#true goto --’);

Emit(R₁.in_flag ‘:= #true’)}

S {R₂.in_init:= R₁.in_init; R₂.in_next_case:= next_case + S.next;

R₂.in_flag:= R₁.in_flag}

R₂{R₁.next := R₂.next}

R::= end {BK(R.in_next_case, quad);

Emit(‘if’ R.in_flag [=] ‘#true goto’ R.in_init); R. next:=[]}

Esercizio 24.b

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

S::= M1 end {Emit(‘if’ M1.flag [=] ‘#true goto’ M1. init); S.next:=[]}

M1::= R:

S {M1.init:= R.init; M1.flag:= R.flag; BK(R.next+S.next, quad)}

R::= M1

; B {R.next:= [quad]; Emit(‘if’ B.loc [<>]‘#true goto --’); Emit(M1.flag ‘:= #true’);

R.init:= M1.init; R.flag:= M1.flag}

R::= M0

B {R.next:= [quad]; Emit(‘if’ B.loc [<>]‘#true goto --’); Emit(M0.flag ‘:= #true’);

R.init:= M0.init; R.flag:= M0.flag}

M0::= loop {flag:= newtemp(); M0.flag:= flag; M0.init:= quad; Emit(flag ‘:= false’)}

---

Esercizio1.2

Utiliziamo la grammatica della parte 1, fattorizzata limitatamente alle produzioni che richiedono azioni interne. Otteniamo la seguente nuova grammatica, che verifichiamo essere LR(1), quindi adatta a schemi ascendenti:

        Program::= Block
        B ::= Statement Rest_of_program
R ::= ; S R
        R ::= e
        S ::= ide := E
        S ::= H else S
        H ::= G then S
        G ::= if F
        E ::= T + E
E' ::= T
        E' ::= e
        T ::= ide
        T ::= (E)
        T ::= S
        F ::= ide = ide
        F ::= ide
        F ::= e

Per lo schema utiliziamo i seguenti attributi:
usuali: sintetizzato loc per la locazione del codice generato dall'attraversamento. In aggiunta:
t per il simbolo H: contiene la locazione generata dall'attraversamento del "ramo then" e che riferira' il valore calcolato dall'intero if. Peratnto tale locazione dovra' essere la stessa utilizzata dal "ramo else".
init_else per G: contiene gli incompleti generati dopo l'attraversamento della guardia e che devono far riferimento all'inizio del codice per il "ramo else".
end_if per H: contiene gli incompleti generati dopo l'attraversano del "ramo then" e che devono essere completati con la fine fisica del codice dell'if (ovvero l'inizio del codice che segue), come richiesto esplicitamente dall'esercizio.

P::= B

B::= C
      R

R₁::= C
        R₂

R::= e

S::= ide :=
E {emit(ide.loc ':=' E.loc); S.loc := ide.loc}

S₁::= H else S₂ {emit(H.t ':=' S₂.loc); BK(H.end_if, quad); S₁.loc:= H.t}

H::= G then S {H.t := newtemp(); emit(H.t ':=' S.loc); H.end_if:= [quad]; emit('goto' --); 
                       BK(G.init_else, quad)}

G::= if F {G.init_else:= [quad]; emit('if' F.loc '= false goto' --);}

E₁::= T + E₂ {t := newtemp(); emit(t ':=' T.loc  +.val  E₂.loc);  E₁.loc:=t}

E ::= T {E.loc := T.loc}

E'::= e {E'.loc:= E'.inloc}

T ::= ide {T.loc:= ide.loc}

T ::= ( E ) {T.loc:= E.loc}

T ::= S {T.loc:= S.loc}

F ::= ide₁ = ide₂ {t:=newtemp(); emit('if' ide₁.loc '=' ide₂.loc 'goto' quad+3); emit(t ':= false'); 
                           emit('goto' quad+2); emit(t ':= true'); F.loc := t}

F ::= ide {t:=newtemp(); emit('if' F'₁.inloc '=' 0 'goto' quad+3); emit(t ':= true'); 
               emit('goto' quad+2); emit(t ':= false'); F'.loc := t}

Esercizio21.2

Fattoriziamo la grammatica utilizzata nella parte 1, limitatamente alle produzioni che richiedevano azioni interne (di generazione di codice). Otteniamo la seguente grammatica che verifichiamo essere LR(1), quindi adatta ad un'analisi ascendente:

        S ::= H S
        H ::= R L :
        H ::= Case E of L :
        R ::= H S ;
        L ::= L , num
        L ::= num

Per lo schema utiliziamo i seguenti attributi, ovviamente tutti sintetizzati:
    loc per H ed R contiene la locazione del valore calcolato dall'esecuzione del codice generato dall'attraversamento dell'espressione di guardia
    list per L contiene i valori della lista di interi attraversata.
    nextcase sintetizzato di R 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.

S₁::= H S₂ {S₁.next:= H.next + S₂.next}

H::= R L: {BK(R.nextcase,quad);
                   scan:=L.list; open:=[]; 
                   while scan<>null do {open:=open+[quad]; 
                                                   emit('if' R.loc '=' top(scan) 'goto' --);
                                                   push(scan)};
                   BK(open, quad+1);
                   H.nextcase:= [quad];
                   emit('goto' --);
                   H.loc:= R.loc; H.next:= R.next}

H::= Case E of L: {scan:=L.list; open:=[]; 
                             while scan<>null do {open:=open+[quad]; 
                                                             emit('if' H.loc '=' top(scan) 'goto' --);
                                                             push(scan)};
                             BK(open, quad+1);
                             H.nextcase:= [quad];
                             emit('goto' --);
                             H.loc:= E.loc; H.next:= []}

R::= H S ; {R.loc:= H.loc; R.next:= S.next}

L₁::= L₂ , num {L₁.list:= [num.val] + L₂.list}

L::= num {L.list:= [num.val]}

Esercizio 24.a-1

Variante in cui utiliziamo traduzione short circuit per le espressioni booleane B. Riassumendo I nostri attributi sono:
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.
in_flag ereditato per R contiene il nome della variabile di controllo.
In aggiunta agli standard:
next per comandi
true per incompleti veri delle booleane.
false per incompleti falsi delle booleane.

S₁::= loop {flag:= newtemp();init:= quad; Emit(flag ‘:= false’)}

B: {next_case:= B.false; BK(B.true, quad); Emit(flag ‘:= true’)}

S₂ {R.in_init:= init; R.in_next_case:= next_case + S₂.next; R.in_flag:= flag}

R{S₁.next := R}

R₁::= {BK(R₁.in_next_case, quad)}

; B: {next_case:= B.false; BK(B.true, quad); Emit(flag ‘:= true’)}

S {R₂.in_init:= R₁.in_init; R₂.in_next_case:= next_case + S.next;

R₂.in_flag:= R₁.in_flag}

R₂{R₁.next := R₂.next}

R::= end {BK(R.in_next_case, quad);

Emit(‘if’ R.in_flag [=] ‘#true goto’ R.in_init); R. next:=[]}

---

[ Home | Back ]