1. Si consideri la seguente grammatica:

$$ S\rarr aSbc\space |\space aB\\B\rarr ccB\space |\space c $$

1. Si scriva formalmente il linguaggio generato dalla grammatica come insieme di stringhe
2. La grammatica è SLR? Si giustifichi la risposta

• Soluzione

2. Si consideri la seguente grammatica:

$$ S\rarr B\space |\space Caa\\ B\rarr bC\\ C\rarr bbCa\space |\space \epsilon $$

1. Si scriva formalmente il linguaggio generato dalla grammatica come insieme di stringhe
2. Si dia l’automa degli item LR(1) per la grammatica e la relativa tabella di parsing. Eseguire il parsing shift-reduce bottom-up per la stringa “bbba” utilizzando la tabella data
3. La grammatica è LALR? Si giustifichi la risposta

• Soluzione

3. 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. 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 è il seguente (dove id e un token di tipo identificatore che conterrà come lessema il nome specifico della variabile o del tipo):

type id {
					id : int;
					id : bool;
					id : type id {
													id : int;
													id : bool
											 }
				}

1. Definire uno schema di traduzione (Syntax Directed Translation Scheme - SDT) che calcoli, per il simbolo iniziale, un attributo v di tipo int. Per un certo tipo dato, v deve essere uguale allo spazio in byte necessario per memorizzare una variabile del tipo stesso. Si consideri che lo spazio necessario per memorizzare un int è 4 e lo spazio necessario per memorizzare un bool è 1. Per l’esempio dato sopra il valore v calcolato dovrà essere uguale a 10, corrispondente a 5 byte per le due variabili int e bool iniziali più 5 per la terza variabile il cui tipo (definito ricorsivamente) ha di nuovo bisogno di 4 (per l’intero) + 1 (per il booleano) = 5 byte.

• Soluzione

4. Si consideri un linguaggio di espressioni definite ricorsivamente come segue:

• $x$ è una espressione;