Si consideri la seguente grammatica:

$$ S\rarr aAb\space |\space bAa\\ A\rarr Ac\space |\space \epsilon $$

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

• 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è $a$ o $b$, o una sotto-lista essa stessa (anche vuota)

1. Si dia uno schema di traduzione che calcoli un attributo intero $n_a$ del simbolo iniziale che sia pari al numero di ‘a’ che appaiono nella lista stessa e in tutte le sue sotto-liste. Non è necessario che la grammatica che si definisce per l’SDT sia LL(1)

Esempi: per la lista $()$ l’attributo $n_a$ deve essere uguale a 0. Per la lista $(a,(a,b),b)$ l’attributo $n_a$ deve essere uguale a 2 (cioè il numero di ‘a’ totali). Per la lista $((),(b,b))$ deve essere $n_a=0$

• Soluzione

Si consideri il seguente SDD:

$$ S\rarr L\space \{L.exp=0; S.v=L.v\}\\ L\rarr L_1B\space \{L_1.exp=L.exp+1; L.v=L_1.v+2^{L.exp}\times B.b\}\\ L\rarr B\space \{L.v=2^{L.exp}\times B.b\}\\ B\rarr \underline 0 \space \{B.b=0\}\\ B\rarr \underline 1 \space \{B.b=1\} $$

dove gli attributi $exp,v$ e $b$ sono di tipo intero

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 1001. Si disegnino gli attributi ereditati a sinistra di ogni nodo e gli attributi sintetizzati a destra di ogni nodo.

• Soluzione