Suggerimenti










Esercizio1.1

Tra le molte ragionevoli, conviene sceglierne una analizzabile LL(1): le analisi richieste nei punti successivi richiedono tutte un tale tipo di grammatica. Esercizio2.1 La grammatica data per l'esercizio 1.1 e' una soluzione anche per questo esercizio (si ricordi l'inclusione tra grammatiche: LL(1) inclusa in LR(1)). Potremmo domandarci se tale soluzione sia la piu' adatta. In effetti le analisi richieste in questo esercizio2 differiscono da quelle dell'esercizio1 per l'ordine di visita: discendente (top-down) il primo, ascendente (bottom-up) il secondo. Come sappiamo, i due ordini sono indifferenti allorche' gli attributi siano sintetizzati. Possiamo cosi' osservare che:
    tutte le soluzioni date nell'esercizio1 ed utilizzanti solo attributi sintetizzati sono soluzioni anche nel caso di
    analisi ascendente.
E' nel caso di ereditati che le cose cambiano. Esercizio3.1 Possiamo fornire una semplice grammatica in grado di applicare una derivazione ad ogni simbolo di imput letto. Ne daremo una LL(1) adatta per analisi discendente.
Ne daremo una seconda LR(1) vantaggiosa per analisi ascendente (sebbene nella soluzione delle altre parti dell'esercizio tale grammatica non sara' usata). Esercizio4 E' una semplificazione dell'esercizio1.7: se si incontrano difficolta' si affronti anzitutto l'esercizio1 a partire dal punto2 e continuando fino al punto8. Poi si affronti questo. Esercizio5 Si proceda nel seguente ordine.
1) si definisca una grammatica adatta per lo schema discendente, quindi LL(1): se ne controlli correttezza e proprieta';
2) l'analisi richiesta puo' essere condotta attraverso due analisi compeltamente indipendenti tra loro:
        a) Calcolo dell'occupazione di memoria: lo si affronti. Si definiscano gli attributi e le azioni per il loro calcolo. La soluzione proposta utilizza due attributi, entrambi sintetizzati, per questa analisi. Terminata questa parte si proceda con la successiva analisi come in b.
        b) Calcolo della profondita'. Si definiscano attributi ed azioni, estendendo cosi' lo schema di a. La soluzione proposta utilizza due attributi, uno ereditato. Esercizio6.1 Si proceda nel seguente ordine.
1) si definisca una grammatica adatta per lo schema discendente, quindi LL(1). Utilizzeremo la seguente: Program::= Qprocedure Rest_of_procedure
R::= ; Q R | e
Q::= procedure ide Formals; Body
F::= ( List_of_ide)
L::= ide Again_ide| e
A::= , ide A | ide
B::= Declaration Command; Sequence_of_commands | Command; Sequence_of_commands
D::= var ide A ;
C::= read ( ide A ) |  write ( ide A )  | ide := ide Expression| while ide = ide do C S od | call ide F
E::= + ide | e 2) L'esercizio e' impegnativo si affronti con la dovuta preparazione e in caso di difficolta' si affronti prima altri esercizi piu' semplici, inclusa la parte 6.2.
L'analisi richiede di rendere visibile ad ogni "C" che attraversa una struttura "while..." la lista delle variabili modificate nel corpo del while stesso. Occorre fare attenzione al calcolo delle modificate, tale lista deve includere tutte le variabili che sono assegnate, che occorrono in un comando read, che sono modificate in un comando while, che occorrono in una invocazione di procedura in corrispondenza di un parametro che e' modificato dalla procedura. Il calcolo di quest'ultima proprieta' richiede che le procedure sia analizzate e sia raccolta la lista dei parametri che pur trasmessi per riferimento sia modificabili all'interno del corpo della procedura (ovvero non siano coperti dalla portata di una variabile locale avente stesso nome, ed occorrano in statement che ne consentano la modifica: assegnamento, read, while, call.)
  Esercizio 8.1
        L'esercizio lascia ampia liberta nella scelta delle strutture con cui visualizzare il risultato della nostra analisi. Proponiamo una lista di coppie: una per ogni procedura. La coppia contiene il nome della procedura dichiarata come primo elemento e come secondo elemento, nell'ordine: la lista delle variabili o procedure usate ma non dichiarate, e un booleano segnalante la presenza di identificatori di procedura sati come variabili o viceversa di variabile usati come procedura. Ad esempio, il programma sotto a sinistra genera l'attributo sotto a destra:
 
Var x;
Procedure D;
  var x;
  x:=x+z;
  call E;
Procedure E;
  Var z;
  call D;
  x:= x+z;		 [<D,<[z,E], false>
  <E,<[],false>]
 
 
 
 
 
 
 

Si assume che lo scoping di ogni dichiarazione includa solo le dichiarazioni che seguono (e che non dichiarino un nuovo identificatore con stesso nome).

Esercizio9

L'esercizio in se' non presenta difficolta'. Occorre scegliere una grammatica LL(1) e affinche' non sia ambigua occore stabilire una priorita' per gli operatori: Abbiamo scelto la seguente grammatica.         E::= F E
       E::= "|" F E  |  e
        F::= H F
       F::= . H F  |  e
        H::= (E)M | "e" |  a | b | c
        M::= * | e

Puo' essere conveniente preoccuparsi all'inizio del calcolo dell'abero di sintassi astratta, quindi:

  1.     decidere gli operatori utilizzati per costruire l'albero
  2.     decidere l'attributo sintetizzato dei non terminali che dopo ogni attraversamento conterra' la rappresentazione della struttura attraversata
  3.     osservare che ne' E ne' F vedono il primo operando quindi devono averne la rappresentazione come ereditato.
A questo punto si arrivera' alle azioni per M: esso riceve come ereditato il suo operando e nel caso della produzione M::=* dovrebbe costruire un nuovo albero con operatore "*". Pero' l'esercizio richiede di evitarlo se l'operando e' gia' un'albero con radice *. Come distinguere questa situazione da quella in cui l'operando non ha radice *? E' sufficiente man mano che si costruiscono alberi settare un valore che dica se l'albero costruito ha radice * o meno. Questo valore deve essere ereditato da M insieme all'albero.


Esercizio11

L'esercizio in se' non presenta alcuna difficolta', salvo la scelta delle operazioni da utilizzare nelle azioni per costruire le strutture di record e puntatori richieste. Possiamo pensare subito a due distinte operazioni una per costruire puntatori a record a due campi, e una per costruire puntatori a record con tre campi, ad esempio:         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 puntatore pointer3
        newfield _ _ _: string x pointer2 x ponter3 -> pointer3 // calcola un puntatore, pointer3, ad un record di tre campi contenente quanto atteso.

Esercizio1.2

        Basta un attributo sintetizzato, tree. Inseriremo azioni che assegnino, durante l'analisi sintattica di ogni non terminale P, all'attributo P.tree il parse-tree "rooted" al nodo P.

Esercizio2.2

        Basta un attributo sintetizzato, tree. Inseriremo azioni che assegnino, durante l'analisi sintattica di ogni non terminale P, all'attributo P.tree il parse-tree "rooted" al nodo P.
 

Esercizio3.2

       La grammatica scelta, peraltro ragionevole, consente tuttavia di vedere solo un simbolo per volta mediante la produzione: S1::= L S2. Cio' comporta che S, in particolare S1, ricordi il simbolo attraversato precedentemente. Questo richiede un attributo booleano ereditato, cmd, che vale true se e solo se l'ultimo simbolo attraversato e' "&". Un attributo sintetizzato, string, calcolera' la stringa risolta tenendo conto anche del valore dell'attributo cmd.
 

Esercizio6.2

E' un'analisi contestuale: il valore da associare alle procedure dipende dalle procedure dichiarate prima. In questo caso la scelta della grammatica LR puo' essere importante: converra' uan grammatica che strutturi i programmi in modo che il "padre" di ogni nodo "procedura" possa avere visibilita' delle procedure che precedono. Cio' si ottiene banalmente fattorizzando a sinistra, ovvero:
      Program::= Rest_of_procedureQprocedure
useremo una grammatica che segua questo approccio. Esercizio 8.2
        Possiamo partire dalla grammatica data nella parte (1) ed usare i marcatori o la fattorizzazione a sinistra. Utilizzeremo la fatorizzazione a sinistra.

Esercizio1.3

Si introducano tre attibuti 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
 

Esercizio2.3

come esercizio1.3 sopra

Esercizio3.3

La soluzione data in esercizio3.2 ricorre all'impiego dell'attrinuto ereditato, cmd. La figura sotto mostra nella parte sinistra il grafo delle dipendenze di tale attributo per il parse di una qualunque stringa del linguaggio di 5 simboli. Possiamo utilizzare tale grammatica a patto di utilizzare i marcatori, trasformare l'attributo ereditato in un sintetizzato dei marcatori e esprimere le azioni come effetti laterali.
Una seconda soluzione puo' invece consistere nel fornire una grammatica per il linguaggio che fornisca parse tree della forma come a sinistra in figura. Questa forma di fattorizzazione (pero' effettiva) consente grafi di dipendenze come in figura e tratta gli ereditati come sintetizzati.

 
Esercizio1.4

Si introduca un attributo sintetizzato:

    depth per S, F, T: contiene il numero di archi del piu' lungo cammino contenuto nella foresta o albero rappresentato dalla frontiera del parse tree attraversato a partire
                da S,F, o T.
 

Esercizio2.4

Come esercizio1.4 sopra
 

Esercizio3.4

Occorre modificare la grammatica e con cio' definire un nuovo schema ad attributi. La nuova grammatica deve consentire di scorrere l'input guardando i due simboli adiacenti.
Diamo una seconda soluzione che risolve il problema dei due simboli terminali adiacenti come fosse un problema di analisi statica, ovvero introduce attributi che controllano che la stringa analizzata sia nel sottolinguaggio richiesto.

Esercizio1.5

Si introducano due attributi sintetizzati:

    outd per S, F, T: contiene l'outdegree massimo dei nodi nella foresta o albero rappresentato dalla frontiera del parse tree attraversato a partire
                da S,F, o T.
   length per F: contiene il numero di alberi (ovvero lunghezza lista fratelli) nella foresta rappresentata dalla frontiera del parse tree attraversato a partire da F

Esercizio1.6

Si introduca un attributo sintetizzato:

    A per S, F, T, L: contiene il numero di nodi etichettati "A" nella foresta o albero rappresentato dalla frontiera del parse tree attraversato dal simbolo.

Esercizio1.7

Si introducano tre attibuti sintetizzati:

    DepthA per S, F, T: contiene la profondita' massima dell'albero con radice "A" occorrente nella foresta o albero rappresentato dalla frontiera del parse tree attraversato dal
                     simbolo.
    depth per S, F, T come in esercizio 1.4
    label per L come in esercizio 1.3

Esercizio1.8

Si introducano quattro attibuti sintetizzati:

    OutdA per S, F, T: contiene l'outdegree massimo dell'albero con radice "A" occorrente nella foresta o albero rappresentato dalla frontiera del parse tree attraversato dal
                     simbolo.
    outd per F, T come in esercizio 1.5
    length per F come in esercizio 1.5
   label per L come in esercizio 1.3
 
 

[ Home | Back ]