Relazione Progetto Informatica Teorica 2006/2007


Progetto Svolto da
Filippo De Santis
mat. 0000245081


Creative Commons License
Questo/a opera è pubblicata sotto una Licenza Creative Commons.



Indice Argomenti :
  1. Linguaggio
  2. Scanner
  3. Parser
  4. Inteprete






Linguaggio


Linguaggio : Introduzione

Il linguaggio scelto per implementare questo progetto, comprende costrutti molto simili al C e ad altri linguaggi della stessa famiglia.
Si è utilizzata la stessa forma del linguaggio C per le dichiarazioni delle variabili, per l'assegnamento e le operazioni aritmetiche. Per le operazioni condizionali invece si è preferito utilizzare dei costrutti simili al C ma che definissero in maniera più specifica l'inizio e la fine di tali operazioni ("if - endif" e "while - endwhile").
Per il costrutto che specifica la parallelizzazione di una o più istruzioni si è creata la parola chiave "parallelo". Le operazioni da eseguire tramite il costrutto "parallelo" sono racchiuse tra parentesi graffe.
Infine, per quel che riguarda l'ordine in cui verranno valutate le operazioni aritmetiche, esse saranno valutate da destra a sinistra senza la possibilità di inserire parentesi o altri simboli per la modifica dell'ordine di valutazione delle operazioni.

Linguaggio : La Grammatica (Forma BNF)


Insieme dei Simboli Terminali : T = {begin, var, real, [(a..z)+(A..Z)+(0..9)*]+, (0..9)+.(0..9)+ , end, parallelo, endp, while, endwhile, (, ), ;, = =, >, <, >=, <=, <>, AND, OR, =, +, *, /, -, if, else, endif, return};

Insieme dei Simboli Non Terminali : N = {INI, DIC, A, R, Ob, Oc, COD, CONDS, VARS, TYPE, NAME, OP_COND, OP_LOGIC, Vn, Tn, VTn};

Insieme delle Produzioni : P
  1. <INI> ::= begin <DIC> <A> <R> end
  2. <DIC> ::= <DIC> <DIC>
  3. <DIC> ::= var <TYPE> <NAME> ;
  4. <A> ::= <A> <A> | <Vn> = <Ob> | <Oc> | parallelo {COD} 
  5. <COD> ::= <COD> <COD> | <A> endp
  6. <Ob> ::= <Vn> ; | <Tn> ;
  7. <Ob> ::= <Vn> + <Ob> | <Tn> + <Ob>
  8. <Ob> ::= <Vn> * <Ob> | <Tn> * <Ob>
  9. <Ob> ::= <Vn> / <Ob> | <Tn> / <Ob>
  10. <Ob> ::= <Vn> - <Ob> | <Tn> - <Ob>
  11. <Oc> ::= while ( <CONDS> ) <A> endwhile
  12. <Oc> ::= if ( <CONDS> ) <A> endif
  13. <Oc> ::= if ( <CONDS> ) <A> else <A> endif
  14. <CONDS> ::= <VTn> <OP_COND> <VTn> | <VTn> <OP_COND> <VTn> <OP_LOGIC> <CONDS>
  15. <VTn> ::= <Vn> | <Tn>
  16. <R> ::= return ( <VARS> ) ;
  17. <VARS> ::=  <Vn> ; <VARS> | <Vn>
  18. <TYPE> ::= real
  19. <NAME> ::= [(a..z)+(A..Z)+(0..9)*]+
  20. <Vn> ::= [(a..z)+(A..Z)+(0..9)*]+
  21. <Tn> ::= (0..9)+.(0..9)+
  22. <OP_COND> ::=  = = | >= | <= | > | < | <>
  23. <OP_LOGIC> ::= AND | OR

Le Produzioni più siognificative presenti in questa grammatica sono quelle derivabili direttamente dal simbolo non terminale "A".
Queste produzioni comprendono tutte le attività che si possono sviluppare con questo linguaggio : operazioni di assegnamento di un valore ad una variabile, operazioni condizionali e cicli, operazioni di parallelizzazione del codice.

- Assegnamento: Da "A" derivano tutte le produzioni di terminali della forma " <variabile> = <variabili o numero> ;" o "<variabile> = <variabile o numero> <+,*,-, / > <variabile o nuemro> ... ;" . Per la scrittura di queste espressioni di terminali viene coinvolto anche il simbolo non terminale "Ob" da cui derivano le "operazioni base o aritmentiche" presenti nel mio linguaggio.

- Condizioni e Cicli : Da "A" si possono derivare direttamente il costrutto "IF" e il costrutto "WHILE". Il primo prevede due possibili scritture, una con la presenza della keyword "else" al siuo interno e una senza la keyword "else". Una particolarità di questo costrutto è che se l' "if" prevede la presenza dell' "else" allora ne può contenere solamente una occorrenza (per eseguire degli "else if" cosecutivi l'unico modo è prevedere una derivazione "if" da "A" successiva alla keyword "else"). Il secondo costrutto, invece, ci dà la possibilità di implementare dei cicli rispetto a una o più condizioni che vengono valutate una prima volta prima di svolgere il costrutto "while" e poi ad ogni ciclo di operazioni contenute tra le keyword "while" ed "endwhile".

- Parallelizzazione : Infine da "A" si può derivare l'operazione di parallelizzazione. Questa operazioni prevede la presenza di una (banale) o più sezioni di codice da svolgere in parallelo. In particolare, per come si è implementato l'interprete, per ogni porzioni di codice presente nel costrutto "parallelo" si svolgeranno le operazioni della sezione e poi tutte quelle successive restituendo un risultato per ogni porzione di istruzioni "parallelizzata".

Linguaggio : Esempi


1) Calcolare il fattoriale di un numero e verificare se è superiore o meno a "b"
L'esempio sotto riportato esegue queste operazioni:
Codice esempio:

begin
var real a;
var real b;
var real c;

a = 5;
c = a - 1;

parallelo{
        b = 30;
    endp
        b = 200;
    endp
}

while(c > 0)
    a = a * c;
    c = c - 1;
endwhile

if(a > b)
    c = 1;
else
    c = 0;
endif

return (c);

end

Il risultato dell'applicazione dell'interprete a questo listato di operazioni è la produzione di due vettori di variabili:

V1(b = 30) : [a, 120.0] [b, 30.0] [c, 1.0]
V2 (b = 200): [a, 120.0] [b, 200.0] [c, 0.0]

Si nota che nel primo vettore la variabile "c" è ad 1, quindi la condizione è verificata, mentre nel secondo vettore la variabile "c" è 0 e la condizione a > b non è verificata.


2) Calcolare la divisione di un numero per i primi 4 numero primi a partire da 2:

Operazioni eseguite:
Codice:

begin
var real a;
var real b;
var real c;

a = 100;
c = 0;

parallelo{
b = 2;
endp
b = 3;
endp
b = 5;
endp
b = 7;
endp
}

c = a / b;

return (c);

end

Questo secondo esempio prevede l'utilizzo solamente dei costrutti "if" e  "parallelo". I vettori delle variabili risultanti dall'applicazione dell'interprete a questo listato sono:

V1 : [a, 100.0] [b, 2.0] [c, 50.0]
V2 : [a, 100.0] [b, 3.0] [c, 33.333333333333336]
V3 : [a, 100.0] [b, 5.0] [c, 20.0]
V4 : [a, 100.0] [b, 7.0] [c, 14.285714285714286]


3) Calcolo della potenza n-esima di un numero:

Operazioni eseguite:
Codice:

begin
var real pot;
var real a;
var real b;
var real c;

a = 2;
c = 1;

parallelo{
pot = 4;
endp
pot = 8;
endp
pot = 12;
endp
pot = 16;
endp
}

b = pot;

while(b > 0)
c = c*a;
b = b - 1;
endwhile

return (c);

end

In questo ultimo esempio abbiamo utilizzato il costrutto parallelo e il costrutto while per il calcolo della potenza di un numero rispetto a diversi valori dell'esponente. I vettori delle variabili per ogni sezione di codice parallelo risulteranno:

V1 : [pot, 4.0] [a, 2.0] [b, 0.0] [c, 16.0]
V2 : [pot, 8.0] [a, 2.0] [b, 0.0] [c, 256.0]
V3 : [pot, 12.0] [a, 2.0] [b, 0.0] [c, 4096.0]
V4 : [pot, 16.0] [a, 2.0] [b, 0.0] [c, 65536.0]





Scanner

Scanner : Introduzione

Lo scanner implementato esegue le operazioni di lettura dei token dal file e di memorizzazione di questi token su uno stack.
Lo stack di token creato dallo scanner sarà poi utile al parser per la valutazione delle produzioni e conterrà degli oggetti identificati da un valore e un tipo ([abc Vn], [= OP_AS], [ > OP_COND], [OR OP_LOGIC], etc.).
All'interno dello scanner  viene anche creato il vettore delle variabili diachirate. Questo vettore è fondamentale per lo svolgimento delle operazioni dell'interprete in quanto è utilizzato per contenere il valore delle variabili del mio listato. Inoltre lo scanner sfrutta questo vettore per verificare se una stringa del listato è una variabile o meno, e se non lo è viene segnalato un'errore.

Scanner : I Token

Per il riconoscimento dei token presenti nel mio listato ho utilizzato diversi automi. In particolare questi automi andavano a valutare le stringhe che incontravo e in base al loro primo carattere le categorizzavano come numeri, stringhe, condizioni, keyword, etc.

1) Riconoscimento numeri: Se il priomo carattere della mia stringa è un numero, continuo a leggere gli altri carattere fintanto che sono numeri o contengono una virgola seguita da almeno un numero.

2) Operazione "=" e "= =" : Se leggo il primo carattere ed è un "=" vado a verificare se anche il successivo è un uguale. Se non lo è ho un'operazine di assegnamento e memorizzo l'oggetto corrispondete nello stack, altrimenti ho una operazione condizionale e memorizzo sullo stack un simbolo "condizione" con valore corrispondente alla stringa trovata.

3) Operazione ">" e "> =" : Analogamente al caso precedente se leggo ">" ho sicuramente una operazione condizionale ma devo verificare se ci sia o meno la presenza del simbolo "=". Una volta verificata la presenza di "=" posso memorizzare sullo stack un simbolo "condizione" con valore corrispondente alla stringa trovata.

4) Operazione "<" e "< =" e "<> : Analogamente al caso "3" valuto la presenza , dopo il simbolo "<", dei simboli "=" o ">". Queste tre stringhe rappresentano tutte una condizione, quindi verificata quale delle stringhe mi trovo a leggere memorizzo sullo stack un simbolo "condizione" con valore corrispondente alla stringa trovata.
 
5) Riconoscimento variabili e keyword: Se trovo un carattere dell'alfabeto dia minuscolo che maiuscolo posso applicare l'utoma per il riconoscimento delle stringhe. Una volta ottenuta la stringa vado a valutare se questa è una variabile, controllando nel vettore delle variabili dichiarate, o se è una keyword confrontandola con le keyword utilizzabili nel mio linguaggio. Se la stringa non corrisponde a nessuna di queste due tiipologie di strnghe il programma viene bloccato e viene segnalato un errore.

Scanner : Descrizione Classi

Scanner.java

All'interno di questa classe viene letto il file e vengono implementati gli automi per il riconoscimento delle stringhe, dei terminali numerici e dei terminali come parentesi, operazioni algebriche e operazioni condizionali.

Attributi della classe:
  1. SchemaListato schema : Oggetto utilizzato per la memorizzazione dei token e la verifica che questi appartengano al linguaggio
La classe contiene i seguenti metodi:
  1. public Scanner() : E' il costruttore della classe;
  2. public boolean cercaToken(String percorso) : Metodo per far partire la ricerca dei token; la stringa "percorso" viene utilizzata per indicare il path del file da cui ricavare i token. All'interno di questo metodo vengono applicati gli automi per il riconoscimento dei token che poi vengono passati alla classe SchemaListato.java;
  3. public Stack<StackObject> get_stack() : Metodo che restituisce lo stack dei token;
  4. public VarID getVarIDList() : metodo che restituisce il vettore delle variabili dichiarate;

SchemaListato.java

All'interno della classe SchemaListato.java vengono eseguiti i controlli sulle dichiarazioni delle variabili e vengono memorizzati i token nello stack che poi verrà passato al parser. La classe contiene come attributi l'array delle keyword e l'array delle operazioni condizionali del linguaggio.

Attributi della classe:
  1. String parole_chiave[] : array delle keyword del mio linguaggio
  2. String op_logic[] : array delle operazioni logiche del mio linguaggio
  3. VarID variabili : array delle variabili dichiarate
  4. MemorizzaElementoListato memo : Oggetto a cui viene delegata la memorizzazione dei token su file
  5. Stack<StackObject> stack : Oggetto Stack in cui memorizzare i token

La classe contiene i seguinti metodi:
  1. SchemaListato() : Costruttore;
  2. public void putElemento(String tipo, String value, int riga) : Metodo per l'inserimento di un token nell'array dei token; Il nome del token è dato dalla variabile "name", il valore dalla variabile "value" ed infine il parametro "riga" indica la riga in cui è stato trovato il token ed è utilizzata per indicare, se si verificano errori, che token si stava valutando e in che riga si trovava. All'interno di questo metodo viene anche valutato quando si sta leggendo una dichiarazione di una variabile (serie di token "var", "real" "<name>" e ";"), se la verifica va a buon fine la variabile viene memorizzata nel vettore delle variabili dichiarate. Infine per ogni stringa che non corrisponde ad una keyword del mio linguaggio si valuta se è una variabile dichiarata e se non lo è si segnala un errore.
  3. public VarID getVarIDList() : Restituisce il vettore delle variabili dichiarate creato nel metodo precedente;
  4. public Stack<StackObject> get_stack() : Restituisce lo stack dei token creato nel metodo "putElemento";

VarID.java

Classe utilizzata all'interno di SchemaListato.java. Questa classe descrive un oggettro tramite cui memorizzare le variabili dichiarate in un vettore.

Attributi della classe:
  1. Variabili[] variabili_listato : Array dove memorizzo il vettore delle variabili dichiarate
  2. int ind_var : numero di variabili memorizzate
La classe contiene i seguenti metodi:
  1. public VarID() : Metodo costruttore, inizializza l'array delle variabili.
  2. public boolean put_varID_stringa(String var_name, String var_type, String value, boolean output) : Inserisce una variabili di nome "var_name", di tipo "var_type" con valore "value" nell'array delle variabili dichiarate. Inoltre il parametro "output" indica se questa variabile dovrà essere stampata a video o meno al momento dell'interpretazione dell'istruzione "return".
  3. public boolean setValueVar(String var_name, String value) : Aggiornamento del valore della variabile "var_name" con il valore "value";
  4. public String getVarValue(String name) : Restituisce il valore della variabile "name";
  5. public Variabili getVar(String var_name) : Restituisce un oggetto di tipo "Variabili" descritto dalla classe "Variabili.java". Questo oggetto contiene tutte le caratteristiche di una variabile dichiarata;
  6. public boolean isSet(String var_name) : Verifico se esiste una variabile di nome "var_name";
  7. public boolean isOutput(String var_name) : Verifico se la variabile "var_name" è indicata come una variabile di output;
  8. public void setOutput(String var_name) : Setto la variabile "var_name" come una variabile di output;
  9. public int getNumeroVariabili() : Restituisco il numero di variabili dichiarate;
  10. public void printVar() : Metodo utilizzato dall'interprete per stampare le variabili di output e i loro valori alla fine dell'esecuzione del listato;
  11. public VarID clone() : Override del metodo "Object.clone()". Necessario per l'implementazione del costrutto parallelo all'interno del quale si devono "moltiplicare" i vettori delle variabili dichiarate per tenere traccia di ogni opperazione parallela.

MemorizzaElementoListato.java

Classe attraverso la quale andiamo a memorizzare su file ogni oggetto memorizzato poi sullo stack.

Attributi della classe:
  1. File f
  2. FileOutputStream fos
  3. PrintStream ps
La classe contiene i seguenti metodi :
  1. public MemorizzaElementoListato() : Costruttore, inizializza il file su cui andremo a tenere traccia dei token trovati;
  2. public boolean inserisciElemento(String tipo, String value) : Inserisce l'elemento di tipo "tipo" e valore "value" nello stack che poi utilizzarà il parser e scrive l'elemento nel file di riferimento dei token.

Variabili.java

Classe utilizzata per descrivere gli oggetti che compongono il vettore delle variabili dichiarate.

Attributi della Classe :
  1. String name
  2. String type
  3. String valore
  4. boolean output : parametro che indica se una variabile va stampata o meno alla conclusione dell'interpretazione del codice
La classe continene i seguenti metodi:
  1. public Variabili() : Costruttore
  2. public boolean setVar(String identificativo, String tipo) : Utilizzato per modificare il nome e il tipo dell'oggetto;
  3. public String getNameVar() : Restituisce il parametro "name";
  4. public String getTypeVar() : Restituisce il parametro "type";
  5. public void valorizza(String val) : Modifica il parametro "valore" dell'oggetto;
  6. public String getVal() : Restituisce il parametro "valore";
  7. public void setOutput() : Setta a "true" il valore del parametro "output";
  8. public boolean isOutput() : Resistuisce il valore del parametro "output";

Stack.java

Classe utilizzata per implementare uno stack i cui elementi possono essere oggetti diversi. Questa classe infatti per mette di istanziare uno stack formato da una tipologia di elementi qualsiasi. All'atto della crazione dell'oggetto Stack sarà quindi necessario esplicitare a quale classe apparterrano gli elementi di Stack. In particolare ho crato una classe StackObject.java che descrive gli oggetti che utilizzo.

Attributi della classe :
  1. ArrayList<E> stack_token : Array di oggetti "E" che viene manipolato come fosse una pila
La classe continene i seguenti metodi:
  1. public Stack() : Costruttore
  2. public void push(E item) : Inserimento di un elemento in cima alla pila;
  3. public E pop() : Rimuovo un elemento dalla cima della pila
  4. public int nchild() : Restituisce il numero di elementi della pila
  5. public Stack<E> clone() : Override del metodo "Object.clone" utilizzato per la gestione del costrutto "parallelo" nel parsing.

StackObject.java

La classe descrive gli oggetti che andrò ad utilizzare come elementi dello stack dei token.

Attributi della classe:
  1. String type : Descrizine del tipo di elemento memorizzato
  2. String value : Valore dell'elemento memorizzato
La classe contiene i seguenti metodi:
  1. public StackObject(String tipo, String valore) : Costruttore;
  2. public String get_type() : Restituisce il parametro "type" dell'elemento;
  3. public String get_value() : Restituisce il parametro "value" dell'elemento;
  4. public StackObject get_object() : Restituisce l'elemento stesso;

Scanner : Osservazione

E' importante osservare che la pila di token creata durante la fase di scansionamento dei token del codice avrà come primo elemento il corrispondente dell'ultimo token letto ( la parola chiave "end") e come ultimo elemento il corrispondente del primo token letto (la parola chiave "begin"). Andremo quindi a derivare le nostre produzione dai terminali partendo dal "fondo" del codice.

Parser

Parser : Introduzione

Il parser implementato è un parser Botto-Up. In particolare l'implementazione è effettuata leggendo l'input da sinistra a destra e andando a creare delle derivazione rightmost.
Ho deciso di implementare un parser con il metodo Bottom-Up prendendo spunto dalla teoria dei parser LR che utilizzano uno stack in cui sono memorizzati i token del mio linguaggio e da questi, per passi successivi, si creano delle derivazioni rightmost che riducono lo stack fino ad avere il solo nodo iniziale della grammatica analizzata. Per la verifica dell'esattezza del linguaggio ho implementato degli automi che riconoscessero i prefissi delle produzioni della grammatica e che sono descritti al punto "Parser : La Grammatica".
Infine il parser produrrà, oltre alla verifica della sintassi del cosdice, anche un albero di parsing che verrà utilizzato dell'interprete.

Parser : La Grammatica

La Grammatica utilizzata è la stessa descritta al punto "Linguaggio : La Grammatica". All'interno del parsing ho sviluppato degli automi per il riconoscimento delle varie porzioni del codice tramite la lettura dei token memorizzati sulla pila creata durante la fase di "scansione" del codice.
Descrivo ora gli automi implementati per il riconoscimento delle produzioni della grammatica.
  1. Produzione : <R> ::= return ( <VARS> ) ;
    1. Estraggo dalla pila il token "end", altrimenti segnalo un errore;
    2. Stato R1 : Se estraggo il token ";" passo allo stato R2, altrimenti segnalo un errore;
    3. Stato R2 : Se estraggo il token ")" passo allo stato R3, altrimenti segnalo un errore;
    4. Stato R3 : Se estraggo il token "Vn" passo allo stato R4, altrimenti segnalo un errore;
    5. Stato R4 : (Eseguo una riduzione a VARS )
      1.  Se estraggo il token ";" passo allo stato R3, altrimenti segnalo un errore;
      2. Se estraggo il token "(" passo allo stato R5, altrimenti segnalo un errore;
    6. Stato R5 : Se estraggo il token "return" passo allo stato accettante R6, altrimenti segnalo un errore;
    7. Stato R6 (accettante) : Eseguo una riduzione a "R" e accetto l'input;
  2. Produzione : <DIC> ::= <DIC> <DIC> | var <TYPE> <NAME> ; 
    1. Estraggo dalla pila il token ";", altrimenti segnalo un errore;
    2. Stato D1 : Se estraggo il token "NAME" passo allo stato D2, altrimenti segnalo un errore;
    3. Stato D2 : Se estraggo il token "TYPE" passo allo stato D3, altrimenti segnalo un errore;
    4. Stato D3 : Se estraggo il token "var" passo allo stato accettante D4, altrimenti segnalo un errore;
    5. Stato D4 : Eseguo una riduzione a "DIC" e accetto l'input;
  3. Produzione : <A> ::= <Vn> = <Ob> | <Oc> | parallelo {COD}
    1. Produzione : <A> ::= <Vn> = <Ob>
      1. Produzione :  <Ob> ::= <Vn> ; | <Tn> ; | <Vn> + <Ob> | <Tn> + <Ob> | <Vn> * <Ob> | <Tn> * <Ob> | <Vn> / <Ob> | <Tn> / <Ob> | <Vn> - <Ob> | <Tn> - <Ob>
        1. Estraggo dalla pila il token ";", altrimenti segnalo un errore;
        2. Stato AS1 : Se estraggo il token "Vn" o "Tn" passo allo stato AS2, se estragggo "NAME" passo il controllo all'automa per il riconoscimento delle dichiarazioni, altrimenti segnalo un errore;
        3. Stato AS2 : (Eseguo una riduzione a Ob)
          1. Se estraggo uno dei token {+, *, /, - } passo allo stato AS3, o
          2. Se estraggo il token "=" passo allo stato AS4, altrimenti segnalo un errore;
        4. Stato AS3 : Se estraggo il token "Vn" o "Tn" passo allo stato AS2, altrimenti segnalo un errore;
      2. Stato AS4 : Se estaggo il token "Vn" passo allo stato AS5 accettante, altrimenti segnalo un errore;
      3. Stato AS5 : Eseguo una riduzione ad A e accetto l'input;
    2. Produzione : <A> ::= <Oc>
      1. Produzione : <Oc> ::= while ( <CONDS> ) <A> endwhile | if ( <CONDS> ) <A> endif | if ( <CONDS> ) <A> else <A> endif
        1. Estraggo il token "endwhile"
          1. Stato W1 :  Estraggo il token successivo e richiamo l'automa per le produzioni di A
          2. Se l'automa per le produzioni di A accetta ed estraggo il token il token ")" passo allostato C1, altrimenti segnalo un errore;
            1. Prosuzioni : <CONDS> ::= <VTn> <OP_COND> <VTn> | <VTn> <OP_COND> <VTn> <OP_LOGIC> <CONDS>
              1. Stato C1 : Se estraggo il token "Vn" o "Tn" passo allo stato C2, altrimenti segnalo un errore;
              2. Staco C2 : Eseguo una riduzione a "VTn", se estraggo un token {= =, >=, <=, >, <, <>} passo allo stato C3, altrimenti segnalo un errore;
              3. Stato C3 : Se estraggo il token "Vn" o "Tn" passo allo stato C4, altrimenti segnalo un errore;
              4. Stato C4 :  (Eseguo prima una riduzione a VTn e poi una riduzione a CONDS)
                1. Se estraggo un token {AND , OR} passo allo stato C1 o
                2. Se estraggo il token "(" passo allo stato W2, altrimenti segnalo un errore;
          3. Stato W2 : Se estraggo il token "while" passo allo stato W3 accettante, altrimenti segnalo un errore;
          4. Stato W3 : Eseguo una riduzione a Oc e accetto l'input
        2. Estraggo il token "endif"
          1. Stato I1 : Estraggo il token successivo e richiamo l'automa per le produzioni di A
          2. Se l'automa per le produzioni di A accetta ed estraggo il token "else" passo allo stato I2, se estraggo ")" passo allo stato C1, altrimenti segnalo un errore;
          3. Stato I2 : Estraggo il token successivo e richiamo l'automa per le produzioni di A
          4. Se l'automa per le produzioni di A accetta ed estraggo il token ")" passo allo stato C1, altrimenti segnalo un errore;
            1. Produzioni : <CONDS> ::= <VTn> <OP_COND> <VTn> | <VTn> <OP_COND> <VTn> <OP_LOGIC> <CONDS>
              1. Stato C1 : Se estraggo il token "Vn" o "Tn" passo allo stato C2, altrimenti segnalo un errore;
              2. Staco C2 : Eseguo una riduzione a "VTn", se estraggo un token {= =, >=, <=, >, <, <>} passo allo stato C3, altrimenti segnalo un errore;
              3. Stato C3 : Se estraggo il token "Vn" o "Tn" passo allo stato C4, altrimenti segnalo un errore;
              4. Stato C4 :  (Eseguo prima una riduzione a VTn e poi una riduzione a CONDS)
                1. Se estraggo un token {AND , OR} passo allo stato C1 o
                2. Se estraggo il token "(" passo allo stato I3, altrimenti segnalo un errore;
            2. Stato I3 : Estraggo il token "if" e passo allo stato I4 accettante, altrimenti segnalo un errore;
            3. Stato I4 : Eseguo una riduzione a "Oc" e accetto l'input;
    3. Produzione : <A> ::= parallelo {COD}
      1. Stato P1 : Estraggo il token "}" e passo allo stato P2, altrimenti segnalo un errore;
      2. Stato P2 : Estraggo il token "endp" e passo allo stato COD1, altrimenti segnalo un errore;
        1. Prosuzione : <COD> ::= <COD> <COD> | <A> endp
          1. Stato COD1 : Estraggo il token successivo e richiamo l'automa per le produzioni di A
          2. Se l'automa per le produzioni di A accetta passo allo stato COD2, altrimenti segnalo un errore;
          3. Stato COD2 : (Eseguo una riduzione ad "A")
            1. Estraggo il token "endp" e passo allo stato COD1 o 
            2. Estraggo il token "{" e passo allo stato P3, altrimenti segnalo un errore;
      3. Stato P3 : Estraggo il token "parallelo" e passo allo stato P4 accettante, altrimenti segnalo un errore;
      4. Stato P4 : Eseguo una riduzione ad "A" e accetto l'input

Nella fase di implementazione del parser gli automi sono stati "adattati" alla programmazione e al riconoscimento di istruzioni successive. Ad esempio l'automa che riconosce le produzioni di assegnamento ("<A> ::= <Vn> = <Ob>") viene impiegato fintanto che si ha un token ";" come primmo token e non si è arrivati alla dichiarazione delle variabili. Anche gli altri automi saranno richiamati tante volte quanti sono i token trovati che portano al loro stato iniziale.
Come dicevo nella paragrafo di introduzione, durante il parsing dei token viene creato l'albero di parsing (descrizione dettagliata nel paragrafo "Parsing"). In particolare all'albero vengono aggiunti dei nodi ogni qualvolta si effettua una riduzione da un terminale ad una variabile o da una produzione ad una variabile della mia grammatica.

Paerser : Le Classi

Per implementare il parser abbiamo utilizzato la classe Parser.java. All'interno di questa classe abbiamo implementato diversi metodi per il parsing delle diverse produzioni.

Parser.java

Attributi della classe:
  1. Stack<StackObject> stack_parsing : Stack dei token da ridurre alle produzioni della grammatica;
  2. NodoAlbero ini : Nodo "root" dell'albero di parsing;
  3. NodoAlbero ret :  (figlio di ini) Radice del sottoalbero di parsing del costrutto "return"; 
  4. NodoAlbero a : (figlio di ini) Radice del sottoalbero di parsing delle produzioni di "A";
  5. VarID variabiliDaControllare : Vettore delle variabili dichiarate, è utilizzato nel parsing della produzione "return" per settare le variabili da stampare una volta interpretato il codice;
La classe contiene i seguenti metodi:
  1. public Parser() : Costruttore
  2. public boolean go_parsing(Stack<StackObject> stack, VarID variabili) : Metodo richiamato per far partire il parsing. In input deve ricevere lo stack da cui estrarre i token e il vettore delle variabili a cui, durante il parsing della sezione di codice "return", potrebbero essere modificato il campo "output".
  3. private boolean parsing() :  Metodo in cui viene implementato il riconoscimento della produzione "<INI> ::= begin <DIC> <A> <R> end"; viene valutato se esiste il token "begin" all'inizio del listato, se esistono le dichiarazioni e sono corrette, se esistono e sono corrette le attività, se esiste ed è corretto il costrutto "return" e infine se esiste il token "end".
  4. private boolean return_automaton() : Metodo per il parsing delle produzioni della variabile "R".
  5. private boolean attivita_automaton() : Metodo per il parsing delle produzioni di della variabile "A".
  6. private boolean dichiarazioni_automaton() : Metodo per il parsing delle produzioni della variabile "DIC"
  7. private NodoAlbero assegnamento(Stack<StackObject> stackOp) : Implementazione dell'automa per la produzione "<A> ::= <Vn> = <Ob>"; all'interno di questo metodo vengono implementati i controlli per verificare se si è in presenza di una dichiarazione piuttosto che di una operazione di assegnamento e viene implementata la creazione dei nodi che rappresentano operazioni di assegnamento da inserire nell'albero di parsing che verrà utilizzato dall'inteprete.
  8. private NodoAlbero parallelo(Stack<StackObject> stackOp) : Metodo per l'implementazione dell'automa che riconosce le produzioni di "<A> ::= parallelo {COD}"; oltre alla verifica della correttezza delle produzioni contenute all'interno del costrutto parallelo si crea anche il nodo "parallelo" per l'albero di parsing utilizzato poi dall'interprete.
  9. private NodoAlbero se(Stack<StackObject> stackOp) : Metodo per l'implementazione dell'automa che riconosce le produzioni "<A> ::= <Oc>" ed in particolari per la produzione "<Oc> ::= if ( <CONDS> ) <A> else <A> endif | if ( <CONDS> ) <A> endif".
  10. private NodoAlbero mentre(Stack<StackObject> stackOp) : Metodo per l'implementazione dell'automa che riconosce le produzioni "<A> ::= <Oc>" ed in particolari per la produzione "<Oc> ::= while ( <CONDS> ) <A> endwhile".
  11. private NodoAlbero conds(Stack<StackObject> stackOp) : Metodo per l'implementazione dell'automa che riconosce le produzioni "<CONDS> ::= <VTn> <OP_COND> <VTn> | <VTn> <OP_COND> <VTn> <OP_LOGIC> <CONDS>". Questo particolare metodo è richiamato all'interno delle operazioni condizionali "if" e "while" per valutare la correttezza delle condizioni espresse in quei costrutti.
  12. public NodoAlbero get_albero() : Metodo utilizzato dall'interprete per ottenere l'albero di parsing da utilizzare.
  13. public VarID getVariabili() : Metodo che restituisce il vettore delle variabili dichiarate aggiornate dopo la valutazione delle produzioni di "R".





Interprete

Inteprete : Introduzione

L'interprete implementato sfrutta la navigazione dell'albero di parsing per interpretare il codice inserito. In particolare questo interprete parte dal nodo radice dell'albero di parsing (nodo corrispondente alla produzione "<INI> ::= begin <DIC> <A> <R> end") e ne naviga ricorsivamente tutti i figli: scorre l'albero fino alle produzioni che riguardano dei terminali e poi si risale aggiornando il valore delle variabili.
Una particolarità del nostro Albero di parsing è che i figli dei nodi vengono letti da destra a sinistra.

Interprete : Architettura e Strutture Dati

La struttura dati che utilizzo per l'interpretazione del codice è un albero di nodi che rappresentano le operazioni che devo interpretare. Questo albero è stato creado durante la fase di parsing. L'elemento generico del mio albero è un elemento di tipo NodoAlbero di seguito descritto:

NodoAlbero Generale
Nome : Stringa Tipo : Stringa Figli : Array NodoAlbero HasChild : boolean

Descrivio ora le strutture dati generali che creo durante la fase di parsing (assemblando l'albero), e navigo durante l'interpretazione:

NodoAlbero INI :
Nome: ini Tipo : root Figli : {"end", RET, A, "begin"} HasChild : true

Descrive il nome e il tipo del nodo che fa da radice al mio albero di parsing. I suoi figli sono 4 : (da destra) il nodo che descrive l'inzio del codice da interpretare "begin", il nodo "A" che indica la radice di tutte le attività presenti nel listato, il nodo "RET" che rappresenta l'operazione di "return" delle variabili ed infine il nodo "end" che descrive la fine del mio codice da interpretare.


NodoAlbero RET :
Nome : return Tipo : return Figli : {VARS} HasChild : true

Nodo che viene interpretato quando si sono interpretate tutte le attività e che contiene un solo figlio "VARS".


NodoAlbero VARS:
Nome : vars Tipo : VARS Figli : {Vn}* HasChild : {true, false}

Nodo che contiene una serie di figli che indicano le variabili diachiarate che devono essere riportate in output, nel nostro caso stampate a video.


NodoAlbero A :
Nome : A Tipo : attivita Figli : {Assegnamento, Parallelo, IF, IF-ELSE, WHILE}+ HasChild : true

Nodo radice del sottoalbero delle attività da interpretare. Questo nodo ha una serie non ordinata e un numero non fissato di figli. Questi figli saranno nodi di tipo "assegnamento", "Oc" o "Parallelo". Da questo no parte lì'interpretazione vera e propria dell'albero di parsing, visto che sono queste le operazioni più complesse da interpretare.


NodoAlbero Assegnamento :
Nome : AS Tipo : Assegnamento Figli : {Assegnamento?, Ob, OP_AS,Vn} HasChild : true

Nodo che può contenere al suo interno una operezione di assegnamento ed eventualmente un nuovo nodo "assegnamento". Questo nodo quindi descrive o la radice di un albero di nodi "assegnamento" o uno dei nodi interni o una foglia di questo sottoalbero.


NodoAlbero Ob:
Nome: Ob Tipo : Ob Figli : {{Ob, {+, -, *, /}}?, {Vn,Tn}} HasChild : true

Il nodo in questione è analogo al nodo assegnamento, solo che viene descritto in modo diverso. I suoi figli possono essere o una coppia formata da un nodo Ob e una delle operazioni aritmetiche, o da un valore terminale "Vn" o "Tn". L'interpretazione di una serie di questi nodi porta a svolgere una serie di operazioni aritmetiche su variabili e/o su numeri.


NodoAlbero Parallelo:
Nome : parallelo Tipo : COD Figli : {As, Ap}* HasChild : true

Il nodo parallelo creato nel momento del parsing è formato da una serie di coppie di nodi. Entrambi sono dei nodi attività (quindi insiemi di operazioni come assegnameto, while, etc.) ma quello indicato con Ap è la radice delle operazioni di una delle porzioni di codice da "parallelizzare", mentre As è la radice delle operazioni da svolgere a partire dalla prima operazione che si incontra superando il costrutto "parallelo".
In pratica si replica in As quello che è l'albero restante di operazioni successive al nodo "parallelo" e lo si fa tante volte quante sono le porzioni di codice da parallelizzare.


NodoAlbero IF:
Nome : IF Tipo : Oc Figli : {A, CONDS} HasChild: true

Nodo radice del sottoalbero i cui figli descrivo le operazioni da interpretare (nodo attività) all'interno dell' "if" se, interpretato il nodo "CONDS", le condizioni risultano verificate.


NodoAlbero IF-ELSE :
Nome : IF-ELSE Tipo: Oc Figli : {A, else, A, CONDS} HasChild : true

Nodo radice del sottoalbero i cui figli descrivo le operazioni da interpretare subito dopo l' "if" se, interpretato il nodo "CONDS", le condizioni risultano verificate, altrimenti si interpretano le attività successive al nodo "else".


NodoAlbero WHILE:
Nome: while Tipo : Oc Figli : {A, CONDS} HasChild : true

Nodo radice del sottoalbero i cui figli descrivono le operazioni da ninterpretare se e fino a che le condizioni del nodo "CONDS" verngono verificate.


NodoAlbero CONDS:
Nome : conds Tipo: conds Figli : {{CONDS, OP_LOGIC, CONDS}, {VTn, OP_COND, VTn}} HasChild : ture

Nodo che descrive le condizioni da valutare in ogni operazione condizionale "if" o "while". Queste condizioni possono essere formate o da tre nodi che indicano 3 simboli terminali VTn, OP_COND, VTn, oppure da tre nodi che indicano rispettivamente : un nodo CONDS, un simbolo terminale (operatore logico) e un secondo nodo CONDS. In questo secondo caso si dovranno sviluppare i nodi CONDS trovati e interpretare le condizioni al loro interno per poi poter tornare a valutare il nodo precedente.

Interprete : Esecuzione

Istruzioni per avviare il programma:
  1. Assicurarsi di aver compilato senza errori il package "Scanner" o comunuque tutti i file della cartella "Scanner"
  2. Aprire il prompt dei comandi;
  3. Entra nella cartella dove è contenuto il file "Main.java"
  4. Scrivi il comando "java Main <percorso_file>", sostituendo a <percorso_fiile> il path del file con il codice da sperimentare
  5. Lancia il comando e il programma è in esecuzione
Se non fosse possibile compilare i sorgenti, viene fornito anche un file “scanner.jar” che contiene l’intera applicazione. Tramite il comando “java –jar scanner.jar” si avrà comunque il mio interprete in esecuzione.

Una volta che il programma termina la sua esecuzione vengono stampati a video i risultati richiesti, se si vuole avere una visione completa delle variabili in uso e del loro risultato finale, si deve aprire il file di nome "reportVariabili" creato nella cartella di esecuzione del programma.

Interprete : Esempi

Un primo semplice esempio di codice che sfrutta il costrutto "parallelo" e da cui si ottengono risultati diversi è il seguente:

Codice esempio 1:

begin
var real a;
var real b;
var real c;

a = 5;
c = a - 1;

parallelo{
        b = 30;
    endp
        b = 200;
    endp
}

while(c > 0)
    a = a * c;
    c = c - 1;
endwhile

if(a > b)
    c = 1;
else
    c = 0;
endif

return (c);

end

Il risultato dell'applicazione dell'interprete a questo listato di operazioni è la produzione di due vettori di variabili:

V1(b = 30) : [a, 120.0] [b, 30.0] [c, 1.0]
V2 (b = 200): [a, 120.0] [b, 200.0] [c, 0.0]

Questo primo esempio è stato già descritto in precedenza (Linguaggio : Esempi), ma è comunque un buon punto i partenza per la comprensione di come il costrutto "parallelo" possa essere applicato all'interno del nostro codice per esaminare più scenari ogniuno legato ad una o più modifiche di una o più variabili.

Gli altri due esempi presentati sotto sono esempi in cui il costrutto "parallelo" viene utilizzato proprio per valutare, rispetto al cambiamento di una variabile, quali sono gli effetti su i risultati finali dell'interpretazione del nostro codice. Nel terzo esempio inoltre ci sono due operazioni di aprallelizzazione successive, ed è importante notare come la seconda operazioni di parallelizzazione venga applicata ad ogni ramo della prima per ottenere un aumento esponenziale delle possibili soluzioni.

Codice Esempio 2:

begin
var real a;
var real b;
var real c;

a = 100;
c = 0;

parallelo{
b = 2;
endp
b = 3;
endp
b = 5;
endp
b = 7;
endp
}

c = a / b;

return (c);

end

I vettori delle variabili risultanti dall'applicazione dell'interprete a questo listato sono:

V1 : [a, 100.0] [b, 2.0] [c, 50.0]
V2 : [a, 100.0] [b, 3.0] [c, 33.333333333333336]
V3 : [a, 100.0] [b, 5.0] [c, 20.0]
V4 : [a, 100.0] [b, 7.0] [c, 14.285714285714286]

Codice Esempio 3:

begin
var real pot;
var real a;
var real b;
var real c;

a = 2;
c = 1;

parallelo{
pot = 4;
endp
pot = 8;
endp
pot = 12;
endp
pot = 16;
endp
}

b = pot;

while(b > 0)
c = c*a;
b = b - 1;
endwhile

parallelo{
pot = 2;
endp
pot = 3;
endp
}

b = pot;

while(b > 0)
c = c*a;
b = b - 1;
endwhile

return (c);

end

In questo ultimo esempio abbiamo utilizzato il costrutto parallelo e il costrutto while per il calcolo della potenza di un numero rispetto a diversi valori dell'esponente. I vettori delle variabili per ogni sezione di codice parallelo risulteranno:

V1 : [pot, 2.0] [a, 2.0] [b, 0.0] [c, 64.0]
V2 : [pot, 3.0] [a, 2.0] [b, 0.0] [c, 128.0]
V3 : [pot, 2.0] [a, 2.0] [b, 0.0] [c, 1024.0]
V4 : [pot, 3.0] [a, 2.0] [b, 0.0] [c, 2048.0]
V5 : [pot, 2.0] [a, 2.0] [b, 0.0] [c, 16384.0]
V6 : [pot, 3.0] [a, 2.0] [b, 0.0] [c, 32768.0]
V7 : [pot, 2.0] [a, 2.0] [b, 0.0] [c, 262144.0]
V8 : [pot, 3.0] [a, 2.0] [b, 0.0] [c, 524288.0]

Interprete : Le Classi

Interprete.java

La classe Interprete.java è la classe principale dove  viene implementato il metodo di navigazione dell'albero di parsing.

Atributi della classe :
  1. VarID VariabiliDichiarate : Vettore dove sono memorizzate le variabili dichiarate; questo vettore è utilizzato sia per ottenere il valore delle variabili che per modificarlo (ad esempio in seguito ad operazioni di assegnamento)
  2. ReportInterprete report : Oggetto che viene utilizzato per la scrittura su file del vettore delle variabili una volta eseguite tutte le operazioni richieste.
  3. int MaxCicli : Intero che indica il numero massimo di cicli che un'istruzione while può eseguire, serve per prevenire i cicli infiniti.
  4. int livelloParallelo : intero che indica quante istruzioni "parallelo" sono state seguite; utilizzato per capire a che profondità si è con l'interpretazione di una istruzione parallelo.
La classe contiene i seguenti metodi :
  1. public Interprete() : Costruttore;
  2. public boolean interpreta(NodoAlbero radice, VarID schemaVaribili) : Metodo che valuta la validità del nodo "INI"; verifica la presenza di "begin", delle dichiarazione delle varibili, lancia l'interpretazione delle attività e se sono corrette verifica la presenza del parametro "return" e dell' "end" finale.
  3. private boolean intepretaAttivita(NodoAlbero nodoRadice) : Metodo per l'interpretazione dei nodi "attivita".
  4. private boolean interpretaAssegnamento(NodoAlbero nodoIni) : Metodo per l'interpretazione dei nodi "assegnamento".
  5. private double interpretaOb(NodoAlbero Ob) : Metodo per l'intepretazione delle operazioni basi; Viene passato al metodo il primo nodo di tipo "Ob" che trovo e tramite quello calcolo il valore dell'operazione base scorrendo il sottoalbero con radice "Ob".
  6. private boolean interpretaIf(NodoAlbero nodoIni) : Metodo per l'interpretazione del nodo "IF"; 
  7. private boolean condizioni(NodoAlbero nodoCondizioni) : Metodo per l'interpretazione delle condizioni di una delle operazioni condizionali "while" o "if".
  8. private boolean trueFalseCombination(boolean v1, boolean v2, String OP_LOGIC) : Metodo per la combinazione dei risultati di un di più condizioni legate fra loro da un operatore logico come "AND" o "OR".
  9. private boolean interpretaIfElse(NodoAlbero nodoIni) : Metodo per l'interpretazione del nodo che indica un'operazione condizionale "IF-ELSE".
  10. private boolean interpretaWhile(NodoAlbero nodoIni) : Metodo per l'interpretazione del nodo che indica un'operazione condizionale "WHILE".
  11. private boolean interpretaParallelo(NodoAlbero nodoIni) : Metodo per l'interpretazione del nodo che indica un'operazione "parallelo".
  12. private boolean interpretaReturn(NodoAlbero nodoRadice) : Metodo per l'interpretazione del nodo "return".

ReportInterprete.java

La classe ReportInterprete.java viene utilizzata per la memorizzazione del vettore delle variabili dichiarate quando si è conclusa l'interpretazione dell'albero di parsing.

Attributi della classe:
  1. File f
  2. FileOutputStream fos
  3. PrintStream ps
La classe contiene i seguenti metodi :
  1. public ReportInterprete() : Costruttore; si occupa anche di inizializzare il file su cui poi andrà a scrivere il vettore delle variabili dichiarate.
  2. public boolean writeReport(VarID variabili) : Metodo che scrive su file il vettore delle varabili passatogli come parametro.