ESAME DI LINGUAGGI E TRADUTTORI

3 Febbraio 2000 - Parte I (2 ore)

Esercizio 1

1. Scrivere una grammatica che generi ed un automa che riconosca il linguaggio

L = { c^s (a^q (b | c)^m bdⁿ )^p b^h b⁺ a^2k |m>= n+q, p+h+k< s, p,q > 0 , n,k,s,m >=0}

2. Scrivere un parser discendente per il Linguaggio definito dalla grammatica le cui produzioni sono di seguito riportate:

S ®RaS| P| Q

P ®bR| V

Q ®cUdR| QbS

R ®RT| e

V ®fRR f| fRf| bR

T ®0| ...|9

U ®a | aT

ESAME DI LINGUAGGI E TRADUTTORI

3 Febbraio 2000 - Parte II (2 ore)

Esercizio 2

1. Sia data una lista di liste di interi L. Ogni sottolista Li e’ costituita da H interi, H>1, e l’ultimo elemento C definisce la classe di appartenenza dei primi H-1 interi diLi. Scrivere un programma Prolog

classi(L,T)

che costruisca una lista T, a partire da L, del seguente formato:

[C1,[A1,A2,...,An],C2,[B1,B2,...,Bm],...CK,[Z1,Z2,...,Zp]]

dove Ci, i=1,...,K sono le differenti classi dichiarate dalle sottoliste con i rispettivi elementi ottenuti fondendo le liste Li appartenenti ala stessa classe. Ad esempio, se

L=[[1,1,2,3],[3,4,5,1,2],[2,4,3],[5,7,10,11,12,2],[1,2,1]]

allora T sara’

[3,[1,1,2,2,4],2,[3,4,5,1,5,7,10,11,12],1,[1,2]]

2. Siano dati una lista T dello stesso formato della lista T dell’esercizio precedente ed un intero K. Ricostruire la lista L dell’esercizio precedente in cui ogni sottolista consiste di al piu’ K elementi. Questo implica che, se gli elementi di una classe sono M e M>K, si dovranno costruire M/K liste per quella classe.

Esercizio 3

1. Scrivere una macchina di Turing che date due stringhe v, w Î{0,1}⁺ separate da uno spazio bianco, verifichi se esistono due sottostringhe r di v e s di w di lunghezza 3 tali che r = sT.

2. Verificare se la seguente grammatica e’ LR(1) :

S ®Bb| SAaS| e

A ®eA| c

B ®BdB| a