Si consideri la seguente grammatica:

$$ S\rarr Sa\space |\space aA\\ A\rarr bAc\space |\space bcc $$

1. Scrivere il linguaggio generato dalla grammatica tramite insiemi di stringhe
2. La grammatica è SLR? Giustificare la risposta
3. In caso di risposta affermativa alla domanda precedente, dare la tabella del parser bottom-up associato ed eseguire il parsing della stringa “abbccc”

• Soluzione

Si consideri un linguaggio di liste definite ricorsivamente come segue:

• $()$ è la lista vuota;
• $(x_1,\dots,x_k)$ è una lista dove ogni $x_1$ può essere un atomo, cioè $p$ o $q$, o una sotto-lista essa stessa (anche vuota)

1. Si dia una grammatica per il linguaggio associata a uno schema di traduzione che calcoli un attributo intero $n_p$ del simbolo iniziale. L’attributo $n_p$ deve essere uguale al numero totale di elementi $p$ che appaiono nella lista stessa o in una delle sue sotto-liste. Non è necessario che la grammatica che si definisce per l’SDT sia LL(1)

Esempi: per la lista $()$ l’attributo $n_p$ deve essere uguale a 0. Per la lista $(p,(p,q,p),(p,q))$ l’attributo $n_p$ deve essere uguale a 4 (cioè il numero totale di $p$ nella lista e in ogni sotto-lista). Per la lista $((p,q),p,(p),q)$ l’attributo $n_p$ deve essere uguale a 3. Per la lista $((),(q,q))$ deve essere $n_p$ uguale a 0.

• Soluzione

Si consideri il seguente SDD:

dove gli attributi $i,t$ sono di tipo stringa

1. Si disegni l’albero di parsing annotato (cioè l’albero di derivazione in cui tutti i nodi hanno associati tutti i loro attributi con i relativi valori) per la stringa $\underline{int}[2][4][3]$. Si disegnino gli attributi ereditati a sinistra di ogni nodo e gli attributi sintetizzati a destra di ogni nodo.

l’attributo $b$ in $B$ in realtà dovrebbe essere $t$

• Soluzione