Home > GOF Pattern, java > GoF Patterns: Interpreter

GoF Patterns: Interpreter

25 novembre 2011

Translate in English with Google Translate
In questo articolo tratterò il pattern Interpreter

Motivazione

Si tratta di un pattern comportamentale basato su classi e viene utilizzato quando si vuole definire una grammatica e il relativo interprete.  La grammatica è costituita da tutte le espressioni che possono essere utilizzate mentre l’interprete permette di valutare il risultato complessivo.

Pensiamo ad una lingua straniera, per esempio lo spagnolo, che è costituita da una serie di vocabili e da regole grammaticali che disciplinano il loro ordine ed uso. Un interprete conoscendo i vocabili e le regole grammaticali riuscirà a capire il significato di una frase. Anche la matematica può essere usata come metafora, in cui i numeri rappresentano i dati e le operazioni rappresentano le funzioni, entrambi devono essere disposti secondo un preciso ordine quindi dovranno rispettare delle regole sintattiche. Un matematico è colui che conoscendo queste regole sarà in grado di capire il risultato di una operazione.
Pensiamo per esempio ad una semplice addizione: 3 + 4. In questo caso la grammatica è costituita da 2 espressioni: dai numeri “3” e “4” e dall’operatore  “+”,  l’interprete analizza le espressioni per ottenere il risultato, ossia “7”.

Il termine “espressione” è utilizzato per definire un simbolo ed il suo comportamento.

  • nel caso di un numero: il simbolo è costituito da un carattere rappresentato dauno o più di questi valori  “0123456789” mentre il comportamento è costituito dal valore del simbolo quindi il carattere “1” ha il valore del numero 1 ( in java Integer.parseInt(“1”) )
  • nel caso di operazioni aritmentiche: l’addizione utilizza il simbolo “+” ed il suo comportamento è costituito dall’operazione di  somma.

Le espressioni possono essere semplici o composte a seconda che aggregano o meno altre espressioni e vengono definite:

  • terminali: quando definiscono in modo autonomo il comportamento, come nel caso di un numero che definisce il suo simbolo ed il suo comportamento
  • non terminali: quando dipendono da altre espressioni, come nel caso dell’addizione che definisce il suo simbolo ma il suo comportamento è associato ai numeri utilizzati per effettuare la somma.

Quindi possiamo creare una nostra calcolatrice elementare, per fare questo dobbiamo definire una grammatica costituita da numeri ed operazioni aritmetiche, pertanto abbiamo bisogno di 5 espressioni: numeri, addizioni, sottrazioni, moltiplicazioni e divisioni. Tali espressioni vengono valutare da un interprete che elabora il risultato.

Di seguito vediamo un esempio che utilizza questo pattern per realizzare una semplice calcolatrice.

Partecipanti e Struttura
Questo pattern è composto dai seguenti partecipanti:

  • Client: colui che costruisce un albero sintattico costituito da TerminalExpression e NonTerminalExpression che dovrà essere elaborato dall’interprete
  • Context: contiene le informazioni che l’interprete dovrà utilizzare
  • AbstractExpression: definisce un comportamento astratto che le espressioni devono implementare
  • TerminalExpression: implementa il comportamento dell’espressione semplice
  • NonterminalExpression: implementa il comportamento dell’espressione composta richiamando il comportamento delle espressioni semplici.
Interpreter Pattern

Interpreter Pattern

Conseguenze

Tale pattern presenta i seguenti vantaggi/svantaggi:

  • facilità nel cambiare la grammatica: attraveso l’estensione delle classi è possibile inserire e modificare la grammatica
  • difficoltà nel gestire una grammatica complessa: quando la grammatica contiene molte regole risulta molto complicato riuscire a gestirla e comprendere il flusso dell’albero sintattico

Implementazione

Questo pattern si presta per molti esempi. Solitamente per ogni pattern tendo a fare uno o al massimo due esempi e mi focalizzo solo sugli aspetti più importanti. In questo caso ho pensato di fare più esempi per chiarire meglio l’uso.

Gli esempi sono relativi ad operazioni algebriche, in particolare:

  1. realizzazione di una operazione di addizione con due addendi
  2. realizzazione di una calcolatrice elementare
  3. soluzione di polinomio a più variabili

Primo esempio: realizzazione di una operazione di addizione con due addendi

Il primo esempio è l’implementazione del caso presentato all’inizio dell’articolo, ossia implementare una operazione di addizione di due addendi
Vediamo come si presenta il pattern in UML in base all’esempio:

Addizione

Addizione

L’interfaccia Espressione definisce il metodo “interpreta” che le classi concrete dovranno implementare.

package patterns.interpreter.addizione;
public interface Espressione {
    public int interpreta(Contesto operazione);
}

La classe Numero è il primo esempio di una classe concreta e terminale che identifica il simbolo del numero e memorizza il suo valore.

package patterns.interpreter.addizione;
public class Numero implements Espressione {

    private int numero;
    public Numero(String numero){
        this.numero = Integer.parseInt(numero);
    }

    @Override
    public int interpreta(Contesto contesto) {
        return numero;
    }

}

La classe Addiziona implementa l’operazione di addizione, estrendo i 2 numeri dallo stack e sommandoli.

package patterns.interpreter.addizione;
public class Addizione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        return contesto.pop().interpreta(contesto) + contesto.pop().interpreta(contesto);
    }

}

La classe Contesto detiene lo Stack che detiene i valori che devono essere sommati.

package patterns.interpreter.addizione;
import java.util.Stack;

public class Contesto {

    private Stack var = null;

    public Contesto(){
        this.var = new Stack();
    }

    public void push(Espressione exp){
        this.var.push(exp);
    }

    public Espressione pop(){
        return this.var.pop();
    }
}

La classe Client si occupa di dichiarare gli addendi nel contesto e di richiamare l’operazione di addizione:

package patterns.interpreter.addizione;
public class Client {

    public static void main(String[] args) {
        //Operazione di addizione
        Espressione addizione = new Addizione();

        //Contesto delle variabili
        Contesto contesto = new Contesto();
        contesto.push(new Numero("4"));
        contesto.push(new Numero("3"));

        //Risultato
        System.out.println( "risultato: " + addizione.interpreta(contesto) );
    }
}

L’output dell’operazione ci visualizza il risultato.

$JAVA_HOME/bin/java patterns.interpreter.addizione.Client
risultato: 7

Secondo esempio: realizzazione di una calcolatrice elementare

Nel secondo esempio vediamo come realizzare una calcolatrice che utilizza tutte e quattro le operazioni aritmentiche elementari. In questo caso inseriamo gli elementi in un modo più intuitivo utilizzando il classico metodo “infisso” cioè numero, operatore, numero, operatore ecc, così come facciamo quando utilizziamo la calcolatrice.
In questo modo possiamo sia usare sempre lo stesso operatore (5 + 7 + 9) che usare diversi operatori ( 3 + 4 -2 * 6 ). Ovviamente dobbiamo creare delle classi che gestiscono tutte e quattro le operazioni aritmetiche e lasciare al client l’ordine in cui tali operazioni vengono svolte (3-4+6 oppure 3+4-6).
Piccola nota: solitamente ai fini computazionali il metodo “infisso” è poco usato e si preferisce usare il metodo “prefisso” o “postfisso” per motivi prestazionali, in quanto questi metodi utilizzano meglio la memoria e consentono una migliore gestione delle priorità degli operatori.

Vediamo come si presenta il pattern in UML in base all’esempio della calcolatrice:

Calcolatrice

Calcolatrice

Le classi Espressione e Numero sono invariate mentre la classe Addizione prevede una modifica tale che il risultato dell’operazione viene inserito nello Stack.

package patterns.interpreter.calcolatrice;
public class Addizione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) + contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

La stessa cosa viene effettuata anche per la classe Sottrazione:

package patterns.interpreter.calcolatrice;

public class Sottrazione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) - contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

la classe Moltiplicazione:

package patterns.interpreter.calcolatrice;

public class Moltiplicazione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) * contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

la classe Divisione:

package patterns.interpreter.calcolatrice;

public class Divisione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) / contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

La classe Contesto prevede la gestione dell’operazione corretta in base all’operatore.  Il metodo revOperazione è utilizzato per invertire l’ordine dello Stack e processare i numeri e gli operatori nell’ordine di inserimento.

package patterns.interpreter.calcolatrice;

import java.util.*;

public class Contesto {

    private Stack numeri = null;
    private Stack operatori = null;

    public Contesto(String operazione) {
        this.numeri = new Stack();
        this.operatori = new Stack();

        for (String token : revOperazione(operazione)) {
            if (token.equals("+")) {
                operatori.add(new Addizione());
            } else if (token.equals("-")) {
                operatori.add(new Sottrazione());
            } else if (token.equals("/")) {
                operatori.add(new Divisione());
            } else if (token.equals("*")) {
                operatori.add(new Moltiplicazione());
            } else {
                numeri.add(new Numero(token));
            }
        }
    }

    public Espressione getNumero() {
        return numeri.pop();
    }

    public void setNumero(Espressione exp) {
        numeri.push(exp);
    }

    public Espressione getOperatore() {
        return operatori.pop();
    }

    private String[] revOperazione(String operazione) {
        List listOperation = Arrays.asList(operazione.split(" "));
        Collections.reverse(listOperation);
        return (String[]) listOperation.toArray();
    }
}

La classe Client definisce l’operazione da effettuare e la inserisce nel Contesto, poi esegue le operazioni presenti: addizione, sottrazione, divisione, moltiplicazione attraverso il riconoscimento (interpretazione) dell’operazione

package patterns.interpreter.calcolatrice;

public class Client {

    public static void main(String[] args) {
        //Contesto delle variabili ed operatori
        String operazione = "45 + 38 - 13 / 21 * 16";
        Contesto contesto = new Contesto(operazione);

        //Risultato
        int risultato = 0;
        while (true) {
            try {
                Espressione operatore = contesto.getOperatore();
                risultato = operatore.interpreta(contesto);
            } catch (java.util.EmptyStackException ese) {
                break;
            }
        }
        System.out.println(operazione + " = " + risultato );
    }
}

Il risultato è lo svolgimento dell’operazione.

$JAVA_HOME/bin/java patterns.interpreter.calcolatrice.Client
45 + 38 - 13 / 21 * 16 = 48

Terzo esempio: soluzione di polinomio a più variabili

Nel terzo esempio vediamo come definire un polinomio e risolverlo. Il polinomio prevede l’impiego di tre operazioni aritmetiche ad esclusione della divisione, ogni monomio è composto da una incognita e/o numero. L’esempio è solo dimostrativo ma può essere facilmente esteso.

Vediamo come si presenta il pattern in UML in base all’esempio del polinomio:

Polinomio

Polinomio

L’interfaccia Espressione è sempre la stessa.

La classe Numero adesso prevede in più solo una gestione dell’eccezione per l’inizializzazione del monomio.

package patterns.interpreter.polinomio;

public class Numero implements Espressione {

    private int numero;

    public Numero(String numero) {
        try {
            this.numero = Integer.parseInt(numero);
        } catch (Exception e) {
            this.numero = 1;
        }
    }

    @Override
    public int interpreta(Contesto contesto) {
        return numero;
    }
}

Il monomio può essere costituito da un numero, una incognita o entrambe. L’incognita sarà risolta tramite l’HashMap disponibile in sede di inizializzazione del Client in modo tale che per ogni Monomio possiamo ottenere un Numero.

package patterns.interpreter.polinomio;

import java.util.HashMap;

public class Monomio implements Espressione {

    private Numero numeroFisso = new Numero("");
    private Numero numeroRisolto = new Numero("");

    public Monomio(String monomio, HashMap variabili) {
        for (String key : variabili.keySet()) {
            if (monomio.indexOf(key) > -1) {
                numeroRisolto = variabili.get(key);
                monomio = monomio.replaceAll(key, "");
                break;
            }
        }
        numeroFisso = new Numero(monomio);
    }

    @Override
    public int interpreta(Contesto operazione) {
        return numeroFisso.interpreta(operazione) * numeroRisolto.interpreta(operazione);
    }
}

Le operazioni aritmentiche estraggono due Numeri dallo Stack e poi inseriscono il risultato dell’operazione nello Stack in modo che il risultato posso essere usato dall’operazione successiva. In questo modo l’output di una operazione diventa l’input della successiva.

package patterns.interpreter.polinomio;

public class Addizione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) + contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

Idem per la Moltiplicazione:

package patterns.interpreter.polinomio;

public class Moltiplicazione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) * contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

per la Sottrazione:

package patterns.interpreter.polinomio;

public class Sottrazione implements Espressione {

    @Override
    public int interpreta(Contesto contesto) {
        int risultato = contesto.getNumero().interpreta(contesto) - contesto.getNumero().interpreta(contesto);
        contesto.setNumero(new Numero(risultato + ""));
        return risultato;
    }

}

Il Client si occupa di definire il polinomio, assegnare le incognite ed infine avviare le operazioni.

package patterns.interpreter.polinomio;

import java.util.HashMap;

public class Client {

    public static void main(String[] args) {
        //Contesto delle variabili ed operatori
        String polinomio = "3x - y + 4z * 8";
        HashMap variabili = new HashMap();
        variabili.put("x", new Numero("5"));
        variabili.put("y", new Numero("7"));
        variabili.put("z", new Numero("10"));
        Contesto contesto = new Contesto(polinomio, variabili);

        //Risultato
        int risultato = 0;
        while (true) {
            try {
                Espressione operatore = contesto.getOperatore();
                risultato = operatore.interpreta(contesto);
            } catch (java.util.EmptyStackException ese) {
                break;
            }
        }
        System.out.println(polinomio + " = " + risultato);
    }
}

L’output del polinomio è il seguente:

$JAVA_HOME/bin/java patterns.interpreter.polinomio.Client
3x - y + 4z * 8 = 384
Categorie:GOF Pattern, java
  1. 5 maggio 2014 alle 10:59 AM

    Buongiorno, avrei una domanda sulla rappresentazione che viene fatta del pattern originale ed è la seguente: dal momento che esiste un’associazione tra la classe contesto e la classe concreta non-terminale perchè non viene in esso evidenziato?

    Non so se sono stato chiaro, ma guardando il diagramma in UML sembra che l’associazione debba avvenire sono tra client e il contesto utilizzato. Per caso esiste una convenzione di cui non sono a conoscenza? grazie.

    • 5 maggio 2014 alle 3:56 PM

      Se ti riferisci alla “aggregazione” tra NonterminalExpression e AbstractExpression, nei miei esempi non l’ho inserita nel codice java e di conseguenza nell’UML nonostante che il pattern lo preveda. Formalmente non è aderente al pattern, hai ragione, ma sostanzialmente non ha cambiato il comportamento.
      Se guardi lo stesso esempio su wikipedia http://en.wikipedia.org/wiki/Interpreter_pattern la classe “Minus” presenta l’associazione di cui ti riferisci:

      class Minus implements Expression {
          Expression leftOperand;
          Expression rightOperand;
          public Minus(Expression left, Expression right) { 
              leftOperand = left; 
              rightOperand = right;
          }
       
          public int interpret(Map<String,Expression> variables)  { 
              return leftOperand.interpret(variables) - rightOperand.interpret(variables);
          }
      }
      

      mentre la mia classe Sottrazione non la presenta:

      package patterns.interpreter.calcolatrice;
       
      public class Sottrazione implements Espressione {
       
          @Override
          public int interpreta(Contesto contesto) {
              int risultato = contesto.getNumero().interpreta(contesto) - contesto.getNumero().interpreta(contesto);
              contesto.setNumero(new Numero(risultato + ""));
              return risultato;
          }
       
      }
      

      Il motivo è collegato al modo in cui i numeri vengono prelevati.
      Nell’esempio su wikipedia, nella classe di contesto “Evaluator”, i numeri vengono presi dallo stack e poi passati al costruttore Minus

      ...
      else if (token.equals("-")) {
        //ho sintetizzato...
        expressionStack.push( new Minus(expressionStack.pop(), expressionStack.pop()) );
       }
      ...
      

      mentre nel mio caso, nella classe di contesto “Contesto”, i numeri vengono letti direttamente dallo stack dalla classe “Sottrazione”, infatti non vengono passati al costruttore, e questo determina la mancaza dell’aggregazione nel codice e nell’UML:

      if (token.equals("-")) {
          //non passo i valori ma li recupero nella classe "Sottrazione" 
          operatori.add(new Sottrazione());
      } 
      

      Ho notato che questo approccio, quello che ho usato io, è stato usato anche in altre presentazioni del pattern: http://www.programcreek.com/2013/02/java-design-pattern-interprete/ oppure in “Java Design Patterns & Examples” http://www.scribd.com/doc/16738161/Java-Design-Patterns-With-Examples

      Mentre invece ho trovato un’altra presentazione del pattern in cui l’aggregazione viene ereditata, come in questo caso, estratto da http://www.java2s.com/Code/Java/Design-Pattern/InterpreterPatternCalculator.htm

      if (operation.trim().equals("-")) {
            return new SubtractExpression(l, r);
      }
      
      class SubtractExpression extends NonTerminalExpression {
        public int evaluate(Context c) {
          return getLeftNode().evaluate(c) - getRightNode().evaluate(c);
        }
      
        public SubtractExpression(Expression l, Expression r) {
          super(l, r);
        }
      }
      
      abstract class NonTerminalExpression implements Expression {
        private Expression leftNode;
      
        private Expression rightNode;
      
        public NonTerminalExpression(Expression l, Expression r) {
          setLeftNode(l);
          setRightNode(r);
        }
      
        public void setLeftNode(Expression node) {
          leftNode = node;
        }
      
        public void setRightNode(Expression node) {
          rightNode = node;
        }
      
        public Expression getLeftNode() {
          return leftNode;
        }
      
        public Expression getRightNode() {
          return rightNode;
        }
      }
      
  1. No trackbacks yet.
I commenti sono chiusi.
%d blogger cliccano Mi Piace per questo: