Linguaggi e Traduttori

Prof. Marco Gavanelli

21 luglio 2016

Esercizio 1 (punti 14)

In seguito ad un terremoto, alcune strade di una regione non sono più utilizzabili. Le strade ancora attive sono riportate in un file di testo grafo2.txt, che contiene le coppie di città collegate da una strada (una strada per ogni riga del file).

Si desidera sapere quali città non sono più raggiungibili a partire dal capoluogo di regione. Il nome del capoluogo è la prima città che compare nel file grafo2.txt.

Si scriva un programma Haskell che visualizza le città che non sono raggiungibili.

Per ottenere l'insieme delle città raggiungibili, si può usare il seguente algoritmo.

1. Inizialmente, si considera raggiungibile il capoluogo. Sia R₀ l'insieme iniziale di città raggiungibili; l'insieme R₀ conterrà quindi il solo capoluogo.
2. Nell'i-esima iterazione, si inserisce nell'insieme R_i l'insieme delle città che sono collegate con una strada ad una delle città che erano raggiungibili in R_i−1 (più, chiaramente, le città che erano in R_i−1).

Esempio Supponiamo che il file grafo2.txt contenga

Inizialmente, l'insieme dei raggiungibili contiene solo il capoluogo: R₀={0}

Al passo 1, vengono aggiunte le città che sono collegate da una strada alla città 0: R₁={0,1,4}.

Al passo 2, vengono aggiunte le città che sono collegate da una strada alle città in R₁; poiché c'è una strada da 3 a 1, la città 3 viene aggiunta: R₂={0,1,3,4}.

Al passo 3, vengono aggiunte le città collegate da una strada alle città in R₂. Non ve n'è nessuna, per cui R₃=R₂={0,1,3,4}.

A questo punto, visto che non è possibile aggiungere altre città, l'algoritmo termina; le città 2 e 5 vengono considerate irraggiungibili.

Si scriva il programma in modo che possa essere creato l'eseguibile; si usino opportunamente funzioni di ordine superiore e/o list comprehensions.

Per ottenere punteggio pieno, si richiede di utilizzare la funzione predefinita

che, data una funzione f ed un valore a, restituisce la lista infinita [a, f a, f (f a), f (f (f a)), ...].

Esercizio 2 (Punti 4)

Si scriva un programma Lex che, dato un testo, riconosce i numeri romani (3 punti) e li sostituisce con la loro rappresentazione in numeri arabi (1 punto). Non è necessario considerare numeri maggiori o uguali a 4000.

Si può ipotizzare che il testo contenga solo lettere maiuscole e spazi.

Si ricordano le seguenti corrispondenze fra numeri romani e numeri arabi.

e gli altri numeri si ottengono come somma (ad es. MCMXLIV = 1000+900+40+4=1944).

Ad esempio, dato il testo

CI CIC NUMERO LXI MCMXLIX MMXVI VENTIDUE MCMXVIIII

produce

101 CIC NUMERO 61 1949 2016 VENTIDUE MCMXVIIII

Soluzione 1

import Data.List

main = do
    string <- readFile "grafo2.txt" 
    let archi = map words (lines string)
    let nodes = remdups (words string)
    let iteration = iterate (reachable1 archi) [head(words string)]
    let reached = stable iteration
    let unreached = difference nodes reached
    print unreached

-- rimozione duplicati
remdups xs = foldr (\y ys -> y:filter (/= y) ys) [] xs

-- calcola i nodi raggiungibili in 1 passo a partire dall'insieme nodes
reachable1 edges nodes = (sort.remdups) ([a|[a,b]<-edges, n<-nodes, n==b]++[b|[a,b]<-edges, n<-nodes, n==a]++nodes)

stable (a:b:xs)
   | a==b      = a
   | otherwise = stable (b:xs)

difference xs ys = filter (not.((flip elem) ys)) xs

Soluzione 2

%{
#include <:stdio.h>

int convDigit(char c)
{	if (c=='M') return 1000;
	if (c=='D') return 500;
	if (c=='C') return 100;
	if (c=='L') return 50;
	if (c=='X') return 10;
	if (c=='V') return 5;
	if (c=='I') return 1;
	return 0;
}

int convert(char s[])
{
	int i=0,n=0,x;
	while (s[i]!=0)
	{	x=convDigit(s[i]);
		if (convDigit(s[i+1])>x)
			n=n-x;
		else n=n+x;
		i++;
	}
	return n;
}

%}

ROMAN	M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})
ALTRO	[a-zA-Z]+


%%

{ROMAN}	{ int n = convert(yytext);
		  printf("%d",n);
        }

{ALTRO}	{printf("%s",yytext);	}

%%