Si consideri la seguente grammatica:

$$ S\rarr Sab\space |\space Ab\\ A\rarr cA\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 la seguente grammatica:

$$ S\rarr A\copyright A\space |\space A\\ A\rarr A\blacksquare\space |\space B\\ B\rarr \underline{num} $$

1. Scrivere un SDD che calcoli un attributo $p$ del simbolo $S$ che sia un puntatore al nodo radice dell’albero sintattico astratto dell’espressione generata da $S$. $p$ è di tipo Node cioè un nodo che può contenere un solo valore intero, un operatore $(Op\in \{\copyright,\blacksquare\})$ e un puntatore a un nodo oppure un operatore a due puntatori a nodi.

Per generare i puntatori ai nodi dell’albero sintattico astratto si possono usare le funzioni makeLeaf : int → Node, makeNode1 : Op x Node → Node, makeNode2 : Op x Node x Node → Node

Ad esempio, l’espressione $3\copyright 5\blacksquare \blacksquare$ ha come albero sintattico astratto associato quello disegnato qui sotto a sinistra. A destra è riportato invece l’albero che l’SDD deve costruire con le funzioni indicate e deve associare all’attributo $p$ di $S$.

• Soluzione

Si consideri la seguente grammatica

$$ S'\rarr S(0)\\S\rarr aSc(1)\space |\space auBc(2)\\ B\rarr bBc(3)\space |\space vc(4) $$

in cui i numeri tra parentesi sono la numerazione delle produzioni. Per la grammatica è stata calcolata la seguente tabella di parsing bottom-up:

1. Eseguire il parsing della stringa “aaubbvccccc”