Attività progettuale inLinguaggi e Modelli Computazionali M

My Small Language

Realizzato da:Filippo Malaguti

Obiettivi del progetto

Questo progetto ha come scopo la realizzazione di un semplice linguaggio di programmazione, che presenti tutti gli elementi più basilari.

In particolare, il linguaggio ha le seguenti funzionalità:- dichiarazione ed uso di variabili reali o array di numeri reali- definizione di funzioni- operatori aritmetici, logici e condizionali- costrutti if-else e cicli while e for- stampa a video di stringhe e risultati di espressioni

Un esempio Il calcolo del fattoriale

real x = 4;

function main(){real f = fact($x);println($x, "! = ", $f);

}

function fact(n){if($n == 0 || $n == 1){

return 1;}return $n*fact($n-1);

}

Le variabili devono essere dichiarate in modo esplicito ed associate ad un tipo (real o array). Lo scope è sempre locale all'ambientedi definizione.

L'esecuzione inizia sempre dalla funzione main.

Tutte le funzioni, eccetto il main, devono ritornare un valore.

I costrutti come if, while, for, devono essere seguiti da un insieme di istruzioni racchiuse tra parentesi graffe. Nelle espressioni condizionali si considera TRUE un valore maggiore di zero.

Ogni volta che, all'interno di una espressione, si vuole accedere al valore contenuto in una variabile, bisogna usare la forma $id_variabile.

Funzioni:chiusura lessicale e call-by-value

Nel programma è sempre presente un ambiente globale, inoltre ogni funzione ha un proprio ambiente locale. Ogni volta che in una funzione si tenta di accedere ad una variabile non definita al suo interno, si cerca nell'ambiente globale.

Per il passaggio dei parametri viene adottato il modello Call-by-value:ogni espressione passata come parametro viene valutata, poi il valore

calcolato viene assegnato ad una variabile nell'environment della funzione chiamata.

Uso degli array

In questo linguaggio gli array sono un particolare tipo e possono contenere solo valori reali. Non hanno una dimensione prefissata.

array a = [1,2.5,3.6,4];

In fase di dichiarazione si può usare una notazione di assegnamento compatta. Altrimenti si deve assegnare un valore per volta.

a[0] = 1; a[1] = 2.5; … a[n] = r;

Per accedere al valore di un elemento si procede come per le variabili reali, ma si deve specificare l'indice al quale accedere tramite una espressione.

real avg = ($a[0] + $a[1]) / 2;

La Grammatica

Per realizzare il parser della grammatica è stato utilizzato il parser generator ANTLR.

La grammatica risultante è di tipo context-free:a causa di alcune ambiguità la grammatica non poteva essere sempre

LL(1), quindi in generale è LL(2). Per ragioni di efficienza, però, solo dove necessario è stato indicato un valore di lookahead pari a 2.

N.B. Nelle prossime slide si è omessa la sintassi per la generazione dell'albero.

Grammatica del linguaggio

Lo scopo della grammatica è il simbolo non terminale prog:

prog ::= (var_decl ';')* function_def*;

Un programma può cominciare con la dichiarazione di alcune variabli globali seguita dalla definizione di una serie di funzioni.

Dichiarare le variabili

Ogni variabile ha un tipo e un identificativo. Volendo può essere subito inizializzata con il risultato di una espressione.

var_decl: type ID('=' (expr | ('[' (expr (','expr)*) ']')))?;

type: 'real' | 'array';

Esempi:real r;real r = 1;array a = [1,2,3,4];

Definire le funzioni

Ogni funzione ha un nome, zero o più parametri formali e un blocco di istruzioni.

function_def: 'function' ID '(' (ID (',' ID)*)? ')' block;

Esempio:function main(){}

function avg(n1, n2){return (n1 + n2)/2;

}

Le istruzioni - 1

Sono tutte istruzioni: le dichiarazioni di variabili, il costrutto if-else, i cicli, alcuni comandi speciali (continue, break e return) e il block.

stat: ((expr|print|return_stat|'continue'|'break'|var_decl)';') | if_else | repeat | block

| for_stat | while_stat;

Un block è un insieme di istruzioni racchiuso tra '{''}' e costituisce il corpo delle funzioni.

block: '{' stat* '}';

Le istruzioni - 2

if_else: 'if' '(' expr ')' block ('elseif' '(' expr ')' block)* ('else' block)?;

for_stat: 'for' '(' expr ';' expr ';' expr ')' block;

while_stat: 'while' '(' expr ')' block; repeat: 'repeat' '(' expr ')' block;

print:('print'|'println') '(' (expr|STRING)(',' (expr|STRING))* ')';

Sia i cicli, sia il blocco if-else, devono essere seguiti da un block, in questo modo si evita il problema del dangling else.

Le Espressioni - 1

Le espressioni ritornano sempre un valore reale.Per discriminare tra un assegnamento e una chiamata

di funzione è necessario un lookhaead pari a 2.

expr options {k=2;}: logic_expr | assign;

Per come è definita la grammatica, questa è la priorità degli operatori:

-, ! (meno unario e not);*, / (moltiplicazione e divisione)+, - (somma e sottrazione)<=, <, ==, !=, >, >= (operatori condizionali)&&, || (And ed Or logici)= (assegnamento)

Le Espressioni - 2

logic_expr: cond_expr (('&&'|'||') cond_expr)*;

cond_expr: math_expr (('<'|'<='|'=='|'!='|'>='|'>') math_expr)*;

math_expr: term (('+'|'-') term)*;

term: unary_expr (('*'|'/') unary_expr)*; unary_expr: ('-'|'!')? atom;

Le Espressioni - 3

atom: NUM | '$' var_id | '(' expr ')' | function;

Un atomo può essere un valore numerico, una espressione tra parentesi, una chiamata di funzione o un identificativo di variabile; in questo caso serve il simbolo $ per indicare che si intende accedre al suo valore.

assign options{k=2;}: (ID '=' expr) | (array_elem '=' expr);

Lookahead 2 per poter distinguere i due casi:-assegnamento di una variabile-assegnamento di un elemento di un array

Accesso a variabili e chiamata di funzioni

var_id options{k=2;}: ID | array_elem;

Anche in questo caso il lookahead 2 serve per distinguere tra variabile semplice o array.

array_elem: ID '[' expr ']';

function: ID '(' (expr (',' expr)*)? ')';

Quando si chiama una funzione si possono passare dei parametri, che però possono essere solo espressioni: non è possibili passare un array.

Numeri ed identificatori

NUM : INT | FLOAT;ID: (LETTER|'_') (LETTER | DIGIT | '_')*;STRING: '"'.*'"';

fragment NON_ZERO_DIGIT : '1'..'9';fragment DIGIT : '0'|NON_ZERO_DIGIT;fragment LETTER: LOWER | UPPER;fragment LOWER: 'a'..'z';fragment UPPER: 'A'..'Z';fragment INT : '0'|NON_ZERO_DIGIT DIGIT*;fragment FLOAT : INT'.'DIGIT+;

WS: ( ' ' | '\r''\n' | '\n' | '\t' )+ { $channel = HIDDEN; };

Abstract Parsing Tree

Il parser fornisce in uscita un APT adatto ad un approccio a visitor.

Ogni nodo dell'albero discende dalla classe astratta MyLangNode, a sua volta sottoclasse della classe di

antlr CommonTree.

Esempio di APT

ProgNode

FunctionDefNodeVarDeclNode

VarAssignNode

IdNode

NumNodeNumNode

DivNode

BlockStatNode

real x;

function main(){x = 10 / 2;

}

Il parsing del codice sopra producel'albero astratto mostrato affianco.

La radice è il nodo di tipo ProgNode,che ha come figli tutto ciò che è definito in ambiente globale.

Una funzione ha come figli le proprie istruzioni ed eventuali parametri

Visitor

L'albero astratto che si ottiene in seguito al parsing è adatto ad essere esplorato tramite il pattern Visitor.

In questo progetto sono stati realizzati due differenti visitor con la medesima interfaccia:

- TreeBuilderVisitor: consente di visualizzare in un componente JTree la struttura stessa dell'APT

- EvalVisitor: è il vero interprete del linguaggio che si occupa di valutare i singoli nodi dell'APT eseguendo così il programma.

L'Architettura dell'interprete - 1

L'Architettura dell'interprete - 2

Il sistema di interazione con l'utente è basato su due semplici classi:

- una Form per l'interfaccia grafica;

- una classe interprete che invoca il parser e i visitor.

L'interfaccia grafica

Editor di testoVisualizzator

eAlbero

Output

Programmi di Test

Per testare il linguaggio e l'interprete sono stati messi in esecuzione alcuni programmi di prova, i più rilevanti sono:

- Il classico HelloWorld

- Un programma di calcolo del fattoriale tramite funzione ricorsiva

- Un programma di calcolo della media dei valori contenuti in un array

Conclusioni

In conclusione il linguaggio di programmazione realizzato può essere correttamente riconosciuto e valutato dall'interprete.

Si tratta, però, di un linguaggio ancora molto semplice, che manca in particolare di alcune cose:

- la possibilità di fornire input a runtime- array multi-dimensionali- una maggiore gamma di tipi di variabile (caratteri, stringhe, ecc..)