World Library  
Flag as Inappropriate
Email this Article

Interpreter pattern

Article Id: WHEBN0000164860
Reproduction Date:

Title: Interpreter pattern  
Author: World Heritage Encyclopedia
Language: English
Subject: Design Patterns, Software design pattern, Interceptor pattern, Service locator pattern, Servant (design pattern)
Collection: Articles with Example Java Code, Software Design Patterns
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Interpreter pattern

In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a Class (computer science) for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client.[1]:243 See also Composite pattern.

Contents

  • Uses 1
  • Structure 2
  • Example 3
    • BNF 3.1
    • C# 3.2
    • Java 3.3
  • See also 4
  • References 5
  • External links 6

Uses

  • Specialized database query languages such as SQL.
  • Specialized computer languages which are often used to describe communication protocols.
  • Most general-purpose computer languages actually incorporate several specialized languages.

Structure

Example

BNF

The following Backus-Naur Form example illustrates the interpreter pattern. The grammar

expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable  ::= 'a' | 'b' | 'c' | ... | 'z'
digit = '0' | '1' | ... | '9'
number ::= digit | digit number  

defines a language which contains Reverse Polish Notation expressions like:

a b +
a b c + -
a b + c a - -

C#

This structural code demonstrates the Interpreter patterns, which using a defined grammar, provides the interpreter that processes parsed statements.

//IVSR: Interpreter design pattern
namespace IVSR.DesignPaterns.Interpreter
{
// "Context" 
  class Context 
  {
  }

  // "AbstractExpression" 
  abstract class AbstractExpression 
  {
    public abstract void Interpret(Context context);
  }

  // "TerminalExpression" 
  class TerminalExpression : AbstractExpression
  {
    public override void Interpret(Context context)  
    {
      Console.WriteLine("Called Terminal.Interpret()");
    }
  }

  // "NonterminalExpression" 
  class NonterminalExpression : AbstractExpression
  {
    public override void Interpret(Context context)  
    {
      Console.WriteLine("Called Nonterminal.Interpret()");
    }  
  }
  class MainApp
  {
    static void Main()
    {
      Context context = new Context();

      // Usually a tree 
      ArrayList list = new ArrayList();

      // Populate 'abstract syntax tree' 
      list.Add(new TerminalExpression());
      list.Add(new NonterminalExpression());
      list.Add(new TerminalExpression());
      list.Add(new TerminalExpression());

      // Interpret 
      foreach (AbstractExpression exp in list)
      {
        exp.Interpret(context);
      }

      // Wait for user 
      Console.Read();
    }
  }
}

Java

Following the interpreter pattern there is a class for each grammar rule.


import java.util.Map

interface Expression {
    public int interpret(Map variables);
}
 
class Number implements Expression {
    private int number;
    public Number(int number)       { this.number = number; }
    public int interpret(Map variables)  { return number; }
}
 
class Plus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Plus(Expression left, Expression right) { 
        leftOperand = left; 
        rightOperand = right;
    }
                
    public int interpret(Map variables)  { 
        return leftOperand.interpret(variables) + rightOperand.interpret(variables);
    }
}
 
class Minus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Minus(Expression left, Expression right) { 
        leftOperand = left; 
        rightOperand = right;
    }
                
    public int interpret(Map variables)  { 
        return leftOperand.interpret(variables) - rightOperand.interpret(variables);
    }
}

class Variable implements Expression {
    private String name;
    public Variable(String name)       { this.name = name; }
    public int interpret(Map variables)  { 
        if(null==variables.get(name)) return 0; //Either return new Number(0).
        return variables.get(name).interpret(variables); 
    }
}

While the interpreter pattern does not address parsing[1]:247 a parser is provided for completeness.


import java.util.Map;
import java.util.Stack;

class Evaluator implements Expression {
    private Expression syntaxTree;
 
    public Evaluator(String expression) {
        Stack expressionStack = new Stack();
        for (String token : expression.split(" ")) {
            if  (token.equals("+")) {
                Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());
                expressionStack.push( subExpression );
            }
            else if (token.equals("-")) {
                // it's necessary remove first the right operand from the stack
                Expression right = expressionStack.pop();
                // ..and after the left one
                Expression left = expressionStack.pop();
                Expression subExpression = new Minus(left, right);
                expressionStack.push( subExpression );
            }
            else                        
                expressionStack.push( new Variable(token) );
        }
        syntaxTree = expressionStack.pop();
    }
 
    public int interpret(Map context) {
        return syntaxTree.interpret(context);
    }
}

Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.


import java.util.Map;
import java.util.HashMap;

public class InterpreterExample {
    public static void main(String[] args) {
        String expression = "w x z - +";
        Evaluator sentence = new Evaluator(expression);
        Map variables = new HashMap();
        variables.put("w", new Number(5));
        variables.put("x", new Number(10));
        variables.put("z", new Number(42));
        int result = sentence.interpret(variables);
        System.out.println(result);
    }
}

See also

References

  1. ^ a b  

External links

  • Interpreter implementation in Ruby
  • Interpreter implementation in C++
  • SourceMaking tutorial
  • Interpreter pattern description from the Portland Pattern Repository
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.