1. Si consideri la seguente espressione regole sull’alfabeto $\varSigma=\{p,q,r\}$:

$$ (p|q|r)^*(pr|pq)rp $$

Si dia un automa minimo che accetti il linguaggio denotato dall’espressione. Si mostrino tutti i passi che sono stati seguiti per arrivare alla soluzione

• Soluzione

1. Si consideri la seguente definizione regolare sull’alfabeto $\varSigma=\{a,b\}$

$$ d_1\rarr a^b\space \space (\text{Token1})\\ d_2\rarr ba^\space \space (\text{Token2})\\ d_3\rarr abab\space \space (\text{Token3}) $$

Si indica quali token vengono generati da un analizzatore lessicale che usa le regole “longest match” e “first one listed” in corrispondenza della stringa di input ababb$. Si mostrino tutti i passi che sono stati seguiti per il riconoscimento dei token.

• Soluzione

1. Si consideri la seguente grammatica:

$$ S\rarr aS\space |\space bc\space |\space BccC\\ B\rarr bB\space |\space b\\ C\rarr Cc\space |\space \epsilon $$

1. Si scriva formalmente il linguaggio generato dalla grammatica come insieme di stringhe.
2. La grammatica è LL(1)? Giustificare la propria risposta.
3. Il linguaggio generato dalla grammatica è LL(1)? Se sı, si dia una grammatica LL(1) per il linguaggio e la tabella di un parser predittivo top-down.

• Soluzione

Si consideri un linguaggio di definizione di tipi record composti che permette di associare un nome al tipo definito ed elenca tutte le variabili (con relativo tipo) che fanno parte del record, separate da punto e virgola. Un tipo record deve contenere almeno due variabili (sono esclusi quindi i tipi record che contengono una sola variabile). Una o più variabili del tipo possono essere a loro volta un tipo record composto (definito ricorsivamente). I tipi di base sono solo int e bool. Un esempio possibile e il seguente (dove id e un token di tipo identificatore che conterrà come lessema il nome specifico della variabile o del tipo):

Definire una grammatica LL(1) per il linguaggio descritto e dare la tabella di un parser predittivo top-down