Esercizi Grammatiche

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.

Analizzatori lessicali

Utilizzando, a scelta, uno degli applicativi Lex, Flex o Alex, realizzare degli analizzatori lessicali che risolvano due dei seguenti problemi:

1. Riconoscere in un file di testo le seguenti classi di lessemi

   • parole chiave: var, function, procedure, while, do, if, then, else, for
   • identificatori: stringhe che iniziano con una lettera minuscola dell’alfabeto, seguita da lettere, cifre, e i simboli _, -.
   • costanti numeriche: sequenze di cifre,
   • operatori: +, ++, -, --, =, ==,

   Per ogni lessema riconosciuto, stampare una coppia (classe, valore).

2. Rimuovere i commenti da un testo Haskell. I commenti Haskell hanno due possibili formati:

   • iniziano con la stringa di caratteri -- e terminano con il ritorno a capo
   • iniziano con la stringa di caratteri {- 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.

3. 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.

4. 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, 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).

5. Selezionare in un file di testo le stringhe di caratteri che rappresentano un numero multiplo di quattro, nell’usuale notazione decimale. Solo i numeri multipli di 4 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.

6. 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.

7. Riconoscere, in un file di testo, le sequenze di caratteri che rappresentano un numero in uno dei seguenti formati:

   • numero intero: stringa di cifre decimali, eventualmente preceduta dal segno (+/-)
   • numero frazionario: coppia di stringhe di cifre separate da un punto, eventualmente preceduta dal segno; una delle due stringhe, ma non entrambe, può essere vuota.
   • floating point: numero intero o frazionario, seguito da “e”, oppure “E”, seguito da un numero intero.

   Per ciascuna sequenza riconosciuta, stampare in uscita: la sequenza stessa, il tipo di numero rappresentato, il numero di cifre usate nella rappresentazione.

8. Riconoscere stringhe di cifre e caratteri, che rappresentano i numeri in uno dei seguenti formati:

   • numeri interi: stringa di cifre decimali, eventualmente preceduta dal segno (+/-)
   • numeri esadecimali: stringa di cifre esadecimali (0-9, a-f, A-F) preceduta dalla sequenza “0x”, oppure una stringa di cifre esadecimali che inizia con una cifra decimale ed è seguita da ‘H’ (es. 0FFH; la parola BAH non va riconosciuta).
   • numeri ottali: stringa di cifre ottali (0-7) preceduta dalla sequenza “0o”, oppure una stringa di cifre ottali seguita da ‘O’.

   Per ciascuna stringa riconosciuta stampare in uscita il formato del numero riconosciuto e il suo valore decimale.

9. 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).

10. 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.

Analizzatori sintattici

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 stampato in forma testuale, ad esempio parentetica: l’espressione 1 + 2 * 3 diventa (+ 1 (* 2 3)).

1. 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 restituire l’albero della struttura sintattica dell’espressione ricevuta in ingresso.

2. Il linguaggio formato da espressioni aritmetiche scritte in notazione polacca diretta e costruite a partire dalle costanti intere e le 4 operazioni aritmetiche. L’analizzatore deve valutare l’espressione ricevuta in ingresso, usando la divisione intera.

3. Il linguaggio formato da espressioni aritmetiche costruite a partire da:

   • identificatori,
   • costanti numeriche: numeri naturali,
   • le 4 operazioni aritmetiche,
   • esponente: **,
   • le funzioni trigonometriche: sin, cos, tan,
   • parentesi.

   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.

4. Il linguaggio delle espressioni aritmetiche nella forma usata nelle scuole medie, ossia

   • numeri interi,
   • 4 operazioni aritmetiche,
   • le tre forme di parentesi: tonde, quadre, graffe.

   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.

5. Un frammento del linguaggio Java formato da:

   • identificatori,
   • costanti numeriche,
   • espressioni aritmetiche con le 4 operazioni e confronti <, ==,
   • assegnazione =, assegnazione con incremento +=,
   • if else,
   • ciclo while,
   • separatori ; 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.

6. Sequenze di espressioni in linguaggio Haskell formate da:

   • numeri interi
   • identificatori
   • applicazione
   • costrutti let in e case

   Non è 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.

7. Sequenze di espressioni in linguaggio Haskell formate da:

   • numeri interi
   • operazioni aritmetiche: +, *, -
   • test di uguaglianza: ==
   • il costrutto if then else

   L’analizzatore deve valutare le espressioni ricevute in ingresso.

8. Sequenze di espressioni in linguaggio Scheme formate da:

   • identificatori
   • numeri interi
   • operazioni aritmetiche: +, *, -, con un numero variabile di argomenti, come in Scheme (es. (+ 1 2 3))
   • test di uguaglianza: =
   • i costrutti let e case

   L’analizzatore deve restituire gli alberi sintattici delle espressioni ricevute.

9. Sequenze di espressioni in linguaggio Scheme formate da:

   • numeri interi
   • operazioni aritmetiche: +, *, -, con un numero variabile di argomenti, come in Scheme (es. (+ 1 2 3))
   • test di uguaglianza: =
   • costrutti if e case

   L’analizzatore deve valutare le espressioni ricevute in ingresso.