Analisi Statica

Esercizio 2

Si consideri il linguaggio delle foreste di alberi etichettati rappresentati come liste parentesizzate di alberi separati da virgola. Ogni albero, che non sia un solo nodo, e' rappresentato da una coppia di elementi, separati da virgola e racchiusi tra parentesi quadre. Il primo di tali elementi e' l'etichetta della radice, il secondo la foresta degli alberi formata dai figli della radice. Alberi formati da un solo nodo sono rappresentati dall'etichetta del nodo. L'alfabeto delle etichette sia {A,B,C,D,E}.
Un esempio di frase del linguaggio è ([A,(B,[C,(D)]], [D,(A,E,B,C)]) ed essa rappresenta la foresta
 


Si risponda alle seguenti domandi:

  1. Si dia una grammatica per il linguaggio
  2. Si dia una grammatica ad attributi per un analisi ascendente che calcoli come attributo di ogni nodo non terminale il parse tree derivato da tale nodo. Allo scopo si utilizzino le seguenti operazioni per la costruzione di alberi:
    1. MkT:: Etichetta x ListaAlberi -> Albero  /* MkT(a,f) crea albero con radice etichettata a e con figli gli alberi in f, nell'ordine in cui occorrono */
    2. MkE::  -> ListaAlberi  /* crea una lista vuota */
    3. Add:: Albero x ListaAlberi  -> ListaAlberi  /* Add(t,f) aggiunge t come primo albero*/
  3. Si dia una grammatica ad attributi per un analisi ascendente che calcoli come attributo del simbolo distinto la foresta di alberi derivata. Allo scopo si utilizzino le operazioni sopra: in particolare si utilizzino liste di alberi per le foreste.
  4. Si dia una grammatica ad atributi per un analisi ascendente che calcoli come attributo del simbolo distinto la profondita' della foresta rappresentata dalla stringa derivata.
[ Home | Back ]

 
  
Ultimo aggiornamento 26 Aprile 2001