ProgettinoLexYacc < Prog_avanzata

Tags: view all tags

----
----

<H2>Programmazione Avanzata</H2>

<H3>Corso di Laurea Specialistica in Informatica</H3>

<H3>Anno Accademico 2007/08</H3>

----

<H3>[[Users.StefanoGuerrini][Stefano Guerrini]]</H3>

=guerrini&nbsp;at&nbsp;di.uniroma1.it=


----
----

<H1>Progettino sull'uso di Lex/Yacc</H1>

----
----

<nop>[ [[LezioniAA0708][Lezioni]] <nop>]
<!-- <nop>[ [[EsercitazioniAA0708][Esercitazioni]] <nop>] -->
<nop>[ [[AnnoAcc0708][Corso 2007-08]] <nop>]
<nop>[ [[Prog_avanzata.WebHome][Pagina principale]] <nop>]


---++++ Sintassi concreta per il linguaggio di cui si è visto l'interprete a lezione

Lo scopo del progetto è fornire una sintassi concreta per il linguaggio di cui, partendo dalla semantica denotazionale, si è studiato e implementato l'interprete in OCAML nella prima parte del corso (per i lucidi delle lezioni corrispondenti si veda la [[LezioniAA0708][pagina delle lezioni]] è anche disponibile il [[http://twiki.di.uniroma1.it/pub/Prog_avanzata/LezioniAA0708/SemDen-OCAML.tgz][codice OCAML completo]]).


L'obiettivo è scrivere un programma che prende da input il programma scritto nella sintassi concreta e produce in output la stringa corrispondente al termine associato al programma letto rappresentato nella sintassi astratta definita a lezione.

Notare che l'albero del termine rappresentato nella sintassi astratta potrebbe non essere esattamente l'albero sintattico corrispondente al programma nella sintassi concreta. Ovvero, a seconda delle scelte della sintassi concreta, il programma eseguito potrebbe dover eseguire una sorta di compilazione.

Le caratteristiche che si richiede di implementare sono:

   * Espressioni
      * Tipi di dato: interi e booleani.
      * Operazioni su interi: prodotto, somma, differenze, operatore unario per il segno.
      * Predicati su interi: equivalenza, test per zero.
      * Operazioni booleane: or, and e negazione.
      * Espressioni composte:
         * if-then-else su espressioni: il risultato è l'espressione del ramo then se il test è vero, o quella del ramo else altrimenti
         * let: assegnazione (locale) di una espressione ad una variabile all'interno di un'altra espressione
      * Operazioni su variabili e riferimenti (o puntatori):
         * un operatore che restituisce il valore denotato da una variabile (nella sintassi concreta può anche non corrispondere a nessun operatore sintattico, dato che si può assumere che l'occorrenza di una variabile x in una espressione stia ad indicare semplicemente il valore da essa denotata)
         * un operatore che crea e in inizializza una locazione e restituisce il riferimento all'espressione (tipo l'operatore ref di ocaml)
         * un operatore che riceve una espressione che viene valutata a un riferimento e restituisce il contenuto della locazione associata  al riferimento (tipo l'operatore ! di ocaml)
      * Funzioni
         * sintassi per la definizione di funzioni senza nome (lambda-notazione) definite dalla lista dei parametri formali e dall'espressione corrispondente al corpo della funzione
         * applicazione di funzioni
         * costrutto per la definizione di funzioni ricorsive (tipo il costrutto let rec)

   * Comandi
      * Assegnamento: assegnamento del valore di una espressione a un oggetto che viene valutato ad un riferimento
      * If-then-else: esecuzione condizionale di comandi
      * While: iterazione di comandi
      * Blocco: creazioni di blocchi di comandi che nella prima parte possono contenere delle dichiarazioni, ovvero una sequenza di coppie variabile, espressione che associa a ogni variabile il valore denotato dalla corrispondente espressione.

   * Programma
     * Si tratta semplicemente di un blocco

Si può anche scegliere di implementare solo parte delle caratteristiche richieste, omettendo quelle più complicate.

Come detto precedentemente,  l'obiettivo è quello di produrre un output eseguibile dall'interprete ocaml fornito a lezione. La più semplice soluzione prevede che l'analizzatore sintattico generi una stringa corrispondente a un termine ocaml corretto rispetto alla sintassi astratta definita nell'interprete. Questo modo di procedere prevede che, dato il programma scritto nella sintassi concreta, mediante l'analizzatore sintattico si genera il termine ocaml corrispondente, quindi con cut & paste o con una lettura diretta da dentro un programma ocaml il temime viene fornito come argomento all'interprete.

Chi può scegliere di integrare direttamente l'analizzatore dentro l'interprete ocaml, ad esempio, usando i tool [[http://caml.inria.fr/pub/docs/manual-ocaml/manual026.html][ocamllex e ocamlyacc]] invece di lex e yacc.

Per maggiori informazioni e documentazione su ocamllex e ocamlyacc si veda:
   * [[http://caml.inria.fr/pub/docs/manual-ocaml/manual026.html][il capitolo del manuale ocaml che descrive ocamllex e ocamlyacc]]
   * un tutorial su ocamlex (versione [[http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/][html]] o [[http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial.pdf][pdf]]) e su ocamlyacc (versione [[http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/][html]] o [[http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial.pdf][pdf]])

---

*N.B.* In tutto il documento si è fatto riferimento a lex e yacc, ma ovviamente, è possibile (e consigliato) usare le corrispondenti (più potenti ed evoute) versioni free software di questi tool: flex e bison.

---
---
-- Users.StefanoGuerrini - 23 May 2008