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:
Si dia una grammatica per il linguaggio
Si dia una grammatica ad attributi per un analisi discendente 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:
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 */
MkE:: -> ListaAlberi /* crea una lista
vuota */
Add:: Albero x ListaAlberi -> ListaAlberi /*
Add(t,f) aggiunge t come primo albero */
Si dia una grammatica ad attributi per un analisi discendente 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.
Si dia una grammatica ad atributi per un analisi discendente che calcoli
come attributo del simbolo distinto la profondita' della foresta rappresentata
dalla stringa derivata.
Si dia una grammatica ad atributi per un analisi discendente che calcoli
come attributo del simbolo distinto l'ampiezza della foresta rappresentata
dalla stringa derivata (ovvero massimo outdegree dei nodi occorrenti nella
foresta).
Si dia una grammatica ad atributi per un analisi discendente che calcoli
come attributo del simbolo distinto il numero di nodi, della foresta rappresentata
dalla stringa derivata, etichettati con l'etichetta A.
Si dia una grammatica ad atributi per un analisi discendente che calcoli
come attributo del simbolo distinto la massima profondita' degli alberi
(e sottoalberi) occorrenti nella foresta ed aventi radice etichetta A.
Si dia una grammatica ad atributi per un analisi discendente che calcoli
come attributo del simbolo distinto la massima ampiezza degli alberi (e
sottoalberi) occorrenti nella foresta ed aventi radice etichetta A.
