Sviluppare parser in Java

Circa due anni fa scrissi un articolo che spiegava come realizzazare di parser in C utilizzando Lex e Yacc.

Questo articolo, come mi è testimoniato dalle numerose email che ho ricevuto per un anno a seguire dalla pubblicazione, è stato abbastanza apprezzato, più di quanto mi aspettassi. Poiché recentemente ho avuto la necessità di realizzare un interprete che valutasse espressioni in Java, ho deciso di scrivere un articolo che spieghi le tecniche di parsing e i tool disponibile per utilizzare Java come linguaggio per la programmazionie di parser. Gli usi pratici di queste tecniche sono molto ampie. Per esempio supponiamo di avere realizzato una applicazione Java, non necessariamente complessa, e di voler offrire all'utente numerose possibilità di personalizzazione. Non è certo un problema nuovo; tra le soluzioni usata più di frequente c'è quella di dotare l'applicazione di file un sofisticato file di configurazione. Nel caso si voglia ancora più flessibilità è possibile aggiungere un linguaggio di scripting, che consenta lo sviluppo di macro. In entrambi questi casi si tratta di effettuare il parsing di un file espresso in un linguaggio formale, che richiede l'uso delle tecniche presentate in questo articolo.

Generatori di parser

In Java è naturalmente possibile realizzare a mano dei parser. La loro codifica diretta tuttavia è molto

noiosa, complessa, ripetitiva e soggetta a numerosi errori. Fortunatamente si possono usare formalismi

potenti per descrivere in maniera semplice ed intuitiva i linguaggi formali: i più usati sono le grammatiche. Utilizzando una grammatica, si può derivare da essa in maniera automatica il codice del parser utilizzando dei generatori di codice. Questi generatori vengono talvolta chiamati, in maniera un po' esagerata, compiler-compiler (compilatori di compilatori). Con essi si riduce notevolmente il lavoro poiché il codice viene generato automaticamente a partire da una grammatica estesa con opportuno codice di supporto; in gergo si dice che la grammatica viene annotata. Vedremo quindi come utilizzare in pratica un compiler-compiler con un esempio pratico: descrivereremo la realizzazione di un semplice valutatore di espressione. Partendo dal codice fornito insieme all'articolo avrete una ottima base per avventurarvi nello sviluppo del vostro linguaggio di programmazione. Il primo passo per programmare un parser è quindi la scelta del generatore di codice. In rete sono disponibili due generatori di parser in Java: il JavaCC e il JavaCup, entrambi utilizzabili gratuitamente anche se con licenze diverse. Il JavaCC è molto potente, e anche molto usato, ma sebbene l'uso sia gratuito, non ne viene rilasciato il codice sorgente. Non ritengo un gran problema il fatto che il JavaCC non sia OpenSource se non avessi rilevato nell'uso dei messaggi di errore interno, messaggi che mi hanno insospettito non poco. A quanto sembra il JavaCC non è stato aggiornato da tempo e genera errori usando per esempio un interpreta Java 1.1. Per questo motivo non mi sono sentito di utilizzarlo. Di un prodotto commerciale posso eventualmente richiedere l'assistenza (in un progetto industriale), ma di un prodotto gratuito (quindi non commerciale) se il sorgente non è disponibile, c'è il pericolo che venga (nella peggiore delle ipotesi) abbandonato. Un altro motivo per cui non ho apprezzato il JavaCC è che è abbastanza diverso da Yacc, di conseguenza si deve imparare una metodologia un po' differente da quella a cui un esperto di Yacc è abituato. In realtà niente di grave, solo una sensazione di maggior complessità che andava contro i principi di massima semplicità che prediligo.

Poiché esiste il JavaCup, una implementazione di un sistema molto simile a Yacc, per di più distribuito gratuitamente con licenza GPL, compreso il sorgente, ho optato per quest'ultimo. Sia l'esempio che il

JavaCup stesso con il sorgente sono acclusi all'articolo. Devo dire che mi ha meno problemi e lo ho trovato più semplice e immediatamente comprensibile del JavaCC, anche perché ho una certa esperienza con Yacc. Con questo non sto condannando il JavaCC, anche perché è usato dalla maggioranza dei progetti di linguaggi in Java che conosco, osservo solo che si può usare proficuamente anche il JavaCup, che è valido e abbastanza facile da usare. Per questo articolo (e per i miei usi lavorativi) ho solo scelto uno strumento piuttosto che un altro.

Grammatiche

Il JavaCup (e il JavaCC) utilizzano una grammatica per descrivere il linguaggio di programmazione che devono analizzare. Le grammatiche possono essere definite, in maniera un po' pomposa, come "un formalismo per descrivere tutti i programmi esprimibili in un dato linguaggio". Più semplicemente con na grammatica serve a verificare se una certa stringa è un costrutto sintatticamente valido per il linguaggio da essa descritto. Poiché generalmente i costrutti esprimibili con una grammatica sono infiniti, la grammatica li può descrivere soltanto dando delle regole per generarli: sarebbe impensabile che li elencasse tutti. Per esempio:

 Grammatica
1
 (a)
lang ::= LPAREN RPAREN(b)
 lang
::= LPAREN lang RPAREN

In questo caso abbiamo una grammatica che descrive tutte le stringhe che cominciano con n parentesi

tonde aperte e finiscono con altrettante parentesi tonde chiuse. In questa notazione abbiamo due tipi di

simboli: i terminali, come LPAREN e RPAREN , e i non-terminali (come lang); le regole, come (a) e (b), si dicono produzioni. I terminali sono simboli "definitivi", cioè se compaiono non possono essere più rimpiazzati; i non-terminale possono invece essere rimpiazzati dal corpo di una regola che ha quel

non-terminale in testa. In pratica un parser analizza il testo; quando incontra una "(" produce un imbolo LPAREN, quando incontra un ")" produce RPAREN.Vediamo di capire come si usano le regole di una grammatica.

Per verificare se un costrutto appartiene al linguaggio si verifica se si riesce a generarlo applicando le regole, a partire da un non-terminale che viene normalmente chiamato simbolo iniziale. Nel nostro caso il simbolo iniziale sarà necessariamente lang (non abbiamo molta scelta) e possiamo cominciare una generazione. La generazione (che potrebbe anche non terminare mai) termina quando nel programma generato non ci sono più simboli non terminali. Per esempio:

 lang
 (b)=>
LPAREN lang RPAREN
 (a)=>
LPAREN LPAREN RPAREN RPAREN

Ovvero "(())"; quindi questa stringa fa parte del linguaggio generato dalla nostra grammatica. In pratica le

grammatiche non vengono utilizzate in questo modo ma a ritroso: cioè dato un programma si cerca di stabilire se la grammatica è in grado di generare quel programma (il che vuol dire che il programma è grammaticalmente corretto) e, altrettanto importante, la sequenza di regole che hanno consentito di generare quel programma. I generatori di parser intercettano il riconoscimento delle regole, eseguendo delle operazioni al verificarsi del "matching" di una regola.Un parser è un programma capace di verificare, a partire da una grammatica, se una stringa appartiene al linguaggio della grammatica, e soprattutto è in grado di riconoscere la sequenza di regole da applicare. Il problema teorico della costruzione del parser di una grammatica è stato studiato a fondo e ha prodotto strumenti automatici per la loro costruzione.

Questo problema comunque non è risolvibile nella sua formulazione più generale: non è possibile in generale riconoscere se un programma appartiene ad una grammatica per qualsiasi grammatica. È invece risolvibile solo per particolari grammatiche, con determinate limitazioni nel formato delle regole. La casistica è ampia e variegata, e non entreremo nei dettagli. Diciamo solo che sia Yacc che JavaCup sono generatori di parser per grammatiche di tipo LALR(1) non ambigua. Il primo genera codice C mentre il secondo genera codice Java.

Alberi Sintattici

Avere una grammatica in sè non è sufficiente per analizzare un linguaggio, serve solo per riconoscere se un programma è sintatticamente corretto. Sfruttando però il fatto che l'algoritmo di verifica di fatto ricostruisce i passi effettuati per generare un programma, ovvero calcola una derivazione, si possono intercettare alcuni passi effettuati per ottenere una struttura dati utile per operazioni di tipo "semantico": per esempio il calcolo di una espressione o la generazione di codice. Facciamo un altro esempio per chiarire meglio il concetto di derivazione. Nel seguito estendiamo la notazione: il '\|' abbrevia in un unica regola una serie di alternative (ovvero una serie di regole con la stessa testa). Per CIFRA si intende una cifra da 0 a 9, SUM è il più e MUL è l'asterisco).

 Grammatica
2
 (c)
e : CIFRA | t | f
 (d)
t : f SUM f
(e) f
: e MUL e

Consideriamo la stringa '3+5\*7': l'intera derivazione può essere ottenuta con la sequenza rappresentata

dall'albero mostrato in figura. Per leggere l'albero occorre considerare che le foglie sono i terminali. Quando un nodo ha dei figli si tratta di un non-terminale: i figli sono le parti in cui si espande il non-terminale applicando una delle regole:

 Albero
1
 |
 t
 /
|
 f
+ f
 |
/|
 e
e * e
 |
| |
 3
5 7

Javacup genera il risultato dell'analisi sintattica in questo formato. La grammatica 2 è più complicata della grammatica 3, che può sembrare equivalente ma più semplice:

Grammatica 3
e : CIFRA | e '+' e | e '*' e

ma questa ha dei seri problemi, soffre del peggior difetto che possa avere una grammatica: è ambigua.

Infatti è possibile derivare il nostro programma in più di un modo :

 e
e
 /
| \ / |
 3
+ e e * 7
 /|
/|
 e
* e e + e
 |
| | |
 5
7 3 5

quindi non è possibile stabilire univocamente la sequenza di applicazioni di regole che genera il programma. Di una grammatica come la 3 non è possibile generare automaticamente il parser: JavaCup riporta vari errori. Una delle conseguenze di questo problema è che la grammatica non riflette la maggiore associatività della moltiplicazione rispetto all'addizione. La grammatica 2 infatti è scritta in modo tale che tenga conto del fatto che il prodotto ha priorità sulla somma. Infatti ogni algoritmo di ricostruzione della grammatica a partire dalla stringa in presenza di moltiplicazione applicherà la regola (e) prima delle altre, risolvendo così implicitamente il problema di stabilire la priorità.

Ritorniamo all'albero 1, che è il risultato dell'analisi sintattica, ed è detto albero di sintassi concreta. Non è particolarmente comodo da utilizzare, perché mantiene traccia di una serie di dettagli sintattici, utili per risolvere problemi come la priorità della moltiplicazione sull'addizione, ma inutili per il resto del lavoro.

Quello che realmente è utile è una forma semplificata di questo albero, il cosiddetto albero di sintassi astratta, per esempio:

 Albero
2
 +
 /
 3
*
 /
 5
7

Questo albero viene costruito dall'albero di sintassi concreta, semplificando tutti i dettagli sintattici non necessari ed è ciò che realmente si cerca di ricavare dall'analisi sintattica. In un certo senso è il "succo

semantico", sul quale si può comodamente operare per le fasi successive della compilazione.

Classe AST

Poichè costuiremo un albero di sintassi astratta per valutare l'espressione, e poiché in generale costruire l'AST è la prima cosa da fare dopo il parsing, il nostro obiettivo adesso è quello di creare una classe che lo rappresenti. In Java è particolarmente semplice ed elegante definire una classe adatta al essere utilizzata per questo scopo. Veniamo ai dettagli: si comincia definendo una interfaccia, ASTNode, con due implementazioni: ASTLeaf e ASTNodeN. L'interfaccia definisce lo stretto necessario per la costruzione e valutazione dell'albero:

 public
interface ASTNode {
 public
String toString();
 public
double eval();
 }

Le foglie dell'albero saranno dei numeri, per cui ci occorre una foglia cha rappresenti un double; è comodo

avere un costruttore che inizializzi il nodo a partire da una stringa letta in input:

public
class ASTLeaf implements ASTNode{
 private
double value;
 public
ASTLeaf(String value) {
 try
{ this.value= Double.valueOf(value).doubleValue();}
 catch(Exception
ex) { this.value = 0; }
 }
 public
String toString() { return ""+value; }
 }

Il nodo interno di un albero invece ha in generale n figli, per cui implementiamo una foglia che mantiene una

lista di figli, utilizzando un Vector.

class
ASTNodeN extends ASTLeaf {
 private
Vector sons=new Vector();
 private
String value;
 public
ASTNodeN(String s) { super(s); value=s; }
 void
addSon(ASTNode son) { sons.addElement(son); }
 public
String toString() {
 StringBuffer
sb = new StringBuffer("(");
 sb.append(value);
 for(int
i=0; i<sons.size(); i++)
 sb.append("
").append(sons.elementAt(i).toString());
 sb.append(")");
 return
sb.toString();
 }
 }

Annotazione della grammatica

Avendo le strutture dati possiamo usare finalmente il generatore di parser. Nel listato 1 è mostrata una

grammatica JavaCup con le annotazioni, ovvero le azioni che vengono eseguite via via che viene

riconosciuta la struttura sintattica del testo sottoposto a scansione.

Listato 1 — La specifica JavaCup

// Specifica CUP specification per un semplice
// valutatore di espressioni.
import java.io.*;
import java_cup.runtime.*;
/* Preliminaries to set up and use the scanner.  */
init with {: scanner.init();              :};
scan with {: return scanner.next_token(); :};
/* Terminals (tokens returned by the scanner). */
terminal SEMI;  // ;
terminal PLUS;  // +
terminal MINUS; // -
terminal TIMES; // *
terminal DIVIDE;// /
terminal MOD;   // %
terminal UMINUS;// -
terminal LPAREN;// (
terminal RPAREN;// )
terminal String NUMBER; // 12.3
/* non terminals */
non terminal                 goal ;
non terminal                 expr_list ;
non terminal ASTNode         expr ;
/* Precedences */
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;
/* The grammar */
start with expr_list;
expr_list ::=
  expr:e
  {:  e.dump(); System.out.println(" = "+e.eval());  :}
  | expr_list SEMI expr:e
  {: e.dump(); System.out.println(" = "+e.eval()); :}
  ;
expr  ::=
  expr:e1 PLUS expr:e2
  {: ASTNodeN n = new ASTNodeN("+");
    n.addSon(e1); n.addSon(e2); RESULT=n;
  :}
  | expr:e1 MINUS expr:e2
  {: ASTNodeN n = new ASTNodeN("-");
    n.addSon(e1); n.addSon(e2); RESULT=n;
  :}
  | expr:e1 TIMES expr:e2
  {: ASTNodeN n = new ASTNodeN("*");
    n.addSon(e1); n.addSon(e2); RESULT=n;
  :}
  | expr:e1 DIVIDE expr:e2
  {: ASTNodeN n = new ASTNodeN("/");
     n.addSon(e1); n.addSon(e2); RESULT=n;
  :}
  | expr:e1 MOD expr:e2
  {: ASTNodeN n = new ASTNodeN("%");
     n.addSon(e1); n.addSon(e2); RESULT=n;
  :}
  | NUMBER:n
  {: RESULT = new ASTLeaf(n); :}
  | MINUS expr:e
  {: ASTNodeN n = new ASTNodeN("-");
      n.addSon(e); RESULT=n;
  :}
    %prec UMINUS
  | LPAREN expr:e RPAREN
  {: RESULT = e; :}
  ;

Commentiamo dunque il listato passo dopo passo.Le dichiarazioni init with e scan with fanno riferimento, rispettivamente, alle operazioni di inizializzazione e alla definizione della classe scanner. Lo scanner effettua la prima fase della analisi sintattica ovvero la cosiddetta tokenizzazione. Data una stringa come per esempio "12 + 13" lo scanner ha l'incarico di isolare le sequenze di caratteri che sono significative come una unità: per esempio 12 è un numero, + è un operatore e 13 è un altro numero. Il parser ha bisogno di vedere l'input come una sequenza di token, in questo caso NUMERO OPERATORE NUMERO, e quindi è necessaria una classe che si occupi di effettuare questa prima scrematura dell'input. Lo scanner è abbastanza semplice da scrivere e non lo riportiamo, chi è interessato può esaminare il codice accluso all'articolo. In pratica sarà sufficiente modificare in maniera ovvia l'esempio fornito.Ritorniamo alla nostra specifica Cup: come si nota sono elencati i simboli, dichiarando quali sono i terminali e i non-terminali. Un aspetto importante, che sarà sfruttato più avanti, nelle annotazioni, è che ad ogni simbolo terminale è associato un tipo.

Per esempio expr è dichiarato di tipo ASTNode. Poi seguono le dichiarazioni di precedenza, che servono a eliminare le ambiguità. Consideriamo per esempio il caso di una stringa come questa: 1 + 2 \ 3. Come si noterà la grammatica è ambigua e non è capace di determinare se si tratta di (1+2)\3 o 1+(2\3). Sebbene sia possibile scrivere delle grammatiche non ambigue, questo porta a complicarla notevolmente. Per cui si sopperisce con le dichiarazione di precedenza, nella fattispecie si dichiara che \ ha una precedenza maggiore di +; questo significa che sul 2 dell'esempio comanda il \, quindi la stringa va interpretata come 1+(2\3). Tramite meccanismi che non ci interessa approfondire (chi è interessato troverà nel libro di Ullman in bibliografia ampli dettagli), il generatore di parser rileva l'ambiguità e la risolve generando un parser che le gestisce le ambiguità dando priorità alla moltiplicazione rispetto alla somma. In pratica sceglie una regola invece che un altra. Un altro aspetto che viene dichiarato nella specifica è l'associatività che funziona in modo simile alla precedenza. Si tratta di determinare se una stringa come 1 + 2 + 3 debba essere considerata (1+2)+3 o 1+(2+3). L'associatività dichiara se l'operatore associa da destra verso sinistra o da sinistra verso destra, il che signifca scegliere in che modo applicare una stessa regola (non di scegliere tra più regole).

Dopo le dichiarazione seguono le regole sintattiche, che è compito del parser, con associate le cosiddette azioni semantiche. Questo è il succo del funzionamento del sistema. Ogni volta che il parser riconosce una regola sintattica, esegue l'azione semantica corrispondente. Vediamo di capire bene come funziona il meccanismo delle azioni semantiche considerando la regola

 expr
::= expr:a PLUS expr:b

Come si è detto ad ogni non-terminale è associato un valore. L'azione semantica accede ai valori associati perchè viene dichiarato la variabile che deve contenerli, nell'esempio a e b. Il codice Java che gestisce l'azione semantica viene posto tra {: e :} a seguire della regola e viene eseguito quando viene riconosciuata la regola. Utilizziamo le azioni semantiche per costruire l'albero di sintassi astratta.

 expr
::= expr:a PLUS expr:b
 {:
ASTNodeN n = new ASTNodeN("+");
 n.addSon(a);
n.addSon(b); RESULT=n;
 :}

Il meccanismo dovrebbe essere adesso abbastanza intuitivo: costruiamo un nodo dell'albero aggiungendo i figli, che otteniamo dalle variabili associate ai non-terminali. Notare che il tipo delle variabili è quello dichiarato in precedenza insieme al non-terminale: lo scopo delle dichiarazioni era appunto quello di definire il tipo delle variabili associate ai non-terminali nelle azioni semantiche. Infine assegniamo alla variabile speciale RESULT il nuovo nodo, in modo che tale valore potrà essere acceduto quando verrà riconosciuto da una regola di livello superiore.

Valutazione dell'albero sintattico

Rispetto al C/Yacc, l'accoppiata Java/JavaCup offre molti vantaggi, in particolare una maggiore chiarezza del meccanismo. In particolare l'uso di oggetti si sposa molto bene con la struttura a regole del riconoscimento grammaticale, quindi è facile e naturale costruire gli alberi sintattici. La cosa interessante è che, una volta costruito l'albero, utilizzarlo (in questo caso valutarlo) è di solito una questione di aggiungere metodi ai nodi. Vediamo come risolviamo in breve il problema di valutare l'espressione:

 class
ASTNodeN {
 public
double eval() {
 double
a=0, b=0;
 boolean
binary = sons.size() == 2;
 a
= ((ASTNode)sons.elementAt(0)).eval();
 if(binary)
 b
= ((ASTNode)sons.elementAt(0)).eval();
 switch(value.charAt(0))
{
 case
'+':
 return
a+b;
 case
'-':
 return
binary ? a-b : -a;
 case
'*':
 return
a * b;
 case
'/':
 return
a / b;
 return
a % b;
 default:
 return
0;
 }
 }
 }
 class
ASTLeaf {
 double
value;
 public
double eval() {
 return
value;
 }
 }

Nel nostro caso si poteva valutare direttamente l'espressione mentre si esaminava il testo senza avere

necessità di costruire l'albero di sintassi astratta, ma nella maggior parte dei casi occorre costruire l'AST e manipolarlo prima di utilizzarlo, in particolare quando occorre effettuare compilazioni, per cui abbiamo preferito descrivere in dettaglio la costruzione dell'AST.

Conclusioni

Con il presente articolo abbiamo mostrato come sia possibile realizzare parser in Java con molta

semplicità. In effetti, la realizzazione di linguaggi in Java è un aspetto molto interessante per via del suo

substrato, la Java Virtual Machine, la portabilità e le applet. Per questo motivo esistono numerose implementazioni di linguaggi in Java. Va osservato comunque che le migliori implementazioni comunque

trasformano direttamente in bytecode il codice per consentire l'esecuzione diretta da parte della JVM. Si tratta di un aspetto che ci ripromettiamo di approfondire in seguito.

Bibliografia

Scott Hudson JavaCup Home Page http://www.cs.princeton.edu/~appel/modern/java/CUP/
MetaMata, JavaCC Home Page http://www.metamata.com/JavaCC/
Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools Addison Wesley, 1986, il "dragon book".
Robert Tolksdorf JVM Languages http://grunge.cs.tu-berlin.de/~tolk/vmlanguages.html