https://sourcemaking.com/design_patterns/interpreter
Intent
Structure
Example
The following participant classes are involved in this example: Context - keeps the current string that has to be parsed and the decimal that contains the conversion already done. Initially the context keeps the full string that has to be converted and 0 for the output decimal.
http://www.journaldev.com/1635/interpreter-design-pattern-in-java-example-tutorial
http://www.cnblogs.com/java-my-life/archive/2012/06/19/2552617.html
Intent
- Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.
- Map a domain to a language, the language to a grammar, and the grammar to a hierarchical object-oriented design.
The Interpreter is one of the Design Patterns published in the GoF which is not really used. Ussualy the Interpreter Pattern is described in terms of formal grammars, like it was described in the original form in the GoF but the area where this design pattern can be applied can be extended.
A class of problems occurs repeatedly in a well-defined and well-understood domain. If the domain were characterized with a "language", then problems could be easily solved with an interpretation "engine".
The Interpreter pattern discusses: defining a domain language (i.e. problem characterization) as a simple language grammar, representing domain rules as language sentences, and interpreting these sentences to solve the problem. The pattern uses a class to represent each grammar rule. And since grammars are usually hierarchical in structure, an inheritance hierarchy of rule classes maps nicely.
An abstract base class specifies the method
http://www.journaldev.com/1635/interpreter-design-pattern-in-java-example-tutorialinterpret(). Each concrete subclass implements interpret() by accepting (as an argument) the current state of the language stream, and adding its contribution to the problem solving process.
Interpreter pattern is one of the behavioral design pattern and is used to defines a grammatical representation for a language and provides an interpreter to deal with this grammar. The best example of this pattern is java compiler that interprets the java source code into byte code that is understandable by JVM. Google Translator is also an example of interpreter pattern where the input can be in any language and we can get the output interpreted in another language.
To implement interpreter pattern, we need to create Interpreter context engine that will do the interpretation work and then we need to create different Expression implementations that will consume the functionalities provided by the interpreter context. Finally we need to create the client that will take the input from user and decide which Expression to use and then generate output for the user.
Interpreter suggests modeling the domain with a recursive grammar. Each rule in the grammar is either a 'composite' (a rule that references other rules) or a terminal (a leaf node in a tree structure). Interpreter relies on the recursive traversal of the Composite pattern to interpret the 'sentences' it is asked to process.
Context contains information that is global to the interpreter. TheAbstractExpressionprovides an interface for executing an operation.TerminalExpressionimplements the interpret interface associated with any terminal expressions in the defined grammar.
The Client either builds the Abstract Syntax Tree, or the AST is passed through to the client. An AST is composed of bothTerminalExpressions and NonTerminalExpressions. The client will kick off the interpret operation. Note that the syntax tree is usually implemented using the Composite pattern
The pattern allows you to decouple the underlying expressions from the grammar.
The Template Method pattern should be used:
- The Interpreter pattern is used exaustively in defining grammars, tokenize input and store it.
- A specific area where Interpreter can be used are the rules engines.
- The Interpreter pattern can be used to add functionality to the composite pattern.
- The Interpreter pattern is used exaustively in defining grammars, tokenize input and store it.
- A specific area where Interpreter can be used are the rules engines.
- The Interpreter pattern can be used to add functionality to the composite pattern.
The Intepreter pattern defines a grammatical representation for a language and an interpreter to interpret the grammar.
The Interpreter pattern should be used when you have a simple grammar that can be represented as an Abstract Syntax Tree. This is the more obvious use of the pattern. A more interesting and useful application of Interpreter is when you need a program to produce different types of output, such as a report generator.
Example 1 - Roman Numerals Convertor
The classical example fot the interpreter pattern is the one of interpreting the roman numerals. The expresion to be interpreted is a string which is put in the context. The context consists of the remaining unparsed Roman Numeral string and of the result of the numerral that are already parsed. The context is passed to one of four sub-interpreters based on the type of interpreting(Thousand, Hundred, Ten, One). This example it's using only TerminalExpressions.The following participant classes are involved in this example: Context - keeps the current string that has to be parsed and the decimal that contains the conversion already done. Initially the context keeps the full string that has to be converted and 0 for the output decimal.
public class Context {
private String input;
private int output;
public Context(String input)
{
this.input = input;
}
}
public abstract class Expression {
public void interpret(Context context)
{
if (context.getInput().length() == 0)
return;
if (context.getInput().startsWith(nine()))
{
context.setOutput(context.getOutput() + (9 * multiplier()));
context.setInput(context.getInput().substring(2));
}
else if (context.getInput().startsWith(four()))
{
context.setOutput(context.getOutput() + (4 * multiplier()));
context.setInput(context.getInput().substring(2));
}
else if (context.getInput().startsWith(five()))
{
context.setOutput(context.getOutput() + (5 * multiplier()));
context.setInput( context.getInput().substring(1));
}
while (context.getInput().startsWith(one()))
{
context.setOutput(context.getOutput() + (1 * multiplier()));
context.setInput(context.getInput().substring(1));
}
}
public abstract String one();
public abstract String four();
public abstract String five();
public abstract String nine();
public abstract int multiplier();
}
public class ThousandExpression extends Expression{
public String one() { return "M"; }
public String four(){ return " "; }
public String five(){ return " "; }
public String nine(){ return " "; }
public int multiplier() { return 1000; }
}
public class HundredExpression extends Expression{
public String one() { return "C"; }
public String four(){ return "CD"; }
public String five(){ return "D"; }
public String nine(){ return "CM"; }
public int multiplier() { return 100; }
}
public class TenExpression extends Expression{
public String one() { return "X"; }
public String four(){ return "XL"; }
public String five(){ return "L"; }
public String nine(){ return "XC"; }
public int multiplier() { return 10; }
}
public class OneExpression extends Expression{
public String one() { return "I"; }
public String four(){ return "IV"; }
public String five(){ return "V"; }
public String nine(){ return "IX"; }
public int multiplier() { return 1; }
}
public class MainInterpreter {
public static void main(String[] args) {
String roman = "MCMXXVIII";
Context context = new Context(roman);
// Build the 'parse tree'
ArrayList<Expression> tree = new ArrayList<Expression>();
tree.add(new ThousandExpression());
tree.add(new HundredExpression());
tree.add(new TenExpression());
tree.add(new OneExpression());
// Interpret
for (Iterator it = tree.iterator(); it.hasNext();)
{
Expression exp = (Expression)it.next();
exp.interpret(context);
}
System.out.println(roman + " = " + Integer.toString(context.getOutput()));
}
}
Example 2 - Rule Validator
public abstract class Expression {
abstract public boolean interpret(String str);
}
public class TerminalExpression extends Expression {
private String literal = null;
public TerminalExpression(String str) {
literal = str;
}
public boolean interpret(String str) {
StringTokenizer st = new StringTokenizer(str);
while (st.hasMoreTokens()) {
String test = st.nextToken();
if (test.equals(literal)) {
return true;
}
}
return false;
}
}
public class OrExpression extends Expression{
private Expression expression1 = null;
private Expression expression2 = null;
public OrExpression(Expression expression1, Expression expression2) {
this.expression1 = expression1;
this.expression2 = expression2;
}
public boolean interpret(String str) {
return expression1.interpret(str) || expression2.interpret(str);
}
}
public class AndExpression extends Expression{
private Expression expression1 = null;
private Expression expression2 = null;
public AndExpression(Expression expression1, Expression expression2) {
this.expression1 = expression1;
this.expression2 = expression2;
}
public boolean interpret(String str) {
return expression1.interpret(str) && expression2.interpret(str);
}
}
public class Main {
/**
* this method builds the interpreter tree
* It defines the rule "Owen and (John or (Henry or Mary))"
* @return
*/
static Expression buildInterpreterTree()
{
// Literal
Expression terminal1 = new TerminalExpression("John");
Expression terminal2 = new TerminalExpression("Henry");
Expression terminal3 = new TerminalExpression("Mary");
Expression terminal4 = new TerminalExpression("Owen");
// Henry or Mary
Expression alternation1 = new OrExpression(terminal2, terminal3);
// John or (Henry or Mary)
Expression alternation2 = new OrExpression(terminal1, alternation1);
// Owen and (John or (Henry or Mary))
return new AndExpression(terminal4, alternation2);
}
/**
* main method - build the interpreter
* and then interpret a specific sequence
* @param args
*/
public static void main(String[] args) {
String context = "Mary Owen";
Expression define = buildInterpreterTree();
System.out.println(context + " is " + define.interpret(context));
}
}
http://javapapers.com/design-patterns/interpreter-design-pattern/
http://www.tutorialspoint.com/design_pattern/interpreter_pattern.htm
public class InterpreterPattern { public static void main(String args[]) { String tokenString = "4 3 2 - 1 + *"; Stackhttp://www.blackwasp.co.uk/interpreter_2.aspxstack = new Stack (); String[] tokenList = tokenString.split(" "); for (String s : tokenList) { if (isOperator(s)) { IExpression rightExpression = stack.pop(); IExpression leftExpression = stack.pop(); IExpression operator = getOperatorInstance(s, leftExpression, rightExpression); int result = operator.interpret(); stack.push(new NumberExpression(result)); } else { IExpression i = new NumberExpression(s); stack.push(i); } } System.out.println("Result: "+stack.pop().interpret()); } public static boolean isOperator(String s) { if (s.equals("+") || s.equals("-") || s.equals("*")) return true; else return false; } public static IExpression getOperatorInstance(String s, IExpression left, IExpression right) { switch (s) { case "+": return new PlusExpression(left, right); case "-": return new MinusExpression(left, right); case "*": return new MultiplyExpression(left, right); } return null; } }
http://www.tutorialspoint.com/design_pattern/interpreter_pattern.htm
http://www.journaldev.com/1635/interpreter-design-pattern-in-java-example-tutorial
public class InterpreterClient { public InterpreterContext ic; public InterpreterClient(InterpreterContext i){ this.ic=i; } public String interpret(String str){ Expression exp=null; //create rules for expressions if(str.contains("Hexadecimal")){ exp=new IntToHexExpression(Integer.parseInt(str.substring(0,str.indexOf(" ")))); }else if(str.contains("Binary")){ exp=new IntToBinaryExpression(Integer.parseInt(str.substring(0,str.indexOf(" ")))); }else return str; return exp.interpret(ic); } public static void main(String args[]){ String str1 = "28 in Binary"; String str2 = "28 in Hexadecimal"; InterpreterClient ec = new InterpreterClient(new InterpreterContext()); System.out.println(str1+"= "+ec.interpret(str1)); System.out.println(str2+"= "+ec.interpret(str2)); }} |
http://www.journaldev.com/1635/interpreter-design-pattern-in-java-example-tutorial
- Interpreter pattern can be used when we can create a syntax tree for the grammar we have.
- Interpreter pattern requires a lot of error checking and a lot of expressions and code to evaluate them, it gets complicated when the grammar becomes more complicated and hence hard to maintain and provide efficiency.
java.util.Patternand subclasses ofjava.text.Formatare some of the examples of interpreter pattern used in JDK.
Check list
- Decide if a "little language" offers a justifiable return on investment.
- Define a grammar for the language.
- Map each production in the grammar to a class.
- Organize the suite of classes into the structure of the Composite pattern.
- Define an
interpret(Context)method in the Composite hierarchy. - The
Contextobject encapsulates the current state of the input and output as the former is parsed and the latter is accumulated. It is manipulated by each grammar class as the "interpreting" process transforms the input into the output.
- Considered in its most general form (i.e. an operation distributed over a class hierarchy based on the Composite pattern), nearly every use of the Composite pattern will also contain the Interpreter pattern. But the Interpreter pattern should be reserved for those cases in which you want to think of this class hierarchy as defining a language.
- Interpreter can use State to define parsing contexts.
- The abstract syntax tree of Interpreter is a Composite (therefore Iterator and Visitor are also applicable).
- Terminal symbols within Interpreter's abstract syntax tree can be shared with Flyweight.
- The pattern doesn't address parsing. When the grammar is very complex, other techniques (such as a parser) are more appropriate.
http://www.cnblogs.com/java-my-life/archive/2012/06/19/2552617.html
解释器模式是类的行为模式。给定一个语言之后，解释器模式可以定义出其文法的一种表示，并同时提供一个解释器。客户端可以使用这个解释器来解释这个语言中的句子。
模式所涉及的角色如下所示：
（1）抽象表达式(Expression)角色：声明一个所有的具体表达式角色都需要实现的抽象接口。这个接口主要是一个interpret()方法，称做解释操作。
（2）终结符表达式(Terminal Expression)角色：实现了抽象表达式角色所要求的接口，主要是一个interpret()方法；文法中的每一个终结符都有一个具体终结表达式与之相对应。比如有一个简单的公式R=R1+R2，在里面R1和R2就是终结符，对应的解析R1和R2的解释器就是终结符表达式。
（3）非终结符表达式(Nonterminal Expression)角色：文法中的每一条规则都需要一个具体的非终结符表达式，非终结符表达式一般是文法中的运算符或者其他关键字，比如公式R=R1+R2中，“+"就是非终结符，解析“+”的解释器就是一个非终结符表达式。
（4）环境(Context)角色：这个角色的任务一般是用来存放文法中各个终结符所对应的具体值，比如R=R1+R2，我们给R1赋值100，给R2赋值200。这些信息需要存放到环境角色中，很多情况下我们使用Map来充当环境角色就足够了。
为了说明解释器模式的实现办法，这里给出一个最简单的文法和对应的解释器模式的实现，这就是模拟Java语言中对布尔表达式进行操作和求值。
在这个语言中终结符是布尔变量，也就是常量true和false。非终结符表达式包含运算符and，or和not等布尔表达式。这个简单的文法如下：
Expression ::= Constant | Variable | Or | And | Not
And ::= Expression 'AND' Expression
Or ::= Expression 'OR' Expression
Not ::= 'NOT' Expression
Variable ::= 任何标识符
Constant ::= 'true' | 'false'
public class Variable extends Expression { private String name; public Variable(String name){ this.name = name; } @Override public boolean equals(Object obj) { if(obj != null && obj instanceof Variable) { return this.name.equals( ((Variable)obj).name); } return false; } @Override public int hashCode() { return this.toString().hashCode(); } @Override public String toString() { return name; } @Override public boolean interpret(Context ctx) { return ctx.lookup(this); } }
public class Context { private Map<Variable,Boolean> map = new HashMap<Variable,Boolean>(); public void assign(Variable var , boolean value){ map.put(var, new Boolean(value)); } public boolean lookup(Variable var) throws IllegalArgumentException{ Boolean value = map.get(var); if(value == null){ throw new IllegalArgumentException(); } return value.booleanValue(); } }
public class Or extends Expression { private Expression left,right; public Or(Expression left , Expression right){ this.left = left; this.right = right; } @Override public boolean interpret(Context ctx) { return left.interpret(ctx) || right.interpret(ctx); } }public static void main(String[] args) { Context ctx = new Context(); Variable x = new Variable("x"); Variable y = new Variable("y"); Constant c = new Constant(true); ctx.assign(x, false); ctx.assign(y, true); Expression exp = new Or(new And(c,x) , new And(y,new Not(x))); System.out.println("x=" + x.interpret(ctx)); System.out.println("y=" + y.interpret(ctx)); System.out.println(exp.toString() + "=" + exp.interpret(ctx)); }
