Laboratorio di Informatica I: Programmazione

Progetto Pascal

Scopo del progetto è la realizzazione in Pascal di un analizzatore sintattico per grammatiche acontestuali, che implementi l'algoritmo di analisi CYK, descritto nel corso di Programmazione I. Il programma è schematicamente diviso nelle tre fasi seguenti:

1. Acquisizione dei dati (una grammatica acontestuale G);

2. Costruzione della forma normale di Chomsky di G, G';

3. Costruzione dell'analizzatore sintattico CYK di G',

descritte nelle tre sezioni seguenti.

1 Acquisizione dati

La grammatica in input, G = (T, N, S, P), viene letta da un file di testo in cui le produzioni in P sono memorizzate nel formato seguente:

X₁ = s¹₁|s²₁|...|sⁿ¹₁

...

X_m = s¹_m|s²_m|...|s^nm_m

Si assume che S = X₁, che N = {X_1, X_{2, ...,} X_m} e che T sia l'insieme dei simboli che compaiono in almeno una delle stringhe s^j_i, 1<= i <= m, 1<= j <= n_i e non appartengono ad N. Come ipotesi semplificativa, assumiamo che N sia sottoinsieme di [A..Z] e che T sia sottoinsieme di [a..z]. La parola vuota "e" verrà rappresentata dal simbolo "*". Per 1<= j <= m-1, la lista di alternative relative al non terminale Xj termina con un carattere di fine linea, e per j = m con l'end-of-file.

Ad esempio, la grammatica

G = ({A, B}, {a, b}, A, {(A, aAa), (A, B), (B, bBb), (B, e)})

è rappresentata da

A = aAa|B

B= bBb|*

Nella fase di acquisizione dati, il file testo contenente la rappresentazione di G viene letto, e la grammatica memorizzata in una qualche struttura ritenuta opportuna per effettuare le operazioni previste dalle fasi seguenti.

2 Normalizzazione

In questa fase la grammatica G letta nella fase precedente viene normalizzata, eseguendo in sequenza i passi seguenti:

- eliminazione delle produzioni nulle, cioé della forma (A, e), con A diverso da S;

- eliminazione delle produzioni ridondanti, cioé della forma (A, B), con B appartenente ad N;

- eliminazione delle produzioni multiple, cioé della forma (A, s) con taglia (s) >= 2 e s non appartenente a N².

Queste trasformazioni, note dal corso di Programmazione I, trasformano G in una grammatica equivalente (che genera cioé lo stesso linguaggio) in forma normale di Chomsky, che chiameremo G'.

Alla fine di questa fase è richiesto di stampare G', nello stesso formato descritto nella fase precedente, sul terminale, e di memorizzarla in un file.

3. Analisi grammaticale

Questa fase consiste di un ciclo di interazioni con l'utente: in ciascuna iterazione viene chiesto di inserire da tastiera una parola w appatenente a T*, che supponiamo di lunghezza non superiore a 20 caratteri, seguita dal carattere ".", e viene verificato se tale parola appartiene o meno al linguaggio generato da G', attraverso una implementazione dell'algoritmo CYK, descritto nel corso di Programmazione I. Il ciclo e l'esecuzione del programma terminano quando l'utente dichiara di non voler analizzare ulteriori parole.

4. Ipotesi semplificative

Introduciamo due ipotesi su G, che ne facilitano la normalizzazione:

- ipotesi 1: G non contiene e-produzioni, a parte eventualmente la produzione (S, e). Inoltre se (S, e) appartiene a P, allora S non appare in alcun sⁱ_j.

- ipotesi 2: G non contiene produzioni multiple.

Nella realizzazione del progetto si supponga che G soddisfi queste ipotesi. La soluzione del problema nel caso generale, cioé quello in cui le due ipotesi sopra non sono necessariamente verificate, è considerata facoltativa.

Per scaricare il file zip contenente il file eseguibile, il codice e la relazione in formato Word 97, cliccare sull'immagine qui sotto:

Laboratorio di Informatica I: Programmazione

Progetto ML

Scopo del progetto è la realizzazione in ML di un insieme di strumenti che permettano di definire dei circuiti combinatori e compiere alcune operazioni su di essi. I circuiti in questione sono realizzati a partire dai seguenti tipi di porte logiche:

• - porte binarie: AND, OR, NAND, NOR;
• - porte unarie: NOT;
• - porte 0-arie (costanti): VERO, FALSO

e da variabili che denotano linee di ingresso al circuito, e che supporremo essere rappresentate da interi positivi; più specificamente, l'insieme delle variabili di un circuito sarà sempre della forma VAR(1), VAR(2), ..., VAR(n), per un certo intero non negativo n. Una volta definito in ML il tipo ricorsivo circuito i cui elementi rappresentano dei circuiti come quelli descritti sopra, definire le funzioni seguenti:

1. Funzione di valutazione: dato un circuito, stampa sul video il grafo della funzione booleana da esso calcolata. Ad esempio, la valutzione del circuito:

OR(AND(OR(VAR(1), NOT(VAR(2))), AND(VAR(3), VERO)), VAR(1))

è:

2. Funzione di standardizzazione: dato un circuito, ne restituisce uno equivalente (che calcola cioé la stessa funzione) composto unicamente da porte NAND, ca costanti e da variabili.

3. Funzione di fusione: dati due circuiti C e C', aventi rispettivamente n e n' variabili, ne restituisce un terzo, D, avente n+n' variabili tale che la valutazione di D sui valori b₁, ..., b_n, b'₁, ..., b'_n, sia l'AND delle valutazioni di C su b₁, ..., b_n e di C' su b'₁, ..., b'_n'.

4. Funzione di sintesi: data una funzione ML f di tipo

(Bool x Bool x Bool x Bool x Bool) -> Bool

(che supponiamo totale), restituisce un circuito C che calcola f, e che è in forma normale disgiuntiva.

5. Funzione di normalizzazione: preso un circuito, ne restituisce uno equivalente in forma normale disgiuntiva.

6. Funzione di ottimizzazione: un circuito non triviale (diverso cioé da VERO o FALSO) è ridondante se calcola una funzione costante. Ad esempio:

AND(VAR(1), NOT(VAR(1)))

e NOT(VERO) sono circuiti ridondanti. Il circuito:

AND(VAR(1), OR(VAR(1), NOT(VAR(1))))

non è ridondante ma il suo sottocircuito OR(VAR(1), NOT(VAR(1))) lo è. La funzione di ottimizzazione, preso un circuito C, restituisce un circuito equivalente C' che ha la proprietà che nessun sottocircuito (proprio o improprio) è ridondante.

Per scaricare il file zip contenente il codice e la relazione in formato Word 97, cliccare sull'immagine qui sotto:

Ringrazio i miei colleghi Massimo Delungo e Evelise Pintonello per aver contribuito alla realizzazione di questi due progetti.

Indietro