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; :}
  ;

Listato 1

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.