Interpreter Pattern
태그 :
- 개념
- - 간단한 언어의 문법을 정의하는 방법과 그 언어로 문장을 구성하는 방법, 문장을 해석하는 방법을 제시
I. 의도
간단한 언어의 문법을 정의하는 방법과 그 언어로 문장을 구성하는 방법, 문장을 해석하는 방법을 제시
II. 활용
해석이 필요한 언어가 존재하거나 추상구문트리로 언어에 정의된 문장을 표현하고자 할 때
정의할 언어 문법이 간단하고, 효율성은 큰 고려 사항이 아닐 때
III. 장점
- 문법의 변경과 확장이 쉽다
- 문법의 구현이 용이하다
- 표현식을 해석하는 새로운 방법을 추가할 수 있다 - 새 방법 계속 추가해야 할 때는 visitor 패턴이 좋다
IV. 단점: 복잡한 문법은 관리하기 어렵다
관련 패턴: 추상 구문 트리는 Composite 패턴의 한 인스턴스로 볼 수 있다. 하나의 구문 트리 내에 여러 개의 터미널 기호를 공유하기 위해서 Flyweight 패턴을 적용할 수 있다.
Interpreter는 Iterator를 이용해서 자신의 구조를 순회한다.
Visitor 패턴을 이용하면 하나의 클래스에 정의된 구문 트리의 각 노드에 대한 상태를 관리할 수 있다.
- AbstractExpression: 추상 구문 트리에 속한 모든 노드에 해당하는 클래스들이 공통으로 가져야 할 Interpret() 오퍼레이션을 추상 오퍼레이션으로 정의한다.
- TerminalExpression: 문법에 정의한 터미널 기호와 관련된 해석 방법을 구현한다. 문장을 구성하는 모든 터미널 기호에 대해서 해당 클래스를 만들어야 한다.
- NonterminalExpression: 문법의 오른편에 나타나는 모든 기호에 대해서 클래스를 정의해야 한다. 문법에
R :: = R1 R2 … Rn
을 정의하고 있다면 R 에 대해서 NonterminalExpression 에 해당하는 클래스를 정의해야 한다. 또한 규칙의 오른쪽에 나타난 R1 에서 Rn 에 이르기까지의 모든 기호에 대응하는 인스턴스 변수들을 정의해야 한다. 또한 터미널 기호가 아닌 모든 기호들에 대해서 Interpret() 오퍼레이션을 구현해야 한다. 이 Interpret() 오퍼레이션은 R1 에서 Rn 에 이르기까지의 각 인스턴스 변수를 재귀적으로 호출하는 것이 일반적이다.
Context: 번역기에 대한 포괄적인 정보를 포함한다.
Client: 언어로 정의한 특정 문장을 나타내는 추상 구문 트리이다. 이 추상 구문 트리는 NonterminalExpression 과 TerminalExpression 클래스의 인스턴스로 구성된다. 이 인스턴스의 Interpret() 오퍼레이션을 호출한다.
소스코드
The following Reverse Polish notation 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 expressions like:
a b +
a b c + -
a b + c a - -
Following the interpreter pattern there is a class for each grammar rule
import java.util.Map;
interface Expression {
public int interpret(Map<String,Expression> variables);
}
class Number implements Expression {
private int number;
public Number(int number) { this.number = number; }
public int interpret(Map<String,Expression> 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<String,Expression> 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<String,Expression> 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<String,Expression> 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[2] 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<Expression> expressionStack = new Stack<Expression>();
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<String,Expression> 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<String,Expression> variables = new HashMap<String,Expression>();
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);
}
}