Svolgere due esercizi da ciascun gruppo: “Analizzatori lessicali”, “Analizzatori sintattici”. La coppia di esercizi da svolgere in ciascun gruppo è determinata dalla seguente funzione Haskell:
generaCoppia nEsercizi matricola = (primo, secondo) where
primo = matricola `mod` nEsercizi + 1
secondo = ((matricola `div` nEsercizi) `mod` (nEsercizi - 3) + primo + 1) `mod` nEsercizi + 1
dove l’argomento “nEsercizi” deve essere istanziato con il numero di esercizi del gruppo, mentre l’argomento “matricola” è la propria matricola.
Nota. La descrizione delle grammatiche all’interno degli esercizi è informale e a volte ambigua. Nel risolvere gli esercizi, le grammatiche vanno formalizzate e quindi le ambiguità devono essere risolte. Questo può essere svolto in vari modi, tutti sono considerati accettabili.
Consegna. Per ciascun esercizio vanno consegnati: i file sorgente degli analizzatori; un breve documento che descriva la grammatica formalizzata e le scelte fatte per risolvere le ambiguità; alcuni file di prova con il relativo output.
Utilizzando, a scelta, uno degli applicativi Lex, Flex o Alex, realizzare degli analizzatori lessicali che risolvano due dei seguenti problemi:
Riconoscere in un file di testo le seguenti classi di lessemi
_,
-.\" e
\n,+, ++, -,
--, =, ==,Per ogni lessema riconosciuto, stampare una coppia (classe, valore). Per ogni carattere non riconosciuto, segnalare un errore indicandone riga e colonna.
Rimuovere i commenti da un testo Haskell. I commenti Haskell hanno due possibili formati:
-- e terminano con
il ritorno a capo{- e terminano con
la stringa -}Si cerchi inoltre di risolvere il problema di riconoscere coppie di
commenti innestati, ossia la stringa {- aa {- bb -} cc -}
viene riconosciuta come un singolo commento e non come il commento
{- aa {- bb -} seguito dalla stringa cc -}
Si tenga conto che le sequenze -- e {-
all’interno di una stringa (es. "a--b") non iniziano un
commento.
Rimuovere i commenti da un programma Java, sia quelli su una
singola linea, marcati da //, che quelli disposti su più
linee, marcati da /* e */.
Si cerchi inoltre di risolvere il problema di riconoscere coppie di
commenti innestati, ossia la stringa /* aa /* bb */ cc */
viene riconosciuta come un singolo commento e non come il commento
/* aa /* bb */ seguito dalla stringa cc */
Si tenga conto che le sequenze // e /*
all’interno di una stringa (es. "http://...") non iniziano
un commento.
Selezionare, in un file di testo, le stringhe di caratteri che
rappresentano un numero in notazione romana. Solo i numeri romani devono
essere stampati in uscita, ciascuno seguito dal suo valore decimale tra
parentesi (es. XIV (14)) e separati da uno spazio; la
restante parte del testo viene eliminata. Si considerino solo parole
intere, scritte in lettere maiuscole, che rappresentino numeri compresi
tra 1 e 3999 (quindi, ad esempio, le parole “di” e “mi” non vanno
riconosciute).
Selezionare in un file di testo le stringhe di caratteri che rappresentano un numero multiplo di tre, nell’usuale notazione decimale. Solo i numeri multipli di 3 vengono stampati in uscita, separati da uno spazio, la restante parte del testo viene eliminata. Il controllo di divisibilità deve essere implementato usando opportune espressioni regolari, e non l’operazione di divisione-resto.
Selezionare in un file di testo le stringhe di caratteri che rappresentano in notazione binaria un numero multiplo di 3. Solo i numeri multipli di 3 vengono stampati in uscita, separati da uno spazio, la restante parte del testo viene eliminata. Il controllo di divisibilità deve essere implementato usando opportune espressioni regolari, e non l’operazione di divisione-resto.
Riconoscere, in un file di testo, le sequenze di caratteri che rappresentano un numero in uno dei seguenti formati:
Per ciascuna sequenza riconosciuta, stampare in uscita: la sequenza stessa, il tipo di numero rappresentato, il numero di cifre usate nella rappresentazione.
Riconoscere stringhe di cifre e caratteri, che rappresentano i numeri in uno dei seguenti formati:
0FFH; la parola BAH non va riconosciuta).Per ciascuna stringa riconosciuta stampare in uscita il formato del numero riconosciuto e il suo valore decimale.
Ricevuta in input una sequenza di sostantivi nella lingua italiana, trasformare al plurale i sostantivi femminili e al singolare quelli maschili. Il programma può applicare una semplice regola generale per catalogare un sostantivo come femminile-maschile, singolare-plurale ma deve riuscire a gestire almeno una decina di eccezioni a questa regola (es. mano, tema, radio, parentesi, uomo).
Ricevuta in input una sequenza di verbi, trasformare i verbi all’infinito in verbi al gerundio e i verbi al participio passato in verbi all’infinito; il participio passato va riconosciuto anche nelle forme femminili e plurali (es. amata, amati, amate). Le altre forme verbali restano inalterate. Si supponga che i verbi siano quasi tutti regolari ma si arricchisca il programma in modo che sia in grado di trasformare correttamente 5 verbi irregolari a scelta.
Utilizzando Lex-Yacc o Alex-Happy, costruire una coppia di analizzatori, uno lessicale e uno sintattico, che insieme siano capaci di riconoscere i seguenti linguaggi:
Quando è richiesto l’albero sintattico, questo va costruito
esplicitamente durante l’analisi, usando un’opportuna struttura dati (ad
esempio un tipo di dato algebrico in Haskell, o una struttura con
puntatori ai figli in C), e va poi stampato in output in un formato a
scelta dello studente. Un formato possibile consiste nello scrivere la
radice come nome di funzione e i sottoalberi come suoi argomenti:
l’espressione 1 + 2 * 3 diventa
Plus(1, Times(2, 3)).
Il linguaggio formato da espressioni aritmetiche scritte in
notazione polacca inversa e costruite a partire dalle costanti intere e
le 4 operazioni aritmetiche. L’analizzatore deve costruire l’albero
della struttura sintattica dell’espressione ricevuta in ingresso e
stampare l’espressione in notazione infissa, usando il numero minimo di
parentesi: ad esempio, 1 2 3 + * diventa
1 * (2 + 3), 1 2 - 3 - diventa
1 - 2 - 3 e 1 2 3 - - diventa
1 - (2 - 3).
Il linguaggio formato da sequenze di definizioni ed espressioni
aritmetiche scritte in notazione polacca diretta, separate da
;. Le espressioni sono costruite a partire dalle costanti
intere, dalle variabili e dalle 4 operazioni aritmetiche; una
definizione ha la forma x = <espressione>.
L’analizzatore deve valutare le espressioni ricevute in ingresso, usando
la divisione intera, e segnalare l’uso di variabili non definite: ad
esempio, x = + 1 2 ; * x 3 restituisce 9.
Il linguaggio formato da espressioni aritmetiche costruite a partire da:
**,L’ordine di priorità tra i vari operatori è definito in questo modo:
per le operazioni aritmetiche vale l’ordine usuale, l’esponente ha
priorità sulle funzioni trigonometriche che a loro volta hanno priorità
sul prodotto. Tutte le operazioni binarie associano a sinistra, tranne
l’esponente, che associa a destra. Le funzioni trigonometriche possono
essere applicate anche senza parentesi: ad esempio,
sin x ** 2 va letto come sin (x ** 2) e
sin x * y come (sin x) * y.
L’analizzatore deve restituire l’albero della struttura sintattica dell’espressione ricevuta in ingresso.
Il linguaggio delle espressioni aritmetiche nella forma usata nelle scuole medie, ossia
L’analizzatore deve controllare che le parentesi siano inserite secondo le usuali regole: parentesi tonde più interne, seguite dalle quadre, e poi graffe. L’analizzatore deve inoltre valutare l’espressione in ingresso, usando la divisione intera.
Un frammento del linguaggio Java formato da:
<, ==,=, assegnazione con incremento
+=,; e blocchi { }L’analizzatore deve restituire l’albero della struttura sintattica
del comando ricevuto in ingresso. Si presti attenzione all’ambiguità del
dangling else: in if (a) if (b) x = 1; else x = 2;
l’else va associato all’if più interno, come
in Java.
Sequenze di espressioni in linguaggio Haskell formate da:
let in e caseNon è necessario implementare la regola del layout (indentazione): si
può assumere che le definizioni di let e le alternative di
case siano racchiuse tra { } e separate da
;, ad esempio
let { x = 1; y = 2 } in case x of { 1 -> y; n -> 0 }.
L’analizzatore deve restituire gli alberi sintattici delle espressioni ricevute in ingresso.
Sequenze di espressioni in linguaggio Haskell formate da:
+, *, -==if then elseL’analizzatore deve valutare le espressioni ricevute in ingresso.
Sequenze di espressioni in linguaggio Scheme formate da:
+, *, -, con un numero
variabile di argomenti, come in Scheme (es. (+ 1 2 3))=let e caseL’analizzatore deve restituire gli alberi sintattici delle espressioni ricevute.
Sequenze di espressioni in linguaggio Scheme formate da:
+, *, -, con un numero
variabile di argomenti, come in Scheme (es. (+ 1 2 3))=let, if e caseL’analizzatore deve valutare le espressioni ricevute in ingresso: ad
esempio, (let ((x 2)) (if (= x 2) (* x 3) 0)) restituisce
6.